■剰余系と整数生成定規(その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

が成り立つ.

 [参]ポール・ツァイツ「エレガントな問題解決」オライリージャパン

===================================