Шахматная доска 9x9

[Xenia1996]

(Всем-всем пламенный привет и с прошедшими праздниками!!! Я вернулась)

Эту задачу я придумала и решила сама только что (но (определённо) не ручаюсь за то, что не навеяло некой олимпиадой).

Представьте себе шахматную доску 9x9, все клетки которой - белые.
Представили?
А теперь извольте сосчитать, какое наибольшее количество клеток можно перекрасить в зелёный цвет (чёрный не люблю) так, чтобы независимо от того, какие именно клетки перекрашены, обязательно нашёлся прямоугольник 1x4 (и не важно, вертикальный или горизонтальный), совершенно свободный от зелёных клеток.

Удачи в решении!

[caxap]

(Скромная попытка)

19?

[Xenia1996]

caxap в сообщении #397752 писал(а):

(Скромная попытка)

19?

(:oops: Разоблачили)

А пример с 20-ю такими, что нет прямоугольника 1x4, сами сможете привести, или Вам помочь?

[caxap]

Xenia1996 в сообщении #397759 писал(а):

А пример с 20-ю такими, что нет прямоугольника 1x4, сами сможете привести, или Вам помочь?

[venco]

Попробуйте посчитать количество таких конфигураций.

(мой ответ)

18

[Xenia1996]

caxap в сообщении #397768 писал(а):

Xenia1996 в сообщении #397759 писал(а):

А пример с 20-ю такими, что нет прямоугольника 1x4, сами сможете привести, или Вам помочь?

Подобрали?
Или идею уловили?

Моя идея была такова (словно лисица во всем известной басне):
Пронумеруем клетки следующим образом: первая строка - от 1 до 9 слева направо, вторая строка - от 10 до 18 справа налево, третья - от 19 до 27 опять слева направо... (иными словами, обобщение шахматной раскраски на $n=4$).
Перекрасим в зелёный все клетки, номера которых при делении на 4 не дарамдаш натуральный остаток.
В этом случае, если прямоугольник горизонтальный, то ровно одна его клетка будет зелёной, если же вертикальный (9 дарамдаш остаток 1 при делении на 8, ибо является квадратом нечётного числа) - тоже!

Если же перекрасить лишь 19 клеток, то...
Разобьём всю доску на 20 непересекающихся прямоугольников 1x4 *(это влёгкую делается: первые 8 клеток каждой из строк - это два таких прямоугольника, а верхние 8 клеток самого правого столбца - тоже).
В одном из этих прямоугольников не будет ни одной зелёной клетки.

-- Пн янв 10, 2011 19:54:53 --

venco в сообщении #397777 писал(а):

Попробуйте посчитать количество таких конфигураций.

Каких именно?
С ровно двадцатью перекрашенными клетками?

-- Пн янв 10, 2011 19:56:19 --

venco в сообщении #397777 писал(а):

(мой ответ)

18

(Не-а! )

-- Пн янв 10, 2011 20:13:39 --

venco в сообщении #397777 писал(а):

Попробуйте посчитать количество таких конфигураций.

(мой ответ)

18

Ах, простите!
Это Вы о количестве конфигураций сказали "18", а я и не въехала с нулевой попытки. Тут подумать надо (предпочтительнее, нежели на компе перебирать). Я с дороги устала, мозг не успела включить.

[caxap]

venco в сообщении #397777 писал(а):

18

Я тоже больше 18 найти не могу. Изгибания всякие не помогают.