Делимость, сложение и умножение

[lka76]

Задана последовательность из N целых чисел
необходимо расставить знаки + * и () так чтобы полученное число делилось на N без остатка.
для N=2 очевидно что если одно из чисел четно то и произведение четно.. если оба не четны то сумма четна.
для N=3 тоже просто
если хотя бы одно делится то произведение делится.
если остатки от деления равны то сумма делится на 3.
если разные то сумма 2-х с разными остатками делится на 3
для N=4 =2*2
для N=5
для N=7 перебор не осилил (порядка 100 вариантов осталось но есть убеждение что тоже можно)
перебором проверил ...
подскажите как-то можно доказать в общем случае?
смотрел на китайскую теорему об остатках, не могу сюда "прикрутить"

[Профессор Снэйп]

Достаточно рассмотреть случай простого $N$. Почему?

[lka76]

Профессор Снэйп в сообщении #560893 писал(а):

Достаточно рассмотреть случай простого $N$. Почему?

на счет "составных" понятно т.к если N=$R_1* R_2$ то из первых $R_1$ чисел составляем число делящееся на $R_1$ из следующих $R_2$ чисел число делящееся на $R_2$ соответственно произведение будет делиться $N$
причем для составного числа длинна последовательности $<=N$
в общем случае количество чисел$=\sum{R_i}$ где $ R_i$ простой делитель числа N

а по простым числам кроме как перебор пока не вижу способа.

[Cash]

Задача на принцип Дирихле. Кролики здесь - остатки при делении на $N$ чисел

$a_1, a_1+a_2, ... , a_1+a_2+ \cdots +a_N$

[lka76]

Cash в сообщении #561018 писал(а):

Задача на принцип Дирихле. Кролики здесь - остатки при делении на $N$ чисел

$a_1, a_1+a_2, ... , a_1+a_2+ \cdots +a_N$

не понял к чему тут прикладывать принцип Дирихле???

возьмем например $N=7$
последовательность $4, 6, 6, 4, 6, 6, 4$
согласно вашему примеру получаем новую последовательность
$4, 3, 2, 6, 5, 4, 1$
хотя $7*6 = 6 + 6*4 +6+6$
или общая формула
$4 * (6 + 6*4 + 6 + 6) * 4$ делится на 7

[Cash]

Цитата:

получаем новую последовательность
$4, 3, 2, 6, 5, 4, 1$

Подмечаем, что числа на первом и шестом местах равны, а значит
$a_1\equiv 4 \mod 7$
$a_1+a_2+\cdots+a_6 \equiv 4 \mod 7$
Откуда, практически бесплатно, получаем, что
$4 \cdot (6 + 6 + 4 + 6 + 6) \cdot 4$ делится на $7$
Ну а то, что в новой последовательности мы найдем либо равные, либо $0$
и гарантирует принцип Дирихле.

(Оффтоп)

Настоятельный совет, в качестве знака умножения используйте \cdot, а не звездочку

[lka76]

Cash в сообщении #561440 писал(а):

Цитата:

Откуда, практически бесплатно, получаем, что
$4 \cdot (6 + 6 + 4 + 6 + 6) \cdot 4$ делится на $7$
Ну а то, что в новой последовательности мы найдем либо равные, либо $0$
и гарантирует принцип Дирихле.

Спасибо!