Отмеченные клетки

[Ktina]

В квадрате $n\times n$ отмечено $n$ клеток.
При каких $n\geqslant 3$ внутри квадрата всегда можно по клеточкам выделить прямоугольник $2\times 3$ без отмеченных клеток?

[slavav]

(Оффтоп)

При $n \le 6$ есть примеры при которых нельзя поместить "кирпич" (прямоугольник $2 \times 3$).
Для $7 \le n \le 11$ приводится специальные замощения кирпичами, число кирпичей больше $n$.
Для $12 \le n$ приводится регулярное замощение кирпичами, число кирпичей больше $n$.

[dimkadimon]

Предлагаю контер задачу. Какой наибольший (по площади) незакрашенный прямоугольник всегда можно найти для каждого n?

[kotenok gav]

Ну, пока то, что в уме:
1 - 1.
2 - 1.
3 - 2.
4 - 4.

[slavav]

kotenok gav в сообщении #1393315 писал(а):

1 - 1.

В этом случае единственная клетка закрашена.

-- 16.05.2019, 11:23 --

5 - 4.

-- 16.05.2019, 11:32 --

6 - 6.

[kotenok gav]

slavav в сообщении #1393318 писал(а):

В этом случае единственная клетка закрашена.

А, ой, да.

-- 16 май 2019, 19:54 --

Я вот что понял.
Мы не ищем конкретный прямоугольник, везде встречающийся (при фикс. n), с наибольшей площадью.
А мы ищем прямоугольник с конкретной наибольшей площадью в каждом случае (при фикс. n).
Т.е. в первом случае ответ для $n=6$ не 6, а во втором - 6.

-- 16 май 2019, 19:56 --

Первый случай, очевидно, будет сложнее второго.

[dimkadimon]

kotenok gav в сообщении #1393315 писал(а):

4 - 4.

Для n=4 ответ 3:

#...
..#.
.#..
...#

-- 16.05.2019, 18:19 --

slavav в сообщении #1393318 писал(а):

5 - 4.

-- 16.05.2019, 11:32 --

6 - 6.

Это верно. Для n=7 я нашел 6.

[kotenok gav]

dimkadimon в сообщении #1393342 писал(а):

#...
..#.
.#..
...#

О, да, не заметил...

-- 16 май 2019, 20:41 --

dimkadimon, все же, какой случай мы решаем?

[dimkadimon]

Предлагаю решать все n <= 25.

[waxtep]

slavav в сообщении #1380768 писал(а):

Для $12 \le n$ приводится регулярное замощение кирпичами, число кирпичей больше $n$

Можно еще рассматривать неперекрывающиеся полосы $3\times n$, в каждой должно быть не менее $\lfloor n/2\rfloor$ закрашенных клеток; тогда для $n=3k+r,k\geqslant3,0\leqslant r\leqslant2$ общее число закрашенных клеток $p\geqslant k\cdot\left\lfloor\frac{3k+r}2\right\rfloor\geqslant4k>n$. Для $n=8$ аналогично получается $p\geqslant4+4+2=10$, а для $n=7$ строится специальное разбиение на восемь кирпичей, не включающее центральную клетку

[kotenok gav]

dimkadimon в сообщении #1393363 писал(а):

Предлагаю решать все n <= 25.

А для них оба случая решать?

[dimkadimon]

kotenok gav в сообщении #1393581 писал(а):

А для них оба случая решать?

второй - мы ищем прямоугольник с конкретной наибольшей площадью в каждом случае.

[kotenok gav]

Сильное ощущение, что тогда ответ будет $n-1$... Но 6 - 6 в это не вписывается. Может, все же удастся подобрать пример с несуществованием 6?

[waxtep]

kotenok gav в сообщении #1393685 писал(а):

Сильное ощущение, что тогда ответ будет $n-1$.

Вряд ли, при больших $n$ должно быть $\propto n^{3/2}$ (мне так кажется; если равномерно раскидать точки по квадрату)

[waxtep]

waxtep в сообщении #1393688 писал(а):

Вряд ли, при больших $n$ должно быть $\propto n^{3/2}$ (мне так кажется; если равномерно раскидать точки по квадрату)

с коэффициентом в районе $1/4$; например, для $n=(2m+1)^2$, если расставить в каждой из неперекрывающихся полос $(2m+1)\times n$ "по диагонали" $2m+1$ закрашенных клеток, получается максимальная площадь, если нигде не наврал, $S=(m+1)(2m^2+2m-1)\approx\frac14n^{3/2}$; для $n=25$ это дает предсказание $S=33$; интересно, можно ли улучшить

-- 18.05.2019, 00:05 --

Наврал слегка, конечно, лучше $S=2m(m+1)^2$ и $S=36$ для $n=25$

-- 18.05.2019, 00:30 --

Ой нет, это все никуда не годится; "между полосами" влезают более крупные прямоугольники; только как грубая оценка снизу; можно тренироваться на $n=9$, у меня пока получилось $S=12$