AoPS - Problem

Source: Czech and Slovak Olympiad 2017, National Round, III A p1

Tags: combinatorics, game, game strategy

parmenides51

02.02.2020 21:54

There are $100$ diamonds on the pile, $50$ of which are genuine and $50$ false. We invited a peculiar expert who alone can recognize which are which. Every time we show him some three diamonds, he would pick two and tell (truthfully) how many of them are genuine . Decide whether we can surely detect all genuine diamonds regardless how the expert chooses the pairs to be considered.

I will prove that the expert can choose the pairs in a way such that we can never determine all the genuine diamonds. Before we start giving 3-tuples to the expert, let him pick one pair of a genuine and a false diamond $(d_i, d_j)$ out of all $100$ diamonds. If we give a 3-tuple with both $d_i, d_j$, the expert will choose the pair $(d_i, d_j)$ and reveal the number of genuine diamonds that this pair contains ($1$). If the 3-tuple contains at most one of $d_i, d_j$, then the expert will choose the pair that does not contain $d_i$ or $d_j$. This way, we will never be able to identify which diamond among $d_i, d_j$ is genuine, which renders impossible to detect all genuine diamonds. The proof is complete.