Problem 1: EGZ theorem

by henderson, Feb 11, 2016, 5:43 PM

$\bf\color{red}Problem \ 1 \$ $n$ is a power of $2.$ Prove that among $2n-1$ numbers there are $n$ numbers such that their sum is divisible by $n.$
$\bf\color{red}Solution$ $n=1,2$ is trivial.
Suppose inductive hypothesis at $2,n$ , and let's prove on $2n$ .
Among 4n-1 numbers, there are n of them such that their sum is divisible by n. Let it $na$ .
Among rest of them (3n-1 integers), there are n of them such that their sum is divisible by n. Let it $nb$ .
Among rest of them (2n-1 integers), there are n of them such that their sum is divisible by n. Let it $nc$ .
Among $a,b,c$ , there are 2 of them such that their sum is divisible by 2. Let it $a+b$ .
Therefore $2n|n(a+b)$ , as desired.

$\color{blue}\textbf{Comment.}$ The above problem is a special case of $\color{red}\textbf{EGZ theorem.}$
$\color{red}\textbf{EGZ theorem.}$ Each set of $2n-1$ integers contains some subset of $n$ elements the sum
of which is a multiple of $n.$

This post has been edited 11 times. Last edited by henderson, Sep 12, 2016, 2:50 PM

Comment

0 Comments

Submit

Math Path

Problem 1: EGZ theorem

by henderson, Feb 11, 2016, 5:43 PM

0 Comments