Принцип Діріхле в задачах

Розв'язання. Розмістимо дані числа у вигляді таблиці

1. 2  3

4   5  6

7   8  9

і розглянемо два можливі  випадки.

а)Серед вибраних чисел є число 5. Тоді за принципом Діріхле серед інших 5-ти вибраних чисел хоча б два входять до однієї з множин {1,9},{2,8},{3,7},{4,6}.

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

б)Серед вибраних чисел немає п'ятірки. Якщо серед вибраних чисел є три числа, які містяться в одному рядку або в одному стовпці, то ці три числа і є шуканими. В протилежному випадку серед вибраних чисел обов’язково  будуть числа 2,4,6,8 і трійка чисел 2,4,6 с шуканою

На прикладі чисел 1,3,4,8,9 видно, що для вибірки з п'яти чисел  твердження задачі не є правильним.

Задача 52. Множина натуральних   чисел                   {1,2,3,4,5,6,7, 8}

розбита на дві  підмножини А та В (тобто

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

Розв'язання. Доводимо твердження задачі від супротивного. Допустимо, що

М = ,

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

1 А. Далі можливі два випадки.

1)Числа 3,4,5 містяться в  множині В. З рівностей 3+4= 7 і 3 + 5 = 8

і того, що В не володіє вказаною з умов задачі властивістю, випливає, що 7 А і 8 А, Одержали суперечність, бо

1 + 7 = 8 і {1,7,8} А .

2)Хоча б одне з чисел 3,4,5 міститься множині А. Позначимо це число через k. Тоді

k + 1

Оскільки

(k + 1) (k 1) = 2,

 то 2 А. Далі, з того, що 2 А і k А випливає, що

k + 2В і k 2 В,

Оскільки 

k +2Ві k1і (k + 2) (k1) = 3 ,

 то число 3 . Одержали суперечність

({1,2,3} А і 1 + 2 = 3).

Твердженні задачі повністю доведене.

Зауваження. Для множини чисел {1,2,3,4,5,6,7} аналогічне твердження не є правильним. Це випливає з рівності

{1,2,3,4,5,6,7} = {1,2,7} {3,4,5,6}

Задача 53. Натуральні числа

 

такі, що

 

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

Розв'язання. Розглянемо два допоміжні набори чисел

 

.

 Зрозуміло, що

 

 

Тому числа обох нових  наборів належать відрізку [1,140]. Якщо одне з цих чисел дорівнює 40 (а  це може бути лише деяке число ), то

= 40

і твердження задачі є правильним. Якщо ж жодне з цих чисел  не дорівнює 40, то за принципом Діріхле  деякі два числа з різних наборів  є однаковими, тобто існують  j та і такі, що 1,2,..., 70. Тому = 40,

 і, отже,

 

Задача 54. Числа

1,2,3, ...,2000

розбито на 22 множини. Довести, що існують чотири різні числа а, b, с, d з однієї множини такі, що а +b = с+d

Розв'язання. За принципом Діріхле хоча б в одній з множин ( позначимо її А) не менше 91 числа. Тоді з елементів множини А можна утворити принаймні різних

= 4095

 різних пар елементів  цієї множини. Співставимо кожній  такій парі натуральне число,  яке дорівнює різниці між більшим  та меншим елементами, що входять  в одну пару. У нас утворилося 4095 різниць, кожна з яких може  дорівнювати одному із значень: 1,2,..., 1999. За принципом Діріхле  деяка різниця D зустрічається принаймні три рази. Тому існують чотири різні числа а, b, с, d з множини А, для яких

а с = D і d b=D. Тому а + b = с + d.

Задача 55. Числа

1,2,3,...,2000

 розбито на 6 множин. Довести, що існує множина  і число в ній, яке дорівнює  сумі двох інших (не обов'язково  різних)чисел цієї множини.

Розв'язання. Доводимо твердження задачі від супротивного. Допустимо, що для деякого розбиття множини натуральних чисел від 1 до 2000 на 6 підмножин жодна з цих підмножин не володіє потрібною властивістю. За принципом Діріхле в деякій з цих множин (позначимо її через ) є принаймні 334 мила: 

 

Розглянемо наступні числа:

 

За допущенням жодне з  цих 333-х чисел не належить до множини А. Тому в одній з п'яти множин, які залишилися, є щонайменше 67 чисел з утворених 333-х чисел. Нехай це будуть числа

 

Розглянемо числа

 

За допущенням жодне з  цих чисел не належить множині А₂. Зрозуміло також, що ні одне з цих чисел не належить , бо в протилежному випадку різниця деяких чисел з множини   дорівнювала б числу з цієї множини. Тоді числа 

  належать іншим чотирьом  множинам. За принципом Діріхле  деякій з цих множин  належить принаймні 17 даних чисел. Позначимо їх через

 

Міркуючи аналогічним  чином, переконуємося в тому, що серед  чисел

 

є принаймні 6 чисел, які належать множині . Нехай це будуть числа

 

Серед чисел

 

є три числа , що належать множині. Кожне з чисел  належить до множини А₆, а різниця цих чисел не може належати жодній з множин . Одержали суперечність.

Задача 56. Довести, що з довільних 69 різних натуральних чисел, кожне з яких не перевищує 100, можна вибрати 4 числа, одне з яких дорівнює сумі трьох інших.

Розв'язання. І спосіб. Розмістимо довільний набір із 69 вказаних в умові задачі натуральних чисел, в порядку зростання

 

Зрозуміло, що тоді 32. Розглянемо допоміжний набір натуральних чисел

1,2, ...,68,

і покажемо, що в цьому  новому наборі існують 3 числа, одне з  яких дорівнює сумі двох інших. Зрозуміло, що

 

Розглянемо ще один набір  чисел 

= 1,2,..., 67.

Тоді

1 < с₂ < с₃ < ... < с₆₇ 129.

Оскільки кожне з натуральних  чисел k = 2,3, ...,68, та k = 1,2, ...,67, не перевищує 132 і всього їх є 134 числа, то деякі два з цих чисел збігаються , тобто існують натуральні числа i та j такі, що

 j=1,2,…,67; .

Тому

 

Отже

 

тобто

 

Наведене розв'язання є  досить природним і використовує відомі ідеї. Дам ще одне розв'язання цієї задачі, яке на нашу думку є дещо елегантнішим.

ІI спосіб. Розмістимо вказаний в умові задачі набір з 69 натуральних чисел в порядку зростання:

 

Зрозуміло, що

32 і а₂ 33.

Покладемо і розглянемо ще один набір чисел виду , і = 3,4, ...,69. Оскільки

а₄ а₃ + 1 ,

то

а₄  

 

Тому 133 числа = 4,5,..,,69, та s+ = 3,4, ...,69, знаходяться на відрізку , довжина якого не перевищує 130, оскільки

100 + = 130. Отже, деякі два з вказаних чисел збігаються, бо на вказаному відрізку може бути щонайбільше 131 різне натуральне число. Таким чином, існують натуральні числа j(j= 4, 5, ...,69) та і(і= 3,4, ..., 69) такі, що

 

Тобто

 

 

Зауваження. Для 68 чисел виду

33,34,35,...,100

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

Задача 57. Натуральні числа

 

такі, що

х₁ + х₂ + ... + = 101.          (10)

Довести, що кожне  натуральне число від 1 до 101 можна подати у вигляді суми декількох з чисел

Розв'язання. Не порушуючи загальності вважатимемо, що

 х₅₁. (11)

Тоді х= 1, бо якщо було б 2, то

  2 • 51 = 102,

 що суперечить (10). Нехай далі, п - це загальна кількість одиниць та двійок в наборі (11). Тоді

101=,

звідки п 26 . Тому будь-яке натуральне число, яке не перевищує 26 можна зобразити у вигляді суми лише одиниць та двійок з системи (2). З'ясуємо скільки чисел, більших за 26 може бути в наборі (2). Якби таких чисел було два або більше, то

2·27 + 49 = 103

 і ми одержали б  суперечність.

Отже, якщо в наборі (11) є число більше за 26, то таке число одне, причому легко бачити, що це число не перевищує 51. Таким чином, залишилося розглянути випадок набору (11) для якого

 

Нехай натуральне число k таке, що 27 50. Тоді розглядаючи числа

 

 

 

і враховуючи, що

  26 ,

а також те, що нижні два сусідні числа (12) відрізняються не більше ніж на 5 одержимо, що деяке число з набору (12) належить промір [1,26] і тому воно здається у вигляді суми декількох чисел з набору

 

Отже, кожне натуральне число  k, 1 50 , подається у вигляді суми декількох чисел з набору (11). Якщо ж k пробігає множину всіх натуральних чисел від 1 до 50, то числа (101 - k) набувають всіх значень від 1 до 100, і тому ці числа також подаються у вигляді суми декількох чисел з набору (11), чим і завершується розв'язання задачі 7.

При розв'язувані задач, подібних до попередніх, можна також використовувати  наступне твердження.

Задана  58. Натуральні числа

 

такі, що

 

причому

 .

Для того, щоб  кожне натуральне число k яке не перевищує S можна було подати у вигляді суми декількох чисел набору (1) необхідно і досить, щоб для кожного натурального,

11,

виконувалася  нерівність

     (14)

Доведення. Необхідність. Допустимо, що для деякого натурального числа k нерівність (14) не виконується . Тоді

 

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

Достатність. Індукцією по k доведемо, що кожне натуральне число, яке не перевищує

,

 можна подати у вигляді  суми декількох чисел з системи  (13). При k=1 це твердження правильне. Допустимо, що воно правильне при деякому k і доведемо його істинність і для (k+1)- го доданку. Нехай натуральне число n таке, що

 

Якщо

п ,

то правильність твердження випливає з індуктивного допущення. Якщо ж

 

то 

Але згідно (14)

 

тому

 

Якщо то нічого доводити. Якщо ж        ,

то за індуктивним допущенням число, пх_k+1 подасться у вигляді суми декількох доданків з набору (13), а значить число n також подається в такому вигляді.

Наслідок. Якщо для послідовності натуральних чисел

= 1

 і для кожного натурального k виконується (14), то кожне натуральне число можна зобразити у вигляді суми декількох членів даної послідовності.

Задача 59. Натуральні числа

х₃₅

 такі, що

= 102,

причому хоча б  одне з цих чисел дорівнює І, а  інше 35. Довести, що кожне натуральне число від 1 до 102 можна подати у вигляді суми декількох чисел набору х₃₅

Розв'язання. Нехай серед чисел

х₃₅ є

з перших k натуральних чисел 1,2,…,k. Тоді

 

Тому 

 

З доведеної рівності одержуємо, що

 

Оскільки п₂ 2, то

1=

 Тому числа 1 та 2 можна  подати у вигляді суми одного  або двох перших чисел даного  набору. Оскільки

п₃ 13 , то 1 =.

Тоді умова (14) попередньої задачі очевидним чином виконується для чисел

х_{13 .}

Тому кожне натуральне число від 1 до

х₁₃

 можна зобразити у  вигляді суми декількох чисел  з перших 13 чисел. Значить кожне  натуральне число від 1 до 13 можна  зобразити у вигляді суми декількох  чисел з перших 13 чисел даного  набору. Цілком аналогічно з використанням  нерівностей

 

переконуємося в тому, що кожне натуральне число від 1 до 34 можна подати у вигляді суми декількох  чисел даного набору. Оскільки = 35, то кожне з натуральних чисел від 35 до 69 можна подати в потрібному вигляді. Оскільки сума всіх чисел дорівнює 102, то твердження задачі доведене.

Задача 60.Невід'ємні числа

такі, що

 

 

 

Довести, що 

Доведення. Нехай k та l - це відповідно кількості пар елементів (),і = 1,2, ...,2 + 1, для яких або ж відповідно . Оскільки

k +l = 2п + 1,

 то одне з чисел  k або l не менше, ніж +1. Для визначеності вважатимемо, k п +1 та при

 = 1,2, ..., k (тоді  при

.

 Нам потрібно довести,  що для числа

 

виконується нерівність:

 

Використовуючи умову, одержуємо, що

 

 

 

 

Тому

,

звідки дістаємо, що

 

При бажанні цій задачі можна надати більш "олімпіадне" формулювання. Для прикладу розглянемо такий варіант.

Задача 61. Кожні житель однієї з двох країн володіє однією з п'яти мов. На конгресі зібралося по 500 представників кожної з цих країн, причому з'ясувалося, що загальна кількість людей з обох країн, що володіють кожною з цих мов дорівнює 200. Довести, що з делегатів конгресу можна вибрати 100 пар людей, причто кожна пара складаєшся з двох людей з різних країн і ці люди розмовляють однією і тією ж мовою (для різних пар людей ця мова може бути різною).

Доведення. Нехай - це кількість делегатів першої країни, що володіють і-ю мовою, а - це кількість делегатів другої країни, що -ю мовою, і

= 1,2,..., 5. За умовою

 

 

Тоді за попередньою задачею (п=2S =1000)

тіп тіп{х₂, ₂} + … + тіп{х₅, ₅} 100,

звідки и випливає правильність твердження задачі.

 

Задача 62. На площині є п'ять точок,координати яких цілі числа. Довести, що середина принаймі одного з відрізків, який з'єднує ці точки, має цілі координати

 Розв'язання. Розглянемо перші координати даних точок. За принципом Діріхле серед них є принаймі 2  однакової парності. Нехай ці координати будуть абсцисами точок

.

Серед чисел  є два числа однакової парності. Вважатимемо, що це числа та Тоді точки i А₂ є шуканими координати середини М(х₀,у₀) відрізка А₂, які шукаються за формулою

 

є цілими.

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

Розв'язання. Виберемо на числовій прямій точки А() та В(х₂) синього кольору. Позначимо відстань між ними через d і розглянемо наступні дві точки та . Якщо хоча б одна з цих точок- синя, то твердження задачі, очевидно, правильне, якщо ж ні, то С і D зелені, то розглядаючи точку М(), отримаєм,що шуканими трьома точками будуть А,М,В, якщо – синя,  або С, М, D- якщо М - зелена. 

Задача 64. Точки кола розфарбовано в два кольори. Довести, що знайдеться рівнобедрений трикутник з вершинами одного кольору.