Question 5
Let $k$ be a positive integer. A $3k\times3k$ board has cells $(i,j)$, where i counts columns from left to right and j counts rows from bottom to top. Place $4k$ marbles, at most one per cell, subject to:
- Every row and every column contains at least one marble.
- Every marble shares a row or a column with at least one other marble.
a) For $k=1$, how many placements of four marbles satisfy these conditions? Two placements are different if some cell is occupied in one but not in the other.
b) For general $k\ge1$, determine the largest natural number N such that, however N distinct cells are marked, there is a valid placement of $4k$ marbles avoiding every marked cell.
- Every row and every column contains at least one marble.
- Every marble shares a row or a column with at least one other marble.
a) For $k=1$, how many placements of four marbles satisfy these conditions? Two placements are different if some cell is occupied in one but not in the other.
b) For general $k\ge1$, determine the largest natural number N such that, however N distinct cells are marked, there is a valid placement of $4k$ marbles avoiding every marked cell.