質問: 100枚のカードの表裏に数が書かれている「表の数より裏の数のほうが小さい」 100枚のカードの表裏に数が書かれている 「表の数より裏の数のほうが小さい」とルパンは言った。ルパンの発言が正しい事をできるだけ少ない手順で確かめたい。 という問題で、 表の数の最小値を見つけ、カードを裏返し、裏の数が、その最小値以下のカードを取り除く。 残ったカードの裏の数の最大値を見つけ、カードを裏返し、表の数が、その最大値以上のカードを取り除く。 これを繰り返して、カードがなくなれば、正しいことが示せる と答えたのですが、 もっと賢い回答、ありますか? 「少ない手順」の定義次第というツッコミがありそうなので、 カードを裏返すのは何枚でも手順1回 記憶できるのは数値1つだけ つまり100枚のカードを個別にチェックすれば手順は100回となります。
回答: no12 です。 失礼しました。 質問者さんの回答においても、 運が悪くても、手順3回目で、o1を裏返すことになるので、 ルパンの発言が正しいといえる手順回数は 運が悪くても3回になるんですね。 一応、誤解はしていないつもりなのですが、 おそらく「順番に」という表現が 「1回で」としなければならなかったのだと思います。 いずれにせよ、手順回数が減らせていませんし、 運がよくても手順が3回になってしまうので、 no12の回答は取り下げます。 失礼しました。