Team Selection Test

The answer is $2^n-3\cdot 2^{n/3}+2$ for $n=3k$ and $2^n$ for $n\ne 3k$. The number of possible box choices is $2^n$. Let us examine cases when two or more different choices produce the same ball distribution. If different choices $C_1$ and $C_2$ produce the same distribution then these choices should not coincide on any two consecutive boxes. Otherwise $C_1$ and $C_2$ will coincide for all remaining boxes. Suppose that the boxes are numbered in clockwise order as $1,2,\dots ,n$ and the sum $i+j$ is defined in (mod $n$). If in choice $C$ box $m$ is chosen we write $C(m)=X$, otherwise we write $C(m)=Y$. Thus, for two consecutive boxes $m,m+1$ there are four possibilities $XX,XY,YX,YY$. Note that if $C_1(m)=X$, $C_1(m+1)=X$ and $C_2(m)=Y$, $C_2(m+1)=Y$ then $C_1$ and $C_2$ can not produce the same distribution, since box $m$ will contain different number of balls for $C_1$ and $C_2$. for these two choices. Therefore, there are at most three pairwise different choices producing the same distribution. It can be readily shown that if $n$ is a multiple of $3$ then there are only two triples producing the same distribution: $$C_1=\dots XXXXXXXXX\dots$$ $$C_2=\dots XXXXXXXXX\dots (1)$$ $$C_3=\dots XXXXXXXXX\dots$$ $$C_1=\dots YYYYYYYYYY\dots$$ $$C_2=\dots YYYYYYYYY\dots (2)$$ $$C_3=\dots XYYYYYYYYY\dots$$ In each of this two cases each choice can be obtained by shifting of any other one. Evidently if $n$ is not a multiple of $3$ there is no any such triple.

Now let us examine the cases when exactly two choices produce the same distribution. Note that for $C_1$ and $C_2$ there are two consecutive boxes $m$ and $m+1$ such that $C_1(m)\ne C_2(m)$ and $C_1(m+1)\ne C_2(m+1)$. Otherwise for some $m$ we have $C_1(m)=C_2(m)$, $C_1(m+2)=C_2(m+2)$, $C_1(m+4)=C_2(m+3)$, ... and consecutively $C_1$ will coincide with $C_2$. W.L.O.G. let $C_1(m)=X$, $C_1(m+1)=Y$ and $C_2(m)=Y$, $C_2(m+1)=X$. Then we get $C_1(m+2)=C_2(m+2)=Z$, where $Z$ is either $X$ or $Y$. Similarly, $C_1(m+3)=X$, $C_1(m+4)=Y$ and $C_2(m+3)=Y$, $C_2(m+4)=X$. Then we get $C_1(m+5)=C_2(m+5)=Z$, where $Z$ is either $X$ or $Y$. Continuing this way we get that starting from box $m$ the choices $C_1$ and $C_2$ are $XY{Z}_{1}XY{Z}_{2}XY{Z}_{3}XY{Z}_4$... and $YX{Z}_{1}YX{Z}_{2}YX{Z}_{3}YX{Z}_4$,... respectively. If $n$ is not multiple of $3$ then we can not cyclically close this chain and will get a contradiction. Thus, if $n$ is not a multiple of $3$ there are no different choices producing the same distribution and the answer is $2^n$. If $n$ is a multiple of $3$ then the positions of $Z_i$ can be determined in $3$ ways. If for some choice $Z_1=Z_2=Z_3$... then we get one of the six choices from (1) and (2). Therefore, for each of $3\cdot (2^{n/3}-2)\cdot 2$ choices there exists exactly one other choice producing the same distribution. Therefore, the answer is $$2^n-6-6\cdot (2^{n/3}-2)+\frac{6}{3}+\frac{6}{2}\cdot (2^{n/3}-2)=2^n-3\cdot 2^{n/3}+2.$$