| Математическая задачка на интуицию (для математиков) |
[Apr. 26th, 2005|12:40 am] |
Возьмем натуральное число Х, запишем как сумму степеней двойки (из минимального числа слагаемых, так что там будут только степени, соотв. 1-м в бинарной записи), поступим так же с показателями степеней и т.д. Таким образом получим древовидную запись, состоящую из 0 и 2-ек. Назовем ее двойковой записью числа Х. Анаголично определим к-ковую запись: запишем Х как сумму степеней к из минимального числа слагаемых, поступим так же с показателями степеней и т.д.., и получим древовидную запись, состоящую
из 0 и к, возведения в степень и знаков сложения. Например,
1=2^0, 3=2^(2^0)+2^0, 4=2^(2^(2^0)), 18= 3^(3^0+3^0) + 3^(3^0+3^0)
Берем число Х, вычитаем 1, расписываем в 2-ковую запись, заменяем 2 на 3, считаем число, вычитаем 1 из получившегося числа, расписываем в 3-ковую запись, заменяем 3 на 4, считаем число, вычитаем 1 из получившегося числа, расписывем в 4-ковую запись...и так до бесконечности. Что получится в результате ?
Ответ и доказательство несколько удивляют... |
|
|
| Comments: |
Я не очень понял -- откуда каждый раз вычитается 1? Из n-ковой записи? Тогда неплохо бы определить как именно древовидная структура представляется числом. Это можно сделать многими способами. Например, можно от корня по очереди выписывать все ветки, каждую -- такой же процедурой. Можно проходить ветки как минимум в две стороны. Можно выписывать число с конца. Можно более навернутыми способами... В общем я был бы Вам благодарен, если бы Вы это слегка пояснили.
Немного переформулирую. Мне кажется, что без ноликов понятнее.
1. Есть число n и основание b. Раскладываем n по основанию b. Затем в получившемся разложении раскладываем по основанию b каждый показатель степени. Появятся новые показатели, с ними поступаем аналогично. И так пока не остановимся.
2. Теперь с числом n проделываем следующую оперецию. В рассматриваемом представлении везде заменяем b на (b+1); коэффициенты меньшие b при этом не трогаем. Из получившегося числа вычитаем 1, и разность записываем в (b+1)-вой записи.
3. Повторяем операцию.
Начинам с некоторого n и основания 2. Вопрос, что получится, когда зайдём очень далеко? :)
Пример. n=5.
5 = 2^2 + 1;
f(5) = (3^3 + 1) - 1 = 3^3;
f(f(5)) = 4^4 - 1 = 3*4^3 + 3*4^2 + 3*4 + 3;
f(f(f(5))) = 3*5^3 + 3*5^2 + 3*5 + 2;
...
Хорошая задача.
Ответ знаю, так что промолчу :)
![[User Picture]](http://lj.rossia.org/userpic/3556/2147484333) | | From: | ![[info]](http://lj.rossia.org/img/imported-profile.gif) ignat@lj |
|---|
| Date: | April 26th, 2005 - 03:57 pm |
|---|
| | прикалываюсь | (Link) |
|
Неужели дочитал дотуда?
![[User Picture]](http://lj.rossia.org/userpic/3823/2147484672) | | From: | garvej@lj |
|---|
| Date: | April 26th, 2005 - 06:41 pm |
|---|
| | Re: прикалываюсь | (Link) |
|
ага :)
Может, я чего не понял, но, по-моему, у такой задачи может быть только один естественный ответ, который в данном случае легко доказывается. Кстати, что идет после 0?
Начинаем с натурального числа.
Если получаем нуль, то останавливаемся.
По-моему, надо просто ввести соответствующее упорядочение и констатировать, что записи все время убывают. После чего заметить, что упорядочение полно. Разве же это трансфинитная индукция? Просто достаточно навороченная. По-моему, трансфинитная - это когда с теоремой Цермело.
В точку.
Интересно, что бы сказали про такую задачку ультрафинитисты? | |
