Какво представлява?

    Принципът на Дирихле (наричан още принцип на шкафчетата) е основен комбинаторен принцип, който гласи:

    «Ако n предмета са разпределени в m кутии и n е по-голямо от m, то поне една от кутиите ще съдържа повече от          един предмет.»

    Този принцип е прост, но много мощен инструмент в комбинаториката, теорията на числата и информатиката.

Основна идея

    Принципът на Дирихле се базира на простото наблюдение, че ако имаме повече предмети, отколкото налични места за тях, някои места ще трябва да съдържат повече от един предмет.

Примерни задачи

Задача 1:

    В една стая има 13 човека. Докажете, че поне двама от тях са родени в един и същи месец.

    Решение:

    Тъй като има 12 месеца и 13 човека, но броят на хората е повече от броя на месеците, следва, че поне двама от тях ще имат рожден ден в един и същи месец.

Задача 2:

    В кутия има 7 чифта чорапи (общо 14 чорапа). Ако вземем 8 чорапа, докажете, че поне един чифт ще бъде пълен.

    Решение:

    Има 7 различни типа чорапи, но избираме 8. Следователно, според принципа на Дирихле, поне един тип чорапи ще бъде избран поне два пъти, което означава, че ще имаме поне един пълен чифт.

Задача 3:

    В торба има 7 сини, 9 червени и 10 зелени топчета.

    А) Колко най-малко топчета трябва да се извадят, за да е сигурно, че сред тях има 3 едноцветни?

    Б) Колко най-малко топчета трябва да се извадят, за да е сигурно, че сред тях има поне 1 от всеки вид?

    В) Колко най-малко топчета трябва да се извадят, за да е сигурно, че сред тях има поне 3 червени?

    Решение: 

    А) Изваждаме няколко топчета така, че между тях няма 3 едноцветни, тоест има по най-много 2 от цвят. Тогава общият им брой е най-много 3.2 = 6. Следователно ако вземем 7 сред тях ще има 3 едноцветни.

    Б) Ако извадим 19 топчета е възможно сред тях да няма сини (да са 9 червени и 10 зелени). Следователно ако вземем 20 топчета задължително ще има поне 1 от всеки цвят и 20 е най-малкото число, за което задължително има поне 1 от всеки цвят.

    В) Ако извадим 19 топчета е възможно сред тях да има 10 зелени 7 сини и две червени. Следователно трябва да извадим поне 20 за да може сред тях да има поне 3 червени. Ако извадим 20 топчета сред които няма три червени, то сред тях има 10 зелени 7 сини и най-много две червени, което прави 19 топчета. Следователно по какъвто и начин да извадим 20 топчета сред с тях ще има поне три червени и 20-те най-малкият брой топчета за което това изпълнено.

Задача 4:

    В торба има 8 жълти, 6 сини и 12 червени топчета.

    A) Колко най-малко топчета трябва да се извадят, за да е сигурно, че сред тях има 3 едноцветни?

    Б) Колко най-малко топчета трябва да се извадят, за да е сигурно, че сред тях има поне 1 от всеки вид?

    В) Колко най-малко топчета трябва да се извадят, за да е сигурно, че сред тях има поне 4 сини?

    Решение:

    A) Ако изваждаме топчета така, че да няма 3 едноцветни, можем да имаме най-много 2 от всеки цвят.
Тоест, ако извадим по 2 жълти, 2 сини и 2 червени, ще имаме общо 2×3=6 топчета, без да има 3 еднакви.
Следователно, ако извадим 7 топчета, сред тях задължително ще има 3 едноцветни.

    Б) Ако извадим 20 топчета, е възможно всички те да бъдат само жълти и червени (8 жълти + 12 червени).
Тогава е възможно да няма нито едно синьо топче.
Следователно, ако извадим 21 топчета, ще сме сигурни, че сред тях има поне 1 от всеки вид.

    В) Ако извадим 23 топчета, е възможно сред тях да има (8 жълти + 12 червени + 3 сини). Следователно ако извадим 24 топчета сред тях има поне 4 сини и 24 е най-малкият брой топчета, за които това е изпълнено.