夜更かし紀行

もしかしたら何かの役に立つ技術的なもの

数オリの問題に挑戦 (IMO2019問題3) その1

数学

以下は今年7月に行われた国際数学オリンピックの問題の1つです。SNSを題材にしたもので今風な感じが面白いです。世界最高峰の競技数学なので解くのは非常に大変ですが、複雑な数式などは出てこない問題なので数学が苦手な人でも理解できる内容です。

f:id:wpn:20190816014408p:plain:w100

問題3．あるソーシャルネットワークサービスにはユーザーが2019人おり，そのうちのどの2人も互いに友人であるか互いに友人でないかのどちらかである．いま，次のようなイベントが繰り返し起きることを考える：

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

はじめに，友人の数が1009人であるユーザーが1010人，友人の数が1010人であるユーザーが1009人存在するとする．上のようなイベントが何回か起きた後，全てのユーザーの友人の数が高々1人になることがあることを示せ



ちなみに今年の問題は以下のページで言語別にダウンロードできるようになっています。全部で6問、実際は2日間に分けて3問270分ずつの制限時間で競われました。
www.imo-official.org

まずは問題の理解から

1文目

あるソーシャルネットワークサービスにはユーザーが2019人おり，そのうちのどの2人も互いに友人であるか互いに友人でないかのどちらかである．

要はFacebookみたいなSNSにユーザーが2019人いて、AさんにとってBさんが友人ならばBさんから見てもAさんは友人です。図にしてみるなら人を点、友人関係を線として書くと見通しが良さそうです。


f:id:wpn:20190815175715p:plain:w320

イベントについて

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

このイベントを今後は「リフレンド」と呼ぶことにします。リフレンドを図にすると以下のような手順です。


f:id:wpn:20190815180237p:plain:w320

最後の文について

はじめに，友人の数が1009人であるユーザーが1010人，友人の数が1010人であるユーザーが1009人存在するとする．上のようなイベントが何回か起きた後，全てのユーザーの友人の数が高々1人になることがあることを示せ

リフレンドを何回も繰り返していくと友人関係がどんどんばらけていくことがあることを証明できればゴールです。友人の数が高々1人とあるので、うまくリフレンドを繰り返していけば図のように全てのユーザーが点もしくは2点の線で構成されることを示す必要があります。


f:id:wpn:20190815225256p:plain:w400


一般化を考えて少ない人数で試してみる

例示は理解の試金石、ということでまずは少ない人数でどうなるか考えてみます。

■友人の数が1人であるユーザーが2人，友人の数が2人であるユーザーが1人存在する場合の例


f:id:wpn:20190815180237p:plain:w320

1回のリフレンドで"バラけた"状態になりました。

■友人の数が2人であるユーザーが3人，友人の数が3人であるユーザーが2人存在する場合の例



途中経過は省略しますが5回のリフレンドで"バラけた"状態になりました。

いろいろなパターンがありそうですが、友人の数がn人であるユーザーがn+1人，友人の数がn+1人であるユーザーがn人存在する場合はうまくリフレンドしていけば最終的にバラけた状態にできそうです。今回の問題はn=1009の場合ですが、それを手で書き出すのは大変そうです。

逆にNGとなるパターンを考えてみます。
■友人の数が2人であるユーザーが4人存在する場合の例

f:id:wpn:20190815182927p:plain:w240

例えば上のように三角形が出来上がってしまうパターンはこれ以上バラけさせることができません。

どういった特徴の形であればうまくリフレンドできるのか、うまくバラけさせることができるのか、ということが分かれば問題が解けそうです。

グラフ理論について

実はこの問題はグラフ理論と呼ばれる数学体系に含まれる問題で、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合として表現されるモデルです。細かい説明はWikipediaのページがあるのでそちらに任せます。なおグラフ理論に関連した問題は以前にも何回か数学オリンピックで出題されています。

用語の簡単な説明

今後必要そうなグラフ理論の概念をいくつかここで説明します。

  • グラフ

頂点とそれを結ぶ辺の集合で構成されます。今回の場合はSNS全体が1つのグラフで表現できます。

  • 次数

ある頂点から伸びている辺の数(もしくは隣り合う頂点の数)です。今回の場合は友人の数が次数に相当します。

  • 部分グラフ

正確な定義は頂点集合と辺集合がともに部分集合であること。グラフの一部が部分グラフと考えて問題ないと思います。下の図で言うとG1はGの部分グラフですし、赤い部分はG2の部分グラフです。

  • 連結グラフ

頂点から頂点までいくつかの辺を通して辿ることができるようなグラフです。また極大な連結グラフを連結成分(要は繋がった固まり)と言います。例えばG1，G2，G3はGの連結成分です(当然連結グラフでもあります)。図の赤い部分は連結グラフですが連結成分ではありません。

  • 完全グラフ

すべての頂点が繋がっているグラフです。101人いたら101人全員が友達100人いる状態。例えば図のG3は完全グラフです。


f:id:wpn:20190815183006p:plain:w320
グラフ理論の用語について


そして証明へ

長くなるのでその2へ続きます。
wpn.hatenablog.com