Skip to main content
OlympiadHQ

Browse · MathNet

Print

66th Czech and Slovak Mathematical Olympiad

Czech Republic counting and probability

Problem

There are 100 diamonds on display; 50 of them genuine and 50 of them fake. Peter is the only person able to distinguish them. Whenever you point to three diamonds, Peter will cover one of them and (truthfully) tell you, how many of the remaining two are genuine. Determine if it is possible to find the 50 genuine diamonds, no matter how Peter answers your queries. (Michal Rolínek, Josef Tkadlec)
Solution
We prove it is impossible. Let Peter pick one genuine diamond and one fake diamond . Whenever the triplet of diamonds being pointed to contains both and , Peter covers the third diamond (and truthfully answers “One.”). Whenever the triplet contains precisely one of , , Peter covers it. Otherwise he covers any diamond. None of Peter's answers ever distinguishes between and hence it is impossible to say which of , is the genuine one and which is the fake one.
Final answer
No, it is impossible.

Techniques

Games / greedy algorithms