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

.

Згідно з теоремою 4, А₁ містить принаймні дві різні точки такі, що

 

є цілими числами. Оскільки множина А симетрична відносно початку координат, то множина А₁ також симетрична відносно початку координат. Отже, точка () також належить А₁. Крім того, множина опукла. Тому середина відрізка, який сполучає точки ) і (х₂, у₂),

тобто точка

 

і також належить А₁. Помноживши координати цієї точки на 2, матимемо точку, яка належить множині А. Таким чином, точка

,

яка відмінна від початку  координат і має цілі координати, належить множині А.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

РОЗДІЛ ІV. Задачі

 

Задача 1. На відрізку (1,100] вибрано 8 різних дійсних чисел. Довести, що серед цих чисел знайдуться два числа а та b такі, що

1 < < 2.

Розв'язання. Оскільки [1,100]= виберемо замість ящиків проміжки з правої частини цієї рівності, а замість предметів - дані 8 чисел. Оскільки проміжків є 7, а чисел - 8, то є такі два числа а та b, які належать одному проміжку, причому вважатимемо, що а > b. Зрозуміло, що тоді числа а та b є шуканими.

Задача 2. В клітинках таблиці 4x4 розставлено числа: -1,0,1. Розглянемо наступні суми чотирьох чисел: суми чисел які розміщені в одному рядку, одному стовпцю та на великих діагоналях. Довести, що серед цих сум є принаймі дві однакові.

Розв'язання. Зрозуміло, що кожні з вказаних сум може дорівнювати лише одному з наступних чисел :-4, -3, -2, -1,0,1,2,3,4. Оскільки всіх можливих сум є десять і кожна з них може набувати одне із дев'яти вказаних значень, то значення принаймі двох із цих сум співпадають.

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

Розв'язання. Нехай - це кількість людей деякої сукупності. Тоді кількість знайомих кожного співпадає з одним із n чисел: 0,1,...,1. Допустимо, що всі люди з вибраної компанії мають різну кількість знайомих серед вибраних. Тоді знайдуться двоє людей, один з яких матиме 0 знайомих, а інший - (п - 1)-го знайомого, тобто перший з них не має знайомих, а другий знайомий з усіма. Отримали протиріччя (бо поняття знайомства симетричне: якщо А знайомий з В, то В знайомий з А).

Задача 4. Довести, що серед 37 учнів деякого класу є четверо, які народилися в одному місці.

Розв'язання Допустимо, що твердження задачі не вірне. Тоді в кожному місяці народилося не більше 3 школярів, а тому загальна кількість учнів в класі не перевищувала б 3 ·12= 36. Одержали протиріччя.

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

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

Розв'язання. Проведемо доведення від супротивного. Допустимо, що кожен з піратів отримав різну кількість діамантів. Впорядкувавши ці кількості за зростанням, одержимо

 

 

            

            

                 …

             ,

то 

      

 

 

Отримали протиріччя, бо за умовою пірати мали лише 189 діамантів.

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

Розв'язання. Зрозуміло, що як би не було спаковано вантаж в ящики, за один рейс паром зможе перевезти принаймні 19 тон вантажу. Тоді за 6 рейсів паром зможе перевезти вантаж масою 19·6 = 114 тон, а значить і 106 тон. Покажемо, що вантаж може бути спакований в ящиках таким чином, що 5 рейсів не вистачить. Допустимо, що весь вантаж спаковано в 21 ящику, причому маси ящиків однакові. Тоді маса кожного ящика дорівнює т. Якщо б цей вантаж паром зміг перевезти за 5 рейсів, то за узагальненим принципом Діріхле хоча б за один рейс паром повинен був перевезти 5 ящиків, маса яких дорівнює

 ·5 т.,

 і яка більша за 25 тон. Одержали  протиріччя з умовою задачі.

Задача 7. Кожне з восьми даних натуральних чисел не перевищус 16, причому всі числа є різними. Довести, що серед їхніх попарних різниць є принаймі три однакові.

Розв'язання. Розмістимо дані числа в порядку зростання

1

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

 

 

що неможливо.

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

Розв'язання. Наведено два типові методи роз'язання подібних задач. 

1 спосіб. Позначимо вибрані числа через

Додаючи до кожного з цих  чисея по 1, дістанемо 51 різне число:

 

 

Одержали 102 натуральні числа, які  лежать в межах від 1 до 101. Тому деякі  два з цих чисел співпадаю, тобто

 

i для деяких , ϳ = 1,51. Отже

,

1 спосіб. Розіб'ємо дані сто чисел на пари {1,2},{3,4},.. .,{99,100}. Оскільки вибрано 51 число, то за признаком Дїріхле принаймні 2 з вибраних чисел будуть входити в одну пару. Залишається скористатися тим, що різниця між більшим і меншим числом кожної пари дорівнює 1.

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

Розв'язання. Впорядкуємо вибрані числа за зростанням:

  < а₂ < ... < а_п+2

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

а₂— .

 Отримали натуральні числа :

а₂,a₃,.. .,

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

 

 

 

 

Зауваження, (п + 1)-го числа може виявитися не досить. Розглянемо приклад набору чисел з n, n +1,..., 2n. Оскільки сума двох найменших з цих чисел є більшою за 2, то для цього набору з (+ 1)-го числа твердження задачі 9 не правильне.

Задача 10. Нехай п- фіксоване натуральне число. З чисел 1,2,..., 2 довільним чином вибрано +1 число. Довести, що серед вибраних чисел знайдуться 2 числа, одне з яких ділиться на інше.

Розв'язання. Кожне з вибраних чисел однозначно подається у вигляді

(2q + 1) · 2^Р,

де р та q - цілі невід'ємні числа. Оскільки непарні множники виду 2q + 1 кожного з вибраних чисел можуть набувати n значень, а саме:

1,3, ...,2п - 1,

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

Зауваження. Цю задачу придумав відомий угорський математик П.Ердьош.

Задача 11. З чисел 1,2,.. .,50 довільним чином вибрано 20 різних чисел. Довести, що серед вибраних чисел знайдуться два числа, різниця між якими дорівнює одному з чисел: 4,5,9 .

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

а_1, а₂, ..., а₂₀.(1)

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

, а₂ + 4, ..., + 4, (2)

+ 9, а₂ + 9, а₂₀ + 9. (3)

Оскільки загальна кількість чисел  в цих наборах дорівнює 60 і всі вони містяться в межах від 1 до 59, то деякі два з цих чисел співпадуть. Але в кожному з цих наборів находяться різні числа, тому числа які співпадають належать різним наборам. Якщо числа, які співпадають, входять в набори (1) і (2), то різниця між деякими двома з вибраних чисел дорівнює 4. У випадку ж коли ці числа входять набори (2) і (3) або (1) і (3), то різниця між ними дорівнює 9. .

Задача 12. З чисел 1,2,....,52 довільним чином вибрано 17 різних чисел. Довести, що серед вибраних чисел  знайдуться два числа, різниця між якими дорівнює одному з чисел: 4,5,9

Розв'язання. Розіб'ємо числа 1,2,...,52 на  чотири множини, кожна з яких складається з 13-ти послідовних натуральних чисел. Тоді за узагальненим принципом Діріхле принаймні в одній з цих множин буде 5 вибраних чисел. Не порушуючи загальності вважатимемо, що вибраних чисел містяться серед чисел 1,2, ...,13. Як посеред вибраних чисел є 5 та 9, то задача розв'язана.Якшо серед вибраних чисел немає 9, то розглядаючи трирійки чисел

{1,5,10}, {2,6,11}, {3,7,12}, {4,8,13},

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

{1,6,10}, {2,7,11}, {3,8,12}, {4,9,13}

одержуємо розв'язання задачі.

Задача 13. Чи можна числа 1,2, 3,…,16,17 розставити по колу так, щоб кожні два сусідні числа відрізнялись на 4,5,6 або 7?

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

1,2,3,4,14,15,16,17.      (4)

 

Оскільки серед попарних різниць цих чисел немає заданих, то вони не можуть бути сусідніми. Розглянемо 9 чисел, які залишилися

5,6,7,8,9,10,11,12,13.             (5)

Всі вони розміщені між числами (4), причому за принципом Діріхле між деякими двома з чисел системи (4) знаходиться два числа з (5), а між будь-якими іншими числами з (4) . розміщено по одному числу з (5). Числа 5 і 13 мають лише по одному сусіду серед чисел групи (4) (це відповідно числа 1 і 17), тому вони є сусідами. Отримали протиріччя, бо 13-5 = 8.

Задача 14. Довести, що довільна послідовність, яка складається з (тп+1)-го дійсного числа, містить зростаючу підпослідовність з (т+1 )-го числа, або спадну підпослідовність з (п + 1 )-го числа.

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

а т та b п.

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

(; b),

то деяким двом різним членам даної послідовності та відповідає одна і та ж сама пара натуральних чисел (; b). Якщо , то перша координата пари , що відповідає числу , принаймі на 1 більша від першої координати пари (), що відповідає члену послідовності Якщо ж , то число принаймі на одиницю більше за В обох випадках отримали суперечність.

Задача 15. ( Теорема Діріхле) Нехай -ірраціональне, а - натуральне числа. Довести, що існують цілі числа т та п, причому

0 < т ,

для яких |т -п| <

Розв’язання. Розіб'ємо проміжок [0,1) на s рівних за довжиною проміжків, тобто подамо [0,1) у вигляді

[о,1) = [о,)    (6)

Розглянемо s+ 1 число виду: {}, {2},...,{s+ 1)} з проміжка [0,1). Оскільки кількість цих чисел більша за кількість проміжків з правої частини (6), то деякі два з них лежатимуть па одному проміжку, тобто існують різні натуральні числа і та j, які лежать в межах від 1 до s + 1, а також існує натуральне число k в межах від 1 до s, для яких

{ .

Тоді

 

Не порушуючи загальності вважатимемо, що і > j/Враховуючи, що {і} = і — [і], {}=j , отримаємо

 

Позначаючи

і -j = т,

отримаємо, що

|т -n| < ,

причому т та п - цілі, і 0 < m

Зауваження. З теореми Діріхле вишиває, що для довільного > 0 нерівність

 

має дача б один ненульовий цілочисловий розв'язок (х,у). Щоб в цьому переконатися досить для фіксованого > 0 вибрати натуральне s настільки великим, щоб

 

 і скористатися теоремою  Діріхле.

Задана 16. Нехай - ірраціональне число. Тоді для довільного додатного числа нерівність 

 

 

має безліч розв'язків в цілих  числах x, у.

Розв'язання. Доведемо твердження задачі 13 від супротивного. Допустимо, що вихідна нерівність для деякого > 0 має скінченну кількість розв'язків в цілих числах, а саме ненульових розв'язків ( Покладемо

.

 Зауважимо, що , бо в протилежному випадку для деякого   ми одержали  б, що

.

Звідси з врахуванням  ірраціональності ми отримали б, що , тобто () - нульовий розв'язок. За зауваженням до теореми Діріхле нерівність має хоча б один ценульовий цілочисловий розв'язок (x'; у'). Зрозуміло, що цей розв'язок буде також розв'язком нерівності  

(бо ₀ < ), відмінним від розв'язків (

 Одержали протиріччя.

Зауваження. Якщо -ірраціональне, а > 0, то серед цілочислових розв'язків (x; у) нерівності  

є безліч таких, у яких а) x пробігає нескінченну множину натуральних чисел; б) у пробігає нескінченну множину натуральних чисел.

Задача 17. Показати, що для будь якого > 0 існує безліч натуральних чисел п, для яких

Розв'язання. Нехай > 0. Оскільки - ірраціональне число, то за твердженням попередньої задачі існує нескінченна кількість пар цілих чисел (m;n), для яких

.

 Для таких пар маємо

 

.

Залишається скористатися попереднім зауваженням.

Задача 18. ( Теорема Кронскера) Нехай та a – дійсні числа, причому - ірраціональне. Тоді для довільного додатного числа є нерівність

 

має розв 'язки в цілих  числax

Розв'язання. Якщо a= 0, то правильність твердження задачі випливає з теореми Діріхле. Нехай a . Зафіксуємо > 0. За теоремою Діріхле (див. також задачу 16) існує ненулільова пара цілих чисел ()і для яких

 

Оскільки

,

 тo покладаючи

h =

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

.

Оскільки

,

 то з останньої нерівності одержмо, що

 

Отже, пара цілих чиса (l) є розв'язком вхідної нерівності. Зауважимо, що побудований розв'язок є ненульовим.

Зауваження 1. Використовуючи зауваження до задачі 16 можна показати, що при виконанні умов задачі 17 існує нескінченна кількість пар цілих чисел (х;у), для яких