Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.