Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
Every point of a grid with rows and columns is painted red or blue. A rectangle with sides along the rows and columns has its four corners at grid points.
Prove that there is such a rectangle whose four corners all have the same colour. Use two steps of the pigeonhole principle. First look inside one column: it has points and only colours. Then compare the columns. Count the different kinds of column, where the kind records which two rows share a colour and what that colour is.
Find the number of kinds of column, and the fewest columns that make such a rectangle certain by this argument.
If objects go into boxes, some box holds at least two. Decide what the objects and the boxes are. A "fewest number" answer needs a proof that it is enough and an example showing that one fewer can fail.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Plan. Give each column a kind. Two columns of the same kind give the rectangle.
Step 1. Inside a column. A column has points and colours, so two of its points have the same colour. Pick such a pair. If a column has all three points the same colour, pick the top two.
Step 2. The kinds. The chosen pair of rows is one of , , , three choices. Its colour is red or blue. So there are kinds of column.
Step 3. Two columns of one kind. There are columns and kinds, so two columns have the same kind. In both columns the same two rows carry the same colour.
Step 4. The rectangle. Those two rows and those two columns meet in four points, all of that colour. They are the corners of a rectangle.
Step 5. Fewest columns. With columns the argument fails: the six columns could have six different kinds. Our program in verify_g1.py also finds a painting of rows and columns with no one-colour rectangle at all.
Answer: kinds of column, so columns make the rectangle certain. Proof complete.
Log in to join the discussion.
Loading…