Простая задача на принцип Дирихле

[Nakahika]

"Докажите, что среди любых n натуральных чисел найдется поднабор, сумма чисел которого делится на n . В решении используйте принцип Дирихле (формулировка через множества)."

Задачка так-то несложная. Но почему-то нет идей, что взять за большее множество,что за меньшее и как к этому подступиться. Изначально я перешел от рассмотрения самих чисел к рассмотрению остатка от деления на n, чтобы сузить диапазон чисел до (0;n) (итого n-1 возможное число), но вот дальше я встал.

[Someone]

Nakahika в сообщении #1428873 писал(а):

остатка от деления на n, чтобы сузить диапазон чисел до (0;n) (итого n-1 возможное число)

Почему вдруг $n-1$?

[Nakahika]

Someone в сообщении #1428876 писал(а):

Nakahika в сообщении #1428873 писал(а):

остатка от деления на n, чтобы сузить диапазон чисел до (0;n) (итого n-1 возможное число)

Почему вдруг $n-1$?

Ну так не включая 0 и n же. n вообще остатком быть не может, а 0 нас мало интересует, потому что тогда все очевидно.

[Frankenween]

Пусть у нас числа $a_1, a_2, \dots , a_n$, тогда имеет смысл рассмотреть $s_i = \sum_{j = 1}^i{a_i}, \, s_0 = 0$ и понять, что если $s_i \equiv s_j \mod n$, то это победа. Но это точно выполнится как раз по принципу Дирихле.

[Someone]

Nakahika в сообщении #1428881 писал(а):

а 0 нас мало интересует, потому что тогда все очевидно.

Дык, в решении это должно быть сказано в явном виде.

P.S. Формулы оформите как положено. Пока модератор тему в Карантин не унёс.
Как набирать формулы?
FAQ по тегу [math].

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- отсутствуют собственные содержательные попытки решения задачи.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.