この問題において、\(L^{*}=51\) を達成して満点を得ることができます。

では、 \(L^{*} >51\) を達成できるのでしょうか。 ある盤面を渡すと、返ってくるのは \({}_{14} \mathrm{C}_{7}=3432\) 通りの盤面です。したがって、通信可能な文字数は最大で\(\lfloor \log_2{\frac{2^{64}}{{}_{14}\mathrm{C}_7}}\rfloor=\lfloor 52.2..\rfloor=52\) であると評価できます。

つまり、\(L^{*}=51\) を達成する解法が存在するため、通信可能な文字数の最大値は \(51\) または \(52\) であることがわかります。この最大値が \(51\) であることを示します。

盤面を \(\mathbb{F}_2^{64}\) の元とみなし、各経路 \(P\) についても経路上のマスを \(1\) 、それ以外を \(0\) とするベクトルで表すとします。 このとき Chiaroが経路 \(P\) を選んだとき、盤面は \(x \mapsto x \oplus P\) と変化します。

頂点集合を \(V(G)=\mathbb{F}_2^{64}\) とし、異なる \(2\) 頂点 \(x,y\) をある二つの経路 \(P,Q\) を持ちて \(x \oplus P = y \oplus Q\) と書けるときに \((x,y)\) の間に辺を張ったグラフ \(G\) を考えます。

つまり、ある集合 \(S \subseteq \mathbb{F}_2^{64}\) を用いて \(\{x,y\} \in E(G) \iff (x \oplus y )\in S\) と書ける。ここで \(S\) は相異なる \(2\) 経路の排他的論理和全体の集合である。

長さ \(L\) の通信が可能であることは \(G\) において \(|I|=2^L\) となる独立集合 \(I\) を取れることと同値です。

ここで、\(G\) の任意の独立集合 \(I\) とクリーク \(C\) について \(|I|\times|C|\leq |V(G)|=2^{64}\) を示します。

各 \(c\in C\) に対して \(c \oplus I=\{c\oplus i \mid i \in I \}\) とおきます。このとき、異なる二つの \(C\) の元 \((c,c')\) について \((c \oplus I)\) と \((c' \oplus I)\) は互いに素(同じ元を要素として持たない)です。仮に \(i,i' \in I\) であって \(c \oplus i = c' \oplus i'\) となる組が存在すると \(c \oplus c' =i \oplus i'\) を満たします。 \((c,c')\) は \(G\) において間に辺を張られているので \((c\oplus c') \in S\) となるが、\(I\) は独立集合なので \(i \oplus i' \notin S\) となります。しかし、これは矛盾であるため \((c \oplus I)\) と \((c' \oplus I)\) は互いに素です。 よって、\(|I|\times|C|=|\{c \oplus i \mid c \in C, i \in I\}| \leq |V(G)|=2^{64}\) が成り立ちます。

実は、\(|C|=2^{13}\) となる \(G\) のクリーク \(C\) が存在します。

次の \(13\) 個のマスの組を取ります。

\((0,1),(1,0)\\\) \((0,2),(1,1)\\\) \((1,2),(2,1)\\\) \((1,3),(2,2)\\\) \(\vdots\\\) \((6,7),(7,6)\\\)

この\(13\) 組についてそれぞれどちらも黒、どちらも白のどちらかを選び、それ以外はすべて白とした盤面を生成するとすると盤面は \(2^{13}\) 通りあります。この盤面の集合を \(C\) とします。

\(C\) の異なる \(X,Y\) を取ると、\(X\oplus Y \in S\) を示せばよいです。また、\(C\) の要素の性質から \(X \oplus Y \in C\) が言えます。 したがって、任意の \(X \in C\) で \(X\) がすべてが白でないものについて \(X \in S\) を示せばよいです。

与えられた \(X\) について、異なる経路 \(P,Q\) であって、\(P\oplus Q=X\) なるものの存在を示します。\(13\) 個のマスの組について両方とも白のときは、\(k\) が奇数ならば組の前者のマス、\(k\) が偶数ならば組の後者のマスを通るとして、黒のマスの組については\(P\) は組の前者のマス、\(Q\) は組の後者のマスを通るようにすると、\(P\oplus Q=X\) となり、\(X\) には黒のマスが存在するので \(P\neq Q\) になります。

\(|C|=2^{13}\) となるクリークが存在するので、任意の独立集合 \(I\) について、\(|I| \leq \frac{2^{64}}{|C|}=2^{51}\) となります。 したがって、満点解法の \(L^{*}=51\) がこの問題において達成できる理論値であることが言えます。ここでいう理論値は、この問題設定において送信できる最大の情報量であるということです。

この事実はJOI2025/2026 ファイナルステージにて選手およびチューターによって示されました。

特に重要な \(|I|\times |C| \leq |V(G)|\) の証明を提供してくださった Mitarushi さん、大きさ \(2^{13}\) のクリークの構成を提供してくださった lescot さんに感謝申し上げます。