19122：証明...6チームで、10試合終わった時点で互いに対戦した3チームが存在する...

キャンドルライトの中なので暗すぎぃ〜^^;

問題19122・・・http://task.naganoblog.jp/c10116.html より 引用 Orz〜

解答

デジャヴー ？

・わたしの...

Aは4チームと

Aと試合のなかったBがその4チームと試合をしても8試合

その4チームの中でどの2試合をしても、A or Bと互いに試合をしたことになる...

so...9試合でも言えますよね？

*9試合では無理でしたわ ^^; Orz...

・鍵コメT様からのもの Orz〜

9試合の場合，反例が構成できます．
「A,B,CとD,E,Fの2組に分け，違う組どうしの9試合のみ対戦．」
具体的には，AD,AE,AF,BD,BE,BF,CD,CE,CFです．・・・そっか!!

10試合の場合は，示されている議論でほぼよさそうですが，
もう少しきちんと言うと，次のようになります．
・各チームが3試合までだと，全部で3*6/2=9(試合)までとなって不適だから，
4試合以上行ったチームがある．
最大試合数のチーム(複数あればその1つ)をAチームとしてよい．
・Aチームが5試合行っていれば，Aチームは他の全チームと対戦している．
Aチームが関わらない対戦が5試合あり，その内の1試合が例えばB-Cであれば，
A,B,Cの3チームが条件を満たす．
・Aチームが4試合行っていれば，Aチームが対戦していないチームは1つだけ．
それをBチームとすると，Bチームは高々4試合だから，
A,B以外のチームどうしの対戦があり，
その内の1試合が例えばC-Dであれば，A,C,Dの3チームが条件を満たす．

[スモークマン]

＞9:13pmの鍵コメT様へ ^^
9試合の反例了解!!
ですが...
>その内の1試合が例えばC-Dであれば，A,C,Dの3チームが条件を満たす
で証明できてることになると...
4+4+1=9試合になりそうと思ったものでして...^^;...?

[スモークマン]

＞10:37pmの鍵コメT様へ ^^
Aが4試合して、
Aと試合しなかったBも残り４チームと4試合してる場合、・・・ここまでで8試合...A,B以外の4チームの中であと1試合(C-D)しただけで、同時に、A-C-D,B-C-Dが生まれるというだけで...9試合では無理な場合があるから,最低でも10試合してる場合になるわけですね ^^;v
紹介させていただきまっす〜m(_ _)m〜v