上級問題
★は５段階評価
11.★★
問題の設定を理解するのにめちゃめちゃ時間がかかる
大きいものから考えていく
12.★
2冪で考える
2048枚あったとして96回の操作が経過したところからスタートしたと思えばいい
(2^10-1)-96927
13.★
2*2のマスは1999*2001個数ある
offにできるスイッチの数は高々これだけなので不可能
14.★
9の書類が午後に来るか午前に来るかを考える
2^8+Σi*Binom(7,i)=2^8+7*ΣBinom(6,i-1)=2^8+7*2^6
15.★
言い換えを考える
Binom(2n+1,n)からスタートする
{a,b0b1b2,,,,bn,c0c1c2,,,,,cn}の2n+1からn人選ぶとして
biciのいずれかが選ばれるのをx
bic1のどちらも選ばれるのを(k-x)/2とすると
ΣBinom(n,x)*2^x*Binom(n-x,(n-x)/2)=Binom(2n+1,n)
16.★★
知らないパターンですねこれは
n乗根とm乗根をそれぞれαβとして用紙いて
a[i][j] = α^iβ^jとすると
マスの総和が0になることから示される
17.★★★
可能なことは種類数をへらすのが簡単なためわかる。
厳密に証明するのが難しい。
18.★★
解説はまどろっこしいことを書いているが
anが長さnの完全順列の数であることは簡単で
fn=n!+({1,2,3,,,,,n}の置換すべての中の不動点の個数)-(n+1)=2*n!-(n+1)
19.★★
ここまでと毛色の違う問題。
x,y∈Sかつgcd(x,y)=1とすると
xyより多いものはすべてSの含まれる。
よってTは有限個
t0,t1,t2,t3,t4,t5...tnとあって
t0に対してx+y=t0となるxとyのどちらかはSに含まれない。
ti/2<=i-1両辺Σして適当に
20.★★
辺を共有しないハミルトンサイクルの最大数
構築ゲー
