2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Комбинаторика. Есть решение, но не понять его.
Сообщение24.01.2016, 17:39 
В ряд выписано $100$ натуральных чисел. Доказать, что найдутся несколько подряд, сумма которых делится на $100$.

Решение
Рассмотрим числа $1, 1 + 2, ..., 1 + 2 +...+ 100$.
1 случай: одно из указанных чисел делится на $100$ - оно и есть искомое.
2 случай: ни одно из чисел не делится на $100$. Тогда при делении на $100$ мы получим $99$ остатков от $1$ до $99$, а так как мы имеем $100$ чисел (принцип Дирихле), то обязательно найдутся два числа с одинаковыми остатками. Разность чисел с одинаковыми остатками дадут нужную сумму.

Я так понимаю, что числа $1, 1 + 2, ..., 1 + 2 +...+ 100$. образуют множество потенциальных остатков от деления на $100$ нескольких подряд идущих чисел. Верно ли?

Не очень очевиден случай один. Несколько подряд включает в себя "одно" число "подряд"?

Второй случай не очевиден. Причем тут разность. Нам же нужна сумма. Или я что-то не так понимаю?

 
 
 
 Re: Комбинаторика. Есть решение, но не понять его.
Сообщение24.01.2016, 17:58 
Аватара пользователя
Одно число считается тоже «подряд».

Только почему числа от $1$ до $100$? Наверняка задача ставилась для произвольных натуральных чисел $a_1, a_2, ..., a_{100}$. В условии сказано «100 натуральных чисел», но не сказано «первых». Ниже я подправлю Вашу цитату с учётом этого.
mr.tumkan2015 в сообщении #1093876 писал(а):
Я так понимаю, что числа $a_1, a_1 + a_2, ..., a_1 + a_2 +...+ a_{100}$. образуют множество потенциальных остатков от деления на $100$ нескольких подряд идущих чисел. Верно ли?
Они не обязательно дают все возможные остатки при делении на 100. Просто одно из двух:
$\bullet$ либо эти сто сумм (одно число тоже сумма) дают 100 разных остатков — но тогда один из них нулевой;
$\bullet$ либо различных меньше 100, тогда хотя бы у двух сумм остатки одинаковые, тогда построим их разность.

mr.tumkan2015 в сообщении #1093876 писал(а):
Разность чисел с одинаковыми остатками дадут нужную сумму.
Итак, нашлись две суммы $\sum\limits_{i=0}^k a_i$ и $\sum\limits_{i=0}^m a_i$ (причем $1\leqslant k < m \leqslant 100$), дающие равные остатки при делении на $100$. Авторы намекают на разность. Ещё одно неловкое движение, и я решу задачу, и тогда меня забанят.

mr.tumkan2015 в сообщении #1093876 писал(а):
Причем тут разность. Нам же нужна сумма.
Решения могут состоять из нескольких шагов. В конце Вы получите сумму, но в промежуточном шаге по методу автора решения строится разность. Обычная ситуация. Разве Вы ещё не привыкли к тому, насколько непрямолинейными бывают решения?

 
 
 
 Re: Комбинаторика. Есть решение, но не понять его.
Сообщение24.01.2016, 18:44 
Вот недавно аналогичная задача решалась: «Новогодние суммы натуральных чисел».

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group