1からnまで順に重ねる －スパイダーソリティア－

　「スパイダーソリティア」というのがMSのOSを使うと必ず「ゲーム」に入っていますよね。あれは簡単に言えばカードを、Aが一番上に来るように番号順に重ねるゲームです（簡単すぎ）。で、暇に任せてやっていると、上に重ねたつもりが、隣の空白に積んでしまって、１手損することがよくあります。

　そうならないような一番いい方法は、間に空白を作らないことなんですが、「それはいつでも可能なんだろうか」と考えてみました。

　簡単のために1～nのカードがそれぞれ１枚ずつあり、それがランダムに横に並んでいるとします。この状態からカードを移動し、間に空白を作らずに、1からnまで順番に重なるようにできるでしょうか。

　例えば、３１２とあったら、１を２の上に重ねると、３と２（１）の間に空白ができます。これはダメですが、２を３の上に重ねるとo.k.で、さらに１を重ねれば３（２（１））となります。

　両端の数のうち、片方が最大nであっても、その反対の端はnより小さいので、それをどこかに重ねることができます。それをn-1回繰り返すと完成！

　こんな簡単な証明でいいのでしょうか。実際にはカードの束を動かす場合も多いし、厳密かどうかも分かりません。

　どんなnでも、どんな並びでも可能でしょうか。ヒントください。

No.1 ベストアンサー 回答者： Tacosan 回答日時： 2007/06/08 21:11

あ～考えたことなかったなぁ....

基本的にその線でいいと思います. 「1, 2, ..., n のうち k と k+1 を重ねたら (1, 2, .., k-1, [k, k+1], k+2, ..., n になるけど) 1, 2, ..., n-1 と本質的に同じ」といって帰納法かな.

この回答へのお礼

早速ありがとうございます。

お礼日時：2007/06/11 07:51