Problem:
You are playing a game. A rectangle covers two adjacent squares (oriented either horizontally or vertically) of a grid of squares, but you are not told which two squares are covered. Your goal is to find at least one square that is covered by the rectangle. A "turn" consists of you guessing a square, after which you are told whether that square is covered by the hidden rectangle. What is the minimum number of turns you need to ensure that at least one of your guessed squares is covered by the rectangle?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Any rectangle must cover one of the shaded squares in the figure below.
Therefore guessing these shaded squares will always result in finding a square covered by the rectangle.
It remains to show that 3 guesses are not always sufficient. If any 2 of the 3 guessed squares are in the same row (or column), then rectangles in the unselected row (or column) will not cover any of the 3 guessed squares. So if only 3 guesses are made, one square from each row and each column must be selected. There are two ways this can happen, up to symmetry, shown below. A rectangle covering two unshaded squares can be found in each diagram, so 3 guesses are not sufficient in general.
.jpg)
The problems on this page are the property of the MAA's American Mathematics Competitions