цузькою або російською. Доведіть, що серед них знайдуться троє, які переписуються між собою на одному і тому ж мовою.
Рішення.
Означимо кожного з учених точкою і з'єднаємо ці точки всілякими відрізками. Точки розташуємо так, щоб ніякі три з них не лежали на одній прямій. Так як кожен вчений листується з 16 іншими, то з кожної точки виходить 16 відрізків. Кожен з відрізків, що означає переписку вчених англійською мовою, забарвимо в чорний колір, на французькою - в червоний, російською - в білий.
Розглянемо два випадки.
1) Нехай серед відрізків, з'єднують точки А2, А3, А4, А5, А6 і А7 попарно між собою, є чорний, скажімо А2А3. Тоді у трикутника А1А2А3 всі сторони чорні, тобто відповідна трійка вчених переписуються між собою англійською мовою.
2) Нехай серед цих відрізків немає чорного. У цьому випадку відрізки між шістьма точками А2, А3, А4, А5, А6 і А7 пофарбовані не більше, ніж у два кольори - червоний і білий. Тоді на підставі затвердження завдання 3.33 серед відрізків, що з'єднують ці точки, є три, складові трикутник зі сторонами одного цвета.
3.37. На площині дано п точок, з яких ніякі зо три не лежать на одній прямій. Вони з'єднані всілякими відрізками, і кожен відрізок забарвлений в один з чотирьох різних кольорів. При якому найменшому п обов'язково знайдеться трикутник з одноколірними сторонами з вершинами у трьох з даних точок? p> 3.38. Послідовність з 36 нулів і одиниць починається з п'яти нулів. Серед п'ятірок поспіль стоять цифр зустрічаються всі 32 можливі комбінації. Знайдіть п'ять останніх цифр послідовності. p> 3.39. Доведіть, що можна розташувати по колу символи 0 і 1 так, щоб будь-який можливий набір з n символів, що йдуть підряд, зустрівся.
Вказівка.
Розглянути граф, вершини якого суть слова довжини n -1. Дві вершини u і v з'єднуються стрілкою, якщо існує слово довжини n , у якого u є початком, а v - кінцем.
4. Розмальовки
Кажуть, що фігура пофарбована в кілька кольорів, якщо кожній точці фігури приписаний певний колір. Бувають завдання, де розфарбування вже дана, наприклад для шахової дошки, бувають завдання, де розмальовку з даними властивостями потрібно придумати, і бувають завдання, де розфарбування використовується як ідея рішення.
Завдання
4.1. З шахівниці вирізали дві протилежні кутові клітини. Доведіть, що залишилася фігуру не можна розрізати на В«доміноВ» з двох клітин
Рішення.
Кожна фігура В«доміноВ» містить 1 білу і 1 чорну клітку. Але в нашій фігурі 32 чорних і 30 білих клітин (або навпаки).
4.2. Чи всі клітини дошки 9х9 обійти конем по одному разу і повернутися у вихідну клітку?
Рішення.
Кожним ходом кінь змінює колір клітини,...
