A physicist encounters atoms called usamons. Each usamon either has one electron or zero electrons, and the physicist can't tell the difference. The physicist's only tool is a diode. The physicist may connect the diode from any usamon to any other usamon . (This connection is directed.) When she does so, if usamon has an electron and usamon does not, then the electron jumps from to . In any other case, nothing happens. In addition, the physicist cannot tell whether an electron jumps during any given step. The physicist's goal is to isolate two usamons that she is sure are currently in the same state. Is there any series of diode usage that makes this possible?
Solution
Let the physicist label the usamons as . Define if usamon has no electron and if it has an electron.
Lemma: If there exists a permutation such that the physicist's knowledge is exactly
then firing a diode does not change this fact (though may change).
Proof of Lemma: If the physicist fires a diode from usamon to usamon where , then the physicist knows the charge distribution won't change. However, if , then the charges on and will swap. Thus, if is a permutation such that and , and otherwise , then the physicist's information is of the form
Thus, the lemma is proven.
This implies that if the physicist has information
then she can never win, because whatever she does, she'll end up with the information
At this point, if she presents usamons and with , simply set and , and the physicist loses.
Since the physicist starts with no information, and even if she knew the such that
she still couldn't win. Therefore, with no information to start with, she certainly cannot win.
The answer is: