In the cells of an $8\times 8$ board, marbles are placed one by one. Initially there are no marbles on the board. A marble could be placed in a free cell neighboring (by side) with at least three cells which are still free. Find the greatest possible number of marbles that could be placed on the board according to these rules.
Problem
Source: III Caucasus Mathematical Olympiad
Tags: combinatorics
15.05.2018 17:49
Dear Bigant, I find this problem very exciting, as well as the other similar problem proposed at the same 2018 Caucasus Math Olympiad for an n by n chessboard, filled with marbles when 2 adjacent cells are empty, instead of 3 here. I managed to place 32 marbles on the 8x8 grid, but I am sure this is not best. Having spent much time without too much succes,I would appreciate if you could offer solutions for both problems. Thanks for your assistance. Viray.
26.06.2018 00:35
Suppose we have at least $37$ marbles placed. Now everytime we place a marble, we cut the segments between the respective cell and the free neighbours. Hence we will cut at least $3\cdot 37=111$ segments. But we have $2\cdot 56=112$ possible segments to cut, implying we have at most one segment that's not cut. The idea is that marbles can not be put in the corners, we can't have 2 adjacent cells on the border with marbles, and if a marble is on the border, then all its neighbours should be free(since there are only 3)It means that on the border lines, we can't have more than 3 marbles. This implies that on any borderlines, there will be a segment that's not cut, hence at least 4, contradicting the bound. So we have at most $36$ marbles. Construction is very hard.
26.06.2018 17:26
GGPiku wrote: Suppose we have at least $37$ marbles placed. Now everytime we place a marble, we cut the segments between the respective cell and the free neighbours. Hence we will cut at least $3\cdot 37=111$ segments. But we have $2\cdot 56=112$ possible segments to cut, implying we have at most one segment that's not cut. The idea is that marbles can not be put in the corners, we can't have 2 adjacent cells on the border with marbles, and if a marble is on the border, then all its neighbours should be free(since there are only 3)It means that on the border lines, we can't have more than 3 marbles. This implies that on any borderlines, there will be a segment that's not cut, hence at least 4, contradicting the bound. So we have at most $36$ marbles. Construction should be easy, take a diagonal and complete it with marbles(without corners), then complete the 2 parts such that they're symmetric. This gives exactly 30. You can divide the board to 16 2 by 2 squares , every one must contain at most 2, except the two on the upper left and down right, so exactly 16^2 -2 = 30