Здравствуйте, Pushkin, Вы писали:
P>Нарисуем на бумаге в клетку квадрат NxN. P>Закрасим на на нём несколько стартовых клеток некоторым образом. P>После этого будем последовательно закрашивать клетки, следуя простому правилу: P>клетку можно закрасить, если у неё не менее 2-х (из 4-х) соседей уже закрашено. P>Каково минимальное число стартовых клеток, при котором можно закрасить весь квадрат?
Если у клетки соседями считаются только клетки по горизонтали(вертикали), то потребуется N клеток при расположении как указано ниже (O — "чистая" клетка, N — закрашенная)