Блог пользователя LashaBukhnikashvili

One more Math problem

Автор LashaBukhnikashvili, 10 лет назад, По-английски

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)

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 7   Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить