Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the recent IMC 2011, the last problem of the 1st day (no. 5, the hardest of that day) was as follows:

We have $4n-1$ vectors in $F_2^{2n-1}$: $\{v_i\}_{i=1}^{4n-1}$. The problem asks : Prove the existence of a subset $A \subseteq [4n-1], |A| = 2n$ such that $\sum_{i \in A} v_i = \vec{0}$.

Is there a solution that uses the Chevalley-Warning theorem about divisibility of number of solutions by the field's characteristic? The statement of the problem seems as a "xor" analog of Erdos-Ginzburg-Ziv, that is usually proved by Chevally-Warning.

My idea is to formulate homogeneous polynomial equations in $a_1,\cdots,a_{4n-1} \in F_2$: $P_j(\vec{a}) = (\sum a_i v_i)_j$ for $1 \le j \le 2n-1$. Let $A(\vec{a}) = \{ i | a_i = 1\}$ and $g(\vec{a}) = |A(\vec{a})|$ (we want to choose $A = A(\vec{a})$ for a solution $a$ of the system).

Ideas for completing the solution:

  • We can also create $Q_{k}(\vec{a}) = $ Symmetric polynomial of degree $2^k$ = $a_1 \cdots a_{2^k} + \cdots$. We notice that $Q_k(a) = \binom{g(\vec{a})}{2^k}$. By Lucas's Theorem, mod 2 we have $\binom{m}{2^k} = $ k'th digit of $m$ in base-$2$. So we choose the equations $Q_k(a) = \binom{2n}{2^k}$ mod 2.

The problem is that we get $\sum deg(Q_k) \ge 2n$ (sum over number of digits of $4n-1$). Also, $0$ is not a trivial solution.

  • Another idea was to define the equations $R_i(a) = a_{2i-1} + a_{2i} - a_{2i+1} - a_{2i+2} = 0, 1 \le i \le 2n$. A solution implies that $a_{2i-1} + a_{2i}$ is constant. If it is $1$, we get that from each pair of even and odd vector, one is chosen - $2n$ vectors in total. But it has some holes.

  • Another idea is to create equations that force $g(\vec{a}) = 0$ mod n, so $\vec{0}$ is a trivial solution, and another solution would imply that a $A$ exists of size $n, 2n$ or $3n$.

A nice observation is that one of the vectors is (wlog) $\vec{0}$ (can be assumed since $2n$ is even, so replacing $v_i$ by $v_i - v_{1}$ is fine).

If you have idea of how to use the theorem, and examples in general of its non-trivial uses - it would be welcome.

share|improve this question
    
I guess $F_2^{2-1}$ should be $F_2^{2n-1}$. (I don't want to edit it yet since it's <6 characters.) –  Srivatsan Jul 31 '11 at 17:58
    
Ofir: could you please reread your question, there are some obvious typos, but maybe some less obvious ones. –  Peter Patzt Jul 31 '11 at 19:12
    
I've fixed the typos and added an idea, thanks. –  Ofir Aug 1 '11 at 15:41
    
(Re: analog of Erdos-Ginzburg-Ziv) a variant of Kemnitz's problem, I'd say... –  Grigory M Aug 19 '11 at 11:01

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.