2
$\begingroup$

I was looking at this problem, and I have a solution for a finite board with $2^n$ squares, that I want to extend to a countably infinite board.

Label the squares from $0$ to $2^n-1$. Consider the set of all squares with a $1$ at the $i$th position in their binary expansion. If the number of heads in the set is odd, let $p(i) = 2^i$, else $0$. Compute $X = \sum_{i = 0}^n p(i)$.

XOR the index of the Magic Square with your result, and flip the coin with the resulting index. Thus, when your friend enters the room, when he computes $X^\prime$, by the same approach, he will get the correct index.

When I try to extend this to an infinite board, I have trouble with defining parity. There are many functions that map $\{0, 1\}^\infty$ to $\{0, 1\}$, so it doesn't seem unreasonable that there is such a function that obeys one rule: flipping any bit changes the value. Is there?

And would this strategy still work on an infinite board, assuming your friend can examine infinite coins? (Pretty sure the devil wins when your friend must examine arbitrarily large, but finite number)

Pardon the abuses of notation; I suspect there's a more accurate way to write "all infinite bitstrings" than putting an $\infty$ up there.

$\endgroup$
2
$\begingroup$

There are such functions, but I'm not sure if one can actually construct one. To obtain such a function, note that $\{0,1\}$ with addition and multiplication is the field $\mathbb F_2$. Then $\mathbb F_2^{\mathbb N}$, the sets infinite bitstrings is a vector space over $\mathbb F_2$. The set $B' := \{e_n \mid n \in \mathbb N\}$ of the unit vectors $e_n = (0, \ldots, 0, 1, 0, \ldots)$ forms a linear independent subset. Choose a basis $B\supset B'$ of $\mathbb F_2^{\mathbb N}$. Define $f$ on the basis by $$ f\colon b \mapsto \begin{cases} 1, & b = e_n \text{ for some } n \in \mathbb N\\ 0, & b \in B\setminus B'\end{cases} $$ extend $f$ linearly to a $\mathbb F_2$-linear function $f \colon \mathbb F_2^{\mathbb N} \to \mathbb F_2$.

Then $f$ is as wished: Flipping the $n$-th bit corresponds to adding $e_n$ and for $x \in \mathbb F_2^{\mathbb N}$ we have $$ f(x + e_n) = f(x) + f(e_n) = f(x) + 1 = \begin{cases} 1, & f(x) = 0\\ 0, & f(x) = 1.\end{cases} $$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ NB. The non-constructive bit is "Choose a basis $B \supset B'$ of $\Bbb F_2^{\Bbb N}$." $\endgroup$ – Lord_Farin Jun 19 '13 at 7:06
  • $\begingroup$ Why isn't $B^\prime$ a basis of $F_2^\mathbb{N}$ itself? All elements are independent, and I think they span the space. For an arbitrary $x$ in $F_2^\mathbb{N}$, just add $1 \cdot e_n$ if the $n$th bit of $x$ is $1$. What's the catch I'm missing? $\endgroup$ – Henry Swanson Jun 19 '13 at 16:02
  • $\begingroup$ @HenrySwanson For $B'$ to be a basis, each element of $\mathbb F_2^{\mathbb N}$ had to be a linear combination - that is, by definition a finite sum - of elements of $B'$. But each linear combination of elements from $B'$ has all but a finite number of entries equal $0$. So $B'$ spans $\{x \in \mathbb F_2^{\mathbb N} \mid \exists N \,\forall n \ge N \,: x_n = 0\}$. $\endgroup$ – martini Jun 19 '13 at 21:36
  • $\begingroup$ Ah. So span implies a finite combination? And there are such functions, but there's no way you and your friend could actually create one? $\endgroup$ – Henry Swanson Jun 19 '13 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.