5-26. 伝説の入試問題をPythonで解いてみた【1998年東大後期第3問】

数理モデル / 論理

2024/04/07

やること
どんな問題？
可視化の関数、操作１, ２の関数
探索の関数
問（１）
問（２）
さいごに

やること

「大学入試史上最も難しい数学の問題」と言われているのが1998年の東京大学、後期第3問。大手予備校が当日に解答速報を出せなかったとか。

今回はこのグラフ理論の問題をPythonで解いてみたいと思います。先に言っておきますが（２）は全探索すると無限の時間がかかるので解けていません。

どんな問題？

引用ですみません。問題、解答、予備校が解答速報を出せなかった逸話がすべてこちらのサイトにまとまっているのでご参照ください。感謝します。

1998年東京大学　大学入試史上No.1の超難問～20年目の真実～

1998年東京大学後期第3問は、問題文からして只ならぬ様相を醸し出していた。一見して高校数学とは思えないこの問題は、大学入試史上No.1の超難問として伝説を残した。99％の大学受験生は問題を見た時点で心が折れることだろう。鬼畜ともいえる難易...

問（１）は、初期状態から操作１と操作２を繰り返すことで図５の各グラフが作成可能であることを示すというもの。問（２）では図６が可能グラフになるための必要十分条件を求めます（正解者ゼロ）。

可視化の関数、操作１, ２の関数

さっそくプログラミングしていきましょう。

グラフの操作にはお馴染みの「networkx」を使います。

import os
import numpy as np
from copy import deepcopy
import matplotlib.pyplot as plt
import networkx as nx

まずは可視化の関数です。

def show(G):
    #ノード色
    whites = [G.nodes[node]['white'] for node in G.nodes()]
    node_colors = ['w' if white == 1 else 'k' for white in whites]
    font_colors = ['k' if white == 1 else 'w' for white in whites]
    #
    plt.figure()
    pos = nx.spring_layout(G) #kの値が小さい程図が密集する
    #ノードとエッジの描画
    nx.draw_networkx_nodes(G, pos, node_color=node_colors, edgecolors='k')
    nx.draw_networkx_edges(G, pos, edge_color='k')
    #ノード名を付加
    for i in range(nx.number_of_nodes(G)):
        nx.draw_networkx_labels(G, pos, labels={i: f'{i}'}, font_color=font_colors[i], font_size=10)
    #エッジ名を付加
    edge_labels = nx.get_edge_attributes(G, 'label')
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
    #X軸Y軸を表示しない
    plt.axis('off')
    plt.show()

初期ノードを表示してみます。

#初期化
G = nx.Graph()
G.add_node(0, white=1)
show(G)

操作１の関数を作って実行します。指定したノードに新規ノードをくっつけて色を整えます。

def action1(G, target_node):
    #コピー
    G2 = deepcopy(G)
    #新規ノード番号とエッジ
    new_node = nx.number_of_nodes(G2)
    new_edge = nx.number_of_edges(G2)
    #新規ノードを付ける
    G2.add_edge(target_node, new_node, label=new_edge)
    #新規ノードを白にする
    G2.nodes[new_node]['white'] = 1
    #ターゲットノードを反転する
    G2.nodes[target_node]['white'] *= -1
    return G2

#操作１
G = action1(G, 0)
show(G)

ノード０に対して新しいノードがくっつきました。

同様に操作２の関数を作って実行します。指定したエッジを切り、そこに新規ノードを挟み込んで色を整えます。

def action1(G, target_node):
    #コピー
    G2 = deepcopy(G)
    #新規ノード番号とエッジ
    new_node = nx.number_of_nodes(G2)
    new_edge = nx.number_of_edges(G2)
    #新規ノードを付ける
    G2.add_edge(target_node, new_node, label=new_edge)
    #新規ノードを白にする
    G2.nodes[new_node]['white'] = 1
    #ターゲットノードを反転する
    G2.nodes[target_node]['white'] *= -1
    return G2

#操作２
G = action2(G, 0)
show(G)

エッジ０に新しいノードが挿入されました。

探索の関数

パーツを一個作ります。ある枝分かれ数を持つノードの数を調べて返す関数です。

#ある枝分かれ数を持つノードの数
def num_nodes_with_degree(G, degree):
    nodes_with_degree = [node for node, deg in G.degree() if deg == degree]
    return len(nodes_with_degree)

この関数は、例えば次のグラフをdegree=4で調べると2が返ってきます。（4本腕を持つノードが2つあるという意味）

ここからはガチで。ノードを増やしながら全探索する再帰関数を作ります。

#再帰関数
def do_all_action(G):
    global count
    #規定のノード数であれば再帰を終了
    if nx.number_of_nodes(G) == 3:
        #ノードが全部白、かつ、ある枝分かれ数を持つノードの数が規定通りなら表示
        whites = [G.nodes[node]['white'] for node in G.nodes()]
        num = num_nodes_with_degree(G, 2)
        if set(whites) == {1} and num == 1:
            print('found!!')
            show(G)
            raise
        return
    
    #すべてのノードとエッジ
    node_list = np.arange(nx.number_of_nodes(G))
    edge_list = np.arange(nx.number_of_edges(G))
    
    #各ノードに操作1をしてから再帰送り
    for target_node in node_list:
        G2 = action1(G, target_node)
        count += 1
        if count % 10000 == 0: print(count)
        do_all_action(G2)
    
    #各エッジに操作２をしてから再帰送り
    for target_edge in edge_list:
        G2 = action2(G, target_edge)
        count += 1
        if count % 10000 == 0: print(count)
        do_all_action(G2)

再帰関数をうまく作るコツを紹介します。まず冒頭に終了条件。ここでは分かりやすく「raise」でプログラム自体を強制終了させます。その後に自身を呼び出す部分を書くのですが、主人公であるグラフ（G）は、現在の世界線（スコープ）で使っているものをそのまま次の世界線に渡してしまうと上書きでぶっ壊れたりするので、deepcopyした別人（G2）を渡すようにします。今回は操作１と２の中でdeepcopyして別人を作成しています。まあ、伝われ。

問（１）

１個目

では、グラフを初期化して再帰探索してみましょう。問（１）の１個目は◯－◯－◯を作れというものなので終了条件は次のとおり。ノード数3で、degree=2が1個になったら終了です。

    #規定のノード数であれば再帰を終了
    if nx.number_of_nodes(G) == 3:
        #ノードが全部白、かつ、ある枝分かれ数を持つノードの数が規定通りなら表示
        whites = [G.nodes[node]['white'] for node in G.nodes()]
        num = num_nodes_with_degree(G, 2)
        if set(whites) == {1} and num == 1:
            print('found!!')
            show(G)
            raise
        return

探索開始。

#初期化
G = nx.Graph()
G.add_node(0, white=1)
show(G)

#総探索数
count = 0

#探索
do_all_action(G)

found!!

Traceback (most recent call last):
（中略）
  File main.py:116 in do_all_action
    raise
RuntimeError: No active exception to reraise

すぐに発見しました。手順は簡単にバックトレースできると思います。

２個目

２個目はメタンを作れということで、ノード数5、degree=4が1個になったら終了です。

found!!

Traceback (most recent call last):
（中略）
  File main.py:116 in do_all_action
    raise
RuntimeError: No active exception to reraise

こちらも一瞬でした。

３個目

最後はエタンを作れということで、ノード数5、degree=4が2個になったら終了です。

10000
20000
30000
40000
50000
60000
found!!

Traceback (most recent call last):
（中略）
  File main.py:116 in do_all_action
    raise
RuntimeError: No active exception to reraise