1991IMO候補リストの問題 $\#11$

このような問題（特に一般的なパターンがあることに気付いた場合）の場合、いくつかのアイデアは、漸化式を見つけ、伸縮するものを作成する（またはそれを母関数として扱う）ことです。

ここではこれらのアイデアを使用します。

---

そのことに注意してください $ \left(\frac{1}{n-m} - \frac{1}{n}\right) { n - m \choose m } = \frac{m}{ n (n-m) } { n - m \choose m } = \frac{1}{n} {n-m-1 \choose m-1}$、 またはその

$$ \frac{ 1 } { n-m } { n-m \choose m } = \frac{1}{n} \left[ { n - m \choose m } + { n - m - 1 \choose m- 1 } \right]. $$

それは厄介なものを取り除くので、これは良い代替品です $ \frac{1}{n-k}$ これは再発を困難にし、また私たちに $\frac{1}{1991}$ RHSで。

したがって、目標は決定することです $ \sum_{k=0}^{995 } (-1)^k \left[ {1991-k\choose k} + { 1991 - k - 1 \choose k - 1 } \right] $。（これは1に等しいことを示します。したがって、必要な合計は次のようになります。$\frac{1}{1991}.$）

---

しましょう $ S_n = \sum_{k=0}^{ \lfloor \frac{n}{2} \rfloor} (-1)^k { n-k \choose k } $。

そのことに注意してください ${n-k \choose k } = { n-k - 1 \choose k } + { n-k - 1 \choose k - 1 } $、 そう

$ S_n = \sum_{k=0}^{\lfloor \frac{n+1}{2} \rfloor} (-1)^k { n - k + 1 \choose k } \\ = \sum_{k=0}^{\lfloor \frac{n+1}{2} \rfloor} (-1)^k \left[ {n-k \choose k } + {n-k \choose k - 1 } \right] \\ = \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} (-1)^k {n-k \choose k } + \sum_{k=0}^{\lfloor \frac{n-1}{2} \rfloor} (-1)^k { n-k \choose k } \\ = S_{n} - S_{n-1}. $

（インデックスをチェックする際には注意して、それらを覚えておいてください ${n \choose m } = 0 $ いつ $m > n $。）

この漸化式を使用し、いくつかの初期値を計算すると、次のようになります。 $S_n = 1 , 0, -1, -1, 0, 1, 1, 0, -1, \ldots$、期間は6
です。したがって、次のように決定します。$S_{1991} - S_{1990} = 0 - (-1) = 1$。

---

ノート

1. ここに組み合わせ論的証明があったらいいのにと思います。例えば、$S_n$ 偶数と奇数の順列の違いとして即座に解釈されます $p$ そのような $|p(i) - i | \leq 1$。（IE最初から$n$ 整数、あります ${n-k \choose k }$連続する整数のkペアを選択する方法（合計2k）。これらのペアを切り替えて残りを固定するperumatationにはパリティがあります$k$。）しかし、この違いが次のようになっていることを示す明確な方法がわかりません。 $1, 0, -1, -1, 0, 1, \ldots $。

2. の価値についてのWhatsUpの結論 $s_n$ 上記からも続きます。

関数の生成を知っている場合は、次の解決策があります。

しましょう $s_n$ 合計を示します $\sum_{k \geq 0} \frac{(-1)^k}{n - k}\binom{n - k}k$ そしてしましょう $S(X)$ 正式なべき級数になる $S(X) = \sum_{n \geq 1} s_n X^n$。

私たちは計算します：

\ begin {eqnarray} S（X）＆=＆\ sum_ {n \ geq 1} \ frac 1 n X ^ n + \ sum_ {n \ geq 1} \ sum_ {k \ geq 1} \ frac {（-1 ）^ k} {n-k} \ binom {n-k} k X ^ n \\＆=＆-\ log（1-X）+ \ sum_ {k \ geq 1} \ sum_ {n \ geq 2k} \ frac {（-1）^ k} k \ binom {n-k-1} {k-1} X ^ n \\＆=＆-\ log（1-X）+ \ sum_ {k \ geq 1} \ frac {（-1）^ k} k X ^ {2k} \ sum_ {n \ geq 0} \ binom {n + k-1} {k-1} X ^ n \\＆=＆-\ log（ 1-X）-\ sum_ {k \ geq 1} \ frac {（-1）^ {k-1}} k \ left（\ frac {X ^ 2} {1-X} \ right）^ k \\ ＆=＆-\ log（1-X）-\ log \ left（1 + \ frac {X ^ 2} {1-X} \ right）\\＆=＆-\ log（1-X + X ^ 2 ）\\＆=＆-\ log（1- \ omega X）-\ log（1- \ overline \ omega X）\\＆=＆\ sum_ {n \ geq 1} \ frac {\ omega ^ n + \ overline \ omega ^ n} n X ^ n、\ end {eqnarray}ここで、$\omega = \frac{1 + \sqrt{-3}}2$ は、1の原始的な6番目の根です。

したがって、 $s_n = \frac 1 n \cdot 2 \operatorname{Re}(\omega^n)$。

今 $\omega^n$ にのみ依存 $n \mod 6$。したがって：$$s_n = \begin{cases} \frac 2 n, & n \equiv 0\mod 6;\\ \frac 1 n, & n \equiv 1, 5\mod 6;\\ \frac {-1} n, & n \equiv 2, 4 \mod 6;\\ \frac{-2} n, & n \equiv 3 \mod 6. \end{cases}$$

そして、元の質問への答えは、 $1991 \equiv 5 \mod 6$。