入試問題

質問

今受験の入試問題をしているのですが理解に苦しむ問題があるのです！！教えてほしぃです。。。

任意の異なる5枚のカードを、2枚のカードを見比べることによってのみ判断し、7回で小さい順に並べ替える、具体的な手順を述べよ。

回答No.3

kts2371148 · ベストアンサー

この先逐一やり取りするわけにはいきませんので、
別サイトの回答をご覧下さい… といってリンクを貼るのは
規約違反（営業妨害とみなされる）ようですので、
こちらにも回答を書いておきます。

１回目に a と b を比較し、２回目に c と d を比較します。
ここでは仮に a < b , c < d だったとします。
もし例えば a > b であったときは、
続きの手順の a と b を読み替えればＯＫです。
（以降の説明で「仮に～だったとします」と書いてある場合、
同様に読み替えてください。）

３回目は、a と c を比較します。ここでは仮に a < c だったとします。
（この時点では、a < b , a < c < d が判明しています。）
４回目は、c と e を比較します。
この結果によって、５回目以降の手順が異なります。

（４回目が c < e の場合）
この時点では、a < b , a < c < d , c < e が判明しています。
５回目で d と e を比較します。ここでは仮に d < e だったとします。
この時点では a < b , a < c < d < e が判明していますので、
あとは b がどこにくるかということになります。
したがって、６回目で b と d を比較し、
７回目では b < d なら b と c を比較し、
b > d なら b と e を比較すると、５枚の大小関係がわかります。

（４回目が c > e の場合）
この時点では、a < b , a < c < d , e < c が判明しています。
５回目では、b と c を比較してもＯＫですし、a と e を比較してもＯＫです。
もし以上の手順が理解できていれば６回目・７回目は容易だと思いますので省略します。

お礼

本当にありがとぅございました。わたしのお礼の気持ちです。

回答No.2

kts2371148

＃１です。
a<b かつ c<d を満たす a,b,c,d の並べ方の総数はＯＫのようですね。
あとは、e を５箇所のどこかに入れればいいので、
a<b かつ c<d を満たす a,b,c,d,e の並べ方の総数は
６×５＝３０通りです。
これは 2^5=32 以内ですから、問題ありません。

というわけで、３回目の比較になります。
どれかとどれかを比較して、その結果として
１５通りと１５通りにきれいに分かれればＯＫですが、
１０通りと２０通りなどのように分かれてしまうとＮＧです。
選択肢は、
e と他のどれかを比較する
a と c を比較する（b と d でも同様）
b と c を比較する（a と d でも同様）
の３つで、ＯＫなのはこのうち１つしかありません。

回答No.1

kts2371148

私は別サイトでこの問題を見たのですが、
なかなかおもしろい問題だと思いました。
でも、入試問題でこれを出されるとちょっときついですが…

まず、ヒントを出してみます。
５枚のカードを a,b,c,d,e とします。
５枚のカードを並び替える並べ方の総数は 5!=120 通りです。
７回の判定で、2^7=128 通りの区別が可能ですから、
理論上は７回でできる可能性がある、ということになります。

１回目はどれでもいいので、a と b を比較します。
ここでは、仮に a < b とします。
a < b を満たす並べ方の総数は 60 通りですから、
残り６回の判定で、2^6=64 通りを区別すればＯＫです。

２回目の比較がポイントです。
もし b と c を比較すると、
(b < c の場合) a < b < c を満たす並べ方の総数は 20 通り
(b > c の場合) a < b , c < b を満たす並べ方の総数は 40 通り
となり、残り５回の判定で 2^5=32 通りしか区別できませんので、
前者であればいいですが、後者であれば７回を越える場合が出てきます。
それで、２回目の比較は c と d （またはそれと同等のもの）でなければなりません。

このように、残りの比較回数で区別が可能かどうか計算してみて、
不可能であれば早めにその方法を切り捨てて、
違う方法で比較する、というのがポイントです。

とりあえず、今日はここまでにします。
もしよければ、この先わかる範囲で答えを書いてみてください。

補足

回答ありがとぅございます。。。
学校の先生が教えてくれるみたいになってますね！？ワラ

cとdを比較して、仮にc<dとします。
a<b<c<d
a<c<d<b
a<c<b<d
c<d<a<b
c<a<b<d
c<a<d<b
それぞれの並べ方の通り数を出して、残り5回の2^5=32通り内にこれが入るか調べる・・・・・・・・・・・

ごめんなさぃ。。。全然わかりません。教えてぇ！！