2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Отмеченные клетки
Сообщение08.03.2019, 23:55 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Отмеченные клетки
Сообщение09.03.2019, 14:57 
Заслуженный участник


26/05/14
981

(Оффтоп)

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

 Профиль  
                  
 
 Re: Отмеченные клетки
Сообщение14.05.2019, 05:32 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Отмеченные клетки
Сообщение16.05.2019, 11:02 


21/05/16
4292
Аделаида
Ну, пока то, что в уме:
1 - 1.
2 - 1.
3 - 2.
4 - 4.

 Профиль  
                  
 
 Re: Отмеченные клетки
Сообщение16.05.2019, 11:11 
Заслуженный участник


26/05/14
981
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 


21/05/16
4292
Аделаида
slavav в сообщении #1393318 писал(а):
В этом случае единственная клетка закрашена.

А, ой, да.

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

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

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

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

 Профиль  
                  
 
 Re: Отмеченные клетки
Сообщение16.05.2019, 12:33 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
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 


21/05/16
4292
Аделаида
dimkadimon в сообщении #1393342 писал(а):
#...
..#.
.#..
...#

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

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

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

 Профиль  
                  
 
 Re: Отмеченные клетки
Сообщение16.05.2019, 14:35 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Предлагаю решать все n <= 25.

 Профиль  
                  
 
 Re: Отмеченные клетки
Сообщение17.05.2019, 02:48 
Аватара пользователя


07/01/16
1426
Аязьма
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 


21/05/16
4292
Аделаида
dimkadimon в сообщении #1393363 писал(а):
Предлагаю решать все n <= 25.

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

 Профиль  
                  
 
 Re: Отмеченные клетки
Сообщение17.05.2019, 15:37 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
kotenok gav в сообщении #1393581 писал(а):
А для них оба случая решать?

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

 Профиль  
                  
 
 Re: Отмеченные клетки
Сообщение17.05.2019, 18:28 


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

 Профиль  
                  
 
 Re: Отмеченные клетки
Сообщение17.05.2019, 18:38 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Отмеченные клетки
Сообщение17.05.2019, 23:51 
Аватара пользователя


07/01/16
1426
Аязьма
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