2010-01-16
頭の体操
またまた「人生を書き換える者すらいた。」のエントリから
http://okajima.air-nifty.com/b/2010/01/post-c7b3.html
６人でミーティングをする。 どの２人を取っても、初対面か会ったことがあるかのいずれかである。 このとき、「互いに初対面の３人組」か「互いに会ったことのある３人組」の どちらかは存在することを証明せよ
【再々考察】
つまりこういうことか。
ある人を基準にして知り合いか初対面かを振り分け、それぞれでまた振り分けていく。
つまりニ分木を構成していく。
どこかに左左 or 左右左が出れば「互いに会ったことのある３人組」が抽出される。
どこかに右右 or 右左右が出れば「互いに初対面の３人組」が抽出される。
それで、5人ならばルートノード＋左右＋右左までは埋められる。これは上記２パターンを満たさない。
しかし、6人目は左左、(左)右右、左右左、右右、(右)左左、右左右のいずれかしか取りえない。
したがって（1+2+2*(2-1)+1で）6人いると「互いに会ったことのある３人組」か「互いに初対面の３人組」のいずれかを抽出できることとなる。
これだと「どの２人を取っても、初対面か会ったことがあるかのいずれかである。」というのがヒントだと理解できる。
「会ったかどうか（酔っ払ってて）覚えてない」を入れると子ノードの数が3になる…「互いに会ったかどうか覚えてない３人組」の存在も考慮すると（1+3+3*(3-1)+3*(3-1)*(3-2)+1で）１７人ミーティングで成り立つかな？
区分がnあると必要な人数が 3(n=1), 6(n=2), 17(n=3), 66(n=4), 327(n=5), ... と増えていく。
N(n)=(N(n-1)-1)*n+2; N(1)=3 →同じ区分の人が3人。
分かる人は10秒で説明できるというのはそうなのかも知れない。
ってこれがすぐに分からないとか自分がアレ過ぎる……
お給料もらっててごめんなさい。
【再考察：不完全】
よく見たら間違ってたことに気づく。
必要十分→十分
でした。ある一人は複数のグループを持つことができるので。ただ、上記は十分条件を満たすので証明に使うことはできるはず。
思い込みは危険でした、反省。
ホントに正しいのか自信が無くなってきた。ダメっぽいので再考。画像の色は意味ないです。
三角形を作ってれば「互いに会ったことのある３人組」が出来る。
三角形を作ってなければ「互いに会ったことのある３人組」は出来ない。
このとき「互いに初対面の３人組」について、
任意の3人間で互いに初対面の2人組は出来る。
(a)その2人のどちらかが残りの3人に会ったことがある場合、最初の3人のうちの残りの1人は後者の3人の中で初対面の2人組とは初対面であり、「互いに初対面の3人組」となる。
(b)その2人のどちらも残りの3人の中で会ったことがない人がいればそれが「互いに初対面の3人組」である。
(a),(b)は三角形を作れない制約から成立して十分条件である、はず？
10秒どころか48時間掛かってます。
【1/18：以下間違い】
「どの２人を取っても、初対面か会ったことがあるかのいずれかである。」というのは関連が真偽のいずれかで表現され曖昧さが無い、ということと考えると、
例えば全員が初対面の場合
ABCDEF
と表現される。また、
AABCDE
と表現される場合、AAを抽出すると「会ったことがある」ということとする。
つまり、6人は何グループに分類されるか、という問題に帰着される。
「互いに初対面の３人組」
ABCCCCなどのように3グループ以上に分類されることが必要十分条件である。
「互いに会ったことのある３人組」
AAABBCなどのように同一グループの人数が3人以上であることが必要十分条件である。
また、2グループ以下に分類されることはこの条件を満たす。
つまり2グループ以下であることが十分条件である。
ということで、2グループ以下、3グループ以上はいずれかの条件を満たし、この2通りの論理和が全体集合となるため、命題が真であることを示すことができる。