Problem

Source: 2024 Vietnam National Olympiad - Problem 4

Tags: combinatorics



$k$ marbles are placed onto the cells of a $2024 \times 2024$ grid such that each cell has at most one marble and there are no two marbles are placed onto two neighboring cells (neighboring cells are defined as cells having an edge in common). a) Assume that $k=2024$. Find a way to place the marbles satisfying the conditions above, such that moving any placed marble to any of its neighboring cells will give an arrangement that does not satisfy both the conditions. b) Determine the largest value of $k$ such that for all arrangements of $k$ marbles satisfying the conditions above, we can move one of the placed marble onto one of its neighboring cells and the new arrangement satisfies the conditions above.