上級問題
★は５段階評価
1.★★
合計を二通りの方法で表す。
全員の得点の合計は、試合の結果に関わらず一試合で1なので(0+1,1/2+1/2,0+1)
Σai=Binom(n,2)
下位同士での勝ち点の合計はBinom(10,2)であり、これが合計の半分になることより
Σ下位=Binom(n-10,2)*2
上位同士も同様
Σ上位=Binom(10,2)*2
なのでΣai=Σ上位+Σ下位として連立方程式を解く
とn=16,25となる。
まだ構築可能なことをを示す必要がある
n=16のとき上位と下位の平均が逆転してしまうので不適
n=25のときは
上位vs上位:0-14-0
上位vs下位:6-2-2(上位目線)
下位vs上位:3-3-9(下位目線)
下位vs下位:0-9-0
として適当に振りわける
2.★
まず上界を考える
Σ2*((n+3)/2+........n)-Σ2*(1+2+3+....(n-1)/2)=(n^2-1)/2
上界を満たす通り数を数えればいい
(n+1)/2とペアになるもがをn通り
それぞれ[1,(n-1)/2]とのペアが((n-1)/2)!
[(n+3)/2,n]とのペアも同様
3.★
連続する表、裏を１つのブロックでまとめて考える
[x][o][x][o][x][o][x][o]の構造になる。
あとは余りをどこに振り分けるかだけなのでBinom(5,3)*Binom(8,3)
4.★
11,,,,122,,,,,,2233,,,,,,,33が最大っぽい気がする
これをちゃんと証明したい
適当に操作をすると適当な数列を単調増加に並び替えても答えが小さくならないことがわかる
さらに適切な操作をすると
[aaaaaa][a+1,a+1,,,,,a+1][a+2,,,a+2]のような形にしても答えは小さくならない
このときの答えはサイズをs0s1s2s3s4...とすると
ans=Σsi*s(i+1)*s(i+2)となる
{a,b,c,d,e}に対してabc+bcd+cdeと
{b,c,a+d,e}で比較するとabc+bcd+ace+cdeとなるのでサイズは3になる
つまりx+y+z=2001かつxyzが最大になるxyzの組み合わせを考えればいい。
これはx=y=zのとき。
5.★
存在すると仮定し矛盾を導く。
解の集合のうち、全員が一致しないかつ和が最も小さいものを１つ用意する
23人の偶奇について考えると全員の偶奇が一致するのは明らか
全員偶数のとき全員の体重を半分にすると和がより小さいものができるので過程に反する
全員奇数のときx->(x+1)/2とすると和が小さいものが用意できるので矛盾する
6.★★★
要素はmod20で考えて構わない。
mod20で見た要素が7個以上あったら
Binom(7,2)=21なので鳩の巣集合的な考え方で存在する
mod20で見た要素が6つ以下の場合を考える
n>=9のとき
{a,b,c,d,e,f,a,a,a}でも{a,b,c,d,e,a,b,?}でも満たすので存在する
n=8について考える
{0,0,0,1,2,4,7,12}とすると
相異なる元を４つ選んだ{a,b,c,d}に対して(aは>=bcdとする)
0 < a-c-d<=a+b-c-d<=a+b<20となるので以下略
これ解説の0 < a-b-d<=a+b-c-dは
0 < a-c-dの誤植だと思います
7.★
一般項を求めろとかじゃないので
適当にdpを手計算でする。末尾3つ状態4つのdpをする
8.★★
不等式評価で雑に絞って、統合成立する構築ができないことより
最小の候補が決まる。
あとは構築
9.★
n角形の頂点をすべて結ぶ
始点と終点を適当に決めて最長のパスを考える
適当にやるとオイラーの一筆書き定理に落ちる
10.★
fpsをする
f(x)=(1+x)(1+x^2)(1+x^3)(1+x^4).....(1+x^2000)
のxの次数が5の倍数なものの係数和
1でないω^5=1となるもの用意して
5S=Σf(ω^i)
Π(1+ω^i)=2なので
5S=(2^2000+4*2^400)
