数オリの問題に挑戦 (IMO2019問題3) その2
IMO2019の問題3について、その1からの続きです。
wpn.hatenablog.com
問題3．あるソーシャルネットワークサービスにはユーザーが2019人おり，そのうちのどの2人も互いに友人であるか互いに友人でないかのどちらかである．いま，次のようなイベントが繰り返し起きることを考える：
- 3人のユーザーA，B，Cの組であって，AとB，AとCが友人であり，BとCは友人でないようなものについて，BとCが友人になり，AはB，Cのどちらとも友人ではなくなる．これら以外の2人組については変化しないとする．
はじめに，友人の数が1009人であるユーザーが1010人，友人の数が1010人であるユーザーが1009人存在するとする．上のようなイベントが何回か起きた後，全てのユーザーの友人の数が高々1人になることがあることを示せ
証明への方針
グラフは頂点と辺の集合であることに着目するとリフレンドの際に発生する「辺の減少」は重要な性質です。
問題のゴールは友人の数が高々1人なので、これは、全ての連結成分について「頂点の数が2以下」や「辺の数が1以下」とグラフ理論で言い換えることができます。
そのためリフレンドを繰り返していく過程で、3点以上のリフレンドすることができない連結成分が出現したらNG。逆にリフレンドを続けることが出来れば、自然と辺の数が減少していくので最終的には必ずゴールに辿り着きます。
あらゆるパターンのリフレンドを考えることは大変ですが、リフレンドを持続させられるような普遍的なグラフの特徴を見つけることが証明の鍵になります。
グラフの特徴を捉える
リフレンドを持続させるのにそれぞれの連結成分における十分な条件を探す必要がありますが、結論から言うとそれは次の2つです。
(1) 完全ではない
(2) 奇数次(次数が奇数)の頂点を持つ (友人の数が奇数であるユーザーが存在する)
(1)について、完全なグラフはリフレンドできないため完全ではないことが条件となります。
(2)は唐突に見えて難しいですが、その1で行ったような試行から推測して引張り出してきます。この記事では証明を急ぎますが、こちらの補足記事ではもう少しそのあたりについて触れています。
ここで証明までの道筋を一旦整理します。
Q1. 初期状態の3点以上の全ての連結成分が(1)(2)を満たす
Q2. (1)(2)を満たす3点以上の連結成分はリフレンド可能で、うまくリフレンドすれば新たに発生する3点以上の連結成分はやはり(1)(2)を満たす
上記2つが証明できれば初期状態からリフレンドを繰り返し続けていくことが可能で、最終的に全ての連結成分の辺の数を1以下にすることができます。
初期状態は条件を満たすのか
初期状態ではユーザーの友人の数は1009人もしくは1010人です。そのため任意の2人について友人数の合計は少なくとも2018人です。ところでSNSにいるこの2人以外のユーザーは2017人なので、必ず重複している友人が1人はいるはずです。どの2人を選択しても共通の友人が1人以上いるので、実は初期状態においては連結成分が1つしかありません。
上記を考慮すると、初期状態が(1)(2)を満たすことは容易に分かります。
- 2019人のユーザーは連結しているものの全員が友達同士ではないので完全ではありません。
- 友人が1009人(奇数)のユーザーが存在します。
グラフの特徴を維持しながらリフレンドを行う
次にQ2を証明します。まず、3点以上の連結成分Gの中には友人の数が2人以上のユーザーが必ず存在するので、その中から適当に選んでAさんと呼ぶことにします。ただしAさんはAさんの友人同士の間で友人関係にない人がいるように選択します。Gが完全ではないのでそうしたAさんは必ず選択できます。
ここで図のようにこのAさんで区切った部分グラフを考え、区切られたk個の成分をそれぞれG1, G2, ..., Gkとします。これらの成分とAさんとの接続の仕方でどのようにリフレンドするか場合分けをします。
パターン1. kが2以上で、2人以上Aさんの友人がいる成分がある場合
2人以上Aさんの友人がいる成分GiからAさんの友人を選びBさんとします。別の成分GjからAさんの友人を選んでCさんとします。このABCの3人でリフレンドを行います。このとき、AさんとGiはBさん以外の友人で接続したままで、GiとGjはBさんとCさんで接続しているので、Gの連結は崩れません。Aさんは友人が2人減少、BさんとCさんは友人の数が変わらないので友人の数について偶奇は誰も変わりません。そのためリフレンド前のGが(1)(2)を満たすならば、リフレンド後のG'も(1)(2)を満たします。
連結成分は1つのまま
パターン2. kが2以上で、k個全ての成分にAさんの友人が1人だけいる場合
k個の各成分にとってAさんは1人のユーザーで接続しています。グラフの一般的な特徴として奇数次の頂点は必ず偶数個あるので（辺は2点で共有しているので次数の合計は必ず偶数になります）、各成分(G1, G2, ..., Gk)の中には必ず奇数次の頂点がA以外に存在します。Aさんと隣接するBさんCさんを適当に選んでリフレンドすると、Gは2つの連結成分に分割されます。このときそれぞれの連結成分には奇数次の頂点を含みますし、3点以上であれば完全にもなりません。
連結成分は2つに分かれる
パターン3. kが1で、その成分にAさんの友人が3人以上いる場合
Aさんはその友人同士の間で友人関係にない人がいるよう選択されています。その友人関係にない2人をBさんCさんとしてリフレンドを行います。kが1であることからBさんとCさんは別の人を通してAさんと連結しているので、リフレンド後も連結は崩れません。後はパターン1と同様です。
パターン4. kが1で、その成分にAさんの友人が2人いる場合
Aさんはその友人同士の間で友人関係にない人がいるよう選択されています。そのためAさんの友人2人をBさんCさんとすると、BさんとCさんは友人関係にありません。またこの3人でリフレンドを行うと、BさんCさんを含んだ連結成分G'1とぼっちAさんに分割されます。リフレンド前のGには奇数次の頂点があったことを考えると、新たにできたG'1も奇数次の頂点があります。後はG'1が完全でないことを証明できれば完了ですが、厄介なことにG'1は完全になり得ます。そのため実はパターン4はさらに場合分けが必要です。
G'1が完全になってしまう場合、リフレンド前のGは完全グラフからBCを引いて、ABとACを足したもので頂点は5つ以上あります(4つの頂点だとGが四角形になりますがこれはそもそも(2)を満たさないのでありえません)。この場合は適当な点をDとしてBADでリフレンドします。するとリフレンド後のG'は分割されず後はパターン1と同様になります。
Aを分離してもG'1は完全でないなら上のようにリフレンドすればOK
Aを分離すると完全な連結成分が発生するなら下のようにリフレンドすればOK
一部複雑なところはありますが以上4つの場合分けからQ2が証明できました。
証明完了
Q1とQ2が両方証明できたので、この問題は証明完了です。(1)(2)の特徴を維持しながらリフレンドを続けることで、初期状態では全員に1000人以上の友人がいたにも関わらず最後には全員が友人1人以下にされてしまいました。
なおこの問題が実際にSNSで役に立つかは知りません。
追記：リフレンドについての補足記事
wpn.hatenablog.com
