The Art Gallery Guardian

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


I once saw the following puzzle:

Problem1

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\displaystyle \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.

Theorem2

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

Proof

See the answer by Pete Clark.

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