てんびんを使って品物の重さを測るために,
a1グラム,a2グラム,a3グラム,…,anグラム,…
のおもりを1つずつ用意して,次の条件を満たすようにしたい.
- 各nについて,a1グラムからanグラムまでのおもりを使うと,
1グラムからSn=a1+a2+…+an
グラムのすべての重さ(整数値)が測れる.
- Snをできるだけ大きくする.
問題 次の2つの場合について,それぞれ数列{an}を求めよ.
- おもりを品物と別の皿にだけ乗せる場合.
(品物の重さは,おもりの重さの足し算の組み合わせで表せる.)
- おもりを品物と同じ皿にも乗せてよい場合.
(品物の重さは,おもりの重さの足し算と引き算の組み合わせで表せる.)
解答1
- a1を使って測れる重さはa1だけである.
- 1が測れないといけないので,
- a1=1 とする.
- 1〜S1=1 が測れる.
- a2を追加すると,新たに
- a2,a2+1 が測れるようになる.
- 2が測れないといけないので,
- a2=2 とする.
- 1〜S2=2+1=3 が測れる.
- a3を追加すると,新たに
- a3,a3+1〜a3+3 が測れるようになる.
- 4が測れないといけないので,
- a3=4 とする.
- 1〜S3=4+3=7 が測れる.
-
- a1〜an-1が定まったとする.
- anを追加すると,新たに
- an,an+1〜an+Sn-1 が測れるようになる.
- Sn-1+1が測れないといけないので,
- an=Sn-1+1 とする.
- 1〜Sn=an+Sn-1=2Sn-1+1 が測れる.
- これから,{an}の漸化式と一般項を求める
- Sn+1=2Sn-1+2
- ∴ an+1=2an
- ∴ an=2n-1
- yグラムを測るために使われるおもりは次のようにしてわかる.
- y=x11+x22+x322+x423+…
とする(xk=0か1).
- yを2で割ると
- 余りが x1
- 商が x21+x32+x422+…
- したがって,次のように帰納的に求められる.
- y1=y
- xk=ykを2で割った余り
- yk+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
- a1を使って測れる重さはa1だけである.
- 1が測れないといけないので,
- a1=1 とする.
- 1〜S1=1 が測れる.
- a2を追加すると,新たに
- a2−1,a2,a2+1 が測れるようになる.
- 2が測れないといけないので,
- a2−1=2 すなわち a2=3 とする.
- 1〜S2=3+1=4 が測れる.
- a3を追加すると,新たに
- a3−4〜a3+4 が測れるようになる.
- 5が測れないといけないので,
- a3−4=5 すなわち a3=9 とする.
- 1〜S3=9+4=13 が測れる.
-
- a1〜an-1が定まったとする.
- anを追加すると,新たに
- an−Sn-1〜an+Sn-1 が測れるようになる.
- Sn-1+1が測れないといけないので,
- an−Sn-1=Sn-1+1 すなわち an=2Sn-1+1 とする.
- 1〜Sn=an+Sn-1=3Sn-1+1 が測れる.
- これから,{an}の漸化式と一般項を求める
- 2Sn+1=6Sn-1+3
- ∴ an+1=3an
- ∴ an=3n-1
- yグラムを測るために使われるおもりは次のようにしてわかる.
- y=x11+x23+x332+x433+…
とする(xk=−1か0か1).
- y+1を3で割ると
- 余りが x1+1
- 商が x21+x33+x432+…
- したがって,次のように帰納的に求められる.
- y1=y
- xk=((yk+1)を3で割った余り)−1
- yk+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 | |
|
|