ヤマネの姪の椅子



  • @Hannibal さん
    ムズイ。スイスイ行ってたら14~16回で詰みました。
    地蔵和讃が聞こえております。(;'∀')



  • @Hannibal さん
    新しい問題ありがとうございます。
    前回の問題の想定解の咀嚼がまだ済んでないのですが、こちらの問題からm(__)m
    昨日は疲れていたため、作図までして寝落ちして今頃ごそごそ起きてきたらすでに第2問が出てますね。
    せっかく作った図なのでとりあえず

    第1問回答

    0_1574478560836_パズル1.png
    椅子にそれぞれ1~4の番号を、4人をA,B,C,Dと記号をふる。
    1,2,3,4の椅子にA,B,C,Dの順に座った状態でスタート
    最初は1の椅子に座ったAを固定し2,3,4の中で入れ替えていく
    ①3,4の椅子に座ったC,Dが入れ替わる(入れ替わった椅子の色を黄色で示す)
    ②2,3のB,Dが入れ替わる
    ③3,4のB,Cが入れ替わる
    ④2,3のD,Cが入れ替わる
    ⑤3,4のD,Bが入れ替わる
    ここまででAが1に座った6通り(最初の状態も含む)が網羅できる。
    次に1,3を入れ替えAの代わりに1の椅子にBが座りBを固定して同様に2,3,4の席を入れ替え6通り
    さらにC,Dをそれぞれ1の席に固定して6通りずつ入れ替えていくと最初の状態も含めて24通りが網羅できる。

    第2問はこれからむくんだ頭で考えます



  • @Hannibal さん
    第2問はまず4人のまま考えました。というより前回の図を少し順番を入れ替えました

    第2問回答4人バージョン

    0_1574480098711_パズル2.png
    前回はA,B,C,Dを順番に1番で固定しましたが、今回は
    A6通り→C6通り→B3通り→D6通り→B6通り
    のようにBのケースを分割しました。



  • 対称性を追求したら詰みましたので、中途半端をトライしたr出来ましtが
    今度は法則性が???

    失敗

    0_1574488373868_sippai.jpg

    法則性😢

    0_1574488919861_nazeka.png



  • Hannibalさん
    7人バージョンまるで考え付きませんが
    場合の数5040ではないでしょうか?・・・



  • @riffraff 自己レス

    ハノイの塔?

    二人{A,B}~<AB,BA>
    三人 {A,B.C}=<A{B,C},B{C,A},C{a,B}>
    以下略
    4人での説明お絵かき考えます



  • @Hannibal さん
    現時点で

    7人バージョンの方針

    最初に座った椅子の番号で移動の様子を見ることにしました。
    0_1574503717389_パズル3.png
    1番はそのまま固定で残りの3人を移動させると
    最初に真ん中2つの移動のケースと右側2つの移動のケースを見ると
    真ん中スタートは1の隣だった2が6通りの最後に再び1の隣に戻ってくる。
    右側スタートの時は3が最後に1の隣に来る。
    4を1の隣に持ってきたい時は右スタートの3段目を利用できる。
    ※右端の番号の移動も上記と対称で考えられる。

    これを利用して第2問回答の4人バージョンができたので、7人の場合は
    4番目を固定して右の3人、左の3人を移動させ、4番のところで左右の入れ替えを行っていきすべてを確認
    すべて確認していたらとてもトイレは持ちそうにありません💦
    検証も途方もなくてちょっと気合が入りません。(;^_^A



  • マーモセットさん、riffraffさん。
    4人バージョン正解導出、おめでとうございます。

    riffraffさんの正解第一版とマーモセットさんの正解第一版は、本質的な部分でよく似ています!!

    相似点を隠しました

    4ブロック(いづれも長さは6)のうちひとつを二分割して全体をつなげています。これには驚きました。マーモセットさんは左端の椅子、riffraffさんは右端の椅子が長時間すわりっぱなしなのですよね。

    また、おふたりの解は、ネット上には見当たりません。とても珍しいものです。

    実はこの問題は順列を生成するアルゴリズムについてのものに関連していまして…うまくいけば新基軸なのです。

    (一般のnについて上手に定式化できれば論文になるのではないかと思います。)

    もちろん、私が想定していた解とは異なります。

    いやあ参りました。



  • マーモセットさんの7人バージョン、持ち帰らせてください。
    (≧∇≦)

    riffraff さん。
    5040ですね、御指摘を有り難うございました。



  • @マーモセットさん。

    7人バージョンの解説を有り難うございました。4人バージョンでriffraffさんとマーモセットさんとで解の構造が似ていたのはこうしたところに原因があるのかも……?



  • Hannibalさん

    独り言です

    {1,2,3}では、隣接する互換のみを認めた場合
    {1.2.3}からの重複を許さない置換の終点は{1.3.2}と{3.2.1}の二つしかありません。対象人数4人で題意を満たすためにはどこかで端6連を破ることが必要になります。
    {1,2,3,4}以降はどうなるのか・ここで失神しています。
    地蔵和讃が聞こえてきました。(;'∀')



  • 想定解を発表します

    まず2名の順列を考えます。

    じゃじゃーん。

    12
    21

    隣どうしの交換になっていますが、あたりまえすぎますね。

    留意点ですが、前半と後半とがペアになっています。そのココロは…

    12 を 逆順にすると 21 になっています。

    次に3名の順列を考えます。

    それには作成済みの2名の順列群を利用します。すなわち

    12 21

    を利用します。

    これを3名にしたいわけですが、まず奇数番目を処置し、ついで偶数番目を処置します。

    奇数番目の 12 の右側に 3 をつけます。

    123

    この新メンバー 3 は順列の列挙を目的とするならば他にも位置をつけることが可能です。

    そのためには、右端にある 3 を ひとつづつ左側に寄せていけばよいのです。

    123 132 312

    以上が順列列挙のうち奇数番目の順列に新メンバーを追加する操作となります。

    かんたんに標語をつくるならば、
    奇数番目には新メンバーを右端にくっつけて、それから新メンバーの位置をひとつづつ左にずらしていく、このようにしたいわけです。

    偶数番目の 21 の左側に 3 をつけます。

    321

    この新メンバー 3 は順列の列挙を目的とするならば他にも位置をつけることが可能です。

    そのためには、左端にある 3 を ひとつづつ右側に寄せていけばよいのです。

    321 231 213

    以上が順列列挙のうち偶数番目の順列に新メンバーを追加する操作となります。

    かんたんに標語をつくるならば、
    偶数番目には新メンバーを左端にくっつけて、それから新メンバーの位置をひとつづつ右にずらしていく、このようにしたいわけです。

    以上でつくったものをペタペタとくっつけますと、

    123 132 312
    321 231 213

    となります。隣同士で席交換を可能となっていて、しかも、作り方から自明なように、全ての順列を尽くしています。

    なお興味深いことですが、上の3人バージョンの前半、すなわち
    123 132 312
    について、
    ABC→CBA
    と変換してやると、(逆順にすると)
    321 231 213
    を得られることです。これは後半と一致します!!!

    次に4名の順列を考えます。

    それには作成済みの3名の順列群を利用します。すなわち

    123 132 312 321 231 213

    を利用します。

    左からかわりばんこに奇数番目と偶数番目とを処置していきます。

    奇数番目には新メンバー 4 を右端にくっつけて、それから新メンバーの位置をひとつづつ左にずらしていく、偶数番目には新メンバー 4 を左端にくっつけて、それから新メンバーの位置をひとつづつ右にずらしていく、こうい風に処置をしていきます。

    とりあえず新メンバーをくっつけますと

    1234 4132 3124 4321 2314 4213

    となります。

    ついで、4 をシフトしていきます。
    得られるものは以下の通りとなります。

    1234 1243 1423 4123
    4132 1432 1342 1324
    3124 3142 3412 4312
    4321 3421 3241 3214
    2314 2341 2431 4231
    4213 2413 2143 2134

    隣同士で席交換を可能となっていて、しかも、作り方から自明なように、全ての順列を尽くしています。

    なお興味深いことですが、上の4人バージョンの前半、すなわち
    1234 1243 1423 4123 4132 1432 1342 1324 3124 3142 3412 4312

    について、
    ABCD→DCBA
    と変換してやると、(逆順にすると)

    4321 3421 3241 3214 2314 2341 2431 4231 4213 2413 2143 2134

    を得られることです。これは後半と一致します!!!

    実は作り方からみてこの一致は偶然ではなく必然なのだとわかることでしょう。

    なお、証明は省きますが感覚的にもわかる通りに、上記のロジックは、4人バージョンから5人バージョンへの生成、5人バージョンから6人バージョンへの生成、6人バージョンから7人バージョンへの生成、でも有効です。

    オシッコは漏れそうですが……

    ところで座席交換をゆっくりやれば当該の2名の他は連れだってトイレに行っても良いのではないか、たった今思いました。おそらく悪い魔法使いの呪いと言えどもレディのトイレを邪魔するほどの悪意はないのではないでしょうか?

    という感じです。

    なお、この手順を実際に行うとなると多量のメモが必要となります。

    ところが別の手順がありまして、7人バージョンでさえも! たった14個の変数格納容器さえあれば、巧みな手段で次から次へと座席交換の指示が出せる方法が…どうやらあるようなのですよね。

    数学魔法の源泉たる神はなんと偉大なことでしょう!

    なお、この偉大な手順について私は理解が不足していますので、ひょっとしたらガセを言い放つ羽目になっているのかもしれません。ご容赦を!



  • @riffraff さん、6連が破れてしまうこと、仰る通りです。おそらく @マーモセット さんも同様の見地に立っていらっしゃることかと存じます。



  • @Hannibal さん
    想定解拝見しました。
    最初の問題が

    【隣同士に座る2人の座席のみをいれかえることが可能】

    の縛りがなく自由度が高かったため比較的簡単に解けてしまい、縛りを設けたあともその時の手法をそのまま適応させたことで結局難しい方法になってしまったようです。💦
    想定解はとてもシンプルで分かりやすいですね。


Log in to reply
 

Looks like your connection to パズルハウス was lost, please wait while we try to reconnect.