この組合せ文字列をルールに従って並べることは可能でしょうか

質問

A、B、C、D、Eという5つのアルファベットの重複を許さない組合せは35通りあります。
（A、B、C、D、E、AB、AC、AD、AE～ABCDE）
これを1組づつ書いた35枚のカードがあるとします。

そしてまず初めにそのカードの中から「A」とだけ書かれたカードを置き、その下に続けて以下の２つのルールにしたがってカードを並べて行きます。

ルール１
下に並べるカードはすぐ上にあるカードに書かれてある文字から１つ減らした物か、１つ増やした物しか置けない。
ルール２
並べて行きとき、同じ文字が9個以上続いてはならない。

例
A
AB
ABC
A C
：
：
この例ではAが4個続いていると見ます。

ここように続けて並べて行き、残りの34枚すべてを並べることは可能でしょうか。
もし可能でしたらその並べ方を教えてください。
お願いいたします。

回答No.1

stomachman · ベストアンサー

35通り？ 31通りじゃないですか？
それはさておき。
ルール２について、同じ文字（例えばA)を含むカードはたった12枚しかない。となると、10枚以上連続してAを含むカードが並ぶようにする方が難しいんじゃなかろうか。というわけで、まずはルール１に注目します。

31枚のカードを机の上に適当にばらまいて、互いに「上下に置ける」もの同士の間を線で結ぶと、カードをノードとするひとつの無向グラフができます。ルール１だけを考えると、「このグラフ上でAから出発して、全てのカードを通る経路を求む」という問題です。

まずは実際にグラフを描いてみてはいかがでしょう。こんな風にすると見やすいでしょう：
カードを４つのグループに分けます。
グループ1: 1文字のカード全部と、AB, BC, CD, DE, AE。
グループ2: 2文字のカードの残り5枚と、ABD, BCE, ACD, BDE, ACE。
グループ3: ３文字のカードの残り5枚と、4文字のカード全部。
グループ4: ABCDE
　次に三重の同心円を考えて、それぞれの円にグループをひとつずつ割当て、同心円の中心にグループ４を置きます。もうちょっと詳しく言うと、
(1)大きな円の円周上にグループ1を並べます。まずA～Eを等間隔で並べ、AとBの中間にABを置く。BとCの中間にBC、以下同様。互いに「上下に置ける」もの同士の間を線で結べば１０角形になります。
(2)一回り小さい円の円周上にグループ2を並べます。Aの近くにBEを置く。Bの近くにAC。以下BD、CE、ADを置く。またABの近くにABD、BCの近くにBCE、以下ACD、BDE、ACEを置いて行きます。互いに「上下に置ける」もの同士の間を線で結びます。自己交差のある10辺形が現れるでしょう。一番大きい円とはAB-ABD、BC-BCE、のように5箇所だけで繋がることになります。
(3)一番小さい円の円周上にグループ3を並べます。BEの近くにABEを置く。ACの近くにABC、以下BCD、CDE、ADE。ABEとABCの中間にABCE、以下ABCD、BCDE、ACDE、ABDE。互いに「上下に置ける」もの同士の間を線で結ぶと、１０角形が現れます。
(4)真ん中にABCDを置く。互いに「上下に置ける」もの同士の間を線で結びます。
こう並べると、対称性がはっきり見えるでしょう。

　経路のひとつの例として、グループを順番に網羅して行くのはどうでしょうか。最初にグループ１を全部網羅する。Aから出発して一番大きい円を一周するだけです。次にグループ２を網羅する。これには二番目の円を２つ飛ばしで３周します。それからグループ３を網羅する。三番目の円を一周するだけです。で、最後がABCDE。

さて、ルール2を満たすような経路が存在するかどうか、というのがご質問ですが、上記の例はどうでしょうかね。

お礼

本当に間違いだらけの質問にとても丁寧な解答をしていただいてありがとうございました。
どう考えてこの問題を解けば良いのかすら分からなかった物ですから、
考え方を教えていただいたことは非常に参考になりました。
ありがとうございました。

補足

さっそくありがとうございます。
>35通り？ 31通りじゃないですか？
ご指摘の通りです。31通りです。すみませんでした。m( _ _ )m
他にも誤字だらけで何を考えてたんでしょう。
お恥ずかしい限りです。