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

100枚のカードの表裏に数が書かれている
「表の数より裏の数のほうが小さい」とルパンは言った。ルパンの発言が正しい事をできるだけ少ない手順で確かめたい。

という問題で、
表の数の最小値を見つけ、カードを裏返し、裏の数が、その最小値以下のカードを取り除く。
残ったカードの裏の数の最大値を見つけ、カードを裏返し、表の数が、その最大値以上のカードを取り除く。
これを繰り返して、カードがなくなれば、正しいことが示せる
と答えたのですが、

もっと賢い回答、ありますか？

「少ない手順」の定義次第というツッコミがありそうなので、
カードを裏返すのは何枚でも手順１回
記憶できるのは数値１つだけ
つまり１００枚のカードを個別にチェックすれば手順は１００回となります。

No.14 ベストアンサー 回答者： sukitaro 回答日時： 2021/09/16 22:38

No12 です。

失礼しました。

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

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

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

失礼しました。

この回答へのお礼

応答ありがとうございます
＞No12の回答は取り下げます。
二次元配置を利用しても、妙案が見いだせない件、了解です。

私も考えてみましたが、結局、二次元配置を利用しても、最初の解答より良い手順はみつかりませんでした。

その理由です。
二次元配置上のあるカードを確かめると、そのカードより左下にあるカード（表の数が大きく、裏の数が小さい）の確認が可能になりますよね。

ということは、二次元配置上のカードを囲む凸多角形を考えて、その頂点のカードを確かめることが必要であり、また十分であることがわかります。
この「頂点のカードを調べる」ことは、正に、
　私の最初の解答と同じ
であることに気が付きました。

もちろん、数値の絶対値を含めて位置記憶できれば、
　対角線より左下にカードが配置されることで判断
できますが、これでは当たり前すぎて、数学パズル問題にならないですよね（笑い）

お付き合いありがとうございました。

お礼日時：2021/09/17 13:58

No.13 回答者： Tacosan 回答日時： 2021/09/16 18:34

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

どのような「数」がどのように書かれているか
というのも影響するよ.

この回答へのお礼

再度のツッコミですね

＞どのような「数」がどのように書かれているか

ルパンの発言から、大小関係が判定可能な数　でしょうか。
つまり複素数ではなく、実数、答案では「正の整数」と仮定しても一般性は失われないと思います。

お礼日時：2021/09/16 21:14

No.12 回答者： sukitaro 回答日時： 2021/09/16 17:41

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

・おもての小さい順で左から右に並べ替える
・質問者さんの手順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

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

この回答へのお礼

場所の記憶をつかって２次元に配置するアイデアありがとうございます。
すいません、その先の具体的な手順がよくわかりません。
再度の回答お願いします。

以下、私の答案を誤解されていますので、説明させて下さい。
＞質問者さんの手順2回目では、u5を覚えて、
＞順番に、おもてに返していくと思います。

違います。私の答案では、裏の最大値 u5 を覚えて
まとめて１回でおもてに返して、
　カードおもてにU5以上の値が書かれているカード
を取り除きます。
この取り除くカードとは、ルパンの発言が正しい事が確認できたカードです。

運が良ければ全てのカードが取り除けて終了となります。
運が悪くても、最低u5 のカード１枚は取り除けます。

つまり、１回の手順で最低１枚、運がよければ複数枚カードを取り除けることになっています。

お礼日時：2021/09/16 21:37

No.11 回答者： ありものがたり 回答日時： 2021/09/16 14:38

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

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

この回答へのお礼

＞どれがまだ裏返してないカードかは、覚えておけるんですかね？
問題に書いてないですが、
　場所の記憶（処理済みのカードと、処理前のカードを別の場所に置くなど）
で可能な気がします。

私の答案も、確認済みのカードは取り除いていますので、これも場所の記憶を活用した回答ですね。

大きさ順に並べて、その場で裏返すと、順序については、場所の記憶を使うことで、賢い答案をひねり出せそうでしょうかね。

賢い答案、お待ちしています。

お礼日時：2021/09/16 15:00

No.10 回答者： ありものがたり 回答日時： 2021/09/16 12:26

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

＞ のは手順１回で可能です。

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

この回答へのお礼

再度の応答ありがとうございます

＞それって、一手で100枚裏返して終わりじゃないの？
運良く、表のカードの最小値よりも、裏返したカード全てが小さい値ならば、おっしゃるとおりです。

＞全ての情報が得られるのだから。
確かに。でも、
　記憶できるのは数値１つだけ
なので裏返した瞬間に、今見えているカードのどれが記憶したカードの表裏関係なのかは不明ですよね。

表裏関係が確実なのは、指定した１枚のカードを裏返した場合だけです。
＃全ての情報を記憶できるなら、数学パズル問題にならないですよ（笑い）

お礼日時：2021/09/16 14:21

No.9 回答者： sukitaro 回答日時： 2021/09/16 12:21

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

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

この回答へのお礼

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

＞並べ替えるのは、手順回数に含まれるのでしょうか？
含まれない様です。

手順回数は、カードを裏返す回数だけですね。

お礼日時：2021/09/16 14:53

No.8 回答者： Tacosan 回答日時： 2021/09/16 01:01

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

どっちが表でどっちが裏
なんだろうか.

この回答へのお礼

ツッコミありがとう。
問題の前提条件については、あんまり考えたことなかったです。

＞どっちが表でどっちが裏
＞なんだろうか.

さー、わかりませんね。
きっと表が赤、裏が青いカードのように
　表裏が明白にわかるカード
なんでしょね。
また、初期状態は、
　全てのカードが表になっている状態でテーブルに広げられている
んでしょうね。

で、もっと賢い回答、お待ちしています。

お礼日時：2021/09/16 07:23

No.7 回答者： ありものがたり 回答日時： 2021/09/16 00:47

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

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

この回答へのお礼

＞実は全部めくってみるまで正しいかどうかは判らない。
そんなことないですよ。
全てのカードが、表の最小値より小さい数値が書かれている場合、
　例えば表は３桁の数値、ウラ面は２桁の数値
なら私の回答した方法では、
　１回裏返した段階で、全てのウラ面が表の最小値より小さいことが確認できるので、手順１回で、ルパンの発言が正しい事を確認できると思います。

確認ですが、問題は
　ルパンの発言が正しい事をできるだけ少ない手順で確かめたい。
です。
また、
　個別でなく全部のカードをまとめて裏返す
のは手順１回で可能です。

引き続き、もっと賢いやり方の回答、お待ちしています。

お礼日時：2021/09/16 07:38

No.6 回答者： kairou 回答日時： 2021/09/15 19:23

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

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

この回答へのお礼

何度も応答ありいがとうございます。

もっと賢い回答、思いついたら、再度の応答お待ちしています。

お礼日時：2021/09/15 20:41

No.5 回答者： ありものがたり 回答日時： 2021/09/15 17:34

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

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

この回答へのお礼

応答ありがとうございます。

＞100枚全部めくってみる以外に確認する方法は無い。
私の解答のどこがダメなのですか？

表の数の最小値を見つけ、カードを裏返し、裏の数が、その最小値以下のカードを取り除く。

少なくとも１回に１枚は取り除け、普通は２枚以上取り除けるので、ルパンの発言が正しい事が１００回以内の手順で確かめると思うのですが・・・

もし取り除くカードが見つからない場合は、
　表の数の最小値のカードが反例
ということで、ルパンの発言が間違っていたことの確認になりますよね。

お礼日時：2021/09/15 20:49