論理パズルの最小手数

質問

天秤を使って偽物の玉を選び出す問題、川渡りの問題などいろいろな論理パズルがありますが、あれらの最小手数を求めることは可能なのでしょうか？
たとえば適当に
『ここに見た目、質量、手触りなどが全く同じ玉2005個と、質量のみが少しだけ重い玉が1個、計2006個ある。これらの中から重さの違う1個を選ぶには、天秤ばかりに最低何回乗せればいいか』
といった問題を作ったとして、すぐに答えを出せるような公式は求められるのでしょうか？

回答No.1

okg00 · ベストアンサー

http://www-imai.is.s.u-tokyo.ac.jp/~yato/puzzle/y2001/q200104.html

パズルによりますが、例題の場合だと上記URLに参考となる証明があります。
発展問題として、「天秤が一回だけウソをつく」などもありますよ。
http://q.hatena.ne.jp/1160186888

お礼

回答ありがとうございます

回答No.7

mayan99

天秤を使う問題は、３グループに分けて、そのうち２つを計ると、重い玉があるグループが特定できるのですから、３で割っていって１以下になる回数になります。

３＾７＝２１８７
２００６個の場合は７回ですね

お礼

回答ありがとうございました

回答No.6

ebinamori

「ゲーム理論」とかしらべてみるといいかも

お礼

回答ありがとうございました

回答No.5

stomachman

「どんなパズルでも最小手数を求められる」という訳には行きません。なぜなら、どうやっても解けないことが証明されている「パズル」もあるからです。実際、天才的パズル作家サム・ロイド作の「15パズル」は決して解けないパズルです。（　http://ja.wikipedia.org/wiki/15パズル
の「不可能な配置」の所に元々の15パズルが示されています。）

　さらに、全てのアルゴリズム、および数学の大抵の問題は「パズル」という形で表現することも可能なんじゃなかろうかと思います。だとすると、「いろんな論理パズル」と仰る中には、極めて多様な問題が含まれています。その中には未解決の難問もあるし、運が良ければ解けて運が悪いと解けないもの、絶対解けないと分かっているものもある。

　ところで、ご質問の例題の答は「１回」です。
　2006個のうちから２個をテキトーに選んで天秤に掛ける。運良く天秤が傾けば、下がった方が求める１個である。だから、最小手数は１回。つまり、「運が良ければ1回でできる」わけです。

　冗談を言ってるんじゃありません。これは、計算の手数についての数学である「計算量の理論」に出て来る重要な概念「非決定的アルゴリズム（non-deterministic algorithm)」の一例です。

　で、（おそらく）tatumi10さんが意図なさった例題のほうは、たとえば以下のように表現されるべきでしょう：
『ここに見た目、質量、手触りなどが全く同じ玉2005個と、質量のみが少しだけ重い玉が1個、計2006個ある。これらの中から重さの違う1個を選ぶために天秤だけを使うあらゆる手順のうち、天秤ばかりの使用回数の最大値が最小であるような手順について、その最大値は幾らか』

お礼

回答ありがとうございました

回答No.4

akitaken

私は０回だと思います。

重さが違うのなら自分の手で持てば分かるのではないでしょうか？

恐らくこんな回答では×だとおもいますが＾＾；

お礼

回答ありがとうございました

回答No.2

chiropy

http://oshiete1.goo.ne.jp/kotaeru.php3?q=3528
http://oshiete1.goo.ne.jp/kotaeru.php3?q=30706
http://oshiete1.goo.ne.jp/kotaeru.php3?q=2405085

この手の質問はたくさんありますね。私自身もこういうのに興味があるので、よく調べているのですが、上のURLの二つ目なんか読みごたえありますよ。来年に大学受験を控えた私は、最近こういう問題に触れる時間がめっぽうなくなり悲しいです（涙）

回答No.3

chiropy

http://oshiete1.goo.ne.jp/kotaeru.php3?q=3528
http://oshiete1.goo.ne.jp/kotaeru.php3?q=30706
http://oshiete1.goo.ne.jp/kotaeru.php3?q=2405085

この手の質問はたくさんありますね。私自身もこういうのに興味があるので、よく調べているのですが、上のURLの二つ目なんか読みごたえありますよ。来年に大学受験を控えた私は、最近こういう問題に触れる時間がめっぽうなくなり悲しいです（涙）

お礼

回答ありがとうございました