■剰余系と整数生成定規(その63)
天秤の両方の皿を使って,nグラム(nは任意の正の整数)のものを量る問題では,
1,2,2^2,2^3,2^4,・・・
グラムでなく
1,3,3^2,3^3,3^4,・・・
グラムのおもりを使えばよいことはよく知られている.
たとえば,10グラムは同じ皿に1グラムと9グラムのおもりを置けばはかることができる(10=1+3^2),73グラムは同じ皿に9グラムのおもりを置けば1グラムと81グラムのおもりを使ってはかることができる(73+3^2=1+3^4).
もっと詳しくいうと,
1,3,3^2,3^3,3^4,・・・,3^r
のおもりによって,1から(3^(r+1)−1)/2グラムまでのすべての整数の重さを量ることができ,しかもそれが唯一の方法であるという.
===================================
任意の正の整数nに対して,そのnを異なる3の累乗の和と差で表す問題であるが,2進数のように数字2を許さない代わりに,数字−1を認めている.
母関数を使ってアプローチすると,
f(x)=(1+x+x^-1)(1+x^3+x^-3)=x^4+x^3+x^2+x+1+x^-1+x^-2+x^-3+x^-4
を得る.これは1グラムと3グラムのおもりによって4グラム以下の任意の正(負も)の整数を量ることができ,かつ,係数がすべて1であるのでその方法が1通りであることを示している.
同様に
f(x)=(1+x+x^-1)(1+x^3+x^-3)(1+x^9+x^-9)=(x^27−1)/x^13(x−1)=x^13+x^12+・・・+x+1+x^-1+・・・+x^-12+x^-13
は1グラムと3グラムと9グラムのおもりによって13グラム以下の任意の正(負も)の整数を量ることができ,かつ,係数がすべて1であるのでその方法が1通りであることを示している.
f(x)=(1+x+x^-1)(1+x^3+x^-3)(1+x^9+x^-9)(1+x^27+x^-27)=(x^81−1)/x^40(x−1)=x^40+x^39+・・・+x+1+x^-1+・・・+x^-39+x^-40
一般に,母関数に関する美しい恒等式
Π(1+x^(3^n)+x^-(3^n))=Σx^n
が成り立つ.
[参]ポール・ツァイツ「エレガントな問題解決」オライリージャパン
===================================