Maths Olympiad Prep

Library / /26 of 37

Combinatorics Difficulty 8.1 Shortlist Find the answer

A physicist encounters 20152015 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 AA to any other usamon BB. (This connection is directed.) When she does so, if usamon AA has an electron and usamon BB does not, then the electron jumps from AA to BB. 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?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let the physicist label the usamons as 1,2,,20151, 2, \ldots, 2015. Define xi=0x_i = 0 if usamon ii has no electron and xi=1x_i = 1 if it has an electron.

Lemma: If there exists a permutation σSn\sigma \in S_n such that the physicist's knowledge is exactly
xσ(1)xσ(2)xσ(n), x_{\sigma(1)} \le x_{\sigma(2)} \le \cdots \le x_{\sigma(n)},
then firing a diode does not change this fact (though σ\sigma may change).

Proof of Lemma: If the physicist fires a diode from usamon ii to usamon jj where σ(i)<σ(j)\sigma(i) < \sigma(j), then the physicist knows the charge distribution won't change. However, if σ(i)>σ(j)\sigma(i) > \sigma(j), then the charges on ii and jj will swap. Thus, if σ\sigma' is a permutation such that σ(j)=σ(i)\sigma'(j) = \sigma(i) and σ(i)=σ(j)\sigma'(i) = \sigma(j), and otherwise σ(x)=σ(x)\sigma'(x) = \sigma(x), then the physicist's information is of the form
xσ(1)xσ(2)xσ(n). x_{\sigma'(1)} \le x_{\sigma'(2)} \le \cdots \le x_{\sigma'(n)}.
Thus, the lemma is proven. \blacksquare

This implies that if the physicist has information
xσ(1)xσ(2)xσ(n), x_{\sigma(1)} \le x_{\sigma(2)} \le \cdots \le x_{\sigma(n)},
then she can never win, because whatever she does, she'll end up with the information
xσ(1)xσ(2)xσ(n). x_{\sigma'(1)} \le x_{\sigma'(2)} \le \cdots \le x_{\sigma'(n)}.
At this point, if she presents usamons ii and jj with σ(i)<σ(j)\sigma'(i) < \sigma'(j), simply set xi=0x_i = 0 and xj=1x_j = 1, and the physicist loses.

Since the physicist starts with no information, and even if she knew the σSn\sigma \in S_n such that
xσ(1)xσ(2)xσ(n), x_{\sigma(1)} \le x_{\sigma(2)} \le \cdots \le x_{\sigma(n)},
she still couldn't win. Therefore, with no information to start with, she certainly cannot win. \blacksquare

The answer is: No.\boxed{\text{No}}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.