Browse · MathNet
PrintAutumn tournament
Bulgaria counting and probability
Problem
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, of Lady Gilmore's servants, whom we will refer to as , , , , , , 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, claims to have met , , , in the room; claims to have met , , , , ; claims to have met , , ; claims to have met , , ; claims to have met , , , ; claims to have met , and claims to have met , , . Inspector Goodenough concluded that one of the servants was lying. Who is he?
(Lyuben Lichev)
(Lyuben Lichev)
Solution
We will first prove the following lemma.
Lemma. Let , , and be four of the servants. If it is known that the pairs ; ; and were in the room together at some point, then one of the pairs and also detected each other.
Proof of Lemma. Let us assume, without community restriction, that and were not in the room together, and left the room before (the other cases are analogous). Then, and were in the room together in the period between 's departure and 's arrival.
Notice that , , , satisfy the condition of the lemma, but none of and intersect. The same goes for , , , . The only common element of these pairs is . 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 , enter , exit , enter , enter , exit , enter , exit , enters, exits, exits, exits.
Lemma. Let , , and be four of the servants. If it is known that the pairs ; ; and were in the room together at some point, then one of the pairs and also detected each other.
Proof of Lemma. Let us assume, without community restriction, that and were not in the room together, and left the room before (the other cases are analogous). Then, and were in the room together in the period between 's departure and 's arrival.
Notice that , , , satisfy the condition of the lemma, but none of and intersect. The same goes for , , , . The only common element of these pairs is . 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 , enter , exit , enter , enter , exit , enter , exit , enters, exits, exits, exits.
Final answer
A
Techniques
LogicAlgorithmsOther