2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Отмеченные клетки
Сообщение08.03.2019, 23:55 
Аватара пользователя
В квадрате $n\times n$ отмечено $n$ клеток.
При каких $n\geqslant 3$ внутри квадрата всегда можно по клеточкам выделить прямоугольник $2\times 3$ без отмеченных клеток?

 
 
 
 Re: Отмеченные клетки
Сообщение09.03.2019, 14:57 

(Оффтоп)

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

 
 
 
 Re: Отмеченные клетки
Сообщение14.05.2019, 05:32 
Аватара пользователя
Предлагаю контер задачу. Какой наибольший (по площади) незакрашенный прямоугольник всегда можно найти для каждого n?

 
 
 
 Re: Отмеченные клетки
Сообщение16.05.2019, 11:02 
Ну, пока то, что в уме:
1 - 1.
2 - 1.
3 - 2.
4 - 4.

 
 
 
 Re: Отмеченные клетки
Сообщение16.05.2019, 11:11 
kotenok gav в сообщении #1393315 писал(а):
1 - 1.

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

-- 16.05.2019, 11:23 --

5 - 4.

-- 16.05.2019, 11:32 --

6 - 6.

 
 
 
 Re: Отмеченные клетки
Сообщение16.05.2019, 12:22 
slavav в сообщении #1393318 писал(а):
В этом случае единственная клетка закрашена.

А, ой, да.

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

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

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

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

 
 
 
 Re: Отмеченные клетки
Сообщение16.05.2019, 12:33 
Аватара пользователя
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.

 
 
 
 Re: Отмеченные клетки
Сообщение16.05.2019, 13:11 
dimkadimon в сообщении #1393342 писал(а):
#...
..#.
.#..
...#

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

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

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

 
 
 
 Re: Отмеченные клетки
Сообщение16.05.2019, 14:35 
Аватара пользователя
Предлагаю решать все n <= 25.

 
 
 
 Re: Отмеченные клетки
Сообщение17.05.2019, 02:48 
Аватара пользователя
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$ строится специальное разбиение на восемь кирпичей, не включающее центральную клетку

 
 
 
 Re: Отмеченные клетки
Сообщение17.05.2019, 08:38 
dimkadimon в сообщении #1393363 писал(а):
Предлагаю решать все n <= 25.

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

 
 
 
 Re: Отмеченные клетки
Сообщение17.05.2019, 15:37 
Аватара пользователя
kotenok gav в сообщении #1393581 писал(а):
А для них оба случая решать?

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

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

 
 
 
 Re: Отмеченные клетки
Сообщение17.05.2019, 18:38 
Аватара пользователя
kotenok gav в сообщении #1393685 писал(а):
Сильное ощущение, что тогда ответ будет $n-1$.
Вряд ли, при больших $n$ должно быть $\propto n^{3/2}$ (мне так кажется; если равномерно раскидать точки по квадрату)

 
 
 
 Re: Отмеченные клетки
Сообщение17.05.2019, 23:51 
Аватара пользователя
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$

 
 
 [ Сообщений: 20 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group