2023年EGMOスロベニア大会3問目の解答、解説

組合せ論の問題です。
少し悪問感はありますが、かなり面白い設定です。

問題(改)

kを正整数とする。
レクシーは相異なる「文字A,Bのみからなるk文字の文字列」いくつかからなる辞書Dを持っている。
レクシーはk×kのマス目の各マスに、A,Bのいずれかを書き込むことで、各列を上から下に読むことで得られる文字列、および各行を左から右に読むことで得られる文字列がすべて辞書Dに含まれるようにしたい。
このとき、以下の条件をみたすような整数mとしてあり得る最小値を、kを用いて表せ。

条件…辞書Dに少なくともm個の文字列が含まれていれば、辞書Dに含まれている文字列にかかわらず、レクシーは上記の条件を満たすようにマス目に文字を書き込むことができる。

考え方

レクシーの必勝法を構成するのは難しいので、まずはmの最小値の下限、すなわち条件を満たす書き込みが不能な辞書Dの構成を考えます。
特に、相手の行動(レクシーによる書き込み)にかかわらずに、とある文字列が現れ、それが辞書Dに含まれないようなものは、かなり構成が楽でしょう。
例えば、辞書Dが「Aから始まる文字列のうち,A…(Aがk個)…Aという文字列以外のすべての文字列」からなる場合、辞書Dは2^(k-1)-1個の文字列を含みます。
そして、辞書Dから文字列を選んで各行に書き込むとすると、レクシーの書きこみ方によらず、1列目にA…(Aがk個)…Aという文字列が現れ、これは辞書Dに含まれないため、条件を満たす書き込みは存在しません。

ここでメタ読みをします。
問題の題意が「〇〇が〇〇以上であれば、〇〇によらず〇〇」の形式なので、鳩の巣原理が使えそうなのですが、文字列としてあり得るものの総数は2^k、対して上記の考察よりmの最小値は2^(k-1)-1であると当たりをつけると、全ての文字列を2つ組程度にして、鳩の巣原理が適用可能であるようにすればいい気がします。

以上のことを踏まえて、解答を作っていきます

解答

辞書Dが「Aから始まる文字列のうち,A…(Aがk個)…Aという文字列以外のすべての文字列」からなる場合、辞書Dは2^(k-1)-1個の文字列を含む。
そして、辞書Dから文字列を選んで各行に書き込むとすると、レクシーの書きこみ方によらず、1列目にA…(Aがk個)…Aという文字列が現れ、これは辞書Dに含まれないため、条件を満たす書き込みは存在しない。
よって、mとしてあり得る最小値は2^(k-1)-1以上である。

次に、m≧2^(k-1)のとき、条件を満たす書き込み方が存在することを、鳩の巣原理を用いて示す。
A,Bからなるk文字の文字列全てを、以下のような2つ組達の集合Xに分割する。

「各組において、一方の文字列がもう一方の文字列のAをBに、BをAに置き換えたものである。」

(S,S')∈Xについて、S,S'がどちらも辞書Dに含まれる場合、レクシーが以下のようにマス目に書き込むことで、条件を満たす。

「まず1列目に、上から下にかけてSを書き込む。
S,S'のうち、一方の1文字目はA、もう一方はBのため、1列目の文字に合わせて、各行に、左から右にかけてS,S'を書き込む」

また、(A…(Aがk個)…A,B…(Bがk個)…B)∈Xのうち少なくとも一方が辞書Dに含まれる場合、レクシーが全てのマス目に同じ文字を書き込むことで、条件を満たす。

Xの元のうち、(A…(Aがk個)…A,B…(Bがk個)…B)を除いた元の個数は
2^(k-1)-1、対して辞書Dに含まれる文字列は2^(k-1)以上のため、鳩の巣原理より、(S,S')∈Xが存在し、S,S'がいずれも辞書Dに含まれ、レクシーは条件を満たす書き込みが可能となる。

上記より、条件を満たすmとしてあり得る最小値は2^(k-1)。…(答)

感想

文字列の文字を置換するという手法（今回のA→B,B→A）はいろいろな問題で使えます。
三種類の文字A,B,Cだと、A→B,B→C,C→AやA→A,B→C,C→B、置換ではないけれどA→B,B→C,C→Bだったり、いろいろです。

本問題の考察は、wikipediaの「極値集合論」の項目で紹介されている問題の議論と酷似しているので、乗せておきます。

「集合{1,2,…,n}の相異なるN個の部分集合族であり、そのうちどの2つの集合をとっても共通部分が空でないようなものが存在するとき、Nとしてあり得る最大値をnを用いて表せ。」