正の整数からなる2つの数列 $a_1, a_2, \dots$ と $b_1, b_2, \dots$ があり、任意の正の整数 $n$ について、次のいずれかが成り立つ。 $(a_{n+1}, b_{n+1}) = (\frac{a_n}{2}, b_n + \frac{a_n}{2})$ または $(a_{n+1}, b_{n+1}) = (a_n + \frac{b_n}{2}, \frac{b_n}{2})$ このとき、$(a_1, b_1)$ としてありうる40以下の正の整数の組はいくつあるか。

1. 問題の内容

正の整数からなる2つの数列 $a_1, a_2, \dots$ と $b_1, b_2, \dots$ があり、任意の正の整数 $n$ について、次のいずれかが成り立つ。

$(a_{n+1}, b_{n+1}) = (\frac{a_n}{2}, b_n + \frac{a_n}{2})$ または $(a_{n+1}, b_{n+1}) = (a_n + \frac{b_n}{2}, \frac{b_n}{2})$

このとき、$(a_1, b_1)$ としてありうる40以下の正の整数の組はいくつあるか。

2. 解き方の手順

数列 $a_n, b_n$ が最終的にどのような値に収束するかを考える。

ある $N$ 以降で $a_n$ と $b_n$ が一定の値に収束すると仮定する。つまり、ある $N$ が存在し、$n \ge N$ ならば $a_n = a, b_n = b$ (定数) となる。

このとき、$n \ge N$ に対し、以下のいずれかが成り立つ。

$(a, b) = (\frac{a}{2}, b + \frac{a}{2})$ または $(a, b) = (a + \frac{b}{2}, \frac{b}{2})$

最初の式から $\frac{a}{2} = a$ と $b + \frac{a}{2} = b$ が得られ、$a=0$ となる。

二番目の式から $a + \frac{b}{2} = a$ と $\frac{b}{2} = b$ が得られ、$b=0$ となる。

しかし、$a_n$ と $b_n$ は正の整数なので、いずれかの操作を繰り返すと、$a_n$または$b_n$の少なくとも一方は常に減少していく。

したがって、どこかの $N$ で $a_N = b_N$ となる必要があり、その後は $a_n = b_n$ となる。

つまり、最終的に $a = b$ になる必要がある。

漸化式は $a_{n+1} + b_{n+1} = a_n + b_n$ を満たす。

したがって、$a_n + b_n = a_1 + b_1$ は常に成り立つ。

もし $a_n = b_n = a$ に収束するならば、$2a = a_1 + b_1$ となる。

したがって、$a_1 + b_1$ は偶数である必要がある。

$1 \le a_1 \le 40$ かつ $1 \le b_1 \le 40$ なので、$2 \le a_1 + b_1 \le 80$ である。

また、$a_1 + b_1$ は偶数なので、$a_1 + b_1 = 2k$ ($k$ は整数) と書ける。

$2 \le 2k \le 80$ より、$1 \le k \le 40$ である。

$a_1 + b_1 = 2k$ より、$b_1 = 2k - a_1$ である。

$1 \le a_1 \le 40$ かつ $1 \le b_1 = 2k - a_1 \le 40$ を満たす必要がある。

つまり、$1 \le a_1 \le 2k - 1$ かつ $2k - 40 \le a_1 \le 40$ である。

したがって、$\max(1, 2k - 40) \le a_1 \le \min(40, 2k - 1)$ である。

$k$ に対する $a_1$ の個数を $N_k$ とすると、$N_k = \min(40, 2k - 1) - \max(1, 2k - 40) + 1$ である。

全組み合わせ数は $\sum_{k=1}^{40} N_k$ である。

$2k - 40 \le 1$ のとき、$k \le 20.5$ より、$k \le 20$ であり、このとき $N_k = (2k - 1) - 1 + 1 = 2k - 1$ である。

$2k - 1 \ge 40$ のとき、$k \ge 20.5$ より、$k \ge 21$ であり、このとき $N_k = 40 - (2k - 40) + 1 = 81 - 2k$ である。

$21 \le k \le 40$ であり、$N_k = 81 - 2k$ である。

したがって、

$\sum_{k=1}^{20} (2k - 1) + \sum_{k=21}^{40} (81 - 2k) = 2 \sum_{k=1}^{20} k - \sum_{k=1}^{20} 1 + 81 \sum_{k=21}^{40} 1 - 2 \sum_{k=21}^{40} k$

$= 2 \cdot \frac{20(21)}{2} - 20 + 81 \cdot 20 - 2 \cdot (\frac{40(41)}{2} - \frac{20(21)}{2})$

$= 420 - 20 + 1620 - 2 \cdot (820 - 210) = 400 + 1620 - 2(610) = 2020 - 1220 = 800$

3. 最終的な答え

800