Суммы тройной прогрессии

[surfer]

Докажите что из членов ряда 1,3,9,27,81 и т.д., если брать только различные члены, путем сложения и вычитания можно получить решительно все числа.

[незваный гость]

Троичная сбалансированная система записи, а что?

surfer писал(а):

решительно все числа

Ну, это Вы загнули. Натуральные — можно, причем единственным способом. А вот 0 попробуйте…

[Руст]

Можно представить не только натуральные, но и все целые, отличные от нуля.

[surfer]

изначально в условии подразумеваются натуральные числа.
задание выросло из задачи о взвешиваниях при помощи одного набора гирь.

[Someone]

Если договориться, что сумма, не содержащая ни одного слагаемого, равна 0, то и 0 можно представить.

[Руст]

Всё правильно, и это соответствует взвешиванию гирями, ставя их слева или справа. Если равновесие без всяких гирь, то вес равен нулю.

[surfer]

Замечательное доказательство этой задачи принадлежит Эйлеру:

Цитата:

Чтобы показать истинность этого, я рассмотрю такое бесконечное произведение

$$ \left( {{\rm x}^{{\rm - 1}} + 1 + {\rm x}^{\rm 1} } \right)\left( {{\rm x}^{{\rm - 3}} + 1 + {\rm x}^{\rm 3} } \right)\left( {{\rm x}^{{\rm - 9}} + 1 + {\rm x}^{\rm 9} } \right)\left( {{\rm x}^{{\rm - 27}} + 1 + {\rm x}^{{\rm 27}} } \right) $$

и т.д.

$$ = P $$

;
При развертывании оно даст такие степени , которые могут быть образованы из числел 1, 3, 9, 27, 81 и т.д. путем сложения или вычитания. Для того чтобы узнать, получатся ли в самом деле все степени, каждая по одному разу, я поступлю так.
Пусть

$$ P = $$

и т.д.

$$ + cx^{ - 3} + bx^{ - 2} + ax^{ - 1} + 1 + \alpha x + \beta x^2 + \gamma x^3 + \delta x^4 + \varepsilon x^5 + $$

и т.д.;
Ясно, что если написать

$$ x^3 $$

вместо

$$ x $$

, то получится

$$ {P \over {{\rm x}^{{\rm - 1}} + 1 + {\rm x}^{\rm 1} }} = $$

и т.д.

$$ + bx^{ - 6} + ax^{ - 3} + 1 + \alpha x^3 + \beta x^6 + \gamma x^9 + $$

и т.д.
Отсюда находим

$$ P = $$

и т. д.

$$ + ax^{ - 4} + ax^{ - 3} + ax^{ - 2} + x^{ - 1} + 1 + x + \alpha x^2 + \alpha x^3 + \alpha x^4 + \beta x^5 + \beta x^6 + \beta x^7 + $$

и т. д.;
Это выражение в сравнении с вышеуказанным дает

$$ \alpha = 1 $$

,

$$ \beta = \alpha $$

,

$$ \gamma = \alpha $$

,

$$ \varepsilon = \beta $$

,

$$ \xi = \beta $$

и т. д.
и

$$ a = 1 $$

,

$$ b = a $$

,

$$ c = a $$

,

$$ d = a $$

,

$$ e = d $$

и т.д.
Итак, отсюда

$$ P = 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + $$

и т. д.

$$ + x^{ - 1} + x^{ - 2} + x^{ - 3} + x^{ - 4} + x^{ - 5} + x^{ - 6} + x^{ - 7} + $$

и т. д.
Ясно, что здесь будут встречаться все степени , как положительные, так и отрицательные, и что, следовательно, можно получить все числа из членов тройной геометрической прогрессии путем сложения или вычитания, причем каждое число только одним способом.

[Руст]

Это называется использование производящей функции. Но в этом случае результат тривиален и без этого. Для каждого числа n имеется такое k, что $\frac{2n}{3}\ge 3^k<2n$

[surfer]

Я бы не назвал результат тривиальным, скорее отнесу его к общеизвестным результатам типа теоремы пифагора. Меня побудило рассказать о этой задаче эйлеровское доказательство.

Полностью согласен, можно доказать быстрее, воспользовавшись троичной системой записи, как предлогал незваный гость.

[Руст]

На самом деле эту задачу легко обобщить. Например имеется по две гири с достоинствами 1,5,25,125,... Это уже экономнее (требуется меньшее количество гирь для взвешивания больших весов). Можно ещё экономнее по k гирь с достоинствами $1,m,m^2,m^3,...$, \ m=2k+1.$

[Руст]

Ошибся насчёт экономичности. Легко доказать, что самый экономный набор это троичная система. Т.е. если набором из n гирь $m_1,m_2,...,m_n$ можно всвесить любые веса, выраженные натуральным числом вплоть до веса N(n), максимальное значение достигается в троичной системе и равно $max N(n)=\frac{3^n-1}{2}$.