smc

Question

You are playing a game. A 2 1 rectangle covers two adjacent squares (oriented either horizontally or vertically) of a 3 3 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?

Accepted Answer

First, note that since the rectangle covers 2 squares, we only need to guess squares that are not adjacent to any of our other guesses. To minimize the amount of guesses, each of our guessed squares should try to touch another guess on one vertex and one vertex only. There are only two ways to do this: one with 5 guesses, and one with 4. Since the problem is asking for the minimum number, the answer is 4.