?

Log in

задачка (математика) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка (математика) [янв. 22, 2008|02:27 am]
Anatoly Vorobey
Вот, скажем, еще одна задачка, рассказали на работе, тоже не очень сложная. Комментарии скрывать не буду.

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

Comments:
[User Picture]From: ppetya
2008-01-22 12:40 am

написал на бумажке 2000=2^4x5^3
8=2+2+2+2
23=8+15
15=5+5+5
(Ответить) (Thread)
[User Picture]From: avva
2008-01-22 12:53 am
:)
а как просто доказать, что хватает 5 для 5? (надо же, рифма нечаянная)
(Ответить) (Parent) (Thread)
[User Picture]From: ppetya
2008-01-22 01:08 am
про это я в голове подумал!
перебор на самом деле..

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

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

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

Хорошая задача!
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-01-22 01:18 am
Мне кажется, сложнее: ведь могут быть противоположные по сложению остатки, не стоящие рядом - и тогда не факт, что их можно встретить. Т.е. может быть мешанина из всех 4 остатков (кроме 0) на 5 местах.

Я себя убедил, что всегда получается, в уме, но это получился действительно уродливый долгий перебор кучи возможностей (начиная с того, который стоит в середине на 3-м месте, посмотрим, кто может быть слева-справа итд.). Меж тем вообще-то кажется резонным, что для в общем случае для p достаточно p, если p простое, и может быть есть какое-то простое док-во, но я немного подумал и не придумал.
(Ответить) (Parent) (Thread)
[User Picture]From: ppetya
2008-01-22 01:34 am
да, соврал!
доказал уже вроде, но не коротко
еще лучше:)
(Ответить) (Parent) (Thread)
[User Picture]From: ppetya
2008-01-22 01:45 am
есть вроде простое для вашего 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
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-01-22 01:51 am
Ага, действительно просто. Спасибо!
(Ответить) (Parent) (Thread)
[User Picture]From: ppetya
2008-01-22 01:54 am

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

(сначала забыл условие и разрешил себе переставлять числа в пятерке)
(Ответить) (Parent) (Thread)
[User Picture]From: scolar
2008-01-22 04:50 am
Для наглядности можно даже не делать первого замечания, а рассмотреть
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?

Edited at 2008-01-22 04:51 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: ppetya
2008-01-22 04:00 pm
Да, так еще "проще". Простотой тут, конечно, не пользуется никто, лень писать было.
Подобный вопрос правильно ставить для простого р отдельно.

Bчера еще подумал, и мне кажется, что на самом деле "р чисел для р" это слишком много. Гипотетически хватит Cln(p), или, может, даже лучше.
(Ответить) (Parent) (Thread)
From: baca6u
2008-01-23 05:40 pm
Долго не мог врубится, пока не сформулировал тоже самое на простом человеческом языке.
есть ряд из 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.
Вот теперь даже мне понятно.
(Ответить) (Parent) (Thread)
From: baca6u
2008-01-23 05:52 pm
похоже это и есть доказательство, для получения P надо максимум P чисел.
(Ответить) (Parent) (Thread)
[User Picture]From: induke
2008-01-22 01:08 am
2000=2*2*2*2*5*5*5

Чтобы получить множитель 2 нужно максимум два нечетных слагаемых подряд.

Чтобы получить множитель 5 нужно максимум пять слагаемых подряд неделящихся на 5 (легко проверяется, пусть даже перебором остатков).

Получается четыре пары по два слагаемых, и три - по пять. В сумме - 23.
(Ответить) (Thread)
[User Picture]From: avva
2008-01-22 01:22 am
Все верно. Но есть ли хорошее доказательство для 5? (перебором проверяется, но долго и уродливо)
(Ответить) (Parent) (Thread)
[User Picture]From: azzo27
2008-01-22 01:55 am
Я делал тоже перебором, только по mod 5 взял +1, -1, +2, -2 - тогда из-за симметрии чуть меньше вариантов, чем при 1,2,3,4
(Ответить) (Parent) (Thread)
[User Picture]From: pigmeich
2008-01-22 02:21 am
16 получаем из любых четырех пар чисел. Если числа разные по четности - умножаем, если одинаковые складываем.

С пятерками:
Берём пять чисел подряд.
Если есть равные 0 по модули - все перемножаем.
Если рядом стоят два числа при сложении дающие 0 - перемножаем.
Надо еще пару отборов бы от этой точки совершить, а потом разобрать единственный оставшийся ряд.
(Ответить) (Thread)
[User Picture]From: ella_p
2008-01-22 05:44 am
эээ... а если у нас 23 нуля?
(Ответить) (Thread)
[User Picture]From: scolar
2008-01-22 06:57 am
Ноль прекрасно делится на 2000.
(Ответить) (Parent) (Thread)
[User Picture]From: mirdin
2008-01-22 09:05 am
ммм. а 22 нуля и единица?
(Ответить) (Parent) (Thread)
[User Picture]From: scolar
2008-01-22 09:11 am
А умножается ноль даже чуть лучше, чем делится.
(Ответить) (Parent) (Thread)
[User Picture]From: arno1251
2008-01-22 11:10 am
Это -- фраза дня!
(Ответить) (Parent) (Thread)
[User Picture]From: french_man
2008-01-22 05:48 am
Кажется очевидным. Из двух чисел можно почить 2, из 5 - 5. Значит, из 7 - 10. Значит, из 21 - 1000. Значит, из 23 - 2000.
(Ответить) (Thread)
From: (Anonymous)
2008-01-23 02:41 pm
Тебе и должно быть очевидно :-)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-01-23 02:42 pm
это я был.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2008-01-22 09:40 am
из 20-ти чисел можно, вроде.

из 6-ти чисел получаем число, заканчивающееся на 0 (ищем два числа, которые в сумме дают числа, делящееся на 10 ну и * на оставшееся).

6 * 3 = 18, ну и 2 цифры на "2", т.е. 2000 = 10^3 * 2.
(Ответить) (Thread)
From: myckolah
2008-01-22 05:02 pm
»из 6-ти чисел получаем число, заканчивающееся на 0 (ищем два числа, которые в сумме дают числа, делящееся на 10 ну и * на оставшееся).

шесть чисел:
1 1 1 1 1 1
получите число, оканчивающееся на нуль, пожалуйста.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2008-01-23 12:09 pm
111-111=0
(Ответить) (Parent) (Thread)
From: (Anonymous)
2008-01-23 12:16 pm
1+1+1-1-1-1, of course.
(Ответить) (Parent) (Thread)
From: baca6u
2008-01-23 04:50 pm
"-" нельзя, только +, * и ()
(Ответить) (Parent) (Thread)
[User Picture]From: likeabur
2008-01-28 03:11 pm
пардон, только сейчас ссылку на этот пост дали. Я чего-то не понял, или задача спрашивает "для любой ли данной строки из 23 чисел можно скомбинировать (получив правильно сформированное выражение) скобки и знаки +, -, * так, чтобы получить множитель 2000?" Ключевое - "для любой ли строки". Конечно существуют строки, для которых этого сделать нельзя, пример - 23 нуля подряд: в задаче не сказано, что числа различны.
Каменты выше удивляют.
(Ответить) (Thread)
[User Picture]From: avva
2008-01-28 06:11 pm
0 делится на 2000.
(Ответить) (Parent) (Thread)
[User Picture]From: likeabur
2008-01-28 06:14 pm
да, спасибо :)
(Ответить) (Parent) (Thread)
[User Picture]From: mperv
2008-02-04 08:13 pm
А если 23 заменить на n и задать вопрос - при каком минимальном n это всегда возможно?
(Ответить) (Thread)