論理パズルの最小手数

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

No.1 ベストアンサー 回答者： okg00 回答日時： 2006/10/15 00:31

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

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

この回答へのお礼

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

お礼日時：2006/10/15 17:41

No.7 回答者： mayan99 回答日時： 2006/10/15 14:54

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

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

この回答へのお礼

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

お礼日時：2006/10/15 17:46

No.6 回答者： ebinamori 回答日時： 2006/10/15 04:44

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

この回答へのお礼

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

お礼日時：2006/10/15 17:45

No.5 回答者： stomachman 回答日時： 2006/10/15 03:32

　「どんなパズルでも最小手数を求められる」という訳には行きません。

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

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

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

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

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

この回答へのお礼

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

お礼日時：2006/10/15 17:45

No.4 回答者： akitaken 回答日時： 2006/10/15 03:01

私は０回だと思います。

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

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

この回答へのお礼

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

お礼日時：2006/10/15 17:45

No.3 回答者： chiropy 回答日時： 2006/10/15 00:35

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の二つ目なんか読みごたえありますよ。来年に大学受験を控えた私は、最近こういう問題に触れる時間がめっぽうなくなり悲しいです（涙）

この回答へのお礼

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

お礼日時：2006/10/15 17:44

No.2 回答者： chiropy 回答日時： 2006/10/15 00:35

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の二つ目なんか読みごたえありますよ。来年に大学受験を控えた私は、最近こういう問題に触れる時間がめっぽうなくなり悲しいです（涙）