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

質問

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

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

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

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

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

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

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

回答No.1

Tacosan · ベストアンサー

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

お礼

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