Find the maximal number of crosses with 5 squares that can be placed on 8x8 grid without overlapping.
Problem
Source: Third Saudi Arabia JBMO TST 2019, P1
Tags: combinatorics
09.04.2020 12:56
答案是8。称每个“cross”的中心格为“special”的,显然任意“special”的格子不在8*8的边界上。若有 $\ge 9$个“cross”,则由Pigeonhole principle我们知道必有一个被染色的3*3(附件中的图片)中有至少3个“special”的格子,而这显然是不成立的。故至多有8个“cross”。 构造见第一个附件。(I have bad English,so I hope someone can do the translete work )
Attachments:


09.04.2020 14:14
yefangzhou wrote: The answer is 8. Consider each of the cross’s centre. It is obvious that none of the centres lie on the boundaries. If there are $\ge 9$ Crosses,From the pigeonhole principle we know there are 3 crosses in a 3 by 3 region (refer to picture), which is obviously impossible. Hence there can only a maximum of 8 crosses. 3(I have bad English,so I hope someone can do the translete work )
09.04.2020 15:31
Thanks for gghx's translation.