Комбінаторні задачі на принцип Діріхле

У попередній публікації ми познайомили вас з принципом Діріхле, та навели приклади застосування такого принципу при розвя’зуванні задач.   У цій публікації пропонуємо добірку завдань Всеукраїнської літьної математичної школи “Мудра макітра” з цієї теми. Спробуйте самостійно розв’язати. Відповіді та короткі пояснення будуть опубліковані у вересні.

Спочатку повторимо  принцип Діріхле   за допомогою такої моделі:

У нас є n+1 свинка , й n калюж. Якщо посадити усіх свинок у калюжі, то знайдеться одна калюжа, мінімум із двома свинками.

Доведіть наступні твердження:

  1. Якщо взяти три довільних числа цілих, то серед них найдеться принаймні 2 (2 й більше) однакової парності (або два парних, або два непарних).
  2. Якщо взяти 15 шестикласників, то принаймні у двох з них день народження буде в один місяць.
  3. Якщо у молодшій школі 366 учнів, то принаймні у двох з них день народження в один день.

Узагальнений принцип Діріхле

У N калюжах сидить k свинок. Тоді знайдеться калюжа, в якій сидить не менше (більше, чи рівно)  k/N  свинок, й знайдеться калюжа, у якій сидить не більше (менше, чи рівно) ніж  k/N свинок.

Задача 1. До магазину привезли 25 ящиків із яблуками трьох сортів, причому у кожному ящику лежать яблука якогось одного сорту. Чи можна знайти 9 ящиків з яблуками одного сорту?

Задача 2. В школі 30 класів й 1000 учнів. Доведіть, що знайдеться клас, в якому:

а) не менше 34 учнів;

б) не більше 33 учнів.

Задача 3. У людини на голові не більше 500000 волосин, а у Києві більше за 2 мільйони людей. Доведіть, що знайдуться 4 киянина з однаковою кількістю волосин.

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

Далі буде=)

Попередня публікація: Клітки для кроликів – принци Діріхле

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *