ウォッチ
100枚のカードの表裏に数が書かれている
「表の数より裏の数のほうが小さい」とルパンは言った。ルパンの発言が正しい事をできるだけ少ない手順で確かめたい。
という問題で、
表の数の最小値を見つけ、カードを裏返し、裏の数が、その最小値以下のカードを取り除く。
残ったカードの裏の数の最大値を見つけ、カードを裏返し、表の数が、その最大値以上のカードを取り除く。
これを繰り返して、カードがなくなれば、正しいことが示せる
と答えたのですが、
もっと賢い回答、ありますか？
「少ない手順」の定義次第というツッコミがありそうなので、
カードを裏返すのは何枚でも手順１回
記憶できるのは数値１つだけ
つまり１００枚のカードを個別にチェックすれば手順は１００回となります。
No.14ベストアンサー
- 回答日時：
No12 です。
失礼しました。
質問者さんの回答においても、
運が悪くても、手順3回目で、o1を裏返すことになるので、
ルパンの発言が正しいといえる手順回数は
運が悪くても3回になるんですね。
一応、誤解はしていないつもりなのですが、
おそらく「順番に」という表現が
「1回で」としなければならなかったのだと思います。
いずれにせよ、手順回数が減らせていませんし、
運がよくても手順が3回になってしまうので、
No12の回答は取り下げます。
失礼しました。
-
-
- 0
- 件
-
応答ありがとうございます
＞No12の回答は取り下げます。
二次元配置を利用しても、妙案が見いだせない件、了解です。
私も考えてみましたが、結局、二次元配置を利用しても、最初の解答より良い手順はみつかりませんでした。
その理由です。
二次元配置上のあるカードを確かめると、そのカードより左下にあるカード（表の数が大きく、裏の数が小さい）の確認が可能になりますよね。
ということは、二次元配置上のカードを囲む凸多角形を考えて、その頂点のカードを確かめることが必要であり、また十分であることがわかります。
この「頂点のカードを調べる」ことは、正に、
私の最初の解答と同じ
であることに気が付きました。
もちろん、数値の絶対値を含めて位置記憶できれば、
対角線より左下にカードが配置されることで判断
できますが、これでは当たり前すぎて、数学パズル問題にならないですよね（笑い）
お付き合いありがとうございました。
No.12
- 回答日時：
並べ替えるのが手順回数を増やさないのだとすれば、
・おもての小さい順で左から右に並べ替える
・質問者さんの手順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
みたいな例であれば、
質問者さんの回答の方が早く答えが出ると思います。
-
-
- 0
- 件
-
場所の記憶をつかって２次元に配置するアイデアありがとうございます。
すいません、その先の具体的な手順がよくわかりません。
再度の回答お願いします。
以下、私の答案を誤解されていますので、説明させて下さい。
＞質問者さんの手順2回目では、u5を覚えて、
＞順番に、おもてに返していくと思います。
違います。私の答案では、裏の最大値 u5 を覚えて
まとめて１回でおもてに返して、
カードおもてにU5以上の値が書かれているカード
を取り除きます。
この取り除くカードとは、ルパンの発言が正しい事が確認できたカードです。
運が良ければ全てのカードが取り除けて終了となります。
運が悪くても、最低u5 のカード１枚は取り除けます。
つまり、１回の手順で最低１枚、運がよければ複数枚カードを取り除けることになっています。
No.11
- 回答日時：
＞ 記憶できるのは数値１つだけ
ああ、そうか。なるほど。
それで、どれがもう裏返したカードで
どれがまだ裏返してないカードかは、覚えておけるんですかね？
-
-
- 0
- 件
-
＞どれがまだ裏返してないカードかは、覚えておけるんですかね？
問題に書いてないですが、
場所の記憶（処理済みのカードと、処理前のカードを別の場所に置くなど）
で可能な気がします。
私の答案も、確認済みのカードは取り除いていますので、これも場所の記憶を活用した回答ですね。
大きさ順に並べて、その場で裏返すと、順序については、場所の記憶を使うことで、賢い答案をひねり出せそうでしょうかね。
賢い答案、お待ちしています。
No.10
- 回答日時：
＞ 個別でなく全部のカードをまとめて裏返す
＞ のは手順１回で可能です。
それって、一手で100枚裏返して終わりじゃないの？
全ての情報が得られるのだから。
-
-
- 0
- 件
-
再度の応答ありがとうございます
＞それって、一手で100枚裏返して終わりじゃないの？
運良く、表のカードの最小値よりも、裏返したカード全てが小さい値ならば、おっしゃるとおりです。
＞全ての情報が得られるのだから。
確かに。でも、
記憶できるのは数値１つだけ
なので裏返した瞬間に、今見えているカードのどれが記憶したカードの表裏関係なのかは不明ですよね。
表裏関係が確実なのは、指定した１枚のカードを裏返した場合だけです。
＃全ての情報を記憶できるなら、数学パズル問題にならないですよ（笑い）
No.7
- 回答日時：
＞ これを繰り返して、カードがなくなれば、正しいことが示せる
なるほど、一見何か凝った方法があるようにみせて、
実は全部めくってみるまで正しいかどうかは判らない。
途中で判例となるカードが見つかればそこで終了というわけか。
それだったら、片っ端からめくってみるだけでいいじゃない。
その方法に何か意味があるの？
-
-
- 0
- 件
-
＞実は全部めくってみるまで正しいかどうかは判らない。
そんなことないですよ。
全てのカードが、表の最小値より小さい数値が書かれている場合、
例えば表は３桁の数値、ウラ面は２桁の数値
なら私の回答した方法では、
１回裏返した段階で、全てのウラ面が表の最小値より小さいことが確認できるので、手順１回で、ルパンの発言が正しい事を確認できると思います。
確認ですが、問題は
ルパンの発言が正しい事をできるだけ少ない手順で確かめたい。
です。
また、
個別でなく全部のカードをまとめて裏返す
のは手順１回で可能です。
引き続き、もっと賢いやり方の回答、お待ちしています。
No.5
- 回答日時：
100枚全部めくってみる以外に確認する方法は無い。
９９枚めくって、それらについて正しかったとしても、
100枚目の裏に、これまで見た199個のどの数よりも
大きい数が書かれている可能性は常にあるからだ。
-
-
- 0
- 件
-
応答ありがとうございます。
＞100枚全部めくってみる以外に確認する方法は無い。
私の解答のどこがダメなのですか？
表の数の最小値を見つけ、カードを裏返し、裏の数が、その最小値以下のカードを取り除く。
少なくとも１回に１枚は取り除け、普通は２枚以上取り除けるので、ルパンの発言が正しい事が１００回以内の手順で確かめると思うのですが・・・
もし取り除くカードが見つからない場合は、
表の数の最小値のカードが反例
ということで、ルパンの発言が間違っていたことの確認になりますよね。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう！
おすすめ情報
このカテゴリの人気Q&Aランキング
-
4
３行３列の行列の和と積の計算...
-
5
積分で1/x^2 はどうなるのでし...
-
6
1000分の３は何％ですか
-
7
６でわると、商が８になる整数...
-
8
キログラム（kg）を立米（m3）...
-
9
アップ率の求め方について
-
10
15％増しの計算方法
-
11
「原価に20％乗っけて販売」っ...
-
12
パーセンテージの平均の出し方は？
-
13
偏微分の記号∂の読み方について...
-
14
どこまで行けますか。
-
15
時間を100進法であらわしたい。
-
16
ln、expの電卓関数の使い方が分...
-
17
減少率の出し方
-
18
±4σに入る確率について教えてく...
-
19
cos x = 0の解の書き方について
-
20
そこにいる確率。
おすすめ情報
公式facebook
公式twitter
