задачка (математика)
Jan. 22nd, 2008 02:27 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaВот, скажем, еще одна задачка, рассказали на работе, тоже не очень сложная. Комментарии скрывать не буду.
Даны 23 целых числа (положительные, отрицательные или 0), написанные подряд в строку. Доказать, что можно так расставить знаки скобок, +, и *, чтобы получилось правильно написанное выражение, значение которого делится на 2000 без остатка. Знаки скобок, +, и * можно ставить где угодно, лишь бы вышло написано правильно. Другие операции, знаки и числа использовать нельзя.
Даны 23 целых числа (положительные, отрицательные или 0), написанные подряд в строку. Доказать, что можно так расставить знаки скобок, +, и *, чтобы получилось правильно написанное выражение, значение которого делится на 2000 без остатка. Знаки скобок, +, и * можно ставить где угодно, лишь бы вышло написано правильно. Другие операции, знаки и числа использовать нельзя.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
8=2+2+2+2
23=8+15
15=5+5+5
no subject
Date: 2008-01-22 12:53 am (UTC)а как просто доказать, что хватает 5 для 5? (надо же, рифма нечаянная)
no subject
Date: 2008-01-22 01:08 am (UTC)перебор на самом деле..
пять чисел -- есть 0 mod 5, среди них, все ок
если нет, то когда плохо: когда нет противоположных по сложению
если все числа в одном остатке - то все ок, складывая
остается случай: в двух остатках (х и у)
в одном из них три числа есть уж точно, пусть это х. тогда либо 2x, либо 3х равно -y.
думаю, что не соврал
Хорошая задача!
no subject
Date: 2008-01-22 01:18 am (UTC)Я себя убедил, что всегда получается, в уме, но это получился действительно уродливый долгий перебор кучи возможностей (начиная с того, который стоит в середине на 3-м месте, посмотрим, кто может быть слева-справа итд.). Меж тем вообще-то кажется резонным, что для в общем случае для p достаточно p, если p простое, и может быть есть какое-то простое док-во, но я немного подумал и не придумал.
no subject
Date: 2008-01-22 01:34 am (UTC)доказал уже вроде, но не коротко
еще лучше:)
no subject
Date: 2008-01-22 01:45 am (UTC)опять предполагаем сразу что нуля нет среди 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
no subject
Date: 2008-01-22 01:51 am (UTC)no subject
(сначала забыл условие и разрешил себе переставлять числа в пятерке)
no subject
Date: 2008-01-22 04:50 am (UTC)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?
no subject
Date: 2008-01-22 04:00 pm (UTC)Подобный вопрос правильно ставить для простого р отдельно.
Bчера еще подумал, и мне кажется, что на самом деле "р чисел для р" это слишком много. Гипотетически хватит Cln(p), или, может, даже лучше.
no subject
Date: 2008-01-23 05:40 pm (UTC)есть ряд из 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.
Вот теперь даже мне понятно.
no subject
Date: 2008-01-23 05:52 pm (UTC)no subject
Date: 2008-01-22 01:08 am (UTC)Чтобы получить множитель 2 нужно максимум два нечетных слагаемых подряд.
Чтобы получить множитель 5 нужно максимум пять слагаемых подряд неделящихся на 5 (легко проверяется, пусть даже перебором остатков).
Получается четыре пары по два слагаемых, и три - по пять. В сумме - 23.
no subject
Date: 2008-01-22 01:22 am (UTC)no subject
Date: 2008-01-22 01:55 am (UTC)no subject
Date: 2008-01-22 02:21 am (UTC)С пятерками:
Берём пять чисел подряд.
Если есть равные 0 по модули - все перемножаем.
Если рядом стоят два числа при сложении дающие 0 - перемножаем.
Надо еще пару отборов бы от этой точки совершить, а потом разобрать единственный оставшийся ряд.
no subject
Date: 2008-01-22 05:44 am (UTC)no subject
Date: 2008-01-22 06:57 am (UTC)no subject
Date: 2008-01-22 09:05 am (UTC)no subject
Date: 2008-01-22 09:11 am (UTC)no subject
Date: 2008-01-22 11:10 am (UTC)no subject
Date: 2008-01-22 05:48 am (UTC)no subject
Date: 2008-01-23 02:41 pm (UTC)no subject
Date: 2008-01-23 02:42 pm (UTC)no subject
Date: 2008-01-22 09:40 am (UTC)из 6-ти чисел получаем число, заканчивающееся на 0 (ищем два числа, которые в сумме дают числа, делящееся на 10 ну и * на оставшееся).
6 * 3 = 18, ну и 2 цифры на "2", т.е. 2000 = 10^3 * 2.
no subject
Date: 2008-01-22 05:02 pm (UTC)шесть чисел:
1 1 1 1 1 1
получите число, оканчивающееся на нуль, пожалуйста.
no subject
Date: 2008-01-23 12:09 pm (UTC)no subject
Date: 2008-01-23 12:16 pm (UTC)no subject
Date: 2008-01-23 04:50 pm (UTC)no subject
Date: 2008-01-28 03:11 pm (UTC)Каменты выше удивляют.
no subject
Date: 2008-01-28 06:11 pm (UTC)no subject
Date: 2008-01-28 06:14 pm (UTC)no subject
Date: 2008-02-04 08:13 pm (UTC)