-
Публикаций
4 310 -
Зарегистрирован
-
Посещение
Тип публикации
Профили
Форум
Блоги
Календарь
Ответы на статус, опубликованные пользователем PhD
-
В теме фильтров BIG потёрли сообщения, но я успел увидеть задачу про волшебный кошелёк (задача 55 по этой ссылке).
Когда только прочитал условие задачи, сразу на ум пришла гипотеза Коллатца (про числа-градины).
Вообще, опустошить кошелёк можно просто совершая ходы с выниманием монет, рано или поздно мы придём к последовательности 3 -> 1 -> 0, за исключением случаев, когда начальное число монет равно 5x-1 (где x=1,2,3,...). То есть когда начальное число монет равно 4, 9, 14, 19 и т.д., то в этом случае мы попадаем на бесконечный цикл (например, 14 -> 39 -> 19 -> 9 -> 4 -> 9...). Для выхода из бесконечного цикла достаточно один раз сделать ход с добавлением монетки.
Поэтому ответы:
а) да.
б) да.
Задачу решил перебором: написал программу, испытал на числах (начальных монет) от 2 до 100.
В обобщённом виде решение не искал, т.к. сложно и лень. Но я сильно удивлён, что это задача для школьников, по сложности эта задача стоит где-то рядом с рядами и комбинаторикой. Либо я просто не догадался, что есть простое и элегантное решение =)
P.S.: почему-то не могу отправить вам сообщение в ЛС.
-
первая часть действительно примитивная для взрослого с iq чуть выше Май, ее толковый 5-6 классник осилит.
А по 2й части за перебор тебе нуль баллов поставят)) это действительно сложная задача для уровня 7-8 кл.
Решения жюри этой задачи я не видел, но с учетом что набрал максимум баллов за нее в конкурсе , решил правильно.
-