数オリの問題に挑戦 (IMO2019問題3) おまけ

IMO2019の問題3について、補足です。
数オリの問題に挑戦 (IMO2019問題3) その1 - 夜更かし紀行
数オリの問題に挑戦 (IMO2019問題3) その2 - 夜更かし紀行

リフレンドの性質

その2では証明だけで済ましてしまったリフレンドについてもう少し補足します。

3人のユーザーA，B，Cの組であって，AとB，AとCが友人であり，BとCは友人でないようなものについて，BとCが友人になり，AはB，Cのどちらとも友人ではなくなる．これら以外の2人組については変化しないとする．

次数の変化

リフレンドではAの次数が2減少し、BとCの次数は変わりません。問題のゴールはすべての頂点の次数を1以下にすることなので、奇数次の頂点は次数が奇数のまま最終的には1に、偶数次の頂点は次数が偶数のまま最終的には0になります。この性質より初期状態から最終状態を把握することができます。例えば今回の問題では友人が1009人いるユーザーが1010人と友人が1010人いるユーザーが1009人が初期状態なので、最終的には友人が1人のユーザーが1010人と友人が0人のユーザーが1009人になります。

リフレンド回数

上記からリフレンドを限界まで行った時のリフレンド回数も算出できます。
初期状態の辺の数は

(1009×1010+1010×1009)÷2 = 1019090
最終的な辺の数は

(1×1010+0×1009)÷2 = 505
辺の数が1018585減少しているので、これと同じ回数だけリフレンドしていることになります。

奇数次の頂点が存在する理由

リフレンドの果てに全てのユーザーが友人1人以下になったとします。そのとき、最後のリフレンドは以下の2通りのいずれかです。

ここで、いずれのパターンでも必ず次数が1の頂点が残ります。リフレンドで次数の偶奇が変わらないことを考えると、最後に次数が1の頂点が残るということは初期状態や途中過程でも必ず次数が奇数の頂点が存在することになります。