Приклад 2.1. Площина розрізана вздовж N прямих загального положення. Довести, що до кожної прямої примикає трикутник.
Розв’язання. Виберемо будь-яку з даних прямих і розглянемо точки перетину інших прямих між собою. Серед цих точок перетину виберемо найближчу до нашої прямої. Дві прямі, що проходять через цю точку, перетинають початкову пряму і утворюють з нею трикутник. Цей трикутник не перетинають інші прямі. ■
Приклад 2.2. Довести, що у будь-якому многограннику є дві грані з однаковим числом сторін.
Розв’язання. Розглянемо грань з найбільшим числом сторін. Позначимо цю грань через G, число її сторін через n. До кожної сторони грані G прилягає грань многогранника, всього прилеглих граней є n. Число сторін у кожної грані міститься між 3 і n − 1, всього n − 3 можливості. Оскільки число можливостей менше числа прилеглих граней, то за принципом Діріхле одна з можливостей повториться. Таким чином, серед граней, що прилягають до грані G, знайдуться дві грані з однаковим числом сторін. ■
Приклад 2.3. У кожній клітинці шахівниці записали число. Виявилося, що кожне число дорівнює середньому арифметичному чисел, записаних в сусідніх (по стороні) клітинках. Довести, що всі числа дорівнюють одне одному.
Розв’язання. Розглянемо найбільше із записаних чисел. Воно дорівнює своїм сусідам. Оскільки будь-які два числа з’єднуються ланцюжком сусідніх чисел, то всі числа рівні між собою. ■
Приклад 2.4. Сім грибників зібрали разом 100 грибів, причому ніякі двоє не зібрали однакової кількості грибів. Довести, що існують троє грибників, які зібрали разом не менше, ніж 50 грибів.
Розв’язання. Розглянемо трьох грибників, які зібрали разом максимальну (серед всіх трійок грибників) кількість грибів. Якщо мінімальна (з цих трьох) кількість грибів дорівнює 16, то разом три грибника зібрали грибів не менше, ніж 16 + 17 + 18 = 51. Якщо зазначена мінімальна кількість менша від 16, то решту чотири грибника зібрали разом не більше 14 + 13 + 12 + 11 = 50 грибів. Звідси отримуємо, що перші троє зібрали разом не менше, ніж 50 грибів. ■
Приклад 2.5. Елементами таблиці розміром n × n є нулі та одиниці. При цьому виконується наступна умова: якщо на деякому місці таблиці записано нуль, то сума чисел стовпця і рядка, що містять цей нуль, не менше від n. Довести, що сума всіх n2 чисел не менша від n22 .
Розв’язання. Розглянемо рядок або стовпець, які мають мінімальну суму елементів серед всіляких сум елементів кожного рядка і кожного стовпця. Нехай, для визначеності, це буде рядок із сумою елементів, яка дорівнює k. Якщо k≥n2 , то сума елементів кожного рядка не менша від n2 і тому сума всіх елементів не менша від n22 . Припустимо, що k<n2 . Тоді в цьому рядку є n − k нулів і сума елементів кожного стовпця, що містить один із зазначених нулів не менша від n – k.
Таких стовпців є n − k, тому загальна сума елементів, що містяться в них, не менша від (n - k)2 . Сума елементів в кожному з решти k стовпців не менша від k, тому загальна сума елементів, що містяться в них, не менша від k2 . Отже, сума всіх елементів таблиці не менша від
(n - k)2+k2=2n2 - k2+n22≥n22. ■
Приклад 2.6. Довести нескінченність множини простих чисел вигляду 4m + 3.
Розв’язання. Припустимо протилежне, тобто що множина простих чисел вигляду 4m + 3 є скінченною. Нехай p1, …, pn ― її елементи. Якщо n ― парне число, то p1 · p2 · … · pn + 2 ≡ (−1)n + 2 ≡ 3 (mod 4), тобто
p1 · p2 · … · pn + 2 = 4m + 3
при деякому m ∈ N. Відтак, це число має простий дільник p виду p = 4k + 3 (справді, якщо всі прості дільники числа 4m + 3 мають вигляд 4k + 1, то і їх добуток має вигляд 4k + 1). З іншого боку, неважко помітити, що жодне з чисел p1, p2, …, pn не є дільником числа p1 · p2 · … · pn + 2. Звідси отримуємо, що p ∉ {p1, p2, …, pn}. Маємо протиріччя з тим, що всі прості числа виду 4m + 3 містяться в множині {p1, p2, …, pn}. Якщо n ― непарне число, то
p1 · p2 · … · pn + 4 ≡ (−1)n + 4 ≡ 3 (mod 4).
Аналогічно міркуючи, доводимо існування простого числа p виду p = 4k + 3 такого, що p ∉ {p1, p2, …, pn}. І знову отримано протиріччя з вихідним припущенням. ■
Приклад 2.7. Довести, що для будь-якого натурального числа n число
1 + 13 + 15 + … + 12n+1 (1)
не є цілим.
Розв’язання. Нехай 3rj ― максимальна степінь трійки, що ділить число 2j + 1 (j = 0, 1, …, n), і 3r = max {3rj | j = 0, 1, …, n}. Покажемо, що тільки для одного j ∈ {0, 1, …, n} має місце рівність r = rj. Припустимо протилежне. Тоді для деяких j ≠ k, де j, k ∈ {0, 1, …, n}, мають місце співвідношення
2j + 1 = 3r · sj,
2k + 1 = 3r · sk.
З побудови числа 3r випливає, що 3r+1 > 2n + 1. Відтак 1 ≤ 3r · sj < 3r+1, 1 ≤ 3r · sk < 3r +1. Звідси отримуємо, що 1 ≤ sj ≤ 2, 1 ≤ sk ≤ 2. Оскільки sj ≠ sk, то одне з чисел sj, sk ― парне. Отримане протиріччя доводить справедливість твердження.
Приводячи вираз (1) до спільного знаменника, отримаємо:
2n + 1‼1 + 2n + 1‼3 + … + 2n + 1‼2n + 12n + 1‼, (2)
де (2n + 1)!! = 1 · 3 · … · (2n + 1).
Нехай r = rj і 3m ― максимальна степінь трійки, що ділить число (2n + 1)!!. Тоді для кожного k ≠ j зі співвідношення 2n + 1‼2k + 1 ⋮3m - rk випливає, що 2n + 1‼2k + 1⋮3m - r + 1 . З іншого боку 2n + 1‼2j + 1 ⋮ 3m - r + 1 . Значить
2n + 1‼1+2n + 1‼3+…+2n + 1‼2n + 1 ⋮3m - r + 1.
Отже, число (2) не є цілим. ■
Приклад 2.8. Довести, що рівняння
x2 + y2 = 3(z2 + t2) (3)
не має розв’язків у натуральних числах.
Розв’язання. Припустимо протилежне, тобто що існують розв’язки x, y, z, t рівняння (3) у натуральних числах. Розглянемо розв’язок, для якого значення виразу x2 + y2 є мінімальним. З рівності (3) випливає, що (x2 + y2) ⋮ 3. Звідси от-римуємо, що x⋮3 і y⋮3 (це випливає з того, що остача від ділення квадрата будь-якого цілого числа на 3 дорівнює 0 або 1). Таким чином, x = 3x1, y = 3y1. Відтак
z2+t2=3(x12 + y12 ).
Зауважимо, що z2+t2<x2+y2 . Отримане протиріччя доводить справедливість вихідного твердження. ■
Приклад 2.9. На площині задано множину точок M таку, що кожна точка з M є серединою відрізка, що з’єднує деякі дві інші точки з M. Довести, що множина M нескінченна.
Розв’язання. Припустимо протилежне. Введемо на площині прямокутну систему координат. Розглянемо точку з M з максимальною абсцисою. Якщо таких точок декілька, то розглянемо ту з них, у якої максимальна (серед точок з максимальною абсцисою) ордината. Позначимо цю крайню точку через A(x, y). Вона є серединою відрізка, що з’єднує деякі дві точки B(x1, y1), C(x2, y2), що належать M. Із співвідношень х = x1 + y12 , x1 ≤ x, x2 ≤ x випливає, що x1 = x2 = x. Тобто точки A, B, C мають однакову абсцису. Тому y1 ≤ y, y2 ≤ y. Це неможливо, оскільки y = y1 + y22 , а точки A, B, C ― різні. Отримане протиріччя доводить необхідне твердження. ■
Приклад 2.10. На площині розташовано n точок, причому площа будь-якого трикутника з вершинами в цих точках не перевершує 1. Довести, що всі ці точки можна помістити в трикутник, площа якого дорівнює 4.
Рис. 2
Розв’язання. Розглянемо трикутник максимальної площі з вершинами в даних точках. Нехай це буде трикутник ABC (рис. 2). Через точки A, B, С проведемо прямі lA , lB , lC , паралельні сторонам BC, CA, AB відповідно. Позначимо трикутник, утворений прямими lA , lB , lC через A1B1C1 . Площа цього трикутника в 4 рази більша від площі трикутника ABC, отже, вона не перевершує 4. Покажемо, що кожна із заданих точок знаходиться в трикутнику A1B1C1 . Припустимо протилежне. Тоді існує точка D з даної множини, яка перебуває з деякою вершиною трикутника A1B1C1 по різні боки щодо сторони, протилежній цій вершині. Нехай, наприклад точки, C1 і D знаходяться по різні боки щодо прямої B1A1 . Тоді відстань від точки D до AB більша, ніж відстань від точки C до AB. Тому площа трикутника ABD більша площі трикутника ABC, що суперечить вибору трикутника ABC. Отже, всі задані точки можна помістити у вказаний трикутник. ■
Приклад 2.11. Довести, що будь-який опуклий многокутник, площа якого дорівнює 1, можна помістити в прямокутник із площею 2.
Розв’язання.
Рис. 3
Нехай AB ― максимальна діагональ (або сторона) вказаного многокутника (рис. 3). Проведемо через точки A і B прямі, перпендикулярні відрізку AB. З побудови відрізка AB випливає, що весь многокутник міститься в смузі, утвореній цими прямими. Проведемо прямі CD, EF, паралельні AB, що проходять через деякі вершини многокутника і мають ту властивість, що многокутник знаходиться по одну сторону відносно кожної з них. Опустимо з точок P та Q перпендикуляри PP1 і QQ1 на AB. Площа вихідного многокутника більша або дорівнює сумі площ трикутників APB і AQB, тобто
12AB∙PP1+12AB∙QQ1=12CD∙CE.
Звідси випливає, що площа прямокутника EFDC, що містить вихідний многокутник, не перевершує 2. ■
Приклад 2.12. Довести, що у многограннику є дві грані з однаковою кількістю сторін.
Розв’язання. Розглянемо грань з найбільшою кількістю сторін. Позначимо її через G. Нехай вона має n сторін. До кожної сторони грані G прилягає грань многогранника, всього ― n граней. Якщо в многограннику є ще одна грань з n сторінками, то твердження задачі доведено. Якщо ж більше такої грані немає, то в гранях, які прилягають до G, кількість сторін міститься між 3 та (n – 1), всього (n – 3) можливості. Оскільки кількість можливостей менше n, то якась із можливостей повторюється, тобто серед граней, що прилягають до грані G, знайдуться дві грані з однаковою кількістю сторін. ■
Приклад 2.13. У тридев’ятому королівстві кожні два міста з’єднані дорогою з одностороннім рухом. Довести, що існує місто, з якого в будь-яке інше місто можна проїхати не більше як двома дорогами.
Розв’язання. Розглянемо місто А, з якого виходить найбільша кількість доріг, а саме ― n доріг. Припустимо, що існує місто В, в яке не можна проїхати з міста А однією чи двома дорогами. Тоді з міста В обов’язково виходять дороги до міста А та всіх міст, до яких виходить дорога з міста А, всього хоча б (n + 1) дорога. Це суперечить тому, що з міста А виходить найбільша кількість доріг. Отже, з міста А в будь-яке інше місто можна проїхати не більше як двома дорогами. ■
Приклад 2.14. Протягом дня в бібліотеці побувало 100 читачів. Кожен читач відвідав бібліотеку рівно один раз. Виявилось, що в цей день з будь-яких трьох читачів принаймні двоє зустрілись у бібліотеці. Довести, що працівник бібліотеки міг зробити повідомлення в такі два моменти часу, щоб усі 100 читачів його почули.
Розв’язання. Нехай А ― той читач, який першим вийшов з бібліотеки, В ― той читач, який першим після виходу читача А зайшов до бібліотеки, С ― довільний читач із читачів, які зайшли до бібліотеки після читача В. Оскільки читач А не зустрівся ні з В, ні з С, то читачі В і С обов’язково зустрілись, а тому читач В знаходився в бібліотеці доти, поки всі читачі не прийшли в бібліотеку. Розглянувши читачів А і С та довільного, відмінного від С, читача D, що прий-шов у бібліотеку після В, отримуємо з умови задачі, що читачі С і D обов’я-зково зустрілись. Тому жоден із читачів, які прийшли в бібліотеку після читача В, не вийшли з бібліотеки раніше за нього.
Отже, потрібні моменти часу такі: перше повідомлення ― безпосередньо перед виходом читача А, друге ― безпосередньо перед виходом читача В. ■