Competition problem — Combinatorics

Library / /12 of 14

Combinatorics Difficulty 6.5 National olympiad Prove it Bulgaria

In the house of the wealthy Lady Gilmore, one of her most precious possessions has been stolen: her pearl necklace. The task of unraveling the mystery fell on the shoulders of Inspector Goodenough. He had the following information: on the day of the theft, $7$ of Lady Gilmore's servants, whom we will refer to as $A$ , $B$ , $C$ , $D$ , $E$ , $F$ , $G$ for the confidentiality of the investigation, entered the room with the necklace. Each claimed to have been in the room only once for an unspecified period of time. Additionally, $A$ claims to have met $B$ , $C$ , $F$ , $G$ in the room; $B$ claims to have met $A$ , $C$ , $D$ , $E$ , $F$ ; $C$ claims to have met $A$ , $B$ , $E$ ; $E$ claims to have met $B$ , $C$ , $F$ ; $F$ claims to have met $A$ , $B$ , $D$ , $E$ ; $G$ claims to have met $A$ , $D$ and $D$ claims to have met $B$ , $F$ , $G$ . Inspector Goodenough concluded that one of the servants was lying. Who is he?

(Lyuben Lichev)

Solution

We will first prove the following lemma.

Lemma. Let $X$ , $Y$ , $Z$ and $T$ be four of the servants. If it is known that the pairs $X, Y$ ; $Y, Z$ ; $Z, T$ and $T, X$ were in the room together at some point, then one of the pairs $X, Z$ and $Y, T$ also detected each other.

Proof of Lemma. Let us assume, without community restriction, that $Y$ and $T$ were not in the room together, and $Y$ left the room before $T$ (the other cases are analogous). Then, $X$ and $Z$ were in the room together in the period between $Y$ 's departure and $T$ 's arrival.

Notice that $A$ , $C$ , $E$ , $F$ satisfy the condition of the lemma, but none of $A, E$ and $C, F$ intersect. The same goes for $A$ , $B$ , $D$ , $G$ . The only common element of these pairs is $A$ . It remains to be ascertained that it is possible that all the other pairs met, as they claim, by entering exactly once. This is possible with the following sequence of entries and exits: enter $G$ , enter $D$ , exit $G$ , enter $B$ , enter $F$ , exit $D$ , enter $E$ , exit $F$ , $C$ enters, $B$ exits, $E$ exits, $C$ exits. $■$

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 and solution reproduced as published; topic and difficulty added by this site.