2023 AMC 10B Problem 10

P1-10~4 minPrint

Paths & Grids Games & Processes Bound the quantity above/below or estimate to pin it down Consider the largest/smallest element or boundary case

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

Show solution without answering

Key insight

Every possible rectangle covers one of the four middle-of-edge squares, so 4 guesses always work. Three guesses can touch at most 10 of the 12 rectangle positions.

Solution

In the worst case you are told "no" every time until you hit. So you need a set of squares that touches every possible position of the hidden rectangle. This is a "least number" question, so there are two halves: show $4$ turns always work, then show $3$ turns can fail.

Name the squares: $4$ corners, $4$ edge squares (the middle of each side), and $1$ center.

Part 1: four turns are enough.

There are $12$ positions for the rectangle: in each of the $3$ rows it can sit in $2$ places ( $6$ horizontal), and in each of the $3$ columns it can sit in $2$ places ( $6$ vertical).
Look at which squares sit next to each other. A corner only touches edge squares. The center only touches edge squares. So any two squares side by side include an edge square.
That means every one of the $12$ positions covers at least one edge square. Guess the $4$ edge squares, and one of them must be covered.

Part 2: three turns are not enough.

4. Count how many of the $12$ positions cover each kind of square:
- a corner: $2$ positions (one horizontal, one vertical),
- an edge square: $3$ positions,
- the center: $4$ positions.
5. Any three guesses together touch at most $4 + 3 + 3 = 10$ positions. That is fewer than $12$ .
6. So there is always some position that none of your three guesses touches. If the rectangle is there, you get three "no" answers and have not found it.

Four works and three does not, so the answer is $4$ .

The answer is $\boxed{\textbf{(C)}\ 4}$ .

Why this works

"Guarantee a hit" means your guesses must touch every possibility. To find a good set, look for squares that every possibility has to use. To prove you cannot do better, count how many possibilities each guess can touch and show a smaller set cannot touch them all.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

In the worst case every answer is "no" until we hit, so we need a set of squares that meets every possible placement of the rectangle.

There are $12$ placements: $6$ horizontal and $6$ vertical. Each placement pairs two adjacent squares, and adjacent squares are always a corner and an edge-middle square, or an edge-middle square and the center. So every placement contains one of the four edge-middle squares. Guessing those four squares guarantees a hit: $4$ turns suffice.

Three turns cannot suffice. Count how many placements contain a given square: a corner lies in $2$ , an edge-middle square in $3$ , the center in $4$ . Any three squares therefore meet at most $4 + 3 + 3 = 10$ placements, fewer than $12$ . Some placement avoids all three guesses, and the hidden rectangle could be exactly that one, so three "no" answers are always possible.

The answer is $\boxed{\textbf{(C)}\ 4}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 5: More With Combinations (§5.2)
Intermediate Counting & Probability, Chapter 13: Events With States (§13.4)