ZOJ Problem Set - 1783
It is said that court intrigues started with people lying about other people, and then lying about other people's lying, and so it went. The intriguers constantly looked for scapegoat who inevitably proved to be someone with the least power, though not always the least morality.
We have faced a similar problem, but this time, in our malfunctioning spacecraft! There are a number of units in the spacecraft. The units are so reliable that it would surprise us very much if more than one unit were faulty. If more than one is faulty, we would lose the probe, so we are sure that exactly one unit is faulty in our spacecraft.
We know that each unit checks exactly two others, and each unit will be checked by at least one other unit. A good unit will give accurate diagnosis of the units it checks. For example, if unit X is good and it says that Y is faulty and Z is good, then, in fact, Y is faulty and Z is good. However, a bad unit is unreliable. So, if unit X is faulty and makes the same statements, then Y may or may not be good, and Z may or may not be good either. Note that a unit cannot check itself.
Now suppose that you have the reports from all units and your duty is to find which unit is indeed faulty.
Source: Asia 2002, Tehran (Iran)