2008年IMOスペイン大会5問目の解答、解説

私が生まれるより前のかなり昔の問題ですが、私の好きな問題なので解説しようと思います。
問題文を少し改変してます。

問題文（改）

n,kをn≦k、(k-n)/2∈ℕなる正整数とする。
1,2,…,2nと番号が付いている2n個のスイッチがあり、最初はすべてoffとなっている。
操作を行うとそのうち1つを選んでon-offを入れ替えることが出来る。

計k回の操作後、1,2,…,nのスイッチがonであり、n+1,…,2nがoffであるような操作方法の個数をNとする。
また、そのうちn+1,…,2nが一度もonとならないような操作方法の個数をMとする。
N/Mを(n,k)を用いて表せ。

考え方

同じボタンが全体で偶数回操作されたなら最終的にoff,奇数回操作されたならonとなります。

そのため、n≦k、(k-n)/2∈ℕは、M,N≠0であるための必要十分条件です。

2つの求めづらい場合の数の比ということで、一対一対応を考えるとよさそうです。

また、n,kが小さな場合について調べると、N/Mの値が整数であることがわかります。
よって、恐らく任意の(k,n)についてN/Mの値は整数であり、「Nに数えられる操作」が、「Mに数えられる操作と何かの組」と一対一対応することを示せるのではと予想できます。

これらを踏まえて、解答を考えていきましょう。

解答

Nに数えられる操作は、スイッチ1,2,...,nを1赤,2赤,…,n赤に、スイッチn+1,n+2,…,2nを1青,2青,…,n青と言い換え、操作したスイッチを表す単語を順に並べることで
「1赤,2赤,…,n赤,1青,2青,…,n青からなる長さkの単語配列aであり、1赤,2赤,...,n赤がちょうど奇数回、1青,2青,…,n青がちょうど偶数回登場するもの」
と表現できる。

同様に、Mに数えられる操作は、
「1,2,…,nからなる長さkの整数列bであり、1,2,...,nがちょうど奇数回登場するもの」
と表現できる。


上記の単語配列aは、上記の整数列bに対して、登場する1,2,...,nそれぞれの偶数個を青、残りの奇数個を赤に対応させる方法と一対一対応している。
任意の正の奇数2x+1(xは非負整数)について、そのうち偶数個を青、残りの奇数個を赤に対応させる方法をTとすると、
T=Σ(0≦i≦x)((2x+1 2i))
=Σ(0≦i≦x)((2x+1 2x+1-2i))
=Σ(0≦i≦x)((2x+1 2i+1))
2T=Σ(0≦i≦x)((2x+1 2i))
+Σ(0≦i≦x)((2x+1 2i+1))
=Σ(0≦i≦2x+1)((2x+1 i))
=2^(2x+1)
T=2^(2x+1-1)

整数列bに1,2,...,nがそれぞれc₁,c₂,…,cn(c₁,c₂,…,cnは正の奇数であり、c₁+c₂+…+cn=k)ずつ登場する場合、bに対して、登場する1,2,...,nそれぞれの偶数個を青、残りの奇数個を赤に対応させる方法は、
2^(c₁-1)×2^(c₂-1)×…×2^(cn-1)
=2^((c₁+c₂+…+cn)-n)
=2^(k-n)
よって、整数列bが何かに関わらずbに対応する単語配列aの個数は2^(k-n)であり、
N=M×2^(k-n)
よって、N/M=2^(k-n)…(答)

感想

今回の場合、単語配列aが(整数列b,赤と青の対応)という組と一対一対応していることを示すことで解く問題でした。
Tを求める部分は有名な公式なので、そこを見越せると解法の決定がスムーズになると思います。