左にメニューが表示されていなければこのバナーをクリック → |
![]() |
パターンあやとりの世界というサイトを作っています。
2021.05.23 更新
あやとりの記録というページを作りました。
2021.11.27 更新ひとこと
8月19日(金) 「泥棒とお巡りさん」(その2)、あやとり
グラフ上のゲーム、パズルの話とあやとりの話です。
○
グラフの上の「警官と泥棒」(Cops and Robbers)というゲームの話をしています。警官(C)が場所を決め、泥棒(R)がそれを見て自分の場所を決め、後はグラフの辺に沿って交互に1手ずつ動かして、警官が泥棒を捕まえる(=同じ頂点に入る)と警官の勝ち、というゲームです。
このゲーム、素朴なルールでは「泥棒は自分の手番のときに必ず動かなければならない」ということになっています。たとえばこんなグラフ(盤面)を考えてみます。
図 1 最初に警官(C)が頂点2に自分のコマを置き、泥棒(R)は唯一安全な頂点5に自分のコマを置いて、こんな風にゲームが進行することを考えてみます。
最初の状態はこうです(図2)。次に動くのが警官(C)なので、青い太文字にしてあります。警官が移動可能先の頂点を赤くしています。
図 2 頂点2〜5の四角形の中をぐるぐる追いかけていても、泥棒は決して捕まりません。そこで警官は一度頂点1に移動して、ある意味「手番を譲り」ます。そうすると、盤面の配置は同じで、手番だけを泥棒(R)に渡した状況を実現できます(図3)。
図 3 次は泥棒(R)が動かなければなりません。移動可能先の頂点3も頂点4も警官(C)が次に踏み込める場所なので、泥棒は捕まってしまいました。
ところが同じ盤面で、「泥棒は動いても動かなくても良い」という風にルールを変更すると、このグラフは泥棒に必勝戦略があるグラフに変わります。グラフ上の Cops and Robbers を研究した論文では、一般的に「泥棒は(警官も)自分の手番のときに動きたくなければ動かなくても良い」というルールを採用しています。
○
たとえば次の6頂点のグラフ、このグラフは泥棒と警官のどちらに必勝戦略があるでしょうか?「泥棒は動かなくても良い」というルールにしますが、「動かなければならない」でもこの場合は同じです。
図 4 ちなみにこのグラフは全ての頂点の次数(辺の数)が4です。全ての頂点の次数が同じグラフを「正則グラフ」(regular graph)と言って、この場合は4正則グラフになります。
なおこれは正八面体の骨格のグラフになっています。
図 5 (つづく) ○
親指・小指に小さな結び目をつくるところからのあやとりの3つ目です。
これはちょっと面白いかなあと思いました。
○
人の顔が覚えられない…専門家が解説する「相貌失認」の基礎知識 という記事がありました。prosopagnosia(相貌失認) という機能障害というふうに解釈されるのですね。私は人の顔を覚えるのが苦手なので、思い当たる節があります。動物のお医者さん というマンガで有名な 佐々木 倫子に 忘却シリーズ という連作があります。これが「人の顔を覚えられない」という主人公が、その特性のために様々な事件に巻き込まれるというコメディでした。これももう40年近く前の作品なんだと気が付いて驚いています。
<おまけのひとこと>
グラフ上のゲームの説明、グラフの説明(用語など)をどこまで書くか、迷っています。おかげで大した内容ではないのに時間がかかってしまっています。
前回の「ひとこと」へ⇒ |