バルタン星人さんからのご出題です。
おまけ問題プレゼント（これも結構有名な問題です）
天秤と４個の分銅で測れる重さの最大種類はいくつか？
（またｎ個の分銅の場合は？）
上述のように分銅が１個増えればどれだけ増えるか考えれば答えに行き着きます。
ページ: 1 2
バルタン星人さんからのご出題です。
おまけ問題プレゼント（これも結構有名な問題です）
天秤と４個の分銅で測れる重さの最大種類はいくつか？
（またｎ個の分銅の場合は？）
上述のように分銅が１個増えればどれだけ増えるか考えれば答えに行き着きます。
ポイント関係なしってことは、マイナスないってことだよな。
ってことで、適当に回答。
（１）４個の場合
１５種類
（２）ｎ個の場合
２ｎ－１種類
それぞれの分銅を使うか使わないかの２通りが考えられる。
ただし、全部の分銅を使わなかった場合は重さ０なので測るとはいえない。
ゆえに上記の回答となる。
で、この場合の条件ですが、（言葉にするのが難しいな）
いかなる任意の分銅の組み合わせも、
その残りの分銅の任意の組み合わせと、
合計の重量が一緒になってはならない。
って感じでしょうか。
さいのぎさん、間違ってるよ。
これは、僕も答えを知らないから、参戦できますね。
僕も最初さいのぎさんと同じように考えたのですが、おもりは天秤の左右両方に乗せることができるので、１個のおもりについて２通りではなく３通りの乗せ方が考えられます。
だから、理論的には、最大３ｎ通り。でも、実際にはそういうおもりの組み合わせはなさそう。で、バルタン星人さんのヒントから、１個ずつ増やすことを考えました。
１個 … １ｇのみ。
２個 … １ｇ、３ｇ。４ｇまで測れる。
３個 … １ｇ、３ｇ、８ｇ。１２ｇまで測れる。
４個 … １ｇ、３ｇ、８ｇ，２１ｇ。３３ｇまで測れる。
結局、前の個数で測ることのできる数（おもりの合計の重さ）より１大きい数を、前の個数の時の最大のおもりに加えてやれば、一番効率が良さそうです。
だから、級数の和の公式を使えば、ｎの場合も出るはずだけど…なんだったっけ？（汗）
藤島さん、
左右に載せられると言う考えは正解。
２個目までも正解。３,４個目は×。
３ｎから解くなら、量れない場合と
ダブルカウントの分を考えないと。
朝ゆっくり考えていられなかったのですが、通勤中にわかりました。（と思います。）
やはり、３ｎで良かったんですね。ｎ個のおもりが使える場合は、
３０ｇ，３１ｇ，…、３ｎ－１ｇ。
だから、４個だと、１ｇ、３ｇ、９ｇ、２７ｇで、４０ｇまで測れるということになります。
ｎ個だと、上の式で得られるおもりで、Ｓ＝（３ｎ－１）／（３－１）ｇまで測れると。
（１）４個の場合： ４０ 種類
（２）ｎ個の場合： （３ｎ－１）／２ 種類
でしょ！
ちがった？
分銅は片側にしか乗せられないなら、
４個の場合１５種類
Ｎ個の場合（２＊＊Ｎー１）種類
分銅を両側に乗せて良いなら、
４個の場合４０種類
Ｎ個の場合（（３＊＊Ｎー１）／２）種類
１つのおもりにつき、「右｣「左｣｢のせない｣の３通りがあります。
だから、ｎ個の場合すべての場合の数は、３ｎ通りになりますね。
でも、３つとものせない場合があるから、それでは量れないので、１通り減らします。
そして、左右の皿のおもりが入れ替わった組み合わせがあるので、２で割るわけです。
で、答えは、（３ｎ－１）／２ 通りになります。
漸化式で考えるのも１つの方法ですが、これくらいの問題だったら、普通に考えたほうが早いですね。
(お団子もそうでしたが・・・・)
藤島さん、ヒャクレンラランジャさん、いっちゃんさん、正解です。
解説は、ヒャクレンラランジャさんの通り。漸化式なら下記。
ｎ個の分銅でA(n)通りの時、もう１個増えると、A(n)通りの左右の皿に
のせる方法で２A(n)＋１(自身の錘分）だけ、量り方が増えます。
A(n+1)＝３A(n)＋１ ｎをさらに１増やして引き算すると
Ａ(n+2)－Ａ(n+1)＝３（A(n+1)－A(n)）
すなわち階差数列が３の等比数列になります。
A(1)＝１、A(2)＝４なのでA(n)は１＋３＋９＋２７＋８１･････
＝（３n－１）／２
A(4)＝４０
（藤島コメント：解説、ありがとうございました。なお、元の文はちょっと読みづらく感じましたので、勝手ながら、「An」を「A(n)」等と改めさせていただきました。）
１５ と ２ｎ－１ ？
何かひっかけがありそうな気もするけど…
なるほど、左右どちらにものせられるのか…