What is a function $f : 2^n \rightarrow n$ such that for each $y \in n$ and $A \in 2^n$ there is $x \in n$ such that $f(\tau(x,A)) = y$?

Question

We first set up some notations and definitions:

• We view each positive integer $n$ as a (particular) set of $n$ elements. We also pick some bijection $\phi_n : 2^n \xrightarrow{\approx} \mathcal{P}(n)$, where the codomain denotes the power set of $n$.
• Define the function $\tau_n : n \times 2^n \rightarrow 2^n$ given by $$ \tau(x,A) = \left\{\begin{matrix} \phi^{-1}( \phi(A) \setminus\{x\} ) \,, & x \in \phi(A) \\ \phi^{-1}( \phi(A) \cup\{x\} ) \,, & x \notin \phi(A) \\ \end{matrix}\right. $$ where the implied subscript on each of the $\tau$'s,$\phi$'s in the above equation is $n$.

Then my question is:

For which positive integers $n$ does there exist a function $f_n : 2^n \rightarrow n$ such that for each $A \in 2^n , y\in n$ there exists $x \in n$ such that $f_n(\tau_n(x,A)) = y$?

And for such $n$, how would we find such a function?

---

For background, the above question arises in considering the following puzzle:

Alice and Bob are in prison, and the warden suggests a deal to them, where they will go free if they can win the following game: 0. First Alice and Bob are allowed to devise a strategy on their own, after being told about this game. However, after they agree to start the game, Alice and Bob may have no further contact. 1. The warden shows Alice an oriented $m\times m$ grid of coins, each of which will be randomly in either the heads or tails position. 2. Next, the warden points to a (randomly chosen) particular coin position, say position $P$, which is seen by Alice. (He doesn't change the coins in any way.) 3. Alice is then required to flip exactly one coin, of her choosing. (She may not avoid flipping any coins.) 4. Alice leaves and Bob is shown the grid of coins. The two have had no contact since Alice saw the coins and Bob has not seen the coins before this. 5. Bob must determine the position $P$, with no further input aside from looking at the coins. If this is accomplished, then Alice and Bob go free. The question is, for which $m$ is a winning strategy possible, and what would be such a strategy? Note: with the above notation, $n=m^2$.

Answer 1

I'll denote $n$ as just cardinality of our set, and will assume that we work with set $\{0, 1, \ldots, n - 1\}$.

If $n$ is power of two, say that $f(B) = \bigoplus\limits_{t \in \phi(B)} t$. Then we have $f(\tau(x, A)) = \bigoplus\limits_{t \in \phi(A) \Delta \{x\}} t = \bigoplus\limits_{t \in \phi(A)} t \oplus x$. Taking $x = y \oplus \bigoplus\limits_{t \in \phi(A)} t$ we get $f(\tau(x, A)) = y$.

This approach doesn't work if $n$ is not power of $2$, because we can get $x \geq n$.

And indeed if $n$ isn't power of $2$, such $f$ doesn't exist.

Let $p(y) = |\{B | f(B) = y|$. Because $\sum\limits_{y = 0}^{n - 1} p(y) = 2^n$ and $n$ doesn't divide $2^n$, we have $p(y_0) < 2^n / n$ for some $y_0$.

For all $A$, let $B(A)$ be such that $f(B(A)) = y_0$ and, for some $x$, $B(A) = \tau(x, A)$. Because there total $2^n$ different values of $A$, and less than $2^n / n$ different values of $B(A)$, there are $n + 1$ different $A_1, A_2, \ldots, A_{n + 1}$ such that $B(A_1) = B(A_2) = \ldots = B(A_{n + 1})$.

But that is impossible, because we have $|\phi(B(A)) \Delta \phi(A)| = 1$, and $\phi(B(A_1)) \Delta \phi(A_i)$ should be different for different $i$, because we can recover $A_i$ from this value as $\phi^{-1}(\phi(B(A_1)) \Delta \phi(A_i) \Delta \phi(B(A_1)))$, but there are only $n$ different 1-element subsets.