Здравствуйте, Pushkin, Вы писали:
P>Ну а теперь на сцену выходит другое решение...
Это может показаться трюком, но на самом деле абсолютно стандартное решение. Во всех задачах такого рода надо прежде всего попытаться увидеть, какая величина не меняется при разовом действии.
В данном случае, так как мы пристыковываем новую клетку не менее чем к двум границам, ясно, что периметр закрашенной области при этом не растёт. Таким образом мы не можем закрасить область периметра P с помощью менее чем P/4 клеток.
В частности для прямоугольника со сторонами A и B потребуется не менее (A+B)/2 стартовых клеток. То, что их достаточно (с округлением вверх) проверяется в лоб.
У меня есть ощущение, что и для любой области ceil(P/4) будет достаточно. Но я не уверен. По крайней мере не могу доказать.
Нарисуем на бумаге в клетку квадрат NxN.
Закрасим на на нём несколько стартовых клеток некоторым образом.
После этого будем последовательно закрашивать клетки, следуя простому правилу:
клетку можно закрасить, если у неё не менее 2-х (из 4-х) соседей уже закрашено.
Каково минимальное число стартовых клеток, при котором можно закрасить весь квадрат?
Здравствуйте, Alik, Вы писали:
P>>Замечательное доказательство достаточности N клеток. P>>Докажешь необходимость, и приз твой.
A>А по индукции? Для 1*1 очевидно. Если расмотреть N*N, который уже "расскрашен" и добавить один столбец и одну строку, т.е. перейти к (N+1)*(N+1), то очевижно, что хотябы одна клетка в строке и одна в столбце должны быть закрашены. Оптимально сделать это на пересечении строки и столбца. Вот и ограничили снизу
Уточнение.
1) Закрашиваемые клетки не могут выйти за рамки минимального прямоугольника, охватывающего все стартовые.
2) Если внутри этого минимального прямоугольника есть строки/столбцы, на которых не стоит хотя бы одна стартовая,
то эта строка/столбец так же не закрашивается.
Следовательно, необходимое условие:
для закрашивания всего квадрата, необходимо, чтобы в каждой строке и столбце находилась, как минимум, одна стартовая.
Здравствуйте, mrhru, Вы писали:
M>1) Закрашиваемые клетки не могут выйти за рамки минимального прямоугольника, охватывающего все стартовые. M>2) Если внутри этого минимального прямоугольника есть строки/столбцы, на которых не стоит хотя бы одна стартовая,
M>Следовательно, необходимое условие: M>для закрашивания всего квадрата, необходимо, чтобы в каждой строке и столбце находилась, как минимум, одна стартовая.
Вот такое расположение позволяет закрасить весь квадрат, хотя содержит столбец и строку без закрашенных клеток.
Здравствуйте, Pushkin, Вы писали:
P>Нарисуем на бумаге в клетку квадрат NxN. P>Закрасим на на нём несколько стартовых клеток некоторым образом. P>После этого будем последовательно закрашивать клетки, следуя простому правилу: P>клетку можно закрасить, если у неё не менее 2-х (из 4-х) соседей уже закрашено. P>Каково минимальное число стартовых клеток, при котором можно закрасить весь квадрат?
Если у клетки соседями считаются только клетки по горизонтали(вертикали), то потребуется N клеток при расположении как указано ниже (O — "чистая" клетка, N — закрашенная)
Здравствуйте, Pushkin, Вы писали:
P>Завтра скажу, время сбора 9-00 по москве P>Вот прикол будет, если оно неправильное
Пока вы все ещё дрыхнете, воспользуюсь своим географическим положением.
1) Закрашиваемые клетки не могут выйти за рамки минимального прямоугольника,
охватывающего все стартовые клетки.
(Это очевидно из алгоритма закраски)
2) Пусть у нас уже закрашен прямоугольник размера X * Y.
ххххх
ххххх
ххххх
Тогда, с помощью ещё одной стартовой клетки, мы можем увеличить площадь закраски двумя способами:
2.1) Разместив стартовую клетку напротив одной из сторон
ххххх
ххххх С
ххххх
или
ххххх
ххххх
ххххх
С
Располагать вплотную к прямоугольнику — не выгодно, а помещать дальше — бесполезно.
При этом мы получим закрашенный прямоугольник размера (X + 2) * Y или X * (Y + 2)
2.2) Разместив стартовую клетку возле одного из углов
ххххх
ххххх
ххххх
С
Закрашенный прямоугольник будет размером (X + 1) * (Y + 1)
3) Повторяя 2.1 или 2.2, мы сможем с помощью двух стартовых клеток увеличить площадь до
(X + 2) * (Y + 2).
ХХХХХxx
ХХХХХxС
ХХХХХxx
xxxxxxx
xxСxxxx
или
ХХХХХxx
ХХХХХxx
ХХХХХxx
xxxxxСx
xxxxxxС
4) Максимальная площадь, которая может быть закрашена с помощью одной стартовой — это
квадрат 1 * 1.
4.1) Для закраски квадрата N * N, где N — нечётное, нам понадобятся
(N - 1)/2 клеток на каждую сторону, плюс ещё одна начальная
(N - 1)/2 + (N - 1)/2 + 1 = N
4.2) Для закраски квадрата N * N, где N — чётное, мы должны начинать с квадрата 2 * 2, для
закраски которого нужны две стартовые клетки.
Итого
(N - 2)/2 клеток на каждую сторону, плюс ещё две начальных
(N - 2)/2 + (N - 2)/2 + 2 = N
Здравствуйте, Pushkin, Вы писали:
P>У меня есть ощущение, что и для любой области ceil(P/4) будет достаточно. Но я не уверен. По крайней мере не могу доказать.
P>О чём ты говоришь? Всё только начинается! P>Самое-то главное это доказать, что нельзя обойтись меньшим чем N числом! P>(А ты, кстати, в этом уверен? )
Практически.
Возьмем квадрат 2*2 (с 1*1 понятно)
ОО
ОО
очевидно,необходимо и достаточно закрасить
так ХО или так ОХ
ОХ ХО
что дает
ХХ
ХХ
оба варианта равноценны.
Будем рассматривать первый.
ООО ХОО ХХО
ООО => ОХО =>ХХО =>
ООО ООО ООО
очевидно, для полной закраски нужно сделать так
ХХО
ХХО
ООХ
что дает
ХХХ
ХХХ
ХХХ
Далее
Любой квадрат можно представить так
ABCD.X
BBCD.X
CCCD.X
DDDD.X
.....X
XXXXXX
каждый следующий слой добавляющий к предыдущему квадрату длину-ширину можно заполнить
закрашивая правую нижнюю диагональную клетку. Это будет и достаточно и необходимо.
Таким образом можно закрасить произвольный квадрат,
добавляя на каждый новый слой 1 закрашенную клутку по диагонали.
На каждом шаге это было достаточно и необходимо, значит для закраски произвольного квадрата
достаточно и необходимо закрасить его диагональ.
q.e.d.
Здравствуйте, 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>Докажешь необходимость, и приз твой.
Не докажу, формулировать ломает
Здравствуйте, Pushkin, Вы писали:
P>Нарисуем на бумаге в клетку квадрат NxN. P>Закрасим на на нём несколько стартовых клеток некоторым образом. P>После этого будем последовательно закрашивать клетки, следуя простому правилу: P>клетку можно закрасить, если у неё не менее 2-х (из 4-х) соседей уже закрашено. P>Каково минимальное число стартовых клеток, при котором можно закрасить весь квадрат?
Встречная задачка
Всё то же самое, только клетку можно закрасить, если у неё не менее 3-х (из 8-х) соседей уже закрашено.
Каково минимальное число стартовых клеток, при котором можно закрасить весь квадрат?
Здравствуйте, 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>
С помощью N закрашеных квадратов при данных условиях можно закрасить максимум N^2 => S(квадрата)^-2 округлённое в большую сторону м есть искомый ответ, но вот формализовать предпосылку о N^2
Здравствуйте, mrhru, Вы писали:
M>Пока вы все ещё дрыхнете, воспользуюсь своим географическим положением.
Непорядочный человек
M>3) Повторяя 2.1 или 2.2, мы сможем с помощью двух стартовых клеток увеличить площадь до M>(X + 2) * (Y + 2).
А если через раз 2.1 и 2.2? Получим (X+3)*(Y+1).
И что из этого следует? А фиг его знает — твоё же решение,
ты и должен был рассматривать все случаи.
Короче вот, как я могу пересказать твоё решение, чтобы оно меня устроило (но чур через чёрточку потом ники писать в ссылках )
1) Если закрашен некий прямоугольник, без дополнительной стартовой точки его очевидно нельзя расширить.
2) Стартовая точка может помочь только в 3-х случаях: а) она пристыкована к стороне б) она отстоит от стороны через одну в)она пристыкована к углу.
3) Во всех случаях эта стартовая точка добавит к прямоугольнику либо ряд, либо столбец, либо два ряда, либо два столбца, либо ряд и столбец. Т.е. сумма рядов и столбцов закрашенного прямоугольника вырастет не более чем на 2.
4) Изначально сумма равнялась нулю. Чтобы получить итоговую сумму A+B надо не менее (A+B)/2 стартовых клеток, (округлять, если потребуется, в большую сторону.)
5) Для полноты нужна ещё достаточность. Но она тривиальна — стартовые клетки через одну по периметру (предложено например здесь
Здравствуйте, MichaelP, Вы писали:
MP>Здравствуйте, Pushkin, Вы писали:
P>>У меня есть ощущение, что и для любой области ceil(P/4) будет достаточно. Но я не уверен. По крайней мере не могу доказать.
MP> MP>Опровержение: MP>
MP> X
MP>XXX
MP> XXX
MP> X
MP>
Да, одной не хватает
Ну найди сам границу достаточности, если такой умный
A>А по индукции? Для 1*1 очевидно. Если расмотреть N*N, который уже "расскрашен" и добавить один столбец и одну строку, т.е. перейти к (N+1)*(N+1), то очевижно, что хотябы одна клетка в строке и одна в столбце должны быть закрашены. Оптимально сделать это на пересечении строки и столбца. Вот и ограничили снизу
Не совсем так. Общее правило такое: Для того, чтобы закрасить прямоугольник N*M нужно не менее (N+M)/2 зерен(округление вверх). Этого же кол-ва достаточно. Засеиваем из угла по диагонали, потом вдоль края через одну.
X00000000
0X0000000
00X0X0X0X
Для того, чтобы ряд нужно закрасить (будем говорить "контролировать") нужно, чтобы в нем была закрашена (не обязательно первоначально) клетка или закрашены (тоже н обязательно сразу) две клетки в соседних рядах друг напротив друга. Вот так
00000X00000
00000000000
00000X00000
Далее доказательство в общем понятно. Но я пока не знаю, как изложить его иначе как долго и нудно с рассмотрение случаев.