夏休みももうすぐ終わりですね。宿題終わりましたか？
明日ホラ経由で見つけた問題を紹介します。
with MOCHA LATTE - 小正裕佳子先生の日記上皿てんびん（腕が２つあって、左右の皿に物をのせられる秤）があります。 これを使って、１グラムから４０グラムまでなら何グラムでも（１グラムごとに）量れるように するためには、おもりは最低何個必要でしょう？また、そのおもりは何グラムでしょう？
ここでは、
明日は明日のホラを吹く-Tomorrow, I'll give you another big talk-:最小限必要なおもりの個数さて、こちらは大人なのだから（笑）一般化のことも考えてみよう。
というわけで一般化したケースを考えてみる。自分で考えたい人は、「続きを読む」をクリックしないように。
この問題のミソは、天秤だということだ。この特徴をまとめてみる。
- ある分銅一個に注目すると、「計量物側に置く」「その反対(分銅側)に置く」「置かない」という３つの状態がある。
- A.より、n個の分銅がある場合に可能な状態は、3^n種類であることが導かれる
あとは、3^n個の状態が
- それぞれ単一(unique)、すなわち別の分銅の組み合わせにならず、
- かつ1gきざみになるには
どうしたらよいか考えればよい。
ある分銅の組み合わせで、すでにNgまで測れることがわかっているとする。それでは分銅を一個加えて、N+1gを測るにはどうしたらよいか？もちろん1gはOKだが、a.の条件を満たさない。それでは既存の分銅を全て計量物側に置いた場合、分銅側には何gの分銅を置いたらよいだろうか？
答えは2N+1である。ということは、分銅を加える場合のルールは、それまで持っている分銅の重量の合計にに２をかけ、１を足せばいいということになる。これを、1gの分銅から続けて行けば、必要な分銅がわかるというわけだ。それではやってみよう。
| 最も重い分銅 | 分銅の合計 | 次の分銅 |
| 1 | 1 | 1*2+1 = 3 |
| 3 | 1+3 = 4 | 4*2+1 = 9 |
| 9 | 1+3+9 = 13 | 13*2+1 = 27 |
分銅の重さが3のべき乗になるという規則性が見えて来た。あとは数学的帰納法を使って、これが任意の場合にあてはまるかを証明すればいい。
- n=1の場合
- 2n + 1 = 3 = 3^1 (自明)
- n=k+1の場合
- Σa^r = (a^(r+1) - 1) / (r - 1) *0 なので
- Σ3^k = (3^(k+1) - 1) / (3 - 1) = (3^n - 1)/2
- ∴ 3^n = 2Σ3^k + 1 [Q.E.D]
こんなもんでいかがでしょうか＞小正裕佳子先生
この問題、すぐにわかったのだけど、証明を書くのにちょっと手こずってしまった。すこし脳のしわの間にはいったほこりがとれた気分。
Dan the Ex-Tutor of Math
おかしいです