In a $10\times 10$ square board, half of the squares are coloured white and half black. One side common to two squares on the board side is called a border if the two squares have different colours. Determine the minimum and maximum possible number of borders that can be on the board.
Problem
Source: CentroAmerican 2004
Tags: geometry, rectangle, combinatorics proposed, combinatorics
11.12.2010 05:51
The maximum is 180; all inner edges of the squares are borders. This is easily achieved by using the chessboard pattern, and is obviously the maximum, since there are no more inner edges. The minimum is 10; achieved by making the first 5 columns white and the last 5 columns black. I haven't find the proof, though my "math intuition" says that the minimum is indeed 10.
11.12.2010 10:44
Key lemma: The borders is a union of closed loops. (the edges of the board can also be a part of this border). This can be proven by contradiction by supposing that there is a path of borders with endpoints not being the same point (deduce a contradiction be looking at what the four squares surrounding an endpoint should be). Now the idea is to suppose that we have only $x$ horizontal borders and $y$ vertical borders. Suppose for contradiction that $x+y\leq 9$. Let us now consider an arbitrary black section. We have that either its lowermost horizontal boundary, or its upper most horizontal boundary is completely made up of borders (and not the boundary of the board). Indeed suppose by contradiction that this did not occur, then that would imply that this piece touches both the upper and lower boundary of the grid which implies that $y\geq 10$ which is a contradiction. Likewise either its leftmost or rightmost vertical boundary is completely made up of borders. Now we draw a minimal rectangle around this piece (that is a rectangle containing this piece such that no smaller rectangle contains it). We do this for each piece and place our minimal rectangles diagonally, and again draw a minimal rectangle around this new shape. (see attatchment for illustration) Let $l,w$ be the length and width respectively, since there are $50$ black squares in total we have: $50\leq lw$ However we also have $w\leq x$ and $l\leq y$ hence: $50\leq xy \leq (x+y)^2/4 \leq 9^2/4$ Which is a contradiction.
Attachments:
nested rectangle.pdf (1kb)
12.12.2010 10:04
Call a row "black" if it consists of black squares only, and call it "white" if it consists of white squares only. If there is no black row nor white row, then there is a border in each row, so there are at least 10 borders. If there is a black row and a white row, then there is a border in each column, so there are at least 10 borders. Finally, assume there is a black row but no white row (the case that there is a white row but no black row is analogous). Suppose there are exactly $x$ black rows. The 50 white squares are distributed among 10 columns, each of which contains at most $10-x$ white squares. Hence there are at least $\frac{50}{10-x}$ columns which contains white squares. Each of these columns has at least one border, and each of the $10-x$ non-black rows has at least one border. So it suffices to prove that $10-x+\frac{50}{10-x}\ge10$. By AM-GM we have $10-x+\frac{50}{10-x}\ge2\sqrt{50}>10$, so our proof is complete.