ПРИНЦИП ДІРІХЛЕ: задачі та розв'язання до них

1. В п’яти класах школи навчаються 160 учнів. Довести, що знайдуться 4 учні, у яких день народження випадає на один і той же тиждень.

Розв'язання

Усього в році не більше 53 тижнів.

1 спосіб (від супротивного)

Допустимо, що щотижня відзначають день народження не більше 3 учнів. Тоді всього учнів не більше 3·53=159. А це суперечить умові (оскільки всього дітей 160). Отримали протиріччя.

2 спосіб (за принципом Діріхле)

Нехай тижні – це «ящики», а учні – «кролі», тоді в деякому  «ящику» сидять не менше 160/53  «кролів», тобто більше трьох, отже, не менше чотирьох.

2. У школі 740 учнів. Довести, що принаймні троє з них народилися в один і той самий день.

Розв'язання

Усього в році не більше 366 днів.

1 спосіб (від супротивного)

Допустимо, що щодня відзначають своє день народження не більше двох учнів. Тоді всього учнів не більше 366·2=732. А це суперечить умові задачі. Отримали протиріччя.

2 спосіб (за принципом Діріхле)

Нехай дні – це «ящики», а учні – «кролі», тоді в деякому  «ящику» сидять не менше 740/366  «кролів», тобто більше двох, отже, не менше трьох.

3. У залі є 2 людей. Довести, що серед них знайдеться принаймні дві людини, які мають серед присутніх однакову кількість знайомих.

Розв'язання

Ці двоє можуть бути незнайомі між собою (тоді вони матимуть однакову кількість знайомих – 0.) А можуть бути знайомі (тоді вони матимуть теж однакову кількість знайомих - 1). Іншого варіантів не існує.

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

4. В клітинках таблиці 3×3 поставлені числа: -1, 0, 1. Розглянемо 8 сум: суми трьох чисел в кожному рядку, в кожному стовпчику і по двох діагоналях. Чи можуть ці суми бути всі різні?

Розв'язання

Розглянемо усі можливі суми, що можуть утворитися при додаванні 0, 1, -1:

-3, -2, -1, 0, 1, 2, 3. Усього їх сім. Але ж у даній таблиці всього має бути 8 різних сум. Отже, за принципом Діріхле, дві суми обов'язково будуть однаковими.

Відповідь: Ні

5. В класі навчаються 29 учнів. Саша Іванов зробив у диктанті 13 помилок, і ніхто інший в класі не зробив більшої кількості помилок. Довести, що принаймні три учні мали однакову кількість помилок.

Розв'язання

Крім Саші Іванова в класі навчаються 28 учнів. Розглянемо усі варіанти можливих помилок, тобто кількість помилок, які могли допустити ці учні: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Всього їх могло бути 13. А учнів 28. Тоді, за принципом Діріхле знайдеться принаймні три учні, які допустили однакову кількість помилок.

6. У ящику лежить 10 пар чорних рукавичок і 10 пар червоних рукавичок одного розміру. Скільки рукавичок потрібно взяти навмання з ящика, щоб серед них були: а) дві рукавички одного кольору; б) одна пара рукавичок одного кольору; в) одна пара рукавичок різних кольорів.

Розв'язання

А) щоб отримати дві рукавички одного кольору, слід взяти не менше трьох рукавичок (тоді за принципом Діріхле (де кольори – це «ящики», а рукавички – «зайці») серед трьох рукавичок дві матиме один колір)

Б) щоб отримати одну пару рукавичок одного кольору, слід взяти не менше  21 рукавиці (можуть бути усі 20 лівих і тоді 21-а буде права, незалежно якого кольору)

В) щоб отримати одну пару рукавичок різного кольору, слід взяти не менше  21 рукавиці  (10 пар одного кольору і 1 іншого (праву чи ліву))

7. Довести, що із n+1 різних натуральних чисел, менших від 2n, можна вибрати три таких, сума двох з яких дорівнює третьому числу.

Розв'язання

Нехай х_1, х_2, …, х_n+1 - задані числа, де х₁ – найменше з них. Утворимо ще n чисел  х_n+1-х₁,…, х₃-х₁, х₂-х₁. Тоді серед 2n+1 чисел х_1, х_2, …, х_n+1; х_n+1-х₁,…, х₃-х₁, х₂-х₁, кожне з яких не більше 2000, знайдеться два однакових, причому одне з них буде з першої групи чисел, а інше -  з другої, тобто 

, де   

Отже,

, що й треба було і довести.

8.Довести, що серед 101 цілого числа можна вибрати два, різниця яких ділиться на 100.

Розв'язання

При діленні довільного числа на 100 можуть бути такі остачі:  0,1,2,…..99. Всього 100 різних остач, а за умовою є 101 число, отже, за принципом Діріхле, серед них є два таких числа, що мають однакову остачу, а це значить, що їх різниця матиме остачу 0, тобто націло поділиться на 100.

9. У місті нараховується 10000 телефонів, їх номери позначаються чотирма цифрами. У центральному районі встановлено більш як половину всіх телефонів. Довести, що хоча б один з номерів центрального району дорівнює сумі номерів двох інших телефонів цього ж району.

Розв'язання

За умовою в центральному районі встановлено більше, ніж половина телефонів, отже більше 5001. Розглянемо найгірший випадок, тобто номера тих телефонів, сума будь-яких двох не дорівнюватиме чотиризначному числу, тобто не дорівнюватиме номеру телефону. Оскільки ми маємо розглянути не менше 5001  номер, то в найгіршому випадку серед них будуть всі номери від 4999 до 9999. Але й при цій умові ми матимемо два номера (4999 і 5000), які в сумі дадуть номер з цієї множини (9999). Отже. Можна зробити висновок, що при будь-якому іншому наборі знайдеться не менше одного набору з двох номерів, сума яких дорівнюватиме третьому номеру.

10. У квадраті із стороною 1 довільно розміщено 126 точок. Довести, що деякі шість із них обов’язково лежать усередині круга, радіус якого дорівнює.

Розв'язання

Розіб’ємо даний квадрат на 25 однакових квадратиків зі стороною 1/5 . (За принципом Діріхле,  квадратики будуть «клітками», а точки - «кроликами», в один квадратик обов’язково попаде не менше шість точок). Радіус кола, описаного навколо квадратика зі стороною 1/5, дорівнюватиме 1/5*(корінь з 2) . А оскільки 

, то значить, що даний квадратик лежить в колі з радіусом 1/7 .

11.Щодня протягом року учень розв’язував не менше однієї задачі, причому щотижня він розв’язував не більше 12 задач. Довести, що знайдеться кілька послідовних днів, за які він розв’язав рівно 20 задач.

Розв'язання

Припустимо, що за перший день учень розв’язав х₁ задач, тоді за перші два дні – х_2, за перші 77 днів (11 тижнів) -  х₇₇  задач. Розглянемо  числа х_1, х_2, …, х_77, х₁+20, х₂+20, …, х₇₇+20. Усього цих чисел 154. Число х₇₇ не перевищує 12·11=132. Отже, кожне з написаних чисел не перевищує 152, і тому серед них є принаймні два однакових. Але ж числа х_1, х_2, …, х₇₇ всі різні, бо щодня учень розв’язував принаймні одну задачу. Тому і числа х₁+20, х₂+20, …, х₇₇+20 теж усі різні. Таким чином, залишається припустити, що деяке число з першого рядка дорівнює якомусь числу з другого рядка, тобто  при деяких i та j:   х_i= х_j+20  і   х_i- х_j=20, що й потрібно було довести.