Помощь - Поиск - Пользователи - Календарь
Полная версия: Покрашенная доска
Портал Естественных Наук. Форум. > Математика > Школьная математика
Xenia1996
Некоторые клетки доски 9\times 9 покрасили в чёрный цвет, остальные - в белый.
Каждый прямоугольник 2\times 3 и каждый прямоугольник 3\times 2 содержит ровно 2 чёрные клетки.
Сколько может быть всего чёрных клеток? Сколько решений имеет задача?
malk
27 и 6?
Xenia1996
Цитата(malk @ 27.4.2011, 0:34) *

27 и 6?

Я так понимаю, что под словом "шесть" Вы имели в виду число способов раскраски 27 клеток соответствующим образом. Вот как раз это я и не смогла доказать. Зато доказала, что задача имеет ровно одно решение: 27 клеток.

Разобьём доску на прямоугольники следующим образом:

1. a1, b1, c1
2. a2, b2, c2, a3, b3, c3
3. a4, b4, c4, a5, b5, c5
4. a6, b6, c6, a7, b7, c7
5. a8, b8, c8, a9, b9, c9
6. d1, e1, d2, e2, d3, e3
7. d4, e4, d5, e5, d6, e6
8. d7, e7, d8, e8, d9, e9
9. f1, g1, f2, g2, f3, g3
10. f4, g4, f5, g5, f6, g6
11. f7, g7, f8, g8, f9, g9
12. h1, i1, h2, i2, h3, i3
13. h4, i4, h5, i5, h6, i6
14. h7, i7, h8, i8, h9, i9

Итак, мы имеем 13 прямоугольников нужных нам размеров и ещё один маленький.
B 13 должно быть ровно 26 клеток по условию, значит, всего может быть 26, 27, 28 или 29.

29 отметаем сразу же, ибо тогда в прямоугольнике a1, a2, a3, b1, b2, b3 будет больше двух клеток.

Теперь пусть клеток ровно 26. Разобьём всю доску на квадратики 3\times 3. Хотя бы в одном из квадратиков должно быть менее трёх клеток. Ровно одна клетка, очевидно, быть не может. Значит их ровно две. B верхней строчке квадратика не может быть чёрной клетки, ибо тогда в прямоугольнике, образованном двумя другими строчками будет ровно одна клетка, a их должно быть две. Аналогично, чёрной клетки не может быть в нижней строчке, a также в левом и правом столбцах. Значит, чёрная клетка может быть лишь в центре. Ho тогда она одна, a не две! Противоречие.
Итак, 26 мы тоже отметаем.

Отметём и 28.
Если клеток 28, то в какм-то квадратике 3\times 3 будет 4 клетки. Ho тогда в соседнем c ним квадратике должно быть ровно две (a мы уже доказали, что это невозможно)! Почему? Да потому, что два таких квадратика образуют три прямоугольника 3\times 2, значит, всего в них должно быть 6 клеток.

Итак, можно только 27.

Пример:

c1, f1, i1, b2, e2, h2, a3, d3, g3,
c4, f4, i4, b5, e5, h5, a6, d6, g6,
c7, f7, i7, b8, e8, h8, a9, d9, g9.

Ho вот как доказать, что более шести способов раскрасить 27 клеток не существует, я, к стожалению, не знаю :wall:


malk
1. Разобьем квадрат на 9 квадратиков 3*3. Если не использовать любой из этих квадратиков, большой квадрат можно замостить 12 прямоугольниками. Если взять 9 таких квадратов c вырезами, то все клетки большого квадрата будут использоваться 8 раз. Итого 12*2*9/8=27.
2. Рассмотрим маленький квадратик 3*3. B нем не менее 3 черных клеток. Если в каком-нибудь квадратике больше 3, то и в большом квадрате больше 27. Значит в квадратике ровно 3 черных клетки.
Значит в прямоугольниках 1*3 и 3*1 ровно одна такая клетка. Следовательно вариантов расстановки в квадратике 6. Дальше несложно(если, конечно, я не ошибаюсь).
F(x)
что-то я не очень понял предложенные решения, поэтому приведу свое

итак

1. Никакие две смежные по вертикали/горизонтали клетки не могут быть одновременно черными.
Доказательство
пусть это так тогда получается:
Нажмите для просмотра прикрепленного файла\toНажмите для просмотра прикрепленного файла\toНажмите для просмотра прикрепленного файла
(зеленым обозначены клетки которые закрашиваем в черный, желтым -- в белый, белым обозначены неопределенные клетки)

2. Теперь выберем некоторый прямоугольник 2x3 (или 3x2) у которого есть черная угловая клетка, например такой:
Нажмите для просмотра прикрепленного файла
и попытаемся произвести дальнейшую закраску:
Нажмите для просмотра прикрепленного файла\toНажмите для просмотра прикрепленного файла\toНажмите для просмотра прикрепленного файла\toНажмите для просмотра прикрепленного файла\toНажмите для просмотра прикрепленного файла\toНажмите для просмотра прикрепленного файла\toНажмите для просмотра прикрепленного файла
обратите внимание что на каждом шаге клетки для закрашивания определяются однозначно (кроме 3-го где можно было выбрать 1 из 2-х диагоналей)
И похоже вырисовывается система: черные клетки образуют диагонали так, что каждые две соседние черные диагонали разделяются 2-мя белыми (кроме крайних)
Получается что если гипотеза верна, то черных и вправду ровно 27 при этом способ раскраски только 1 (если не считать повороты и отражения)
F(x)
P.S. немного соврал: основных способов закраски 2: когда главная диагональ доски черная и нет
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.
Русская версия Invision Power Board © 2001-2014 Invision Power Services, Inc.