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)

That's because all possible mods exist more than one time,i dont know the formal proof though

no the numbers is not consecutively

First fact is right. Try searching for Erdős–Ginzburg–Ziv theorem (if there are 2

n- 1 elements in multiset with elements from , there arenwith zero sum).Thank,I found it ;)

Suppose we have a sequence

a_{i}consisting ofnintegers. We can prove that for every nonnegative integerm< =nwe can choose at mostmnumbers from the sequence such that their sum is divisible bym.Let and

p_{0}= 0Take any

mconsecutive numbers from the sequence. According to pigeonhole principle, there will be at least two indexesLandRsuch thatp_{L}=p_{R}. The sum of numbers with indexes fromL+ 1 toRwill be divisible bym.`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

exactly100 numbers, not less. So, it is Erdos-Ginzburgh-Ziv Theorem.