Приклад 5.1. Коник стрибав вздовж прямої і повернувся в початкову точку (довжина кожного стрибка дорівнює 1 м). Довести, що він зробив парне число стрибків.
Розв’язання. Оскільки коник повернувся в початкову точку, кількість стрибків вправо дорівнює кількості стрибків вліво, тому загальна кількість стрибків є парною. ■
Приклад 5.2. Чи існує замкнена ламана з 7 ланками, яка перетинає кожну свою ланку рівно один раз?
Розв’язання. Припустимо, що існує. Тоді ланки, що перетинаються утворюють пари. Тому кількість ланок повинна бути парною. Одержали суперечність. Отже, вказаної ламаної не існує. ■
Приклад 5.3. У марсіан буває довільне число рук. Одного разу всі марсіани узялися за руки так, що вільних рук не залишилося. Доведіть, що число марсіан, у яких непарне число рук, є парним.
Розв’язання. Назвемо марсіан з парним числом рук парними, а з непарним ― непарними. Оскільки руки утворюють пари, то загальне число рук парне. Загальне число рук у парних марсіан парне, тому загальне число рук у непарних марсіан теж парне. Отже, число непарних марсіан є парним. ■
Приклад 5.4. На координатній площині намальовано коло з центром в точці (0, 0), радіус якого дорівнює 1995. У кожній з точок площини, що лежать в середині кола та обидві координати яких є цілими числами, сидить павук. У деякій момент часу кожен з павуків переповзає на одиничну відстань праворуч, ліворуч, вгору або вниз, залишаючись всередині кола (різні павуки можуть рухатись у різі боки). Чи обов’язково після переповзання два павуки зустрінуться в одній точці?
Розв’язання. Кількість павуків усередині кола є непарним числом, бо кожній точці П(m, n), в якій сидить павук, відповідає симетрична відносно початку координат точка П1(−m, −n), лише точці (0, 0) немає пари. При вказаному в умові переповзанні кожен павук змінює на одиницю одну зі своїх координат, або, що те саме, змінює парність суми своїх координат. Розіб’ємо павуків на дві групи: М1 ― павуки з парною сумою координат, М2 ― павуки з непарною сумою координат. Припустимо, що після переповзання в кожній точці знову сидить рівно один павук. Це означає, що при переповзанні кожен павук групи М1 зайняв місце точно одного павука з групи М2 і навпаки, тобто в групах М1 та М2 однакова кількість павуків. Це суперечить тому, що їхня загальна кількість непарна.
Отже, в деякій точці після переповзання буде два чи більше павуків. ■
Приклад 5.5. Чи можна всі натуральні числа від 1 до 65 розбити на кілька груп так, щоб у кожній групі найбільше число дорівнювало сумі інших?
Розв’язання. Припустимо, що можна. Тоді в кожній групі сума чисел є парним числом, тому сума всіх чисел від 1 до 65 теж має бути парною. Але сума 1 + 2 + … + 65 = 65 · 33 ― непарна. Одержали протиріччя. Отже, розбити числа вказаним способом не можна. ■
Приклад 5.6. По колу написано в довільному порядку 4 одиниці та 5 нулів. Над ними виконують наступну операцію: між однаковими цифрами пишуть нуль, а між різними ― одиницю, після чого попередні цифри витирають. Потім таку ж операцію виконують над отриманими цифрами і т. д. Довести, що після кількох таких операцій неможливо отримати 9 нулів.
Розв’язання. Припустимо, що після k таких операцій отримано 9 нулів. Тоді після (k − 1)-ої операції всі цифри на колі повинні були дорівнювати одиниці, а тому після (k − 2)-ої операції довільні дві сусідні цифри на колі повинні були бути різними. Тоді нулів має бути стільки, скільки й одиниць, звідки отри-муємо, що загальна кількість цифр є парним числом. Це суперечить умові. Отже, отримати 9 нулів неможливо. ■
Приклад 5.7. Зграя мавп розташувалися по колу. Кожна мавпа має певну кількість бананів і певну кількість ананасів. Відомо, що жодні дві мавпи, які не знаходяться поруч, не в змозі відразу поділити загальну кількість бананів і ананасів (окремо тих та інших), які вони мають, порівну між собою, залишивши ласощі цілими. Скільки мавп може бути в цій зграї?
Розв’язання. З умови відразу випливає, що в довільних двох мавп, які не знаходяться поруч, або сума кількостей бананів непарна, або сума кількостей ананасів непарна. Існує лише 4 різні за парністю способи надання одній мавпі бананів та ананасів: (п, п) ― парна кількість бананів і парна кількість ананасів, (п, н) ― парна кількість бананів та непарна кількість ананасів, (н, п) ― непарна кількість бананів і парна кількість ананасів, (н, н) ― непарна кількість бананів та непарна кількість ананасів. Оскільки в довільних двох мавп, які не знаходяться поруч, такі способи повинні бути різні, то отримуємо, що мавп може бути не більше 8 (у двох, але не в трьох, мавп, які знаходяться поруч, можуть бути однакові способи). Приклад 8 мавп легко сконструювати: (п, п), (п, п), (п, н), (п, н), (н, п), (н, п), (н, н), (н, н). Зрозуміло, що з такого набору можна викреслити будь-яку кількість мавп. Отже, мавп може бути не більше восьми. ■
Приклад 5.8. Коло розбите точками на 3k дуг: по k дуг завдовжки 1, 2, і 3. Довести, що серед цих точок знайдуться дві діаметрально протилежні точки.
Розв’язання. Припустимо супротивне, тобто, що таких діаметрально протилежних точок розбиття немає. Тоді отримуємо, що проти дуг завдовжки 1 лежать дуги завдовжки 3. Вилучивши дві такі діаметрально протилежні дуги завдовжки 1 та 3, отримаємо дві рівні «великі» дуги завдовжки 6k - 42=3k - 2 .
Нехай одна з них містить m дуг завдовжки 1 та n дуг завдовжки 3, тоді протилежна містить n дуг завдовжки 1 та m дуг завдовжки 3, причому m + n = k – 1. Оскільки крім цих дуг кожна з «великих» дуг містить лише дуги завдовжки 2, то парність довжини «великих» дуг співпадає з парністю числа k – 1. Але (3k – 2) – (k – 1) = 2k – 1, тобто числа 3k – 2 та k – 1 мають різну парність. Прийшли до протиріччя. Отже, обов’язково знайдуться дві діаметрально протилежні точки розбиття. ■