We call a positive integer $n$ "good" if and only if , in a $6 \cdot 6$ checkerboard , no matter how we put $n$ $1 \cdot 2$ dominoes in the board, there will be a space for another domino (There will be a $1 \cdot 2$ or $2 \cdot 1$ space). Find the maximum "good" integer.
I think the answer is $11$. Here's my work.
Section 1 : 12 isn't "good"
.
As you can see, this is a figure that shows $12$ isn't "good".
Section 2 : 11 is "good" (Where I'm stuck)
So, I learn this and my teacher solution is as follows,
First, assume some counterexample exists.
Let $A$ be sets of all spaces in the upper $5 \cdot 6$ board.
Let $B$ be sets of all spaces in the lower $1 \cdot 6$ board.
If $|B| \geq 4$ ; there will be two spaces that are connected , a contradiction.
So, $|B| \leq 3$
Since there are a total of $36 - 2(11) = 14$ spaces.
Hence, $|A| \geq 11$.
Let $C$ be sets of all dominoes that are fully included in the lower $5 \cdot 6$ board.
Now, assume that , there exists some space in $A$ that there is no domino below it. This will create a $1 \cdot 2$ space which we can put another domino. A contradiction.
So, there will always be a domino below a space in $A$.
We define a function $f : A \rightarrow C$ such that $f(t) = $ domino below $t$ $\space$ $\forall t \in A$
Now, my teacher says that this function is bijective , so $|C| = |A| \geq 11$. But maximum number of dominos is $11$ , $|C| = 11$. But if we consider the upper $1 \cdot 6$ board, we can easily put a domino in it. Hence, a contradiction.
So,$11$ is "good".
My question
From Section 2, I think I can show the injective part,
Let $f(a_1) = f(a_2) =$ domino "m"
Case I : "m" is horizontal.
Now, if $a_1$ is the left space above "m" and $a_2$ is the right space of "m" , we can put another domino above "m", a contradiction. So, $a_1 = a_2$.
Case II : "m" is vertical. This case is obvious.
Thus, $f$ is injective.
I know we can finish the problem using only injectivity and change $|C| = |A|$ to $|C| \geq |A|$ and finish the problem.
But I can't figure out how $f$ is surjective. Can anyone give me a hint or a solution. Thanks in advance.
Yes, the maximum "good" integer for a $6\times 6$ board is 11.
This paper deals with the minimum number $D(m,n)$ of dominoes on a $m\times n$ board needed to prevent placement of another domino. In Theorem 1, the authors show the following general inequality: for $m,n\geq 2$ $$D(m,n)\geq H(m,n)$$ where $H(m,n)=mn-2D(m,n)$ is the number of holes. It follows that $$D(m,n)\geq\left\lceil \frac{mn}{3}\right\rceil$$ In your case, the above inequality says that $D(6,6)\geq 12$.
See also oeis.org/A280984 as a reference.