Let $ n$ be an even number, and $ S$ be the set of all arrays of length $ n$ whose elements are from the set $ \left\{0,1\right\}$. Prove that $ S$ can be partitioned into disjoint three-element subsets such that for each three arrays $ \left(a_i\right)_{i = 1}^n$, $ \left(b_i\right)_{i = 1}^n$, $ \left(c_i\right)_{i = 1}^n$ which belong to the same subset and for each $ i\in\left\{1,2,...,n\right\}$, the number $ a_i + b_i + c_i$ is divisible by $ 2$.
Problem
Source: Serbia 2003
Tags: induction, conics, ellipse, vector, combinatorics proposed, combinatorics
mto
28.04.2008 13:31
Induction on n
nguyentrang
28.04.2008 17:21
Please show it, not just write like this
darij grinberg
19.05.2008 21:39
When copying problems from other sources, please do take some care - for instance, this one is obviously wrong. It's not $ S$ but $ S\setminus\left\{\left(0,0,...,0\right)\right\}$ that can be partitioned into disjoint three-element subsets with the property you want... At least it works for $ S\setminus\left\{\left(0,0,...,0\right)\right\}$, and it obviously does not work for $ S$ because $ 3\nmid 2^n$. And I am also wondering whether, for $ 4\mid n$, we can partition $ S\setminus\left\{\left(0,0,...,0\right)\right\}$ into five-element subsets of arrays, each with sum $ \left(0,0,...,0\right)$... it's clear how to generalize from here on. "Induction on $ n$" is probably the best hint towards the solution. Just write $ S_n$ instead of $ S$, and think about how you would partition $ S_n\setminus\left\{\left(0,0,...,0\right)\right\}$ into disjoint three-element subsets with the property you want given a "good" partition of $ S_{n - 2}\setminus\left\{\left(0,0,...,0\right)\right\}$ into three-element subsets. Notice that if $ a$, $ b$, $ c$ are three arrays with $ a + b + c = \left(0,0,...,0\right)$, then $ \left(\left(0,1\right)\oplus a\right) + \left(\left(1,0\right)\oplus b\right) + \left(\left(1,1\right)\oplus c\right) = \left(0,0,...,0\right)$; $ \left(\left(1,0\right)\oplus a\right) + \left(\left(1,1\right)\oplus b\right) + \left(\left(0,1\right)\oplus c\right) = \left(0,0,...,0\right)$; $ \left(\left(1,1\right)\oplus a\right) + \left(\left(0,1\right)\oplus b\right) + \left(\left(1,0\right)\oplus c\right) = \left(0,0,...,0\right)$; $ \left(\left(0,0\right)\oplus a\right) + \left(\left(0,0\right)\oplus b\right) + \left(\left(0,0\right)\oplus c\right) = \left(0,0,...,0\right)$, where $ \left(a_1,a_2,...,a_k\right)\oplus\left(b_1,b_2,...,b_l\right)$ stands for $ \left(a_1,a_2,...,a_k,b_1,b_2,...,b_l\right)$. Sorry for the brief reply, but tell me how to install a library in Eclipse and I'll have the time to write proofs on MathLinks. darij
darij grinberg
09.02.2009 14:34
Generalization. Let $ p$ be a prime and $ n$ and $ k$ be two positive integers such that $ n\mid p^k - 1$ and $ n\neq 1$. Prove that the set $ \mathbb{F}_p^k\setminus\left\{0\right\}$ can be partitioned into disjoint $ n$-element subsets such that for each of these subsets, the sum of all vectors in this subset is $ 0$. I am not opening a new topic for this just because it's so obvious if you look at it from the right viewpoint. But I am wondering whether this can be generalized to non-prime $ p$ - a suitable generalization of $ \mathbb{F}_p\setminus\left\{0\right\}$ being used (either $ \left(\mathbb{Z}\slash p\mathbb{Z}\right)\setminus\left\{0\right\}$ or $ \left(\mathbb{Z}\slash p\mathbb{Z}\right)^{\times}$ ?). Any ideas?
As an $ \mathbb{F}_p$-vector space, $ \mathbb{F}_p^k\cong\mathbb{F}_{p^k}$. The field $ \mathbb{F}_{p^k}$ has a primitive root $ \zeta$. Now notice that $ \sum_{i = 0}^{n - 1}\zeta^{i\left(p^k - 1\right)\slash n} = 0$...
darij