Задачі на принцип недостатності

Обов'язковий рівень

1.    14 хлопчиків зібрали 100 горіхів. Довести, що два з них зібрали однакове число горіхів (кожен взяв хоча б один горіх).

Розв'язання

Нехай кожен з хлопчиків зібрав різну кількість горіхів: 1,2,3,4,5…14. Тоді всього було зібрано
((1+14)/2)*14=105 горіхів, але за умовою горіхів було всього 100. Тому принаймні два хлопчика взяли однакову кількість горіхів.

3.    В ящику 100 кульок: червоні, блакитні і жовті. Яку найменшу кількість кульок потрібно взяти,щоб серед них було не менше 10 однакових?

Розв'язання

У найгіршому разі для досягнення результату виберемо 9 червоних, 9 блакитних і 9 жовтих, а наступна кулька (не важливо, якого кольору) дасть можливість одержати потрібний результат. Отже, всього слід дістати не менше 28 кульок.

4.    Дано 110 різних чисел. Доведіть, що знайдеться 2 числа, що співпадають не менше, ніж у двох розрядах.

Розв'язання

Розглянемо розряди одиниць і десятків. Можливо 45 різних комбінацій. Оскільки всього чисел 110,то за принципом Діріхле, знайдеться 2 числа, що співпадають не менше, ніж у двох розрядах.

5.    В лісі росте 1000000 ялинок. Відомо, що на кожній з них росте не більше 600000 голок. Доведіть, що в лісі знайдеться хоча б дві ялинки з однаковим числом голок.

Розв'язання

Нехай на кожній ялинці росте різна кількість голок, тобто від 0 до 600000, тоді всього таких ялинок має бути 600001, але за умовою їх 1000000. Отже, обов’язково знайдуться ялинки з однаковою кількістю хвоїнок.

Підвищений рівень

6.    У хлопчика є 25 мідних монет різної вартості (один, два, три, п’ять). Довести, що у нього знайдеться 7 монет однієї вартості

Розв'язання

Припустимо, що монет кожної з чотирьох видів не більше 6. Тоді загальна кількість монет не більше, ніж 6·4=24, що не відповідає умові задачі. Таким чином, обов’язково знайдеться сім однакових монет

7.    У 21 хлопчика є 200 горіхів. Доведіть, що як би ми їх не розділили, знайдеться два хлопчики, яким дісталось порівну горіхів (може бути, що горіхи їм не дістались зовсім)

Розв'язання

Припустимо, що кожному хлопчику дісталась різна кількість горіхів: 0,1,2,..20. Тоді, горіхів має бути 210, але за умовою їх 200, тому обов’язково знайдуться хлопчики, яким дісталась однакова кількість горіхів.

8.    В магазин привезли 34 ящики з яблуками трьох сортів. Яке найменше число ящиків потрібно взяти, щоб серед них було три ящики з яблуками одного сорту?

Розв'язання

За принципом Діріхле, серед цих ящиків принаймні 12 ящиків з яблуками  одного і того ж сорту. Для того, щоб серед обраних ящиків три були однакового сорту необхідно взяти 7 ящиків.