Нарисуем на бумаге в клетку квадрат NxN.
Закрасим на на нём несколько стартовых клеток некоторым образом.
После этого будем последовательно закрашивать клетки, следуя простому правилу:
клетку можно закрасить, если у неё не менее 2-х (из 4-х) соседей уже закрашено.
Каково минимальное число стартовых клеток, при котором можно закрасить весь квадрат?
Здравствуйте, Pushkin, Вы писали:
P>Нарисуем на бумаге в клетку квадрат NxN. P>Закрасим на на нём несколько стартовых клеток некоторым образом. P>После этого будем последовательно закрашивать клетки, следуя простому правилу: P>клетку можно закрасить, если у неё не менее 2-х (из 4-х) соседей уже закрашено. P>Каково минимальное число стартовых клеток, при котором можно закрасить весь квадрат?
Если у клетки соседями считаются только клетки по горизонтали(вертикали), то потребуется N клеток при расположении как указано ниже (O — "чистая" клетка, N — закрашенная)
Здравствуйте, Pushkin, Вы писали:
P>Нарисуем на бумаге в клетку квадрат NxN. P>Закрасим на на нём несколько стартовых клеток некоторым образом. P>После этого будем последовательно закрашивать клетки, следуя простому правилу: P>клетку можно закрасить, если у неё не менее 2-х (из 4-х) соседей уже закрашено. P>Каково минимальное число стартовых клеток, при котором можно закрасить весь квадрат?
А разве у клетки не 8 соседей?
И что значит последовательно? По одной слева-направо сверху-вниз?
Здравствуйте, Pushkin, Вы писали:
P>Нарисуем на бумаге в клетку квадрат NxN. P>Закрасим на на нём несколько стартовых клеток некоторым образом. P>После этого будем последовательно закрашивать клетки, следуя простому правилу: P>клетку можно закрасить, если у неё не менее 2-х (из 4-х) соседей уже закрашено. P>Каково минимальное число стартовых клеток, при котором можно закрасить весь квадрат?
Нанесём предварительно на квадрат шахматную закраску.
Очевидно, что по правилу, клетка закрашивается, если соседи стоят на клетках противоположного (фонового) цвета.
Такми образом, число стартовых клеток
N ^ 2 / 2 для четных N,
(N ^ 2 - 1) / 2 для нечётных N (выбираем меньшее множество).
Здравствуйте, Pushkin, Вы писали:
P>Здравствуйте, LantY, Вы писали:
LY>>OOOON LY>>OOONO LY>>OONOO LY>>ONOOO LY>>NOOOO
P>Замечательное доказательство достаточности N клеток. P>Докажешь необходимость, и приз твой.
А по индукции? Для 1*1 очевидно. Если расмотреть N*N, который уже "расскрашен" и добавить один столбец и одну строку, т.е. перейти к (N+1)*(N+1), то очевижно, что хотябы одна клетка в строке и одна в столбце должны быть закрашены. Оптимально сделать это на пересечении строки и столбца. Вот и ограничили снизу
Здравствуйте, Pushkin, Вы писали: P>Замечательное доказательство достаточности N клеток. P>Докажешь необходимость, и приз твой.
Не докажу, формулировать ломает
P>О чём ты говоришь? Всё только начинается! P>Самое-то главное это доказать, что нельзя обойтись меньшим чем N числом! P>(А ты, кстати, в этом уверен? )
Практически.
Возьмем квадрат 2*2 (с 1*1 понятно)
ОО
ОО
очевидно,необходимо и достаточно закрасить
так ХО или так ОХ
ОХ ХО
что дает
ХХ
ХХ
оба варианта равноценны.
Будем рассматривать первый.
ООО ХОО ХХО
ООО => ОХО =>ХХО =>
ООО ООО ООО
очевидно, для полной закраски нужно сделать так
ХХО
ХХО
ООХ
что дает
ХХХ
ХХХ
ХХХ
Далее
Любой квадрат можно представить так
ABCD.X
BBCD.X
CCCD.X
DDDD.X
.....X
XXXXXX
каждый следующий слой добавляющий к предыдущему квадрату длину-ширину можно заполнить
закрашивая правую нижнюю диагональную клетку. Это будет и достаточно и необходимо.
Таким образом можно закрасить произвольный квадрат,
добавляя на каждый новый слой 1 закрашенную клутку по диагонали.
На каждом шаге это было достаточно и необходимо, значит для закраски произвольного квадрата
достаточно и необходимо закрасить его диагональ.
q.e.d.
Здравствуйте, Alik, Вы писали:
P>>Замечательное доказательство достаточности N клеток. P>>Докажешь необходимость, и приз твой.
A>А по индукции? Для 1*1 очевидно. Если расмотреть N*N, который уже "расскрашен" и добавить один столбец и одну строку, т.е. перейти к (N+1)*(N+1), то очевижно, что хотябы одна клетка в строке и одна в столбце должны быть закрашены. Оптимально сделать это на пересечении строки и столбца. Вот и ограничили снизу
Уточнение.
1) Закрашиваемые клетки не могут выйти за рамки минимального прямоугольника, охватывающего все стартовые.
2) Если внутри этого минимального прямоугольника есть строки/столбцы, на которых не стоит хотя бы одна стартовая,
то эта строка/столбец так же не закрашивается.
Следовательно, необходимое условие:
для закрашивания всего квадрата, необходимо, чтобы в каждой строке и столбце находилась, как минимум, одна стартовая.
Здравствуйте, Pushkin, Вы писали:
P>Нарисуем на бумаге в клетку квадрат NxN. P>Закрасим на на нём несколько стартовых клеток некоторым образом. P>После этого будем последовательно закрашивать клетки, следуя простому правилу: P>клетку можно закрасить, если у неё не менее 2-х (из 4-х) соседей уже закрашено. P>Каково минимальное число стартовых клеток, при котором можно закрасить весь квадрат?
Встречная задачка
Всё то же самое, только клетку можно закрасить, если у неё не менее 3-х (из 8-х) соседей уже закрашено.
Каково минимальное число стартовых клеток, при котором можно закрасить весь квадрат?
Здравствуйте, mrhru, Вы писали:
M>1) Закрашиваемые клетки не могут выйти за рамки минимального прямоугольника, охватывающего все стартовые. M>2) Если внутри этого минимального прямоугольника есть строки/столбцы, на которых не стоит хотя бы одна стартовая,
M>Следовательно, необходимое условие: M>для закрашивания всего квадрата, необходимо, чтобы в каждой строке и столбце находилась, как минимум, одна стартовая.
Вот такое расположение позволяет закрасить весь квадрат, хотя содержит столбец и строку без закрашенных клеток.
Здравствуйте, Chorkov, Вы писали:
M>>Следовательно, необходимое условие: M>>для закрашивания всего квадрата, необходимо, чтобы в каждой строке и столбце находилась, как минимум, одна стартовая.
C>Вот такое расположение позволяет закрасить весь квадрат, хотя содержит столбец и строку без закрашенных клеток. C>
Здравствуйте, UgN, Вы писали:
UgN>Здравствуйте, mrhru, Вы писали:
C>>>Вот такое расположение позволяет закрасить весь квадрат, хотя содержит столбец и строку без закрашенных клеток. C>>>
C>>>X0X0
C>>>0000
C>>>X000
C>>>000X
C>>>
M>>Тогда всё гораздо запутанней.
UgN>Количество остается тем же. UgN>А вот такое
доказательство не катит?
M>Да почти удовлетворительно. M>Если бы не найденное решение Chorkov'а. M>Вот такое расположение закрашивает весь квадрат 3х3, но без опоры на 2х2. M>
M>XoX
M>ooo
M>oXo
M>
Да, но нужно доказательство применимости такого расположения для произвольного квадрата.
Например:
ОООО ООООО
ОООО ООООО
ОООО ООООО
ОООО ООООО
ООООО
Pushkin куда-то смылся, а я хочу узнать самое правильное и красивое решение!
M>В частности, прамоугольник 3х5 закрашивается 4 (!!!) стартовыми M>
)
