|
а) Какое наибольшее количество фишек можно поставить на шахматную доску так, чтобы в каждом квадрате $%3\times 3$% стояло ровно по 3 фишки? б) Какое наибольшее количество фишек можно поставить на шахматную доску так, чтобы в каждом квадрате $%3\times 3$% стояло ровно по 5 фишек? (подразумевается, что две фишки на одно поле ставить нельзя) задан 27 Дек '18 12:51 
Казвертеночка |
|
Поле с расположенными в соответствии с условиями задачи фишками называем конфигурацией. 3х3-квадраты называем квадратами. Используем очевидные свойства:
Утверждение. Максимальное число фишек в 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 |
По-моему, будет а) 27 и б) 44. Оценки тут очевидные, а примеры строятся периодические по обеим координатам.
@falcao, с первым пунктом и вправду всё тривиально, но вот со вторым...
@Казвертеночка: да, я согласен -- пункт б) надо подвергнуть "ревизии".
Писал второпях -- в тот момент показалось, что там всё как и в предыдущих задачах похожего типа.
По п. б) максимум не менее 42 и не более 44. Похоже (?:), можно доказать, что 42.
@Urt: я тоже склоняюсь к выводу, что 42 -- это максимум, но пока не доказал.