![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaВторой день очень раздражает, что не могу доказать:
N - степень двойки (возможно, это условие лишнее, не уверен). Даны 2N-1 целых чисел. Доказать, что можно выбрать ровно N из них так, что сумма выбранных делится на N.
Кажется, что должно быть просто, к нескольким частным случаям подобрался, полностью - никак. Очень неприятное ощущение того, что полностью проржавели мозги.
Комментарии читать не буду, а буду пытаться решать.
N - степень двойки (возможно, это условие лишнее, не уверен). Даны 2N-1 целых чисел. Доказать, что можно выбрать ровно N из них так, что сумма выбранных делится на N.
Кажется, что должно быть просто, к нескольким частным случаям подобрался, полностью - никак. Очень неприятное ощущение того, что полностью проржавели мозги.
Комментарии читать не буду, а буду пытаться решать.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2008-05-30 08:41 pm (UTC)Для N=1 верно (любое целое число делится на 1)
Переход от N-1 к N:
Пока остается хотя бы три числа всегда можно найти пару, которая дает четную сумму. Нашли - отложили. Итого можно отложить N-1 пару с четными суммами. Делим каждую сумму на два, применяем ндукционное предположение. Значит, можно найти N/2 пар, полусуммы которых в сумме делятся на N/2. А значит сумма этих парных сумм делится на N. То есть сумма N участников этих пар делится на N. Что и требовалось доказать.