おもりは何個

最近話題沸騰の某家庭教師さんブログに出ていた問題にチャレンジしてみた。 明日は明日のホラを吹く-Tomorrow, I'll give you another big talk-:最小限必要なおもりの個数
上皿てんびん(腕が2つあって、左右の皿に物をのせられる秤)があります。これを使って、1グラムから40グラムまでなら何グラムでも(1グラムごとに)量れるようにするためには、おもりは最低何個必要でしょう?また、そのおもりは何グラムでしょう?

とはいっても、解答はあっという間に404 Blog Not Foundでdankogai様が提示されていて、文句のつけようもないのだけど、同じことを微妙に違う味付けで(家庭教師風に)パズルっぽく説明をつけてみたのだった。挑戦状とかじゃないんで!

~~~はじまりはじまり~~~
c0041583_1782473.jpg

「a, b, cのおもりを使って上皿天秤でXグラムを測れる」
ということは、上の図を見ながら考えるとわかるように
「a, b, c という数を《足す》《引く》《使わない》によって自由に組み合わせて X という答えを導ける」
ということに等しい。天秤を頭でうーんうーんってイメージし続けるのをやめて数式ひとつの計算を考えるだけにしよう。よくあるよね「1,3,9と"+"、"-"を使って12を作りなさい」とかって問題。あれと同じ。

さて、今、Nグラムまでなら何グラムでも測れるおもりのセットがあるとする。このセットに、新しく(2N+1)グラムのおもりを加えると、一気に3N+1グラムまで測れるようになる。

c0041583_17182954.jpgどういうことかというと、
2N+1グラムを境にしてこんな図を描いてみるとわかりやすい。1グラム~Nグラムっていう重さはもともとのセットで作れるわけだから、N+1グラム~2Nグラムの範囲の重さは、2N+1からそれらを引き算することで作れる。2N+2グラム~3N+1グラムの範囲は、2N+1に足し算すれば作れる。

ここまでわかればあとは簡単。

最小の「Xグラムまで測れるおもりのセット」っていうのは、「1グラムまで測れるセット」だ。もちろん内容は1グラム一つ。ということは
これに(2x1+1=)3グラムのおもりを加えると(3x1+1=)4グラムまで測れるようになる。
さらに(2x4+1=)9グラムを加えれば(3x4+1=)13グラム、
(2x13+1=)27グラムを加えれば(3x13+1=)40グラムまで測れる。

この{1, 3, 9, 27}というのが、40グラムを自由に測れるおもりのセット。



(蛇足)
Nまでの自然数と、《足す》《引く》《使わない》という演算子のすべての順列組み合わせを試して、1からNまでの数が作れたら終了するっていうバカプログラムを作ったら、N=40ではわりとすぐ終わった。

N=1000だと帰ってこなくなった。さようなら。
[PR]
by tockri | 2005-08-30 17:22 | └ 問題集
移転しました。
by tockri
S M T W T F S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30
最新のトラックバック
[media][gove..
from bewaad institu..
甘やかされた男たち
from とっくりばー
~が下手
from たのしい検索・ゆかいな検索
例えバトン
from ひまわりてんびんへの道
例えバトン
from 明日は明日のホラを吹く-To..
リンク
ライセンス

クリエイティブ・コモンズ・ライセンス

このブログのテキストおよび画像は、クリエイティブ・コモンズ・ライセンスの下でライセンスされています。




検索
ファン
ブログジャンル
画像一覧