Competition problem — Combinatorics

Library / /21 of 24

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

Ten cups lie upside down in a line. It is known that pennies lie under two of the cups which are consecutive in the line. Choosing several of the cups, you may ask for the total number of coins under them. Is it possible to determine the positions of the pennies by asking two such questions, without knowing the answer to the first question before making the second?

Solution

Solution:

The answer is yes; here is one strategy that works. On the first turn choose the cups $1, 4, 5, 6, 7$ , and on the second turn choose $1, 6, 7, 8, 9$ . Depending on the locations of the coins, the answers will be:

Coins	$1,4,5,6,7$	$1,6,7,8,9$
1,2	1	1
2,3	0	0
3,4	1	0
4,5	2	0
5,6	2	1
6,7	2	2
7,8	1	2
8,9	0	2
9,10	0	1

Since each possible location for the coins gives a different pair of answers, the answers are enough to reconstruct the location of the coins.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.