RE:兵士たちの大喧嘩



  • ひょっとして放電法を用いてのコンピュータによる四色問題の証明における不可避集合のように人力では数え尽くせないのではと? > @riffraff さん



  • @Hannibalさん
    ギク(;'∀')
    取り敢えず現在位置です

    基本は簡単

    政敵3人として、支点Aと政敵A1~A3の関係は以下の図の通りとなります
    0_1591702500547_第一層.gif
    1層以降のN層とN+1層の関係、N+1層の内部関係は三角形または線(片端が多重化している場合を含みます)
    0_1591702648206_第N層.gif
    これらを踏まえ図3を含めたすべての場合で条件を満足できる配置を行い、最終コマまで拾いおわれば完成。
    0_1591702796412_図3.gif
    基本置換ですので行けると思うのですが。
    全ての場合の数え上げにGive up気味N+1層からN層への逆行が有るためです。



  • お知らせ

    翌週の月曜日または火曜日頃に想定解を発表するかもしれません。しないかもしれません。
    じゅうよくごうをせいす。



  • それでは、想定解の一例をば以下に隠し機能で。

    想定解

    最初にやり方を、次にそのやり方で有限ステップで目標に達することができることを示します。

    【やり方】
    1:まず全員を適当に二派に振り分けます。
    2:この段階で目標が達成されているかどうか検査し合格すれば終了です。
    3:おのおのの派閥にて、同一派閥内に政敵が2名ないし3名いる者をリストアップします。(彼らはその派閥にいづらいわけです) 4:リストアップされた者を全員、もうひとつの派閥に移籍します。
    この移籍先で新たに政敵が発生する恐れがありますから、まだ目標が達成されているかどうかわかりません。2へ戻ります。

    ※問題は、この2から4までのループが永遠に終わらない可能性があるかどうかですが、それは、次の説明をみてください。

    【有限ステップで目標に達する】ことの説明。

    まず全員で数えますが、互いに政敵であるペアの総数をPとします。

    全員が二派に振り分けられていますが、第一の派閥内で互いに政敵であるペアの総数をQとします。同様に第二の派閥内で互いに政敵であるペアの総数をRとします。派閥を横断して互いに政敵であるペアの総数をSとします。
    P=Q+R+S
    が成り立ちます。
    Pは定数で、Q、R、Sは変数とみなします。

    第一の派閥内に政敵が2名ないし3名いる者を1名、第二の派閥に移籍したときにQ、R、Sの値がどうなるか調べます。Qは2ないし3減ります。《ひとりあたり政敵は最大3名であることから》Rは不変であるかまたは1増加します。
    すなわち(Q+R)は、少なくとも1減ります。SはP−(Q+R)と等しいので少なくとも1増えます。

    同様にして
    第二の派閥内に政敵が2名ないし3名いる者を1名、第一の派閥に移籍すると、(Q+R)は、少なくとも1減ります。

    まとめると、どちらの派閥であれ、同派内で【派閥にいづらい】者を1名、もう片方の派閥に移籍すると、(Q+R)は、少なくとも1減ります。

    (Q+R)は非負整数ですから、同様の移籍は有限回しか行われないことが明らかです。
    《高々P回です》

    というわけで、日経サイエンスのパズルの国のアリスにある「兵士たちの大喧嘩」と同じ考え方ができる問題でした。

    @マーモセット さんによるオリジナル解は、上記の想定解を一部に含んでいます。これには参りました。絶対に反例を作れません! てへぺろ。

    追記:訂正版の想定解を以下に! 御指摘を頂きましたマーモセットさん、有り難うございます。

    想定解改

    【やり方】のみ差し替えます。有限ステップで終わることの説明はさきの想定解をご覧ください。

    【やり方】
    1:まず全員を適当に二派に振り分けます。
    2:同一派閥内に政敵が2名ないし3名いる者を派閥にかかわらずひとつのリストに書き出します。リストが空ならば目標達成です。
    目標が達成したら終了です。
    3:リストされた者のなかから1名を選び、属している派閥から、もうひとつの派閥に移籍します。
    (この移籍先で新たに政敵が発生する恐れがあることに留意しながら)2へ戻ります。



  • @Hannibal さん
    想定解拝見しました

    リストアップの順番

    A~Hの8人の議員、カッコ内は政敵を小文字にして表します。
    派閥1
    A(b,c,d)
    B(a,c,d)
    C(a,b,d)
    D(a,b,c)

    派閥2
    E(f,g,h)
    F(e,g,h)
    G(e,f,h)
    H(e,f,g)

    たとえばステップ1で上記のように2派に分かれた場合、ステップ3のリストアップは1人ずつ順番に行い、リストアップされたらすぐに移籍していくという流れですね。
    根底の部分の考え方は私と同じになるんでしょうか?
    とてもシンプルな式で表現ができてしまうのにはビックリですが、自分にはできそうにないです(;´д`)トホホ



  • @マーモセット さん。

    マーモセット さんによる解において、★ステップ2 ★ステップ3 ★ステップ4 は 想定解と同じことをしていらっしゃいます。
    ★ステップ1 でガッツリとその後の展開をスッキリさせていらして、人対人のパターンのバリエーションを激減させていらっしゃるのですよね。これ本当に凄いことだと思います。ゆえにネットワークの収束を詳細レベルにて説明できるのですから。



  • 夜中に目が覚めたら @マーモセット さんからの御指摘を私は先ほどまで正しく掴み損ねていたことに気がつきました。

    おっしゃる通りですね。

    睡眠を取りなおし、顔を洗って出直してから想定解の文面を修正します。

    御指摘をありがとうございました。



  • 想定解の改良版を追記しました。

    @マーモセット さん、有り難うございます。ぺこり。



  • @Hannibal さん
    私のコメントが悪文でしたね。すみませんm(__)m
    はじめ“例で示したケースはどうするのだろう”という疑問から質問しようと思いコメントを書き始め、書いているうちに自己解決したので途中からコメントをあちこち修正しているうちに意味不明な文になってしまいました。
    もともと文を書くのが苦手で一度書いた文を何度も修正してから投稿していますが、ここは必要ないとかここにはもう少し補足をとかやっているうちに余計に分かりにくい文になって意図が伝わらないことがしばしばです💦



  • いえいえ、とてもわかりやすかったですよ、@マーモセット さん。

    当方、先入観がありまして、夢の中でそのことを弁当屋に教わり
    【どわ〜〜〜】と叫んで
    目が覚めた次第です。


Log in to reply
 

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