組合せ論の精選
基本問題51
解法メモ
01.
簡単な計算をします
02.
丁寧に計算をします
03.
二項係数の和が2^nになること
合計が奇数なら奇数が奇数個あること
04.
包除原理をします
05.
丁寧に計算をします
二問目とほぼ同じ
06.
連続する同性をブロックにしてみる
07.
トーナメントの勝ち負けと一対一対応
08.
16!/2^8
09.★
24とおもいきや23
10.
素因数をどっちに振り分けるか
とその半分
2^8/2
11.
考えるまでもなく14C5
12.
自明な上界が最大値
13.
Binom((98-4)/2+3,3)=Binom(50,3)
14.
人名ごとに貪欲
15.
下から考える
16.
Binom(5,2)*3!
17.★★
a+b=c+dを
a-c=d-bと読み替える
差の候補は1から99
Binom(16,2)=120のうち、重複を除くと
a-b=b-cが成り立つbの候補はたかだか16個であり
x-b=b-yも同時に成り立つとすると
a+c=2=x+yが成り立つので99<120-16より明らか
18.
計算をします
19.
abc-abcx
abc-xabcはそれぞれ10^4あり同時に満たすのは
aaa-aaaaのケースなので2*10^4-10
21.
mod3で見ると{0,1,2,0,1,2,0}なので
3!*3!*2!*2!=144
22.
集合1に入るか集合2に入るか両方かと対称性
23.★
a[10]>=a[9]+a[8]>=(a[8]+a[7])+a[8]としていくと
a[10]>=34a[2]+21a[1]となるので
24.★★
これは難しいと思った
まず、A,Bのいずれかが有限集合の場合を考える。
次にどちらも無限集合の場合を考え背理法を考える。
x>y>z>nかつy-z>nを満たすようなx,y,zをAから取れること
x+y,x+z,y+zがBに含まれることがわかる
y-zがA,Bのいずれに含まれても矛盾する。
25.
100(10)=110010(2)
以下略
26.
2つ決めれば残りが決まる
Binom(27,2)/3
27.★★
解答２の考え方がわかりやすい
解答１は少し難しく感じる。
28.
主客転倒
19*Binom(18,6)*2/Binom(20,7)
29.
2^(2n)人いたとして行って返ってくると
2^(2n-2)人残り
4n+2番目の人が残る。
逆からたどるとx->4x-2となるので計算できる
30.
自明
31.
199+1=200の39以下の最大の約数25を考え
1990=25*79+15で構成されていたとして
199/25=7なので
79/7+1の12は必要。
これだけあれば満足なことを示したい
1990人を学校ごとにソートし199人ごとに区切る
と分断される学校が存在するが高々9校
5*39<199より分断された高校は2つに収まる
32.
典型なので略
問題文に大切な部分が抜けているのが最難ポイント
33.★
fpsを考える
f(x)=x*(x+x^2)(x+x^2+x^3)........の[x^m]の係数を考えるといい
手計算をするとn<5は満たすのが確認できる
f(x)の最小次数はn最大次数は(1+n)*n/2
項数は1+(n-1)(n-2)/2でありこれはnより大きい(n>=5)
fn(x) = f(n-1)(x)*(x+x^2+x^3.....x^n)なので
fn[x^m]=f(n-1)[m-1]+f(n-1)[m-2]+..........f(n-1)[m-n]なので
< f(n-1)(1)=(n-1)!
34.★★
6つ以上要素があったとして
Binom(6,1)+Binom(6,2)+Binom(6,3)+Binom(6,4)=56 > 54=12+13+14+15
より鳩の巣原理が適応できる。
{a,b,c,d,e}について考える
c<=13
d+e<=29なので
a+b<=20であること
a+b+c+d+e<=20+13+29=42なので
c<=12を示したい
c=13と仮定する
a+b+c+d+e<=a+b+13+14+15=a+b+42
b=12だと12+15=13+14なため
b<=11
b=11とすると
a+15=11+14なのでaは10でなく
a+15=11+13なので9でもない
8<=aとなるが
8+11+13+14+15=61
またb<=10だと
9+10+11+12+13<=61なので
61より大きくはならない
また{8,11,13,14,15}のときに満たす。
35.★
これ、箱も飴も>=4ですよね？
帰納法が回るので解けます。
(1,1,1,1)->(3,1,0,0)->(2,0,2,0)->(1,0,1,2)->(0,0,0,4)で遷移させると
飴が4のケースがとけるので
飴mのケースが成り立つと仮定して
m+1のケースを1つの飴を無視して考えると(m,1,0,0)か(m+1,0,0,0)になる
(m,1,0,0)->(m-1,0,2,0),(m-2,1,1,0),(m,0,0,0)となるのでOK
36.★
1000個というのが難しくて
2^nなら簡単2^nを解いて不要なものを取り除けばいい
2^nの解き方は2^n-1から再帰的に考える
37.
円環dp
38.★
背理法
人P、Pの友達集合A、その他の集合B
として適当に
39.
上２行固定
6*(1*1+1*6+4*2)=90
40.
上一行固定する
全部交互に並んでいるときとそうでないときにわけて考える
連続して同じ色のものが存在するなら
他の行も決まるので2^n-2通り
交互に並んでいるならすべての行ならそうなので2^n通り
41.
ボールの個数が二冪なのがポイント
ボールのが数が全部偶数ならボールを２つペアで考えると
2^(n-1)で成立すれば帰納的に示される
なので、全部偶数にできるかを考える
奇数個数入っているのは偶数個あるのでペアにして操作すると全部偶数に
42.
自明なことをちゃんと答案にできるかどうか
選択したもの以外の和について考える
これは操作するごとに減少することが簡単に示せる
43.★★
nのみになった状態から更に一回操作をすると初期状態に戻る
合計操作回数2^nの内訳を考える
全体の和は+1-nされるので操作回数はn+1の倍数
となるよってnは2^m-1型
44.★★
問題を前半と後半に分ける
帰納法で考える
全色同じにできるかを考える
初期状態がすべて同じじゃない場合は帰納法が回る
全部同じ時は？
Σi=k*(2k+1)なので順番に塗ればいい
all表orall裏のどちらかにしか出来ないことを示したい
ooooooo->逆操作->初期状態->操作->xxxxx
ができることになるが2k*(2k+1)は偶数なので矛盾
45.
主客転倒
ans=Σ(i=1,n)Σ(j=0,n-i)i*Binom(n-i,j)*(-1)^j*2^(i-1)
二項係数の交代和は0になるので
ans=n*2^(n-1)
46.
0<=a0<=a1<=a2<=a3<=a4<=7
0 < a0+1 < a1+2 < a2+3 < a3+4 < a4+5=12
ans=Binom(12,5)
47.
ababababab
cdcdcdcdcdとして
Σa+Σbは奇数
Σb+Σdも奇数
Σa+Σdは偶数
48.
1～11のなかから6つ選べないことは簡単にわかる。
自明な上界が答え
49.
[12][34][56][78][910]...
1][23][45][67][89][1011]...
みたいなのがあってそれぞれ15!*15!*2^15
重複が2*15!*15!
回転を考慮して30で割ると
15!*14!*(2^30-1)
50.
合計が奇数と偶数で矛盾
51.★★
非自明な言い換え
アパートiに住んでいる人数をaiとすると
S=Σai*(ai-1)/2と定めると
大家の操作後のSをS'とすると
S>S'となる。
そのため無限に操作することは出来ない
