概要

この問題に LGV 公式を適用しようとして困ることとして、「終点が決まっていない」というのがあります。公式解説では終点を決め打つことで解決していますが、本ユーザー解説では LGV 公式を直接使わずLGV 公式の証明に着想を得て、求めたい確率が特定の determinant になることを直接示すという方針をご紹介します。

示したいこと

主張：ロボットの最終位置に重複がなく、座標の大小の定める置換が \(\sigma\) であるような確率を \(P(\sigma)\) とおくとロボットが出会うことのない確率は \(\sum _ { \sigma \in \mathfrak { S } _ K } \mathop { \mathrm { sign } } ( \sigma ) P ( \sigma )\) （ただし \(\mathfrak { S } _ K\) は \(K\) 元集合の置換全体の集合）に等しいです。

証明

ロボットが出会うことのない事象はすべて恒等置換に対応するため、符号 \(+1\) で寄与します。

一方、最終位置に重複のない操作列のうち、ロボット同士が出会うことが１回以上あるようなもの全体の集合には involution （２回施すと戻る自己写像）であって、対応する置換の符号を反転させるものが存在します。それはロボット同士の出会いのうち、出会う座標が最小なものの中で時刻が最小なもののなかで出会っているロボットの番号の組が最小なものを取り、その出会い以降この両者のロボットを入れ替えるという写像です。従ってこれらはすべて相殺します。

感想

証明したといいますか、LGV 公式の証明って終点情報を直接使っていないですよね（とはいえないと、必ず交差するのような条件が書きづらくなりますが。）というお話でした。