The Art Gallery Guardian

Countably infinite groups such that every element has order 2 are isomorphic

I once saw the following puzzle:


Given a list of 2n12n-1 non-negative integers. Every number except one appeared twice. The memory that contain the integers are read only. Can you use O(1)O(1) additional space to find the integer that only appeared once?

The solution was the xor function.

If aja_j is the number that didn’t appear twice, i=12n1ai=aj \bigoplus_{i=1}^{2n-1} a_i = a_j

The reason was because xor have the following property. ab=baa \oplus b = b \oplus a, aa=0a \oplus a = 0 and 0a=a0 \oplus a = a for all a,b0a,b\geq 0. One can see (N,)(\mathbb{N}, \oplus) is a abelian group.

Is this the unique function to solve this problem?

In some way, yes. Here is a theorem.


The countably infinite group GG such that g2=1g^2 = 1 for all gGg\in G is (N,)(\mathbb{N}, \oplus) up to isomorphism.

See the answer by Pete Clark for the proof.

Posted by Chao Xu on .
Tags: group theory, puzzle.