а) Какое наибольшее количество фишек можно поставить на шахматную доску так, чтобы в каждом квадрате $%3\times 3$% стояло ровно по 3 фишки?

б) Какое наибольшее количество фишек можно поставить на шахматную доску так, чтобы в каждом квадрате $%3\times 3$% стояло ровно по 5 фишек?

(подразумевается, что две фишки на одно поле ставить нельзя)

задан 27 Дек '18 12:51

1

По-моему, будет а) 27 и б) 44. Оценки тут очевидные, а примеры строятся периодические по обеим координатам.

(27 Дек '18 14:20) falcao
1

@falcao, с первым пунктом и вправду всё тривиально, но вот со вторым...

(27 Дек '18 17:24) Казвертеночка
1

@Казвертеночка: да, я согласен -- пункт б) надо подвергнуть "ревизии".

Писал второпях -- в тот момент показалось, что там всё как и в предыдущих задачах похожего типа.

(28 Дек '18 1:01) falcao
2

По п. б) максимум не менее 42 и не более 44. Похоже (?:), можно доказать, что 42.

(28 Дек '18 23:24) Urt
1

@Urt: я тоже склоняюсь к выводу, что 42 -- это максимум, но пока не доказал.

(29 Дек '18 0:06) falcao
10|600 символов нужно символов осталось
2

Поле с расположенными в соответствии с условиями задачи фишками называем конфигурацией. 3х3-квадраты называем квадратами. Используем очевидные свойства:

  • В любом квадрате либо все столбцы непустые, либо все строки непустые.

  • Сумма фишек в столбце из трех клеток не изменится, если этот столбец сдвинуть вправо или влево на 3 позиции. Аналогично для строк.

  • 8х8-конфигурация может быть помещена в 9х9-конфигурацию. Для этого достаточно сначала добавить к полю справа столбец повторяющий третий слева столбец, затем добавить нижнюю строку, повторяющую третью сверху строку.

Утверждение. Максимальное число фишек в 8х8-конфигурации равно 42.

Достаточность. Для построения 8х8-конфигурации с 42 фишками достаточно выбрать квадрат со строками (110), (110), (100), затем на основе циклического повторения его столбцов построить 3х8-конфигурацию, затем построить 8х8-конфигурацию путем циклического повторения строк 3х8-конфигурации.

Необходимость. Общее число фишек в 9х9-конфигурации равно 45, поэтому достаточно доказать, что сумма фишек в правом и нижнем столбцах любой 9х9-конфигурации не менее 3.

Пусть А – один из 3-х находящихся на диагонали квадратов, составляющих 9х9-конфигурацию. Если в А все столбцы содержат фишки, то соответствующий правый столбец поля содержит фишку, Если в А все строки содержат фишки, то соответствующая нижняя строка поля содержит фишку, Следовательно, каждый диагональный квадрат дает не менее одной фишки на клетки правой и нижней сторон 9х9-поля, ч. т. д.

ссылка

отвечен 29 Дек '18 12:21

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

(29 Дек '18 12:39) Казвертеночка
1

@Urt: да, аргумент насчёт "или строки, или столбцы" совершенно "железный". Хорошее доказательство!

(29 Дек '18 12:50) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,226
×66
×14
×12
×3

задан
27 Дек '18 12:51

показан
292 раза

обновлен
29 Дек '18 12:50

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

по почте:

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

по RSS:

Ответы

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

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