Maths Olympiad Prep

Library /

Combinatorics Difficulty 6.3 National olympiad Find the answer

Seyed has 998 white coins, a red coin, and an unusual coin with one red side and one white side. He can not see the color of the coins instead he has a scanner which checks if all of the coin sides touching the scanner glass are white. Is there any algorithm to find the red coin by using the scanner at most 17 times?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let us analyze the problem: we have 1000 coins — 998 white coins, one red coin, and one unusual coin with one red side and one white side. The objective is to determine the red coin using a scanner that can check whether all coins placed with one side on the scanner have white sides up. The constraint is to use the scanner at most 17 times.

To solve this problem, we use a strategy based on binary partitioning, aligning with the principles of binary search. Here's a step-by-step breakdown of the strategy:

1. Initial Thoughts:
- We have 1000 coins but the scanner cannot give us direct information about each coin's individual color. Instead, it gives a "Yes" or "No" if all coins on the scanner are white-side up.

2. Utilizing the Scanner:
- Each scan query divided coins into two groups (for binary search purposes).
- We need to identify the non-white coin(s) using as few checks as possible.

3. Strategy Implementation:
- Phase 1: Utilize the binary search method to divide the 1000 coins into approximately equal groups in successive rounds.
- After each scan, rule out halves that show all-white sides.
- Ideally, each scan divides possible candidates roughly in half, resulting in the ability to identify the suspect stack involving unusual coins.

4. Binary Search Analysis:
- log2(1000)=10 \lceil \log_2(1000) \rceil = 10 .
- In theory, with exactly correct implementation, we could locate the red coin in up to 10 checks if the scanner gave perfect half partitions for each process.

5. Checking Unusual Coin:
- Once reduced to a small number, use another set of checks (rotating coins if needed), deducing the exact match of the single red coin through direct color checks or rotation comparisons with the unusual coin.

6. Conclusion:
- According to the limits, it's possible to use the scanner to implement a systematic elimination of possibilities, confirming the red coin's presence with at most 17 checks.

Therefore, it is indeed possible to find the red coin in at most 17 scans, as expected from efficient subdivision strategy such as binary search coupled with rotation checks for ambiguous cases caused by the unusual coin:
YES \boxed{\text{YES}}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.