Принцип дирихле

Розв’язання.

1. Двох рукавичок недостатньо: адже ми можемо витягти чорну і червону

рукавички. Серед  трьох рукавичок, за принципом Діріхле, обов’язково будуть хоча б дві  рукавички одного кольору.

2. Можна витягти 20 рукавичок на одну руку і серед них не буде пари рукавичок

одного кольору. Тому шукане число не менше 21. Доведемо, що число 21 задовольняє умову задачі. Серед 21 витягнутих рукавичок, принаймні 11 будуть одного кольору. Оскільки серед 10 пар рукавичок одного кольору 10 рукавичок на одну руку і 10 рукавичок на іншу руку,то серед 11 рукавичок одного кольору обов’язково знайдеться  пара рукавичок.

 

3. Можна витягти 20 рукавичок на одну руку і серед них не буде пари рукавичок

різних кольорів. Тому шукане число не менше 21. Доведемо, що число 21 задовольняє умову задачі. Серед 21-ї витягнутої рукавички принаймні 11 будуть одного кольору, наприклад чорного, серед яких знайдеться пара чорних рукавичок. При цьому у витягнутому наборі буде принаймні одна червона рукавичка. З пари чорних рукавичок і червоної можна утворити пару рукавичок різних кольорів.

 

Задача  № 6.

У шухляді лежить n пар рукавичок кожного з k кольорів, k 2, всього nk пар одного розміру. Яку найменшу кількість рукавичок потрібно витягти навмання із шухляди, щоб серед них було не менше: 1) двох рукавичок одного кольору; 2) однієї пари рукавичок одного кольору; 3) однієї пари рукавичок різних кольорів?

Розв’язання.

1. K рукавичок недостатньо: адже ми можемо витягти по одній рукавичці

кожного кольору. Серед k+1 витягнутих рукавичок, внаслідок принципу Діріхле, будуть принаймні дві однакового кольору.

2. Можна витягнути nk рукавичок на одну руку і серед них не буде пари

Рукавичок одного кольору. Тому шукане число не менше nk+1. Доведемо, що число nk+1 задовольняє вимогу задачі. Серед nk+1 витягнутих рукавичок принаймні n+1 будуть одного кольору, серед яких знайдеться пара рукавичок одного кольору.

3. Можна витягти nk рукавичок на одну руку і серед них не буде пари. Тому

шукане число не менше nk+1. Серед nk+1 витягнутих рукавичок принаймні n+1 будуть одного кольору, серед яких знайдеться пара рукавичок одного кольору. Серед витягнутих рукавичок є хоча б одна рукавичка іншого кольору. З цієї рукавички та пари рукавичок одного кольору легко утворити пару різних кольорів.

 

Задача  № 7.

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

Розв’язання.

Високосний  рік має 52 тижні і два дні, які віднесемо до неповного 53-го тижня. Оскільки 53· 3 + 1 = 160, то в наслідок узагальненого принципу Діріхле( n = 53, k = 3) знайдуться принаймні k + 1 = 4 особи, дні народження яких припадають на один і той самий тиждень.

 

Задача  № 8.

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

Розв’язання.

Твердження  задачі випливає з умови збігу  для n = 21. Дійсно,

  - 1 = 209 200, тобто більше ніж є. Отже, знайдуться дві клітки, в яких сидить однакова кількість кроликів. Це означає, що принаймні два хлопчики отримали порівну горіхів.

За мотивом  цієї задачі розглянемо задачу на дослідження.

 

Задача  № 9.

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

 

Розв’язання.

Число хлопчиків  позначимо через n. Якщо k < , то внаслідок умови збігу, принаймні два хлопчики отримають порівну горіхів. Для k   наведемо приклад розподілу горіхів, при якому жодні два хлопчики не отримають горіхів порівну: 0, 1, 2, … , n-2, n-1 + . Отже, шукане число n – найменше ціле число, що задовольняє нерівність  k < .

У розв’язуванні  двох наступних задач поряд із принципом Діріхле застосовано додаткові міркування.

 

Задача  № 10.

Чи можна 11 студентів  першого, другого, третього та четвертого курсів розмістити за круглим столом так, щоб серед довільних 5 осіб, які сидять поряд, знайшлися представники кожного курсу?

Розв’язання.

Якби кожний курс був представлений не менш ніж трьома студентами, то всього студентів було б не менше 12. Тому знайдеться курс, представлений не більш ніж двома студентами. Між цими студентами по колу знайдеться не менше 5 осіб, серед яких відсутні студенти саме цього курсу. Отже таке розміщення неможливе.

 

 Задача  № 11.

Чи може самоскид вантажопідйомністю 5т за 9 рейсів перевезти 46 будівельних блоків, якщо маси блоків утворюють арифметичну прогресію з першим членом 940кг і різницею 1кг?

Розв’язання.

Припустимо, що це можливо. Тоді, внаслідок узагальненого  принципу Діріхле, має бути рейс, яким самоскид перевезе не менше шести  будівельних блоків, а це щонайменше 940 + 941 + … + 945 = 5655(кг), що більше п’яти тонн. Отримали суперечність. Отже, наше припущення не правильне і перевезення за 9 рейсів неможливе.

 

Задача  № 12.

 Доведіть, що  з будь – яких десяти різних  двозначних чисел можна вибрати два різні набори так, щоб суми чисел в обох наборах були однаковими.(Два набори різні, якщо відрізняються хоча б одним елементом).

 

 

Розв’язання.

Підрахуємо  число різних наборів, які можна  утворити з 10 чисел. Оскільки кожне  з 10 чисел може ввійти або не ввійти до набору, то кількість усіх можливих наборів дорівнює 2¹⁰ = 1024(тут враховано і порожній набір, який не містить жодного числа). Сума чисел у кожному наборі не перевищує 99· 10 = 990. Отже, за принципом Діріхле, є принаймні два різні набори з однаковою сумою чисел.

 

Задача  № 13.

Знайдіть найменше натуральне число n, для якого правильне наступне твердження: серед довільного набору n цілих чисел можна вибрати 3 числа, сума яких ділиться на 3.

Розв’язання.

Спочатку доведемо, що для набору з п’яти цілих чисел таке твердження правильне. Якщо в цьому наборі є три числа, що мають попарно різні остачі при діленні на , то їх сума ділиться на 3, оскільки 0 + 1 + 2 = 3. Таким чином, в цьму випадку твердження правильне.

 Нехай тепер  задані числа мають не більше  двох різних остач при діленні  на 3. Тоді, за принципом Діріхле,  зайдуться три числа з однаковою  остачею від ділення на 3. Сума  цих чисел ділиться на 3.

Для наборів  з числом елементів, менших п’яти, твердження хибне. Наприклад, набір із чотирьох чисел 0, 3, 1, 4 не має такої властивості.

 

 

 

 

 

 

 

 

 

Розділ 3.

Геометричне застосування принципу Діріхле

Деякі завдання вирішуються також методами, в  якійсь мірі аналогічними принципу Діріхле. Сформулюємо відповідні твердження (усі вони легко доводяться методом від супротивного).

1. Якщо на відрізку довжиною 1 розташовано декілька відрізків, сума довжин яких

більше 1, то принаймні два з них мають спільну точку.

2. Якщо на колі радіусу 1 розташовано декілька дуг, сума довжин яких більше 2π,

то принаймні  дві з них мають спільну точку.

3. Якщо усередині фігури площею 1 розташовано декілька фігур сума площ яких

більше 1, то принаймні  дві з них мають спільну точку .

Розглянемо  декілька геометричних задач, що вирішуються  за принципом Діріхле.

 

Задача  № 1.

Вузли нескінченного  клітчастого паперу розфарбовані в  два кольори. Доведіть, що існують  дві горизонтальні і дві вертикальні  прямі на перетині яких лежать точки  одного кольору.

Розв’язання.

Розглянемо  три вертикальні прямі і дев’ять горизонтальних. Будемо розглядати точки перетину цих прямих. Оскільки є лише 2³ = 8 варіантів розфарбовування трьох точок в два кольори, то за принципом Діріхле, обов’язково знайдуться дві горизонтальні прямі, на яких лежать однаково розфарбовані трійки точок перетину. Серед трьох точок, розфарбованих в два кольори, за принципом Діріхле, обов’язково знайдуться дві точки розфарбовані в однаковий колір. Вертикальні прямі, які проходять через ці точки з раніше вибраними двома горизонтальними прямими є шуканими.

 

 

Задача  № 2.

В прямокутнику 5х6 зафарбовано 19 клітинок. Доведіть, що в ньому можна вибрати квадрат 2х2, в якому зафарбовано не менше  трьох клітинок.

 

Розв’язання.

     Розділимо прямокутник на 6 частин по 5 клітинок (мал. 2). Згідно узагальненого принципу Діріхле, в одній із цих частин обов’язково буде зафарбовано неменше чотирьох клітинок. Тоді в квадраті 2х2, який міститься в цій частині буде зафарбовано або 3 або 4 клітинки.

 

 

Задача  № 3.

Кожна з дев'яти  прямих розбиває квадрат на два чотирикутники, площі яких відносяться як 2 : 3. Доведіть, що принаймні три з цих дев'яти прямих проходять через одну точку.

Розв’язання.

 Дані прямі не можуть перетинати сусідні сторони квадрата ABCD, оскільки інакше утвориться не два чотирикутники, а трикутник і п'ятикутник. Нехай  пряма перетинає сторони BC і AD, квадрата ABCD, в точках M і N. Трапеції ABMN і CDNM мають рівні висоти, тому їх площі відносяться як середні лінії, тобто MN ділить відрізок, що сполучає середини сторін AB і CD у відношенні 2 : 3. Точок,  що ділять середні лінії квадрата у відношенні 2 : 3, є рівно чотири. Оскільки дані дев'ять прямих проходять через цих чотири точки, то за узагальненим принципом Діріхле, через одну точку обов’язково  проходять  три прямі.

 

 

Задача  № 4.

У парку росте 10 000 дерев, посаджених квадратно-гніздовим способом (100 рядів по 100 дерев). Яке найбільше число дерев можна зрубати, щоб виконувалася наступна умова: якщо встати на будь-який пеньок, то не буде видно жодного іншого пенька? (Дерева можна вважати досить тонкими.)

Розв’язання.

Розіб'ємо дерева на 2500 четвірок, як показано на мал.3. У  кожній такій четвірці не можна зрубати  більше одного дерева. Якщо в четвірці зрубати більше одного дерева, наприклад  два, то з одного пенька обов’язково буде видно інший пеньок зрубаний у цій четвірці, це означає, що не буде виконуватись умова задачі. Отже, максимальне число дерев, що можна зрубати в одній четвірці – 1. Тому найбільше дерев, що можна зрубати буде 2500· 1 = 2500. Наведемо приклад такого зрубування.

Якщо зрубати всі дерева, зростаючі в лівих верхніх кутах квадратів, утворених нашими четвірками дерев, то умова задачі буде виконуватись, і з кожного пенька не буде видно жодного іншого. Тому найбільше число дерев, які можна зрубати, дорівнює 2500.

 

 

 

 

 

 

 

 

Задача  № 5.

Всередині опуклого 2n-кутника взята точка P. Через кожну вершину і точку P проведена пряма. Доведіть, що знайдеться сторона многокутника, з якою жодна з проведених прямих не має спільних внутрішніх точок.

 

Розв’язання.

Можливі два  випадки: 

1. Точка P лежить на деякій діагоналі AB. Тоді прямі PA і PB збігаються і не перетинають  сторін многокутника. Залишаються 2n – 2 прямі. Вони перетинають не більше ніж 2n – 2 сторін. За принципом Діріхле, це означає, що принаймні одна сторона 2n-кутника не буде мати спільних внутрішніх точок з жодною проведеною прямою.

2. Точка P не  лежить на діагоналі багатокутника A₁ А₂…А_n. Проведемо діагональ A₁ А_n+1. По обидві сторони від неї лежить по n сторін. Нехай для визначеності точка P лежить усередині багатокутника A₁ A_n+1 (мал.4). Тоді прямі P A_n+1, P A_n+2,…, P A_2n, P A₁ (число цих прямих дорівнює n + 1) не можуть перетинати сторони A_n+1 A_n+2, A_n+2 A_n+3,…,

A_2n A₁. Тому прямі, що залишилися (число цих прямих дорівнює n - 1) можуть перетинати не більше ніж n – 1 з цих n сторін. Отже, за принципом Діріхле, принаймні одна сторона 2n-кутника не буде мати спільних внутрішніх точок з жодною проведеною прямою.

 

 

 

 

 

 

 

 

 

 

 

 

Розділ 4.

Принцип Діріхле  для площ.

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

1. Площа фігури.

Поняття про  площі деяких фігур таких, як прямокутник, трикутник, многокутник, відоме зі шкільного курсу математики. Покажемо, як можна ввести поняття площі для більш широкого класу фігур.

Називатимемо  фігурою простою, якщо її можна розбити на скінченне число трикутників. Площа такої фігури є сумою площ відповідних трикутників. Площу простої фігури А позначимо через S(A). Клас всіх простих фігур позначимо буквою P . Легко впевнитися, що виконуються такі властивості:

1. Якщо проста фігура А має внутрішні точки, то S(A) 0.
2. Якщо фігура А( А є P  ) складена з простих фігур А₁ і А₂, які не мають спільних

внутрішніх  точок, то

S(A) = S(A₁) + S(A₂);

3. Рівні фігури, тобто фігури, які можна накласти одна на одну, мають однакові площі.

Означення. Вважають, що фігура має певну площу(є квадрованою), якщо, для будь – якого 0 існують прості фігури А₁ і А₂ такі, що А₁⊂ А⊂ А₂  і S(A₂) - S(A₁) < .

Клас всіх квадратова них фігур позначимо через K. Очевидно, що кожна проста фігура є кадрованою. Але не кожна фігура на площині є кадрованою. В основному кадрованим фігурами є ті, які обмежені відрізками прямих і дугами кіл.

2. Принцип Діріхле для площ.

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

 

Теорема 1.(принцип Діріхле для площ).

Нехай А – кадрована фігура, А_1, А₂, … ,А_n – кадровані фігури при чому А_k А,