18
$\begingroup$

The squares of a 5 x 5 chessboard are painted in one of two colors in an arbitrary way. Prove that there exist 2 rows and 2 columns such that the 4 squares where they intersect are all of the same color.


This puzzle came from a Leningrad Mathematical Olympiad

$\endgroup$
8
  • 3
    $\begingroup$ Interestingly, this is no longer true if the board is 6 by 4 $\endgroup$
    – xnor
    Jan 29 at 3:22
  • 8
    $\begingroup$ it feels a bit odd to call it a "chessboard" specifically, even though the whole point is that the coloring can be arbitrary, and not a checkered chessboard pattern... $\endgroup$
    – ilkkachu
    Jan 29 at 11:58
  • 2
    $\begingroup$ Oooh, I was ASSUMING "in a square", but it just says "where the rows and columns intersect", they don't have to be adjanced at all. My bad! $\endgroup$
    – Syndic
    Jan 29 at 14:28
  • 1
    $\begingroup$ @ilkkachu I see your point. When I post a puzzle that someone else created, I don’t like changing their wording. When I saw this puzzle it used the word “chessboard”. $\endgroup$ Jan 29 at 22:53
  • 1
    $\begingroup$ puzzling.stackexchange.com/questions/89329/… is related $\endgroup$
    – mathlander
    Jan 31 at 1:51

4 Answers 4

20
$\begingroup$

Borrowing ideas from both @Gareth and @xnor:

WLOG one column has at least 3 black squares. Discard the 2 other rows. If any of the 4 other columns has more than 1 black square we are done. We are left with a 3x4 board with at least a pair of white squares in each column. As there are only 3 distinct such pairs but 4 columns we are done.

$\endgroup$
12
$\begingroup$

Here's an argument that (I think) is entirely different from xnor's. (I don't claim that it's better. It feels a bit more straightforward to me.)

Each column is either majority-black or majority-white. Three of them must have the same majority colour; let's say WLOG that columns 1,2,3 are majority-black. And WLOG column 1 has black in (at least) rows 1,2,3.

If column 2,3 both have black in rows 4,5 then we're done. But if not, one of them has at most one black in rows 4,5 but at least three black in total, hence at least two black in rows 1,2,3, hence two black cells in the same rows as column 1. Done.

$\endgroup$
1
  • $\begingroup$ This was my first thought as well. Straightforward. +1 $\endgroup$
    – justhalf
    Jan 29 at 3:14
7
$\begingroup$

Consider the 5 rows. Take one color, say white, and for each row, note the white cells and write down every pair of their column indexes. For example, if in the first row, cells 2, 4, and 5 are white, you'd write down (2, 4), (2, 5), and (4, 5). If any pair is listed twice among all rows, that's a 2-by-2 white square. There are $\binom{5}{2}=10$ possible pairs.

Now also do the same for black squares. We have 10 white pairs and 10 black pairs to work with, for a total of 20. The number of pairs that each row contributes depends on the black/white split, but it's smallest if it's 3 vs 2, which gives 4 pairs. That's 20 minimum across 5 rows. Well, darn, that's just within our allowance.

But we can save this argument! For each row to give the minimal 4 pairs, it must be 3 vs 2, and so contribute 3 pairs to one color and 1 pair to another. Both 3 and 1 are odd, so across the 5 rows, the total number of pairs for either color is odd, so we can't get 10-and-10 split that's needed for 20 pairs. One of the colors must have at least 11 pairs, and so have a repeat which forms a 2-by-2 square.

$\endgroup$
2
$\begingroup$

You can find the minimum number of monochromatically-cornered rectangles via integer linear programming. Define the following sets:

  • $\text{CELLS} = \{1,\dots,5\} \times \{1,\dots,5\}$ is the set of cells.
  • $C=\{1,2\}$ is the set of colors.
  • $R$ is the set of rectangles. Here, $|R| = \binom{5}{2}^2 = 100$.
  • $\text{CELLS}_r$ is the set of four cells that form the corners of rectangle $r\in R$.

Let binary decision variable $x_{ijc}$ indicate whether cell $(i,j)$ is assigned color $c$, and let binary decision variable $y_r$ indicate whether rectangle $r$ has monochromatic corners. The problem is to minimize $\sum_{r\in R} y_r$ subject to \begin{align} \sum_{c\in C} x_{ijc} &= 1 &&\text{for $(i,j)\in\text{CELLS}$} \tag1\label1\\ \sum_{(i,j)\in \text{CELLS}_r} x_{ijc} - 3 &\le y_r &&\text{for $r\in R$ and $c\in C$} \tag2\label2 \end{align} Constraint \eqref{1} assigns exactly one color to cell $(i,j)$. Constraint \eqref{2} enforces the logical implication $\left(\bigwedge_{(i,j)\in \text{CELLS}_r} x_{ijc}\right) \implies y_r$.

The minimum turns out to be $2$, and here is an optimal two-coloring, with the two monochromatically-cornered rectangles highlighted: \begin{matrix} 1 & 1 & 1 & 2 & 2 \\ 1 & \boxed{2} & 2 & 1 & \boxed2 \\ \boxed2 & \boxed2 & 1 & 2 & 1 \\ 2 & 1 & 2 & 1 & 1 \\ \boxed2 & \boxed2 & 1 & 1 & \boxed2 \end{matrix}

Unfortunately, the linear programming (LP) relaxation obtained by ignoring integrality of the variables yields optimal objective $0$, so the LP duals do not yield a short certificate of optimality.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.