The audience arranges $n$ coins in a row. The sequence of heads and tails is chosen arbitrarily. The audience also chooses a number between $1$ and $n$ inclusive. Then the assistant turns one of the coins over, and the magician is brought in to examine the resulting sequence. By an agreement with the assistant beforehand, the magician tries to determine the number chosen by the audience.
[list][b](a)[/b] Prove that if this is possible for some $n$, then it is also possible for $2n$.
[b](b)[/b] Determine all $n$ for which this is possible.[/list]
### Part (a)

1. **Base Case:**
   We start by showing that the trick is possible for \( n = 2 \). Consider the following strategy: if the first coin is heads, this means the number chosen is \( 1 \); otherwise, it is \( 2 \). The assistant can choose the status of the first coin by either turning that coin or the second one. Thus, \( 2 \in A \).

2. **Inductive Step:**
   Assume the trick is possible for \( m \) and \( n \), i.e., \( m, n \in A \). We need to show that it is possible for \( mn \). 

   - A coin can be seen as an element of \( \mathbb{Z}/2 \), where \( 0 \) means heads and \( 1 \) means tails. Any row of \( n \) coins corresponds to an element of \( (\mathbb{Z}/2)^n \).
   - Assume the assistant is given \( m \cdot n \) coins. Instead of arranging them in a row, he can assume they are arranged in a rectangular shape with sides \( m \) and \( n \), i.e., the given constellation is some \( (a_{i,j})_{i \in [m], j \in [n]} \) with \( a_{i,j} \in \mathbb{Z}/2 \).
   - Define \( b_i := \sum_j a_{i,j} \) and \( c_j := \sum_i a_{i,j} \). Then \( (b_i)_{i \in [m]} \) and \( (c_j)_{j \in [n]} \) are each an arrangement of \( m \) and \( n \) coins, respectively.
   - By assumption, the magician and the assistant can agree on some strategy that encodes a given \( x \in [m] \) in the coins \( (b_i) \) by swapping exactly one of them, say the one with index \( I \). Similarly, they can encode a \( y \in [n] \) by swapping a coin from the \( (c_j) \), say the one with index \( J \).
   - The assistant simply swaps the coin \( a_{I,J} \), which induces exactly the desired swap in the \( (b_i) \) and \( (c_j) \). Thus, the magician can revert this procedure and reconstruct the pair \( (x, y) \in [m] \times [n] \).
   - Fixing any bijection between \( [m] \times [n] \) and \( [mn] \), this shows that the assistant can send the magician a number from \( [mn] \) as well.

Thus, if the trick is possible for \( m \) and \( n \), it is also possible for \( mn \).

### Part (b)

1. **Claim:**
   The trick is only possible for powers of \( 2 \). The sufficiency of this follows inductively from part (a).

2. **Proof:**
   - We say that \( x, y \in (\mathbb{Z}/2)^n \) are neighbors and write \( x \sim y \) if they differ at exactly one position. In terms of rows of coins, this means they differ by exactly one swap of a single coin. Every \( x \) has exactly \( n \) neighbors.
   - For the magician and the assistant to be able to do the trick, they need to define a function \( f: (\mathbb{Z}/2)^n \to [n] \) such that for any given \( x \in (\mathbb{Z}/2)^n \) and any \( m \in [n] \), there is a \( y \sim x \) with \( f(y) = m \).
   - Since every \( x \) has exactly \( n \) neighbors and there are always \( n \) possible \( m \) to be encoded, every \( x \) must have exactly one neighbor for each \( m \). Thus, the following construction is well-defined:
     - For any \( x \in (\mathbb{Z}/2)^n \), there is exactly one neighbor \( y \) such that \( f(y) \equiv f(x) + 1 \mod n \); we call \( y = s(x) \) the successor of \( x \). Note that \( s \) is bijective.
   - Starting at any \( x_0 \in (\mathbb{Z}/2)^n \), we get a sequence \( x_i \) by \( x_{i+1} := s(x_i) \). This sequence must eventually become periodic, and by bijectivity, it will reach \( x_0 \) again. Thus, there is some period \( p > 0 \) with \( x_p = x_0 \).
   - A trivial induction argument gives \( f(x_i) \equiv i + f(x_0) \mod n \), implying \( p \equiv f(x_p) - f(x_0) = 0 \mod n \). Thus, \( p \) is divisible by \( n \).
   - These "cycles" divide \( (\mathbb{Z}/2)^n \) into equivalence classes, each the size of a multiple of \( n \), thus implying \( n \mid 2^n \). This means \( n \) must be a power of \( 2 \).

\(\blacksquare\)

The final answer is \( \boxed{ n } \) must be a power of \( 2 \).