Задачки, решающиеся элементарно, по возможности как можно более элементарно Опции

[Нихт ШиссеН]

Ну вот, например, как проще всего доказать, что правильных многогранников всего пять? И почему только пять? Оказывается, для элементарного доказательства данного факта достаточно обыкновенного здравого смысла плюс формула Эйлера. (IMG:http://www.sci-lib.net/style_emoticons/default/smile.gif) Я доказал, а вы сможете?

Ну, что еще... Вот, знаменитая последовательность x(n+1) = x(n)/2 при x(n) - четном и 3*x(n)+1 при x(n) - нечетном. Требуется доказать, что начав с любого числа всегда придем к 1. Мне доказать не удается ибо сложность полных прообразов возрастает с номером итерации геометрически а регулярной процедуры я что-то сообразить не могу. (IMG:http://www.sci-lib.net/style_emoticons/default/sad.gif) Может у кого-нибудь из вас терпения окажется больше?

В общем, такого плана задачки сыпьте сюда.

[metelev_sv]

Ну, что еще... Вот, знаменитая последовательность x(n+1) = x(n)/2 при x(n) - четном и 3*x(n)+1 при x(n) - нечетном. Требуется доказать, что начав с любого числа всегда придем к 1. Мне доказать не удается ибо сложность полных прообразов возрастает с номером итерации геометрически а регулярной процедуры я что-то сообразить не могу. (IMG:style_emoticons/default/sad.gif) Может у кого-нибудь из вас терпения окажется больше?

Мне тоже стало интересно, как доказать. Немного продвинулся, хоть это и не доказательство, но хочу всё же изложить.

Можно параллельно с последовательностью x(n) рассматривать последовательность m(n), которую строить следующим образом.
1) m(0)=x(0)
2) m(1) находим так: m(0)=2*m(1) если m(0) чётное, и m(0)=2*m(1)+1, если m(1) нечётное.
далее переписываем x(0) через m(1) и совершаем действия, требуемые алгоритмом условия (если получается чётное, то делим пополам,
если получается нечётное, то ... и т.д. и т.п.)
3) Каждый раз, в зависимости от чётности x(n) выбираем m(n+1) чётным или нечётным и выражаем через него m(n)

Будем делать эти итерации, пока m не дойдёт до нуля. Поскольку последовательность m может только уменьшаться, не может быть никаких замкнутых циклов, потому что уменьшаться до бесконечности нельзя. Если производить реальные вычисления, то последовательность m рано или поздно просто-напросто упирается в 0, и дальше идут нули. Ну и ничего страшного, можно в этот момент считать x стартовым и снова начать "спускаться вниз".

Ещё надо подумать, может ещё что-то полезное в голову придёт (IMG:style_emoticons/default/smile.gif)

Сообщение отредактировал metelev_sv - 20.05.2008, 10:07