Let $n$ be an even natural number and let $A$ be the set of all non-zero sequences of length $n$, consisting of numbers $0$ and $1$ (length $n$ binary sequences, except the zero sequence $(0,0,\ldots,0)$). Prove that $A$ can be partitioned into groups of three elements, so that for every triad $\{(a_1,a_2,\ldots,a_n), (b_1,b_2,\ldots,b_n), (c_1,c_2,\ldots,c_n)\}$, and for every $i = 1, 2,\ldots,n$, exactly zero or two of the numbers $a_i, b_i, c_i$ are equal to $1$.
Problem
Source: Bulgarian National Olympiad 2012 Problem 4
Tags: induction, abstract algebra, group theory, combinatorics proposed, combinatorics
test20
22.05.2012 19:12
By induction on $k=n/2$. The statement for $k=1$ is clear. In the inductive step from $k$ to $k+1$, first partition the non-zero sequences ending in 00: according to the inductive assumption after removing the 00. Then partition the remaining sequences: for every sequence $s$ of length $k$, put $s01$ togther with $s10$ and $s11$.
dgrozev
23.05.2012 12:31
test20 wrote: ... Then partition the remaining sequences: for every sequence $s$ of length $k$, put $s01$ togther with $s10$ and $s11$. Why? $s01,\, s10,\, s11$ do not satisfy the requirement "zero or two of the numbers $a_i,b_i, c_i$ are equal to 1". Nevertheless, the same idea works. If $\{a,b,c\}$ is a triad for $k=n/2$ we do the inductive step by generating $4$ triad for $k+1$: $\{a00,b00,c00\},\, \{a01,b10,c11\},\, \{b01,c10,a11\},\, \{c01,a10,b11\}$.
teps
24.05.2012 15:15
The problem can be translated to decimal notation, and the statement is then equivalent to proving that you can always partition first $4^n-1$ natural numbers into groups of three, say $(a,b,c)$ so that every group fulfills: $a+b=c$.
darij grinberg
28.05.2012 20:07
See http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=202317 for this and something more general. And see http://mathoverflow.net/questions/88957/zero-sum-partition-of-an-abelian-group for a possible but unsolved generalization. teps: I don't think your restatement really is equivalent. Decimal or binary addition is not XOR.
teps
28.05.2012 20:25
I'm not 100% sure that it is equivalent, but if you prove the statement I proposed, then the solution of this problem also fallows. And I didn't transfer binary addition to decimal. Here is an example for $n=2$: -->$1+6=7\implies (0001,0110,0111)$ are good, -->$2+12=14\implies (0010,1100,1110)$ are good, -->$3+8=11\implies (0011,1000,1011)$ are good, -->$4+9=13\implies (0100,1001,1101)$ are good, -->$5+10=15\implies (0101,1010,1111)$ are good.