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

 

Задача  № 11.

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

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

Суми можуть набувати не більше семи значень : усі цілі число від -3 до 3 включно. Всього сум вісім. Тому за принципом Діріхле принаймні дві суми набувають однакових значень. Отже різними ці суми бути не можуть.

 

Задача  № 12.

Серед будь –  яких n+1 цілих чисел можна вибрати два числа, різниця яких ділиться на n.

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

Поділимо кожне  з даних чисел на n. При цьому можуть бути остачі 0, 1, 2,….,

n-1. Оскільки чисел n+1, то за принципом Діріхле, принаймні два з них при ділені на n дають однакову остачу. Зрозуміло, що різниця цих чисел ділиться на n.

 

Задача  № 13.

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

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

Нехай a₁, a₂…… a_n – задані числа. Розглянемо n чисел a₁,  a₁ + a₂, … , a₁ + a₂ +…+ a_n. Якщо одне з цих чисел ділиться на n, то твердження задачі правильне. Припустимо, що жодне з цих чисел не ділиться на n. Тоді при діленні на n ці числа дають одну з n-1 остач : 1,2,…, n-1. Всіх чисел n, і кожне з цих чисел при діленні на n дає одну з n-1  остач. Отже, за принципом Діріхле, принаймні два числа при діленні на n дають однакову остачу. Різниця цих двох чисел буде кратна n. Проте будь – яка різниця є сумою кількох сусідніх чисел. Таким чином, твердження задачі є правильним.

 

Задача № 14.

Довести, що для кожного  натурального n є число, яке записується тільки за допомогою цифр 1 і 0 і ділиться націло на n.

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

Розглянемо n+1 число : 1, 11, 111, …, 11…1(останнє число записується n+1  одиницею ). Якщо одне з цих чисел ділиться на n, то твердження задачі є справедливим. Якщо це не так, то, за принципом Діріхле, серед цих чисел є принаймні два, які при діленні на n дають однакову остачу. Це означає, що їх різниця буде кратна n. Залишається лише зауважити, що різниця будь – яких двох розглядуваних чисел записується за допомогою цифр 1 і 0.

 

 

 

Задача № 15.

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

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

 Нехай a₁, a₂…… a_n,  а_п+1 – задані числа. Розглянемо n чисел виду a₂ - a₁, а₃ - a₁, … , а_п+1 - a₁ і n чисел виду a₂…… a_n,  а_п+1. Кожне з цих чисел менше за 2n, а всього їх 2n, при чому числа першого і другого виду всі різні. За принципом Діріхле, принаймні одне число першого виду зорівнює числу другого виду. Залишається припустити, що деяке число a_k- a₁ першого виду дорівнює числу a_l другого виду:

a_k- a₁ = a_l,

a_k = a₁ + a_l.

 

Задача № 16.

 Нехай  a, b, x₀ - деякі натуральні числа. Довести, що серед членів послідовності

x₀, x₁ = ax₀ + b, x₂ = ax₁ + b, … , x_n = ax_{n – 1} + b, …

нескінченно багато чисел, які не є простими.

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

 Задана послідовність  є монотонно зростаюча, при чому всі її члени, починаючи з першого, більші від а. справді,

x_n = ax_{n – 1} + b

x_{n – 1} + b x_{n – 1},  x₁ = ax₀ + b а.

Якщо числа  a і b не взаємно прості і НСД(a, b) = d, то всі члени послідовності, починаючи з першого, діляться на d, d 1. У цьому разі твердження задачі справедливе.

 Припустимо, що a і b взаємно прості. Тоді числа a і x_k, k 1, також взаємно прості. Справді, НСД(a, x_k) = l 1 і оскільки b = x_k - ax_k, то b ділиться на l. Отже ,

НСД (a, b) = l, що суперечить припущенню. Отже, a і x_k взаємно прості.

 Розглянемо  деяке x_k, позначимо його через s. Доведемо, що серед  s+1 чисел x_k, x_k+1, … , x_k+s обов’язково знайдеться складене число. Поділимо кожне з цих чисел на s. При цьому можливі остачі : 0, 1, 2, …, s – 1. Оскільки чисел всього s+1, а можливих остач s, то серед чисел x_k, x_k+1, … , x_k+s знайдуться два, наприклад x_p і x_q, p q, які при діленні на s дають однакові остачі. Різниця цих чисел ділиться на s. Оскільки

x_p - x_q = a(x_p-1 – x _q-1) і НСД(a, s) = 1, то x_p-1 – x _q-1 ділиться на s. Аналогічно, на s ділиться

x_p-2 – x _q-2 і т. д. повторюючи міркування, дійдемо до числа x_k+p-q – x_k . Проте число x_k ділиться на s = x_k тому число x_k+p-q ділиться на s і отже, це число не є простим. Таким чином, серед чисел  x_k, x_k+1, … , x_k+s є число, яке не є простим. Розглянувши тепер замість x_k число x_k+p-q+1, знову серед кількох наступних членів послідовності можемо знайти число, яке не є простим. Таких чисел серед членів нашої послідовності нескінченно багато.

 

Задача № 17.

Розглянемо послідовність 1, 1, 2, 3, 5, 8, 13, 21, 34,… , у якої кожний член дорівнює сумі двох попередніх (послідовність  чисел Фібоначчі). Випишемо під кожним з чисел цієї послідовності три  останні його цифри :

                          001, 001, 002, 003, 005, 008, 013, 021, 034, … .

           Довести, що ця нова послідовність  періодична.

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

Для кожної пари сусідніх чисел  Фібоначчі розглянемо пару чисел, утворених  їх трьома останніми цифрами. Всього може бути щонайбільше 10⁶ різних таких пар. Тому, за узагальненим принципом Діріхле, серед 10⁶ + 1 послідовних чисел Фібоначчі обов’язково трапляється дві пари сусідніх членів з відповідно однаковими останніми трьома цифрами. За останніми трьома цифрами пари сусідніх чисел Фібоначчі однозначно відновлюються три останні цифри наступного числа. Звідси й випливає, що послідовність, про яку йдеться в задачі, періодична.

 

Задача № 18.

     На клітчастому папері відзначили 5 точок, розташованих у вузлах сітки. Довести, що хоч би один з відрізків, що сполучає ці точки, проходить через вузол сітки.

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

 Введемо  на клітчастому папері систему координат з початком координат в одному з вузлів, осями, спрямованими уздовж ліній сітки, і одиничним відрізком, рівним стороні клітини. Тоді усі відмічені точки матимуть цілочисельні координати. Покажемо, що знайдуться дві точки з п'яти, у яких одна і та ж парність координат x і координат y. "Кроликами" у нас будуть точки, а " клітками" – пари (П,П)(П, Н)(Н, П)(Н, Н). Якщо, наприклад, у точки(x, y) координата x парна, а координата y непарна, то ми її помістимо в клітку  (П,Н). Отже, маємо 5 " кроликів" і 4 " клітки". За принципом Діріхле, деякі дві точки мають однакову парність координат. Нехай, (х₁, у₁) і (х₂, у₂) - дві точки, що потрапили в одну " клітку". Середина відрізка, що сполучає ці дві точки, має координати( , ), які є цілими числами в силу однакової парності x₁ і x₂, y₁ і y₂. Таким чином, середина цього відрізку лежить у вузлі сітки, тобто цей відрізок є шуканим.

 

Задача  № 19.

               Усередині рівностороннього трикутника зі стороною 1 розташовані 5 точок.

Довести, що відстань між  деякими двома з них менше 0,5.  
Розв’язання.  
         

  Середні лінії правильного трикутника із стороною 1 розбивають його на чотири правильні трикутнички із стороною 0,5. Назвемо їх " клітками", а точки вважатимемо "кроликами". За принципом Діріхле з п'яти точок хоча би дві опиняться в одному з        чотирьох трикутничків (див. малюнок). Відстань між цими точками  

                                                

 

 

 менше 0,5, оскільки точки не лежать у вершинах трикутничків. (Тут використана відома лема про те, що довжина відрізку, розташованого усередині трикутника, менше довжини його найбільшої сторони).

 

Задача  № 20.

У кожній клітинці дошки 5x5 сидить жук. В деякий момент часу всі жуки переповзають у сусідні по горизонталі чи по вертикалі клітинки. Довести, що при цьому принаймні одна клітинка залишиться порожньою.

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

  Розмалюємо дошку 5×5 в шаховому порядку.

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

 

 

 

 

 

Розділ 2.

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

Умова збігу.

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

Якщо  у n клітках розміщено не менше ніж nk + 1зайців, то знайдеться клітка, яка містить принаймні k + 1зайців.

Доведення.

Пронумеруємо  клітки числами 1, 2, …, n. Через x_і  позначимо кількість кроликів у клітці з номером і, 1 і n. За умовою

x₁ + x₂ + … + x_n

  nk + 1.

Припустимо, що x₁ k, x₂ k, … , x_n k. Тоді

x₁ + x₂ + … + x_n

nk.

Отримали суперечність: кількість зайців, з одного боку, більше ніж nk, а з іншого не перевищує nk. Отже, наше припущення не правильне, тобто знайдеться такий номер і, що x_і k + 1. Узагальнений принцип Діріхле доведено.

 При k = 1 узагальнений принцип Діріхле переходить у звичайний принцип Діріхле. У задачах на дослідження  часто корисним є наступне зауваження до узагальненого принципу Діріхле.

Зауваження. Якщо рівно nk + 1зайців розташовані у n клітках, то не обов’язково знайдеться клітка з k + 2 або більше зайцями . Наприклад,  можливе таке розташування зайців у клітках : n – 1 кліток містять рівно по k зайців, а n- на клітка містить k + 1 зайця.

 

Приклад.

У крамниці є 25 хусток різних розмірів: маленьких, середніх і великих. Доведіть, що серед них є принаймні 9 хусток одного й того самого розміру.

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

Проведемо міркування від  супротивного. Припустимо, що маленьких  хусток не більше восьми, середніх хусток не більше восьми і великих хусток не більше восьми. Тоді всього хусток не більше 8 · 3 = 24. Суперечність з тим, що за умовою у крамниці 25 хусток. Отже, у крамниці є принаймні 9 хусток одного й того ж самого розміру.

 

2. Умова збігу

Якщо розмістити не більше ніж  – 1 кроликів у n клітках, то знайдуться дві клітинки, в яких сидить однакова кількість кроликів (можливо клітки порожні).

Доведення.

Припустимо, що немає двох кліток, шо містять однакове число  кроликів. Це означає. Що у всіх клітках  знаходиться не менше

0 + 1 + 2 +…+

= кроликів, тобто більше ніж є.

Отримали суперечність. Отже, знайдуться дві клітки, в яких однакова кількість кроликів.

 

Задача  № 1.

У місті 2 500 000 жителів. Науковці вважають, що в кожної людини менш як 200 000 волосин на голові. Довести, що є тринадцять жителів з однаковою кількістю волосин на голові.

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

Припустимо, що є 200 000 ящиків, пронумерованих числами 0, 1, 2, …, 199 999 (це можливі числа волосин на голові людини).нехай число волосин кожного жителя записано на окремій картці. Таких карток 2 500 000 шт. розкладемо ці картки відповідно в ящики з номерами 0,1, … , 199 999. За узагальненим принципом Діріхле, в одному ящику повинно бути принаймні не менш як 13 карток. Справді, як би в кожному ящику було менш як 13 карток, то загальне число карток не перевищувало б 12 х 200 000 = 2 400 000.

 

 

 

Задача  № 2.

У класі навчається 29 учнів. Під час диктанту один учень  зробив 13 помилок, а всі інші учні – менше. Довести, що в класі є принаймні три учні, які зробили однакову кількість помилок.

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

Розіб’ємо всіх учнів в класі на 14 груп: до першої віднесемо тих учнів, які написали диктант без помилок, до другої –  тих, які зробили одну помилку, до третьої – дві помилки, і т. д., до тринадцятої – тих, які зробили дванадцять помилок, чотирнадцята група складається тільки з одного учня, який зробив 13 помилок. Якби в кожній з перших  тринадцяти груп було не більше від двох учнів, то загальне число учнів у класі не перевищувало б 2 х 13 + 1 = 27 учнів. Тому за узагальненим принципом Діріхле, принаймні в одній з груп повинно бути не менш ніж три учні.

 

Задача  № 3.

 Довести,  що серед будь – яких 100 чисел  можна знайти 15 чисел таких, що  різниця будь – яких двох  з них ділиться на 7 без остачі. Чи можна знайти 16 чисел, які задовольняли б ту саму умову?

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

Різниця двох чисел  ділиться на 7 тоді і тільки тоді, коли остачі від ділення цих чисел  на 7 однакові. При ділені на 7 є сім різних остач: 0, 1, 2, 3, 4, 5, 6.

 Припустимо, що не можна вибрати 15 чисел, які задовольняють умову. Це означає, що чисел, які при діленні на 7 дають остачу 0, не більше як 14; чисел, які при ділені на 7 дають остачу 1, не більше як 14, і т.д., і чисел, які при ділені на 7 дають остачу 6 не більше як 14. У цьому разі маємо не більше як 7 х 14 = 98 чисел.

 За узагальненим  принципом Діріхле, є 15 чисел,  які при діленні на 7 дають однакову  остачу.

Для 16 чисел  твердження задачі не виконується. Справді, розглянемо числа 

1, 2,…, 100. Серед  них є 14 чисел 7, 14,…, 98, які діляться  на 7 без остачі, дві групи 1, 8, 15,…, 99 і 2, 9, 16,…, 100 по 15 чисел, які при діленні на 7 дають остачі 1 і 2 відповідно; чотири групи, які при діленні на 7 дають остачі 3, 4, 5, 6 відповідно. Отже, серед чисел 1, 2, … , 100 не можна виділити групу з 16 чисел, які при діленні на 7 дають однакову остачу.

 

Задача  № 4.

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

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

Поділимо даний  квадрат на 25 однакових квадратів розмірами х . За узагальненим принципом Діріхле, принаймні в одному з них буде не менш, як  три дані точки. Опишемо навколо цього квадрата коло.  Його радіус буде дорівнювати

. Проте  .

 

Задача  № 5.

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