3
1

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

задан 9 Мар 0:48

10|600 символов нужно символов осталось
2

До n=6 включительно запретные отметки легко строятся. Например для 5: 22, 24, 33, 42, 44 (циферки - номера столбца и строки отмеченных клеток. Для 6: 22, 24, 35, 42, 53, 55

Для $%n\geqslant 9$% такие примеры невозможны, так как в каждом прямоугольнике $%2\times n$% должно быть не менее трёх отмеченных.

Для 8 - 7 идея такова. В самом верхнем прямоугольнике $%2\times n$% нужно отметить не менее 2 клеток, а в $%3\times n$% - не менее трёх. Но тогда в первом и последнем прямоугольниках $%2\times n$% надо отметить две, а в 4-3 промежуточных строчках - по одной клетке. Это очевидно не достигает цели в трёх строчках.

@Казвертеночка, а что в самом деле эту задачу давали в 6-7 классах?

ссылка

отвечен 13 Мар 9:40

изменен 13 Мар 10:09

2

@bot: легко показать, что в квадрате nxn можно расположить [n^2/6] прямоугольников 2x3 без наложений. При n>=7 их оказывается больше n.

Задача вполне годится для младших классов, так как знаний для этого хватает.

(13 Мар 12:33) falcao

@falcao: формулка неверна, например при n=7 не получится поместить 8 штук, при n=13 не поместить 28, но нам столько и не надо. Грубая оценка (n-2)^2/6 обрубит n>=10, но оставит случаи для индивидуального разбора.

(13 Мар 13:32) bot
1

@bot: почему неверна? При n=7 можно покрыть всё кроме центра, это даёт 8 плиток. Надо сделать 4 прямоугольника 3x4 и расположить их так, чтобы фигура была симметрична относительно поворота на 90 градусов. Общий факт также верен.

(13 Мар 15:27) falcao
1

@falcao: беру свой наезд взад.

(13 Мар 16:21) bot
1

@bot: можно ещё заметить, что в квадрате 5x5 достаточно расставить 4 точки -- соседние по стороне с центральной. Или точки из Вашего примера без (3,3).

Факт про [n^2/6] достаточно проверить для n<=7, и дальше индукция с переходами вида n -> n+6. Для прямоугольников вида (6k) на m при m>=2 доказывается простая "лемма" об их заполнении целиком.

(13 Мар 21:56) falcao

@bot, @falcao, большое спасибо!

(14 Мар 11:00) Казвертеночка

@falcao: да, of course, при n=5 центральную клетку красить незачем, я глубоко не задумывался.

(14 Мар 16:57) bot
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,035
×1
×1
×1
×1

задан
9 Мар 0:48

показан
147 раз

обновлен
14 Мар 16:57

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru