Pigeonhole Principle Checkerboard Rectangle problem

Question

On a $6 \times 6$ borad, exactly $3$ checkers are placed in each column. Prove that among the 18 total checkers, it is always possible to find 4 checkers which form the corners of a rectangle.

My professor was able to prove this by breaking up each column into three columns with each sub-column having a different pair of the three checkers in the original column. Then using that, we ended up with $6\cdot 3$ of these sub-columns with $2$ checkers each. He wanted to show that the number of pairs of checkers in the same row across all columns was greater than $\binom{6}{2}$, as that represents the number of ways that we select the vertical sides of the rectangle, as if we have more pairs of checkers in the same row than the number of ways to select columns, then pigeonhole shows that we must have four checkers that form a rectangle. This ended up by showing $18 > 15$ as required.

I wanted to take a different approach, because I noticed that if we arbitrarily choose $3$ columns, we are guaranteed to have $3$ pairs of checkers in the same row across these three columns in question. This can be proven by casing on the number of pairs in the first two columns. This implies that there are $3\cdot \binom{6}{3}$ row-wise pairs of checkers. However, there a lot of double counting happening here, as if we have a pair in columns 2 and 3, then that pair will be counted if we are looking at columns 1-3 or 2-4. Actually, this pair will be counted four times: $(1,2,3)$; $(2,3,4)$; $(2,3,5)$; $(2,3,6)$. This logic holds for all possible pairs, so the true number of pairs is $\dfrac{3}{4}\binom{6}{3}=15=\binom{6}{2}$.

Now, this is bad, because we want this value to be strictly greater than $\binom{6}{2}$, not equal to it, because we are trying to pigeonhole the proof. Based of my professor's answer, I probably should be getting a value of $18$, but I'm not sure where that extra bit will come from. If not $18$, then I still don't know how to proceed with my argument. I had a few ideas of how we might also be guaranteed a triple of checkers in the same column looking across all $6$ columns, but I'm not sure how that would help. Any help would be really appreciated.

Thanks!

Answer 1

I'm not able to follow through on the OP's (i.e. original poster's) idea. However, I did find an alternative (much less elegant) brute force attack.

You get a rectangle if and only if there exists two different columns such that these two columns share at least $2$ of the $3$ rows.

Let $~\{a:b,c,d\}~$ denote that Row $~a~$ uses columns $~b,c~$ and $~d.$

Without loss of generality, assume that $\{1:1,2,3\}.$

At this point, I am going to assume that no corresponding rectangle is formed, and use this assumption to generate a contradiction.

---

Suppose Column 2 shares no rows with column 1.

Then, you have that :
$\{1:1,2,3\}$
$\{2:4,5,6\}$.

Then column 3 is forced to either share at least two rows with column 1, or share at least two rows with column 2.

Therefore, column 2 must share a row with column 1.

---

At this point, you have, without loss of generality:

$\{1:1,2,3\}$
$\{2:1,4,5\}$.

At this point, continuing to assume that no rectangle is formed, you can now conclude that no other column shares row 1. The reason is that if (for example) column 3 shared row 1, then at least one of the other two rows in column 3 would have to share an additional row with either column 2 or column 1.

That is, assuming that column 3 uses row 1, one of its other rows would have to be an element in $\{2,3,4,5\}.$

So, at this point, continuing to assume that no rectangle is formed, you have that :

• $\{1:1,2,3\}$.
• $\{2:1,4,5\}$.
• For $~k \in \{3,4,5,6\},~$ it is not the case that
  column $k$ uses row $1$.

Now consider any column $~k ~: ~k \in \{3,4,5,6\}$.
Column $~k~$ can't use row 1.
Suppose that column $~k~$ does not use row 6.
Then, either column $~k~$ uses two of the rows from the set $~\{2,3\}~$ or column $~k~$ uses two of the rows from the set $~\{4,5\}~$. That is, the assumption that column $~k~$ does not use either row 1 or row 6 forces the conclusion that column $~k~$ shares two rows with either column 1 or column 2.

Therefore, you can now conclude that while none of the columns $~3~$ through $~6~$ use row 1, $~$ all $~4~$ of these columns use row 6.

The only way that this is possible, with none of these $4$ columns forming a rectangle with either column 1 or column 2, is if you have (without loss of generality) the following distribution:

• $\{1:1,2,3\}$.
• $\{2:1,4,5\}$.
• $\{3:2,4,6\}$.
• $\{4:2,5,6\}$.
• $\{5:3,4,6\}$.
• $\{6:3,5,6\}$.

That is, each of columns $~3~$ through $~6~$ must use exactly one row from the set $~\{2,3\}~$ and one row from the set $~\{4,5\}.~$

As shown, this leads to rectangles being formed via columns $~3~$ and $~5~$, as well as via columns $~4~$ and $~6.$

Similarly, this leads to rectangles being formed via columns $~3~$ and $~4~$, as well as via columns $~5~$ and $~6.$

Answer 2

That’s a nice approach. And you only need one little extra ingredient to make it work.

Note that in what you call “casing on the number of pairs in the first two columns”, none of the minimal configurations of three columns that contain only $3$ row-wise pairs has $3$ checkers in a row. Because you already reached equality with $15$, a single triple of columns with $3$ checkers in a row (which would require that triple to have at least $4$ row-wise pairs) would suffice to complete the proof. But obviously you can’t put $3$ checkers in each column without ever putting $3$ checkers in a row (since the row sums and the column sums must add up to the same total), and if there are three checkers in a row, then there’s a triple of columns that have three checkers in a row.

A bit of advice: My impression (I might be wrong) is that you have a good feel for these things, but you don’t seem to have much experience describing your thoughts so others can follow. At first I felt like user2661923 describes in their answer, that I wasn’t able to follow, but your approach seemed interesting so I made an effort to understand it. Formulations like “pairs of checkers in the same row across columns” are a bit ambiguous and can be hard to understand. So I just thought it would be a pity if your good ideas are lost in communication, and you should perhaps try to work on your ability to share them.

Answer 3

This is a version of above, so let us mark the columns with [A..F] and rows with [1..6], like a chess table.

WLOG (without loss of generality) three checkers go in A1, A2, A3. Column B must have exactly one checker in this lower half of the table, because two or three of them produce rectangles, while a B4, B5, B6 triplet will force a rectangle with next two of three pieces on column C. (here is the pidgeon principle)

The colums C,D,E and F follow the situation of column B so until now we managed to forcibly place 3 + 1+ 1 + 1 + 1 + 1 = 8 checkers in the lower half of the table.

It remains to place 10 pieces, 2 on each column, in the 3x5=15 square area [B..F] × [4..6]. After placing WLOG B4, B5, C4, C6, and D5, D6, the remaining 4 checkers can not avoid rectangles.