Задачи на разрезание - Екимова М.А.
IS BN 5-94057-051-8
Скачать (прямая ссылка):
7.15. Решение. а) Площадь прямоугольника mn делится на простое число 5, поэтому хотя бы один из сомножителей (m или n) делится на 5. б) Как в пункте а), получим, что m (или n) делится на 3. Если
80
§8. Задачи с раскраской в условии
оно же делится и на 2, то все доказано. Пусть m кратно 3 (но нечетно), n кратно 2. Раскрасим прямоугольник в 6 разных цветов (1-й, 2-й, 3-й, 4-й, 5-й, 6-й, как на рис. 163). Пластинка 1 х 6 заберет по одной клетке каждого цвета. Если n не делится на 3, то клеток шести разных цветов будет не поровну, и покрытие полосками будет невозможно. Аналогичное решение — у задачи 7.8 (в).
1 2 3 4 5 6 1 2 3
2 3 4 5 6 1 2 3 4
3 4 5 6 1 2 3 4 5
1 2 4
3 5 1
2 4 3
10 1 3 5
2 1 4 4
8 1 7 6
9 9 7 11
Рис. 163
Рис. 164
Рис. 165
§8. Задачи с раскраской в условии Урок 8.1
8.1. Решение. В задаче требуется, чтобы для любых двух цветов нашлись клетки этих цветов, имеющие общую сторону. Пусть наибольшее число цветов — n. Тогда число таких пар цветов n ^ 11 . (Первую клетку можно выбрать n способами, а вторую клетку, имеющую с первой общую сторону, уже (n—1) способами, так как один цвет уже занят. Но одну и ту же пару мы посчитали дважды, поэтому число таких пар ——-). Так как отрезков, по которым соседствуют две клетки, всего
12, то n (r?2 1) ^ 12. Подставляя в это неравенство различные значения n, приходим к выводу, что наибольшее такое n, удовлетворяющее неравенству, n = 5. Следовательно, наибольшее число цветов — 5. Пример смотрите на рис. 164.
8.2. Ответ. В одиннадцать цветов, см. рис. 165.
8.3. Ответ. Доску можно раскрасить в 16 цветов. Клеток каждого цвета не меньше четырех, так как среди трех клеток всегда найдется «крайняя» (граничащая не более чем с одной из остальных двух). Поэтому цветов не более 64: 4 = 16. Пример для 16 цветов: раз-
Ответы и решения
81
делим доску на квадраты 2 х 2 клетки и каждый квадрат выкрасим в свой цвет.
8.4. Ответ. Пример см. на рис. 166.
8.5. Ответ. Пример требуемой раскраски — на рис. 167.
0 0 0 0 0
X 0 X 0 X
0 X 0 X X
X 0 X 0 X
0 X 0 X X
Рис. 166 Рис. 167
8.6. Решение. 1) Ясно, что число цветов не меньше четырех. Допустим, что четырех цветов достаточно, и приведем это предположение к противоречию. Цвета в первой строке занумеруем (от 1 до 4 слева направо, см. рис. 168 (а)). Рассмотрим цвет 2. Он не может стоять во втором столбце и в первой и третьей клетке второй строки, а значит во второй строке он может стоять только в четвертой клетке. Проводя аналогичные рассуждения, получаем, что в третьей строке он может стоять только в первой клетке, а в четвертой строке он занимает вторую клетку. Из соображений симметрии можно расставить третий цвет: во второй строке он занимает первую клетку, в третьей — четвертую, а в четвертой — вторую (рис. 168 (а). В клетку А мы не можем поставить четвертый цвет, так как он уже есть на большой диагонали, и понятно, что не можем поставить цвета 1, 2, 3. Значит, четырех цветов недостаточно. Как раскрасить квадрат в 5 цветов показано на рис. 168 (б).
2) Ясно, что число цветов не меньше пяти. Попробуем раскрасить квадрат в 5 цветов. Цвета в первой строке занумеруем (от 1 до 5 слева направо, см. рис. 169 (а)). Рассмотрим цвет 3. Будем отмечать все клетки, в которых он не может стоять. Он не может стоять в третьем столбце, во второй клетке второго и четвертого столбца и в третьей клетке первого и второго столбца. Во второй строке он может занимать первую или пятую клетки. Закрасим цветом 3 первую клетку (рассуждения в случае, когда цветом 3 закрашивается пятая клетка аналогичны). Теперь можем отметить, что цвет 3 не может стоять в
82
§8. Задачи с раскраской в условии
остальных клетках первого столбца, в третьей клетке второго столбца, в пятой клетке четвертого столбца. Значит в третьей строке цвет 3 может занимать только четвертую клетку. Проводя аналогичные рассуждения, получаем, что в четвертой строке цвет 3 стоит во второй клетке, а в пятой строке — в пятой клетке (рис. 169 (а)). Теперь можно расставить цвет 5. В четвертой строке он может стоять только в четвертой клетке. Во второй строке он занимает третью, в третьем столбце — первую, а пятом вторую клетки. Проводя аналогичные рассуждения для всех цветов, мы получаем раскраску, представленную на рис. 169 (б).
1 2 3 4
3 2
2 3
А 3 2
Б)
1 2 3 4 5
1 2 3 4 3 5
4 5 1 2 5 Y
2 3 4 5 Y 5
5 1 2 3 5 3
В)
Б)
1 2 3 4 5
3 4 5 1 2
5 1 2 3 4
2 3 4 5 1
4 5 1 2 3
В)
Рис. 168
Рис. 169
8.7. Ответ. Пример см. на рис. 170.
1 1 4 4 1 1
1 1 4 4 1 1
2 2 3 3 2 2
2 2 3 3 2 2
1 1 4 4 1 1
1 1 4 4 1 1
Рис. 170
Рис. 171
Урок 8.2
8.8. Ответ. См. рис.171.
8.9. Ответ. Лиса не права. На рис. 172 изображены примеры, когда черных клеток 40. Причем в примере, изображенном на
Ответы и решения
83
рис. 172 (б), по две черных соседних клетки не только у черных клеток, но и у белых.
Б)
Рис. 172
8.10. Ответ. Возможный чертеж Ромы смотрите на рис. 173 (а), возможный чертеж Семы — на рис. 173 (б) (могут быть и другие чертежи), а чертеж Томы — на рис. 173 (в).
