6人ミーティング
先日の迷路と同じサイトが、今度は筆記試験の問題を出していました。
6人でミーティングをする。
6人でミーティングをする。どの2人を取っても、初対面か会ったことがあるかのいずれかである。このとき、「互いに初対面の3人組」か「互いに会ったことのある3人組」のどちらかは存在することを証明せよ
と、とりあえず、答えが出さなきゃダメですよね!? 6頂点グラフは全部で
ううう!?わ、わからない・・・・・・(汗)
6の階乗で720通り2の6*5/2乗で32768通りしかないんだから、全部調べればいいんですよ!
#encoding:shift-jis from __future__ import division, with_statement, print_function __metaclass__ = type from itertools import * def powerset(iterable): "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)" s = list(iterable) return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) N = 6 def has_triangle(graph): for x, y, z in combinations(xrange(N), 3): b1 = frozenset([x, y]) in graph b2 = frozenset([y, z]) in graph b3 = frozenset([z, x]) in graph if b1 == b2 == b3: return True def main(): allpairs = [frozenset([x, y]) for x, y in combinations(xrange(N), 2)] for graph in powerset(allpairs): if not has_triangle(graph): print(u"三角関係を持たないグラフが見つかりました。") print(graph) exit() print(u"全てのグラフが三角関係を持ちます。") if __name__ == "__main__": main()
実際には、あるグラフに三角関係があるかどうかと、そのグラフの頂点同士の関係を反転させたグラフ
(元のグラフでつながっていない頂点同士を辺でつなぎ、つながっていた頂点同士は辺でつながない様にしたグラフ)に三角関係があるかどうかは同値なので、半分だけ調べればいいのですが、
半分だけというのを実現する方法が、すぐに浮かばなかったので、こう書きました。