задачка (математика)

[avva]

Вот, скажем, еще одна задачка, рассказали на работе, тоже не очень сложная. Комментарии скрывать не буду.

Даны 23 целых числа (положительные, отрицательные или 0), написанные подряд в строку. Доказать, что можно так расставить знаки скобок, +, и *, чтобы получилось правильно написанное выражение, значение которого делится на 2000 без остатка. Знаки скобок, +, и * можно ставить где угодно, лишь бы вышло написано правильно. Другие операции, знаки и числа использовать нельзя.

Comments

[ppetya.livejournal.com]

про это я в голове подумал!
перебор на самом деле..

пять чисел -- есть 0 mod 5, среди них, все ок
если нет, то когда плохо: когда нет противоположных по сложению
если все числа в одном остатке - то все ок, складывая

остается случай: в двух остатках (х и у)
в одном из них три числа есть уж точно, пусть это х. тогда либо 2x, либо 3х равно -y.

думаю, что не соврал

Хорошая задача!

[avva.livejournal.com]

Мне кажется, сложнее: ведь могут быть противоположные по сложению остатки, не стоящие рядом - и тогда не факт, что их можно встретить. Т.е. может быть мешанина из всех 4 остатков (кроме 0) на 5 местах.

Я себя убедил, что всегда получается, в уме, но это получился действительно уродливый долгий перебор кучи возможностей (начиная с того, который стоит в середине на 3-м месте, посмотрим, кто может быть слева-справа итд.). Меж тем вообще-то кажется резонным, что для в общем случае для p достаточно p, если p простое, и может быть есть какое-то простое док-во, но я немного подумал и не придумал.

[ppetya.livejournal.com]

да, соврал!
доказал уже вроде, но не коротко
еще лучше:)

[ppetya.livejournal.com]

есть вроде простое для вашего p
опять предполагаем сразу что нуля нет среди p чисел
a_1,a_2...
рассмотрим все подсуммы кончающиеся предпоследним числом, то есть
a_1+a_2+a_3+...+a_{p-1}
a_2+a_3+...+a_{p-1}
a_3+...+a_{p-1}
если среди них есть две одинаковые mod p -- дело сделано
если одна из них 0 mod p, тоже
остается случай, когда нет одинаковых и нуля
стало быть эти суммы заполняют все ненулевые остатки, в том числе и -a_p.
эту сумму и сложим с a_p

[avva.livejournal.com]

Ага, действительно просто. Спасибо!

[ppetya.livejournal.com]

да это кому-то из вас четверых спасибо!

(сначала забыл условие и разрешил себе переставлять числа в пятерке)

[scolar.livejournal.com]

Для наглядности можно даже не делать первого замечания, а рассмотреть
S_1 = a_1
S_2 = a_1 + a_2
...........
S_p = a_1 + a_2 + ... + a_p

Либо среди них есть сумма S_i = 0 (mod p), либо S_i = S_j (mod p)

Кстати, а где мы воспользовались простотой p?

[ppetya.livejournal.com]

Да, так еще "проще". Простотой тут, конечно, не пользуется никто, лень писать было.
Подобный вопрос правильно ставить для простого р отдельно.

Bчера еще подумал, и мне кажется, что на самом деле "р чисел для р" это слишком много. Гипотетически хватит Cln(p), или, может, даже лучше.

[baca6u.livejournal.com]

Долго не мог врубится, пока не сформулировал тоже самое на простом человеческом языке.
есть ряд из 5 чисел. а1, а2, а3, а4, а5 (слишком конкретно, разумеется, но вместо 5 можно писать N, смысл тот же)
берем последовательные суммы
S1 = a1
S2 = a1 + a2
S3 = a1 + a2 + a3
..
S5 = a1 + a2 + a3 + a4 + a5
Если mod 5 этих сумм не повторяется, значит там есть или 0 или 5, если повторяется, то слагаемые на которые эти суммы отличаются, дадут 0 mod 5.
Вот теперь даже мне понятно.

[baca6u.livejournal.com]

похоже это и есть доказательство, для получения P надо максимум P чисел.