問題114：Korea Summer Program 2016 P5

#114

組み合わせ

★★★☆☆

Korea Summer Program 2016 P5

Find the maximal possible $n$ , where $A_{1}, \dots, A_{n} \subseteq 1, 2, \dots, 2016$ satisfy the following properties.

For each $1 \leq i \leq n$ , $| A_{i} | = 4$ .
For each $1 \leq i < j \leq n$ , $| A_{i} \cap A_{j} |$ is even.

解いてみた

兒玉：2つずつのグループに分けて、${1008}{\rm C}{2}$ が最大なのかなあ
平山：evenって要は0か2かよみたいな気分には
渡辺： $A_{i}$ と $A_{j}$ の共通部分の集合でも取ってこようかな
平山：同じ2元を重複させる $A$ たちは高々1007個ってことなだよな
兒玉：ある元に注目して、それを含む $A$ たちはどの2つもそれ以外に共通元を持っていて
平山：それって流石に同じじゃないと数稼げない
渡辺：同じ元を含む $A$ が1007個以下で証明が回るけど
平山：同じじゃないとmaxでいくつなんだ
兒玉：5の構成が出来た
平山：いや6いけますね…まだ余裕ありそう
兒玉：そんなに小さい数に拘らなくてもいい気がした
渡辺：7が最大なの証明できました (todo：図1)
平山：いや全然余裕なくて草
兒玉：7の構成は存在して、渡辺の証明も正しいと思う
渡辺：これである元を含む $A$ が1007個以下だといえるはず
平山：あ、終わりじゃん草
平山：うーんなんか気持ち悪いな
渡辺：具体的に7って数字で評価したのが気持ち悪い感じ？
渡辺：4が具体的だからパズルしても有効という印象を受けた
平山：というか実質「3元からなる部分集合でどの2つもちょうど1つの共通部分を持つ」って問題なのか
渡辺：確かに

解説・感想

工事中

解答

工事中