Very nice problem! Here is a sketch of the solution: Let $G$ be a graph on $4k$ vertices such that each show a marble and we connect two vertices if those two marbles are located in the same row or column. Take a connected component of $G$ like $H$. By modeling $H$ using BFS algorithm, we get that the set of the rows and columns that vertices in $H$ are located in, has at most $\vert H\vert +1$ elements. Note that each connected component has at least $2$ vertices. Thus with $4k$ marbles, we can cover at most $2k\times 3$ rows and columns. Note that the equality holds if each connected component of $G$ has exactly $2$ vertices. In the problem statement, the equality in holding, thus we have placed $k$ vertical dominos and $k$ horizontal dominos. Using this, you can get that for part a the answer is $\boxed{9}$. For part b, I will show that the maximum $N$ is $\boxed{N=3k-1}$ by inducting on $k$. Note that $N<3k$ since we can just mark all cells of the first row. The base $k=1$ of our induction can be checked easily. Now assume that we've proved the statement for $k=1,2,\cdots ,t$. Let's prove it for $k+1$. You should prove that we can place a horizontal domino and a vertical domino of marbles such that in the three rows and three columns that they are in, we have at least $3$ marked cells. then we can remove those three rows and three columns and use induction, since we have a $3k-3\times 3k-3$ table with less that $3k-1-3<3(k-1)$ marked cells. Finding those two dominos is not hard and can be done by picking the first domino such that in has at least two marked cells in its rows and column.

Part a Consider a bipartite graph $G=(A,B,E)$, where: - $A=\{a_1,a_2,\ldots,a_{3k}\}$ are the vertices corresponding to the rows of the grid. - $B=\{b_1,b_2,\ldots,b_{3k}\}$ are the vertices corresponding to the columns of the grid. - For all $1\le i,j\le 3k$, $(a_i,b_j)\in E$ if and only if we are able to put a marble in the cell at row $i$, column $j$. For every placement of marble, let $F$ be a subgraph of $G$ containing only the edges corresponding to the cells having marbles. Notice that: - There is no isolated vertex in $F$. - For all $e=(u,v)\in E$, there exists $e'\in E$ such that $e'$ is incident to either $u$ or $v$. Those two statements above are equivalent to the fact that every connected component of $F$ has at least 2 edges. Let $C_1,C_2,\ldots,C_m$ be all the connected components of $F$. We have: $\bullet$ $\displaystyle 4k=\left|E(F)\right|=\sum_{1\le i\le m}{\left|E(C_i)\right|}\ge 2m\Leftrightarrow m\le 2k$ $\bullet$ $\displaystyle 4k=\left|E(F)\right|=\sum_{1\le i\le m}{\left|E(C_i)\right|}\ge\sum_{1\le i\le m}{\left(\left|V(C_i)\right|-1\right)}=\left|V(F)\right|-m=6k-m\Leftrightarrow m\ge2k$ Therefore, $m=2k$, which means, each connected component has exactly 2 edges. For $k=1$, we have 3 vertices in each part. To form a subgraph $F$, we can choose 2 vertices from $A$ and a vertex from $B$ for the first connected component, and the rest will form the second connected component. The number of such graphs is: $\binom{3}{2}\binom{3}{1}=9$. Part b As a convention, we will call the pair of vertices in $E$ which does not have an edge connecting them as a "marked edge". Firstly, we will show that $N\le3k-1$. Indeed, if $N\ge3k$, we could mark all the cells in the first row, which, since then, violates the first criterion of the marble placement. Now, we need to show that $N\le3k-1$ satisfies the problem using induction by $k$. For $k=1$, there are two cases: $\bullet$ Two marked edges are both incident to a vertices. WLOG, suppose that they are $(a_1,b_2),(a_1,b_3)$. Then, we can construct $F$ from $(a_1,b_1),(b_1,a_2),(b_2,a_3),(a_3,b_3)$. $\bullet$ Two marked edges so not share a common vertex. WLOG, suppose that they are $(a_1,b_1),(a_2,b_2)$. Then, we can construct $F$ from $(a_1,b_2),(b_2,a_3),(b_1,a_2),(a_2,b_3)$. The base case is done. Suppose that the statement is true for $k=l-1$ ($l\in\mathbb{Z}^+\setminus\{1\}$), we need to show that it is also true for $k=l$. WLOG, suppose that $a\in A$ is the vertex having smallest degree of $G$. For every vertex $v$ of $G$, $3l-\deg{v}$ is the number of marked edges incident to $v$. Then, for every vertex $v$ different from $a$, we have $(3l-\deg{v})+(3l-\deg{a})\le3k-1$ $\Rightarrow 3l+1\le\deg{a}+\deg{v}\le2\deg{v}\Rightarrow\deg{v}\ge\dfrac{3l+1}{2}\Rightarrow\deg{v}\ge 3$ (as $l\ge2$). We have: $\bullet$ $\exists b\in B:(a,b)\in E$. Choose $b$ with smallest possible degree. $\bullet$ $\exists a_1\in A:a_1\ne a, (a_1,b)\in E$. Choose $a_1$ with smallest possible degree. $\bullet$ $\exists b_1\in A:b_1\ne b, (a_1,b_1)\in E$. Choose $b_1$ with smallest possible degree. $\bullet$ $\deg{b_1}\ge3\Rightarrow\exists a_2\in A:a_2\ne a,a_2\ne a_1,(a_2,b_1)\in E$. Choose $a_2$ with smallest possible degree. $\bullet$ $\deg{a_2}\ge3\Rightarrow\exists b_2\in A:b_2\ne b,b_2\ne b_1,(a_2,b_2)\in E$. Choose $b_2$ with smallest possible degree. Choose $\{(a,b),(b,a_1)\}$ and $\{(b_1,a_2),(a_2,b_2)\}$ as 2 connected components of $F$. It is sufficient to show that we can construct $2l-2$ more connected components of 2 edges from $G'=G\setminus\{a,b,a_1,b_1,a_2,b_2\}$. We have $(3l-\deg{a})+(3l-\deg{a_1})+(3l-\deg{a_2})=9k-(\deg{a}+\deg{a_1}+\deg{a_2})$ is the number of marked edges incidents to either $a$, $a_1$ or $a_2$. Similarly, $9k-(\deg{b}+\deg{b_1}+\deg{b_2})$ is the number of marked edges incidents to either $b$, $b_1$ or $b_2$. We will prove that $\max\{9k-(\deg{a}+\deg{a_1}+\deg{a_2}),9k-(\deg{b}+\deg{b_1}+\deg{b_2})\}\ge 3$, or, $\min\{\deg{a}+\deg{a_1}+\deg{a_2},\deg{b}+\deg{b_1}+\deg{b_2}\}\le9l-3$. Indeed, for the sake of contradiction, suppose that $\min\{\deg{a}+\deg{a_1}+\deg{a_2},\deg{b}+\deg{b_1}+\deg{b_2}\}\ge9l-2$ $\Rightarrow \deg{a}=\deg{b}=3l-1$. That implies there is exactly one vertex of $B$ having degree of $3l$, and it is either $b_1$ or $b_2$. Back to how we chose $b_1$ and $b_2$, we want to guarantee that they have minimum possible degree. However, as both $a_1$ and $a_2$ have degree $3l-1\ge5$, we can choose other vertices in $B$ with degree less than $3l$. Therefore, this contradicts our definition of $b_1$ and $b_2$. Thus, there are at least 3 marked edges incident to a vertex in $\{a,b,a_1,b_1,a_2,b_2\}$. Since then, in $G'$, there are at most $N-3\le 3l-4$ marked edges. According to inductive hypothesis, $F$ can be successfully constructed. By the principle of induction, we finish our proof.

Part a) We can do a case bash to see that every configuration is equivalent (equivalent meaning we can change the order of the rows and the order of the columns to get this configuration) to O O X O O X X X O Now we can "repermutate" the rows and columns. Clearly the only difference in the permutations is the position of the 3rd column in this construction and the 1st row. There are 3 places for each hence there are 9 spots. Here is a solution without induction for Part b) First we will solve for $k=1$. We claim the answer is $N=2$. It is easy to see that any 2 marked cells can be permutated to be one of these: X X O X O O X O O O O O X O O O X O O O O O O O O O O and the construction from a) works. Now the bound: If $N\geq3k$ we can mark a whole row and we are done. Now for the construction, again. We define a rook set of size $k$ to be $k$ rooks on a $k \times k$ square, s.t. every rook is at a different row and column from all other rooks. Main lemma: If we have less than $k$ marked cells in a $k \times k$ area, we have a rook set of size $k$ there with no rook on a marked square. Proof: We have $k$ disjoint rook sets (just take all the diagonals of the form $(i, j)$, $(i+j)=m$ (mod $k$) for all $m$), and if we have less than $k$ marked cells in the $k \times k$, there is some rook set with no marked cells in it. Now divide the $3k \times 3k$ into $9$ $k \times k$ squares. If there is at most $3k-1$ marked cells there, there are at most $2$ $k \times k$ with at least $k$ marked cells in them. Now we can use the construction for $k=1$ and put rook sets on $4$ of the $9$ $k \times k$ s.t. the $4$ squares form a valid construction for $k=1$ and they all have less than $k$ marked cells in them. Now, for each $k \times k$ picked, we will put a valid rook set there, and that will finish the construction.