gooドクター有料プランが1ヶ月間無料!

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

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

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

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

A 回答 (14件中1~10件)

No12 です。



失礼しました。

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

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

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

失礼しました。
    • good
    • 0
この回答へのお礼

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

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

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

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

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

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

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

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


どのような「数」がどのように書かれているか
というのも影響するよ.
    • good
    • 0
この回答へのお礼

再度のツッコミですね

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

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

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

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


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

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

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

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

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

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

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

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

> 記憶できるのは数値1つだけ



ああ、そうか。なるほど。
それで、どれがもう裏返したカードで
どれがまだ裏返してないカードかは、覚えておけるんですかね?
    • good
    • 0
この回答へのお礼

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

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

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

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

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

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


> のは手順1回で可能です。

それって、一手で100枚裏返して終わりじゃないの?
全ての情報が得られるのだから。
    • good
    • 0
この回答へのお礼

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

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

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

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

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

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


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

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

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

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

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

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


どっちが表でどっちが裏
なんだろうか.
    • good
    • 0
この回答へのお礼

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

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

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

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

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

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



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

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

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

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

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

>ある2次関数の(X,Y)のペア という規則性がありますよ。



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

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

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

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

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


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

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

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

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

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

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

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング