Задачи на разрезание - Екимова М.А.
IS BN 5-94057-051-8
Скачать (прямая ссылка):
Рис. 187
Ответы и решения
89
Это соображение позволяет точно назвать цвет некоторых клеток пояса (см. рис. 186 (в)). Поэтому на рис. 186 (в) в клетках * и # стоит цвет 3 (соседние с ними клетки, где разрешалось ставить цвет 3, заняты цветом 2 и 4). Но тогда цвет 3 стоит в клетках Y, а это противоречит условию задачи.
Итак, k ^ 14. На рис. 187 показана раскраска в 14 цветов.
8.24. Ответ. а) Рассмотрим клетку, обозначенную 1, покрасим ее в цвет 1 (рис. 188 (а)). У этой клетки 9 соседок, все они должны быть покрашены в разные цвета. Любые две соседних клетки имеют общую соседку, поэтому любая клетка окрашена не так, как ее соседка. Поэтому для окраски плоскости таким образом необходимо не меньше 10 цветов. Докажем, что 10 цветов недостаточно. Раскрасим соседки клетки 1 в другие 9 цветов, см. рис. 188 (а). Клетки, обозначенные (*) и (**), можно закрасить 7 или 8 цветом, но неизвестно, какую клетку каким цветом закрашивать. Аналогично, клетки, обозначенные (+) и (+—Ь), можно закрасить или 9 или 10 цветом, но неизвестно, какую клетку каким цветом.
Б) В) Ч)
Рис. 188
1) Сначала рассмотрим раскраску этих клеток, которая показана на рис. 188 (б) (по часовой стрелке). Теперь рассмотрим клетки, которые обозначены на рисунке (#), (##), (+), (++), (*), (**). Клетку (#) нельзя закрасить цветами 7, 6, 5, 4, 8, 9, 10, но можно закрасить цветами 1, 2, 3. Клетку (##) нельзя закрасить цветами 7, 6, 5, 4, 8, 9, 10, но можно закрасить цветами 1, 2, 3. Клетку (+) нельзя закрасить цветами 7, 10, 5, 4, 8, 9, 3, но можно закрасить цветами 1, 2, 6. Клетку (+—Ь) нельзя закрасить цветами 7, 10, 5, 4, 8, 9, 3, но можно закрасить
90
§8. Задачи с раскраской в условии
цветами 1, 2, 6. Клетку (*) нельзя закрасить цветами 7, 6, 5, 4, 8, 9, 10, но можно закрасить цветами 1, 2, 3, 6. Клетку (**) нельзя закрасить цветами 7, 6, 5, 4, 8, 9, 10, но можно закрасить цветами 1, 2, 3, 6. У нас есть свободных 4 цвета и нужно закрасить 6 клеток, причем нет общих соседок только у клеток (#) и (+). Закрасим их одним цветом. Тогда останется 4 клетки и 3 цвета, поэтому как бы мы ни закрашивали их, все равно две соседние клетки будут закрашены одним цветом. А этого нельзя допустить по условию.
2) Поменяем цвета 7, 8 и 9, 10 местами, как показано на рис. 188 (в). Тогда для раскраски тех же 6 клеток, которые на рис. 188 (б) были обозначены (#), (##), (+), (++), (*), (**), у нас будет в наличии уже 5 цветов (добавится цвет 10). Тогда эти клетки можно закрасить так, что у каждой клетки все соседки будут разных цветов. Но тогда клетки, обозначенные на рис. 188 (в) символами (#), (##), (+), (+—Ь), (*), (**), нельзя закрасить так, как требуется в условии (доказательство, аналогичное случаю 1).
б) См. рис. 189. Цвета повторяются в указанных стрелками направлениях через три маленьких шестиугольника.
Рис. 189
8.25. Решение. а) Пусть k — наименьшее число цветов, удовлетворяющее условиям задачи. У любых двух клеток-соседок есть общая соседка. Поэтому каждая клетка окрашена иначе, нежели ее соседка.
Ответы и решения
91
Поскольку у каждой клетки 16 соседок, то k ^ 17. Выделим клетку, окрашенную цветом с номером 0, и всех ее соседок (у них номера цветов от 1 до 16), см. рис. 190 (а). Клетка A не может быть окрашена ни в один из цветов с номерами от 1 до 16. Поэтому k ^ 18, а в клетке A цвет номер 17. Предположим, что k = 18, и приведем это предположение к противоречию. В клетках B и C могут стоять только цвета 16 и 17, но неизвестно, в какой из этих клеток цвет 16, а в какой 17. Две соседние клетки, имеющие общую гипотенузу, объединим в четырехугольник с углами 120°, 90°, 60°, 90° (дельтоид). Считаем, что дельтоид окрашен парой цветов. Так, дельтоид D, составленный из клеток B и C, имеет окраску (16, 17) или, в более простых обозначениях, 16+17. На рис. 190 (б) показано разбиение плоскости на дельтоиды. Мы показали (предположив, что k = 18 в условиях задачи), что любые два дельтоида, расположенные также, как дельтоиды D и D' на рис. 190 (б), окрашены одинаково. Следовательно, при окраске дельтоидов использованы только такие пары цветов: 1+2, 3+4, 5+6, 7+8, 9+10, 0+11, 12+13, 14+15, 16+17 (девять вариантов раскраски дельтоидов). Понятно, что любые два различных дельтоида, имеющие хотя бы одну общую точку, окрашены по-разному. Назвав такие дельтоиды соседними, получаем, что любые два соседних дельтоида окрашены по-разному, а у каждого дельтоида все его соседи имеют разную окраску. Поскольку у каждого дельтоида имеется 9 дельтоидов-соседей, то потребуется не менее 10 вариантов окраски дельтоидов. Противоречие. Итак k ^ 19, и пункт а) доказан.
Рис. 190
б) Вариант раскраски в 24 цвета получится, если на рис. 189 (зада-
92
§8. Задачи с раскраской в условии
ча 8.24) каждый дельтоид разделить на два прямоугольных треугольника и покрасить каждый треугольник своим цветом.
Урок 8.5
8.26. Решение. Картинка симметрична относительно оси AB (с заменой красного цвета на черный и наоборот), смотрите рис. 191. Поэтому можно считать центральную клетку красной. Будем предполагать, что одноцветных дорожек, описанных в условии задачи,
