6人ミーティング

先日の迷路と同じサイトが、今度は筆記試験の問題を出していました。

６人でミーティングをする。

６人でミーティングをする。どの２人を取っても、初対面か会ったことがあるかのいずれかである。このとき、「互いに初対面の３人組」か「互いに会ったことのある３人組」のどちらかは存在することを証明せよ

ううう！？わ、わからない・・・・・・（汗）

と、とりあえず、答えが出さなきゃダメですよね！？

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()

実際には、あるグラフに三角関係があるかどうかと、そのグラフの頂点同士の関係を反転させたグラフ
（元のグラフでつながっていない頂点同士を辺でつなぎ、つながっていた頂点同士は辺でつながない様にしたグラフ）に三角関係があるかどうかは同値なので、半分だけ調べればいいのですが、
半分だけというのを実現する方法が、すぐに浮かばなかったので、こう書きました。