Если m>k, то какое наименьшее количество клеток нужно закрасить в квадрате m×m, чтобы в каждом квадрате k×k была ровно одна закрашенная клетка?

задан 6 Мар '14 22:00

изменен 6 Мар '14 22:30

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

Рассмотрим упрощённый вариант задачи, когда имеется полоска из $%m$% клеток. Будем отрезать от неё последовательно полоски длиной $%k$%. Это удастся сделать $%q$% раз, где $%q=\lfloor\frac{m}k\rfloor$% (целая часть частного). В каждой отрезанной полоске должна быть закрашенная клетка, то есть их должно быть как минимум $%\lfloor\frac{m}k\rfloor$%. С другой стороны, этого количества хватит, потому что если клетки пронумерованы от $%1$% до $%m$%, то достаточно закрасить те клетки, номера которых кратны $%k$%. Их будет в точности $%\lfloor\frac{m}k\rfloor$%.

Для квадрата $%m\times m$% рассуждение аналогично. В нём можно расположить $%q^2$% (непересекающихся) квадратов со стороной $%k$%, то есть закрасить нужно как минимум столько клеток. С другой стороны, этого количества достаточно, если мы пронумеруем строки и столбцы числами от $%1$% до $%m$%, закрашивая те и только те клетки, у которых и номер строки, и номер столбца делится на $%k$% нацело. То есть наименьшее количество закрашенных клеток будет равно $%\lfloor\frac{m}k\rfloor^2$%. В любом квадрате $%k\times k$% хотя бы одна закрашенная клетка будет по той причине, что среди любых $%k$% последовательных натуральных чисел найдётся число, кратное $%k$%.

ссылка

отвечен 7 Мар '14 2:07

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×4,501
×3,687
×525
×408

задан
6 Мар '14 22:00

показан
2180 раз

обновлен
7 Мар '14 2:07

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

по почте:

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

по RSS:

Ответы

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

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