Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Assume that you have a set S of having 2^2 elements first, let S={0,1,2,3} Then the desired 2 partitions would be 1-{{0,1},{2,3}} 2-{{0,2},{1,3}} 3-{{0,3},{1,2}}

If S={0,1,2,3,4,5,6,7} having 2^3 elements then similarly the 2 partitions would be

1- {{0,1},{2,3},{4,5},{6,7}} 2- {{0,2},{1,3},{4,6},{5,7}} 3- {{0,3},{1,5},{2,6},{4,7}} 4- {{0,4},{1,6},{2,5},{3,7}} 5- {{0,5},{1,4},{2,7},{3,6}} 6- {{0,6},{1,7},{2,4},{3,5}} 7- {{0,7},{1,2},{3,4},{5,6}}

So it seems that for S having 2^n elements the initial table would like

1: {{0,1},{2,3},{4,5},{6,7},...,{(2^n)-2,(2^n)-1}} 2: {{0,2},... } . . . (2^n)-1: {{0,(2^n)-1},... }

I am just wondering whether there is an direct approach to generate the above table for a given n.

Thanks

share|improve this question
    
I removed the set-theory tag. –  Joel David Hamkins May 15 '10 at 19:04

1 Answer 1

up vote 1 down vote accepted

I presume you want $2^n-1$ partitions of ${0,\ldots,2^n-1\}$ into parts of size two so that each possible pair occurs exactly once in a partition. You can do this as follows. Write the numbers in question base $2$. Then each can be represented by $n$ binary digits going from $00\cdots0$ to $11\cdots 1$. Define an operation $\oplus$ on these as follows: we obtain $a\oplus b$ by add corresponding digits in $a$ and $b$ modulo $2$. For example $11\oplus 14=5$ as in base $2$, $11$ and $14$ are $1011$ and $1110$, and $1+1$ is $0$ mod $2$, $0+1$ is $1$ mod $2$, $1+1$ is $0$ mod $2$ and $1+0$ is $1$ mod $2$ so in binary $a\oplus b$ is $0101$ which is $5$. The operation $\oplus$ is sometimes known as "nim addition" as it is used in the analysis of the game nim.

To get the $j$-th partition where $1\le j\le 2^n-1$ we just pair off $a$ and $a\oplus j$. So for $n=4$, the partition for $j=5$ is $\{ \{0,5 \}, \{1,4 \}, \{2,7 \}, \{3,6 \}, \{8,13 \}, \{9,12 \}, \{10,15 \}, \{11,14 \} \}$ as $0\oplus 5=5$, $1\oplus 5=4$, $2\oplus 5=7$ etc.

share|improve this answer
    
Thanks very much for the detailed explanation. –  Burak May 15 '10 at 18:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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