| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3650 |
| 2 | Benq | 3582 |
| 3 | Geothermal | 3570 |
| 3 | orzdevinwang | 3570 |
| 5 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3532 |
| 8 | Radewoosh | 3522 |
| 9 | Um_nik | 3483 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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 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.
and p0 = 0
Let
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.
We can prove that for every nonnegative integer m < = n we canchoose 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.