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 \(2n-1\) non-negative integers. Every number except one appeared twice. The memory that contain the integers are read only. Can you use \(O(1)\) additional space to find the integer that only appeared once?

The solution was the xor function.

If \(a_j\) is the number that didn't appear twice, \[ \bigoplus_{i=1}^{2n-1} a_i = a_j \]

The reason was because xor have the following property. \(a \oplus b = b \oplus a\), \(a \oplus a = 0\) and \(0 \oplus a = a\) for all \(a,b\geq 0\). One can see \((\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 \(G\) such that \(g^2 = 1\) for all \(g\in G\) is \((\mathbb{N}, \oplus)\) up to isomorphism.


See the answer by Pete Clark.

Posted by Chao Xu on 2011-06-11.
Tags: group theory, puzzle.