数学U 数列

数学的帰納法 てんびんのおもり

てんびんを使って品物の重さを測るために, a1グラム,a2グラム,a3グラム,…,anグラム,… のおもりを1つずつ用意して,次の条件を満たすようにしたい.
  1. 各nについて,a1グラムからanグラムまでのおもりを使うと, 1グラムからSn=a1+a2+…+an グラムのすべての重さ(整数値)が測れる.
  2. nをできるだけ大きくする.

問題 次の2つの場合について,それぞれ数列{an}を求めよ.

  1. おもりを品物と別の皿にだけ乗せる場合. (品物の重さは,おもりの重さの足し算の組み合わせで表せる.)
  2. おもりを品物と同じ皿にも乗せてよい場合. (品物の重さは,おもりの重さの足し算と引き算の組み合わせで表せる.)

解答1

  1. 1を使って測れる重さはa1だけである.
    1が測れないといけないので,
    1=1 とする.
    1〜S1=1 が測れる.
  2. 2を追加すると,新たに
    2,a2+1 が測れるようになる.
    2が測れないといけないので,
    2=2 とする.
    1〜S2=2+1=3 が測れる.
  3. 3を追加すると,新たに
    3,a3+1〜a3+3 が測れるようになる.
    4が測れないといけないので,
    3=4 とする.
    1〜S3=4+3=7 が測れる.
  4. 1〜an-1が定まったとする.
    nを追加すると,新たに
    n,an+1〜an+Sn-1 が測れるようになる.
    n-1+1が測れないといけないので,
    n=Sn-1+1 とする.
    1〜Sn=an+Sn-1=2Sn-1+1 が測れる.
  5. これから,{an}の漸化式と一般項を求める
    n+1=2Sn-1+2
    ∴ an+1=2an
    ∴ an=2n-1
  6. yグラムを測るために使われるおもりは次のようにしてわかる.
    y=x11+x22+x32+x43+… とする(xk=0か1).
    yを2で割ると
    余りが x1
    商が  x21+x32+x42+…
    したがって,次のように帰納的に求められる.
    1=y
    k=ykを2で割った余り
    k+1=ykを2で割った商

    例 y=1234
    2)1234 0
    2) 617 1    +2
    2) 308 0
    2) 154 0
    2) 77 1    +16
    2) 38 0
    2) 19 1    +64
    2) 9 1    +128
    2) 4 0
    2) 2 0
    2) 1 1   +1024
    0  

解答2

  1. 1を使って測れる重さはa1だけである.
    1が測れないといけないので,
    1=1 とする.
    1〜S1=1 が測れる.
  2. 2を追加すると,新たに
    2−1,a2,a2+1 が測れるようになる.
    2が測れないといけないので,
    2−1=2 すなわち a2=3 とする.
    1〜S2=3+1=4 が測れる.
  3. 3を追加すると,新たに
    3−4〜a3+4 が測れるようになる.
    5が測れないといけないので,
    3−4=5 すなわち a3=9 とする.
    1〜S3=9+4=13 が測れる.
  4. 1〜an-1が定まったとする.
    nを追加すると,新たに
    n−Sn-1〜an+Sn-1 が測れるようになる.
    n-1+1が測れないといけないので,
    n−Sn-1=Sn-1+1 すなわち an=2Sn-1+1 とする.
    1〜Sn=an+Sn-1=3Sn-1+1 が測れる.
  5. これから,{an}の漸化式と一般項を求める
    2Sn+1=6Sn-1+3
    ∴ an+1=3an
    ∴ an=3n-1
  6. yグラムを測るために使われるおもりは次のようにしてわかる.
    y=x11+x23+x32+x43+… とする(xk=−1か0か1).
    y+1を3で割ると
    余りが x1+1
    商が  x21+x33+x42+…
    したがって,次のように帰納的に求められる.
    1=y
    k=((yk+1)を3で割った余り)−1
    k+1=(yk+1)を3で割った商

    例 y=1234
    3)1234 1    +1
    3) 411 0
    3) 137 -1    -9
    3) 46 1    +27
    3) 15 0
    3) 5 -1    -243
    3) 2 -1    -729
    3) 1 1   +2187
    0