Задачи на разрезание - Екимова М.А.
IS BN 5-94057-051-8
Скачать (прямая ссылка):
В)
Б) В) Ч)
Рис. 173
Рис. 174
Рис. 175
8.11. Ответ. См. рис. 174.
84
§8. Задачи с раскраской в условии
8.12. Ответ. См. рис. 175.
Урок 8.3
8.13. Ответ. а) 2; б) 2; в) 3 — см. на рис. 176.
Рис. 176 Рис. 177
8.14. Ответ. Лиса Алиса не права. Раскраску см. на рис. 177.
8.15. Решение. Цветов не меньше четырех, так как у клетки четыре соседа, сама же клетка может быть такого же цвета, как какая-нибудь из ее соседей. Пример с четырьмя цветами изображен на рис. 178.
8.16. Ответ. См. рис. 179.
Рис. 179
Рис. 180
Ответы и решения
85
8.17. Ответ. Наименьшее число цветов 3. Пример раскраски на
рис. 180.
8.18. Ответ. Потребуется 3 цвета. Пример раскраски смотрите на рис. 181.
8.19. Решение. Поскольку у каждой клетки 6 соседок, то цветов не менее шести. Однако, если бы две клетки, соседствующие по стороне, были бы одного цвета, то у них нашлась бы общая соседка, а значит у нее эти две соседки были бы одного цвета. Поэтому цветов не менее семи. На рис. 182 указана раскраска, где всего семь цветов.
Рис. 182
86
§8. Задачи с раскраской в условии
Урок 8.4
8.20. Решение. Легко видеть, что в каждой вершине треугольника сходятся 6 треугольников, поэтому использовано не менее 6 цветов. При этом 6 цветов достаточно. Выделим полоску из треугольников (верхняя полоска на рис. 183). Номера цветов на этой полоске: 1, 2, 3, 4, 5, 6 (а затем этот набор повторяется еще раз). Следующая полоска (ниже) раскрашена точно так же, но со сдвигом. В результате под 1 стоит 4, под 2 стоит 5, под 3 стоит 6, и т. д. Таким образом можно окрасить все клетки, используя 6 цветов.
Рис. 183
1/\3/\5/\l/\3/\5/, у/2 VV 4 YV 6 \/2\/4 у 6 1 2 3 1 2
ЛбЛіЛзЛбЛіЛз 4Y6Y2V4Y6Y2Y 4 5 6 4 5
іЛзЛ.бЛіЛзЛб/' 72у4убу 2Y4X /6 7 8 9 7 8
\s Al Лз/\5/\1/\3 Y6Y2YY6Y2Y 1 2 3 1 2
І/ХзЛбЛіЛзЛб/* v/2\/4\/6\/2\/4\/б 4 5 6 4 5
Рис. 184
8.21. Решение. Потребуется 9 цветов. У любых двух клеток-соседок есть общая соседка. Поэтому две соседних клетки — разного цвета. У каждой клетки 8 соседок. Поэтому потребуется не менее 9 цветов. Раскраску в 9 цветов см. на рис. 184.
Рис. 185
8.22. Решение. У любых двух клеток-соседок есть общая соседка. Поэтому каждая клетка окрашена иначе, нежели ее соседка. По-
Ответы и решения
87
скольку у каждой клетки 14 соседок, то требуется не менее 15 цветов. Объясним, почему 15 цветов не хватит. Выделим квадрат из 18 клеток (16 неокрашенных и 2 заштрихованных, см. рис. 185 (а)). Допустим, что возможна окраска в 15 цветов, удовлетворяющая условиям задачи. Тогда какие-то две клетки из 16 неокрашенных имеют один и тот же цвет. Легко проверить, что это могут быть только клетки, помеченные точкой. Вместо раскраски нумеруем клетки числами 0, 1, 2 и т. д. (рис. 185 (б)). Проверяем, что в заштрихованную клетку ни один номер от 0 до 14 поставить нельзя. Поэтому требуется не менее 16 цветов. Пример, когда раскраска в 16 цветов удовлетворяет условиям задачи — на рис. 185 (в).
8.23. Ответ. Потребуется 14 цветов. Вначале докажем, что искомое число k ^ 14, а потом приведем пример раскраски в 14 цветов при выполнении условий задачи.
У каждой клетки 12 соседок, так что k ^ 12. Любые две соседних клетки имеют общую соседку, поэтому любая клетка окрашена не так, как ее соседка. Поэтому k ^ 13.
Приведем к противоречию предположение, что k = 13. Пусть (см. рис. 186 (а)) какая-то клетка окрашена цветом 0, а ее соседки — цветами от 1 до 12. Эти 13 клеток составляют центральный шестиугольник (ЦШ), а 24 клетки, каждая из которых не лежит в ЦШ, но имеет с ним хотя бы одну общую вершину, составляет пояс (П). Клетки пояса, где может быть цвет 1, обозначены буквой Е (таких клеток 5). Какие-либо две клетки пояса окрашены одним и тем же цветом. Если это цвет 1, то среди клеток с меткой Е двум клеткам цвета 1 нет места. Поэтому в клетках пояса цвет 1 (и каждый из цветов 1, 5, 9) встречается не более одного раза. Обозначим буквой C те клетки пояса, которые могут быть окрашены цветом 4. Таких клеток 10. Если даже цвет 4 занимает две крайние клетки с меткой C, то для третьей клетки цвета 4 на поясе нет места. Поэтому в клетках пояса цвет 4 (и каждый из цветов 2, 4, 6, 8, 10, 12) встречается не более двух раз. Поэтому на долю цветов 3, 7, 11 приходится не менее девяти клеток пояса, то есть какой-то из этих цветов встречается в клетках пояса не менее трех раз. Пусть это цвет 3. Обозначим буквой Т те клетки пояса, где может быть цвет 3. Таких клеток 13. Понятно, что для четырех клеток цвета 3 на поясе нет места. Поэтому цвет 3 в клетках пояса встречается ровно три
88
§8. Задачи с раскраской в условии
раза.
Каждый из цветов 3, 7, 11 встречается в клетках пояса ровно три раза, каждый из цветов 2, 4, 6, 8, 10, 12 — ровно два раза, каждый из цветов 1, 5, 9 — ровно один раз.
Итак, ровно три клетки пояса окрашены цветом 3. Тогда это одна из клеток с меткой * и одна из клеток с меткой #, а также непременно клетка Х.
Выделим участок рисунка с клетками 3 и Х (рис. 186 (б)). Любую пару клеток плоскости, расположенных так же, можно накрыть рисунком, аналогичным рис. 186 (а). Таким образом, любые две клетки с таким взаимным расположением окрашены одинаково.
