100枚のカードの表裏に数が書かれている「表の数より裏の数のほうが小さい」

Question

100枚のカードの表裏に数が書かれている
「表の数より裏の数のほうが小さい」とルパンは言った。ルパンの発言が正しい事をできるだけ少ない手順で確かめたい。

という問題で、
表の数の最小値を見つけ、カードを裏返し、裏の数が、その最小値以下のカードを取り除く。
残ったカードの裏の数の最大値を見つけ、カードを裏返し、表の数が、その最大値以上のカードを取り除く。
これを繰り返して、カードがなくなれば、正しいことが示せる
と答えたのですが、

もっと賢い回答、ありますか？

「少ない手順」の定義次第というツッコミがありそうなので、
カードを裏返すのは何枚でも手順１回
記憶できるのは数値１つだけ
つまり１００枚のカードを個別にチェックすれば手順は１００回となります。

sukitaro · Accepted Answer

No12 です。

失礼しました。

質問者さんの回答においても、
運が悪くても、手順3回目で、o1を裏返すことになるので、
ルパンの発言が正しいといえる手順回数は
運が悪くても3回になるんですね。

一応、誤解はしていないつもりなのですが、
おそらく「順番に」という表現が
「1回で」としなければならなかったのだと思います。

いずれにせよ、手順回数が減らせていませんし、
運がよくても手順が3回になってしまうので、
No12の回答は取り下げます。

失礼しました。

Tacosan · Answer

もう 1つ「前提」の話をすると, 「数が書かれている」のところで
どのような「数」がどのように書かれているか
というのも影響するよ.

sukitaro · Answer

並べ替えるのが手順回数を増やさないのだとすれば、
・おもての小さい順で左から右に並べ替える
・質問者さんの手順1回目を実行する
・裏の小さい順で上から下に並べ替える
を実行すれば、行列のようなものが出来上がります。

たとえば、
カード(i)のおもての数字をoi, 裏の数字をuiと書くとして、
おもての小さい順で、
o1<o2<o3<o4<o5
となる5枚のカードについて、
仮に、
u2<u3<u4<u1<u5
となった場合、

* u2 * * *
* * u3 * *
* * * u4 *
u1 * * * *
* * * * u5

とあらわせます。（「*」は、カードを置いていない空白）

横に見れば、左から右に、おもて数字の小さい順で、
縦に見れば、上から下に、裏の数字の小さい順です。
なお、上記の状態では、裏を向いているので、
おもての数字（o1からo5）は、記憶されていません。

質問者さんの手順2回目では、u5を覚えて、
順番に、おもてに返していくと思います。
運が良ければ、u5<o1になって、ルパンの発言が真と分かります。
運が悪ければ、u5<o5しか分からず、カードが4枚残ります。

一方、u5ではなく、u1を覚えてカード(1)をおもてに返せば、
少なくとも4枚は必ず取り除けます。

o1<u1であれば、ルパンの発言は偽です。
u1<o1ならば、
u2<u3<u4<u1<o1<o2<o3<o4で、
カード(1)から(4)まで、すべて取り除けるので、
残りはカード(5)だけなので、
手順をあと1回かけて調べれば、必ず答えが出ます。

上記の例は、たまたま効率的になる例でしたが、

* * * u4 *
u1 * * * *
* u2 * * *
* * u3 * *
* * * * u5

みたいな例であれば、
質問者さんの回答の方が早く答えが出ると思います。

ありものがたり · Answer

＞ 記憶できるのは数値１つだけ

ああ、そうか。なるほど。
それで、どれがもう裏返したカードで
どれがまだ裏返してないカードかは、覚えておけるんですかね？

ありものがたり · Answer

＞ 個別でなく全部のカードをまとめて裏返す
＞ のは手順１回で可能です。

それって、一手で100枚裏返して終わりじゃないの？
全ての情報が得られるのだから。

sukitaro · Answer

並べ替えるのは、手順回数に含まれるのでしょうか？
たとえば、横に表の小さい順、
縦に裏の小さい順に並べ替えるようにすれば、
記憶すべきカードが少し効率的になるような気がします。

Tacosan · Answer

非常に根本的な疑問なんだけど, それぞれのカードで
どっちが表でどっちが裏
なんだろうか.

ありものがたり · Answer

＞ これを繰り返して、カードがなくなれば、正しいことが示せる

なるほど、一見何か凝った方法があるようにみせて、
実は全部めくってみるまで正しいかどうかは判らない。
途中で判例となるカードが見つかればそこで終了というわけか。
それだったら、片っ端からめくってみるだけでいいじゃない。
その方法に何か意味があるの？

kairou · Answer

＞ある２次関数の（X,Y）のペア という規則性がありますよ。

表と裏の数字に 同じ規則性が無いと NO2 は 成立しません。
30, 20, 10 と 25、23、9 が 同じ規則性があるなら、
すみませんが 私の 能力の範囲外ですので、これで 終わりにします。

ありものがたり · Answer

100枚全部めくってみる以外に確認する方法は無い。
９９枚めくって、それらについて正しかったとしても、
100枚目の裏に、これまで見た199個のどの数よりも
大きい数が書かれている可能性は常にあるからだ。

100枚のカードの表裏に数が書かれている「表の数より裏の数のほうが小さい」

No12 です。

もう 1つ「前提」の話をすると, 「数が書かれている」のところで

並べ替えるのが手順回数を増やさないのだとすれば、

＞ 記憶できるのは数値１つだけ

＞ 個別でなく全部のカードをまとめて裏返す

並べ替えるのは、手順回数に含まれるのでしょうか？

非常に根本的な疑問なんだけど, それぞれのカードで

＞ これを繰り返して、カードがなくなれば、正しいことが示せる

＞ある２次関数の（X,Y）のペア という規則性がありますよ。

100枚全部めくってみる以外に確認する方法は無い。

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

＞記憶できるのは数値１つだけ

＞個別でなく全部のカードをまとめて裏返す

＞これを繰り返して、カードがなくなれば、正しいことが示せる

＞ある２次関数の（X,Y）のペアという規則性がありますよ。