### LashaBukhnikashvili's blog

By LashaBukhnikashvili, 7 years ago, I want to prove that for every 200 numbers,it can be choose 100 number which sum will divisible by 100.

I also thinks that,it will be correct: for every n numbers,we can choose x number which sum will divisible by x,if x<=n/2+n%2

can someone help me to prove them(of course,if 2th will be correct)? (sorry for my bad english) math, Comments (6)
 » That's because all possible mods exist more than one time,i dont know the formal proof though
•  » » no the numbers is not consecutively
 » 7 years ago, # | ← Rev. 2 →   First fact is right. Try searching for Erdős–Ginzburg–Ziv theorem (if there are 2n - 1 elements in multiset with elements from , there are n with zero sum).
•  » » Thank,I found it ;)
 » Suppose we have a sequence ai consisting of n integers. We can prove that for every nonnegative integer m <  = n we can choose at most m numbers from the sequence such that their sum is divisible by m. Let and p0 = 0 Take any m consecutive numbers from the sequence. According to pigeonhole principle, there will be at least two indexes L and R such that pL = pR. The sum of numbers with indexes from L + 1 to R will be divisible by m.
•  » » 7 years ago, # ^ | ← Rev. 7 →   We can prove that for every nonnegative integer m <  = n we can choose at most m numbers from the sequence such that their sum is divisible by m.Problem requries exactly 100 numbers, not less. So, it is Erdos-Ginzburgh-Ziv Theorem.