Is it possible to permute an unknown binary sequence so that two particular bits are equal?

Question

A blind mathematician is give a $2015$ bit sequence. The mathematician can take any two bits and switch them (so the bit in position $A$ goes to position $B$ and vice-versa). He knows at what position they are and has really good memory, but he has never seen any of them. Can the mathematician do a certain number of steps (at each time he can select which bits he wants to switch) so that he can point at two bits and be absolutely sure they are equal?

This is from the $2015$ USA TST.

Answer 1

You have translated the problem incorrectly.

If A has an electron and B does not, then the electron jumps from A to B.

This is completely different from just swapping two bits!

The swap only happens when Bit A is 1, and bit B is 0, and you can designate which bit is A and which bit is B.

For that, seems like a bubble sort type of approach will do (just an idea, that is).

Answer 2

For your question, the answer is no. The output string is a known permutation of the input string. If we could say two given bits were equal at the end, we could reverse the permutation and say two given bits were equal at the beginning, which we cannot.

Answer 3

Assume that the bits are given to you already sorted (This problem is not harder).

label the bits $b_1,b_2\dots b_{2015}$ where $b_1\leq b_2\dots \leq b_{2015}$

So that the sequence is $b_1b_2\dots b_{2015}$

To make a move the mathematician must select position $A$ and position $B$,so that if $A$ is $1$ and $B$ is zero they swap, and nothing happens otherwise.

At the start the mathematician has the bits ordered, so if the bit at position $A$ is $b_k$ and the bit at position $B$ is $b_n$ with $k<n$ he may safely assume that nothing has happened. Why? If the digits $(A,B)$ are $(1,1),(0,0)$ or $(0,1)$ the outcome will be the same as if nothing had happened, if they are $(1,0)$ then something will change, but notice this is impossible since $k<n$ and the bits are ordered.

I the other case if $k>n$ he can safely assume the swap did occur. Because if the bits are $(0,0),(1,0)$ or $(1,1)$ the outcome is the same as if the swap had indeed occured. The only case where it is different is $(0,1)$ but this cannot happpen because $k>n$.

So after each step he can be sure the current state of the sequence is going to be a specific permutation of $b_1b_2\dots b_k$ which he knows completely. So suppose there comes a time when the mathematician can be sure two bits are equal, he knows which of those two bits they are from the beginning, suppose they are $b_k$ and $b_l$. He then knows $b_k$ and $b_l$ are equal with $k<l$, from here he can assume that the number of zeros is not $k$ since otherwise $b_k$ would be the largest zero, and $b_l$ would be a one. But there is no way we could have deduced there are not $k$ zeros.

Answer 4

Several commenters say you’ve misquoted a contest problem. But regardless, you asked a question that has an answer, and the answer is no.

Call the bits of the original sequence $b_i$, so the original word is $b_1b_2\dots b_{2015}$. A transposition $b_i\leftrightarrow b_j$ turns the sequence into the sequence $b_{\tau(1)}b_{\tau(2)}\dots b_{{\tau(2015)}}$, where $\tau$ is the function that swaps $i$ and $j$ and leaves every other number alone.

After any number transpositions has been applied, the cumulative effect is that the original sequence has been turned into $b_{\sigma(1)}b_{\sigma(2)}\dots b_{{\sigma(2015)}}$, where $\sigma$ is a permutation of the set $\{1,2,\dots,2015\}$.

What’s key here is that because $\sigma$ is a permutation, it’s undoable (invertible). If the mathematician can say for sure that $b_{\sigma(i)}=b_{\sigma(j)}$, it must have been the case that two specific bits in the original sequence were equal (the bits $b_{\sigma^{-1}(i)}$ and $b_{\sigma^{-1}(j)}$, which were in the positions that were eventually swapped around to be in positions $i$ and $j$). But the mathematician can’t have known that those or any two bits in the original sequence were equal.

In the contest problem commenters say you misquoted, the mathematician applies transformations to the bits that can actually overwrite one of them, not just swap their positions. This is a requirement (but not an assurance) for the answer to such a puzzle to be “yes.” Otherwise, whatever the mathematician does is completely undoable, and the answer has to be no if any original sequence was possible.

Added: Actually, I’m not sure now whether overwriting is a requirement for the answer to be yes. See my comment below.