トップ› 京都大学› 1978年› 文系第6問

京都大学 1978年文系第6問解説

方針・初手

与えられた数列の変換ルールを、数式を用いて表現することが第一歩だ。項が $0$ または $1$ のみであり、「両隣が等しいか異なるか」によって値が決まる操作は、整数の足し算の偶奇（2を法とする合同式）と非常に相性が良い。 $a'_i$ を $a_{i-1}$ と $a_{i+1}$ を用いた合同式で表し、条件 $A = A'$（すべての $i$ について $a_i = a'_i$）を適用することで、隣接する項の間に成り立つ漸化式を導く。そこから数列の周期性を見抜くことが解答の鍵となる。

解法1

円環状に並んだ数列を扱うため、すべての整数 $i$ に対して $a_{i+n} = a_i$ となるように添字を拡張して考える（問題文の $a_0 = a_n, a_{n+1} = a_1$ はこれに含まれる）。

新しい数列の項 $a'_i$ が決まる規則を、2を法とする合同式（$\text{mod } 2$）を用いて表す。

$a_{i-1} = a_{i+1}$ のとき：$a_{i-1} + a_{i+1}$ は $0$ または $2$ であり、$a_{i-1} + a_{i+1} \equiv 0 \pmod 2$ となる。このとき $a'_i = 0$ である。
$a_{i-1} \neq a_{i+1}$ のとき：一方が $0$ で他方が $1$ なので、$a_{i-1} + a_{i+1} = 1 \equiv 1 \pmod 2$ となる。このとき $a'_i = 1$ である。

したがって、いずれの場合も以下の式が成り立つ。

$$ a'_i \equiv a_{i-1} + a_{i+1} \pmod 2 $$

条件 $A = A'$ より、すべての $i$ について $a_i = a'_i$ であるから、

$$ a_i \equiv a_{i-1} + a_{i+1} \pmod 2 $$

これを移項して整理すると、連続する3項に関する条件が得られる。

$$ a_{i-1} + a_i + a_{i+1} \equiv 0 \pmod 2 \quad \cdots \text{①} $$

式①はすべての $i$ について成り立つため、$i$ を $i+1$ に置き換えた式も成り立つ。

$$ a_i + a_{i+1} + a_{i+2} \equiv 0 \pmod 2 \quad \cdots \text{②} $$

式②から式①を辺々引くと、

$$ a_{i+2} - a_{i-1} \equiv 0 \pmod 2 $$

すなわち

$$ a_{i+2} \equiv a_{i-1} \pmod 2 $$

数列の各項は $0$ または $1$ であるため、合同式はそのまま等式になる。

$$ a_{i+2} = a_{i-1} $$

添字をずらすと、$a_{i+3} = a_i$ となる。これは、数列 $A$ が 周期3 で同じ値を繰り返すことを意味する。一方で、数列 $A$ は円環状の定義により 周期 $n$ を持つ（$a_{i+n} = a_i$）。この2つの周期性を同時に満たす必要があるため、$n$ が3の倍数であるかどうかで場合分けをする。

(I) $n$ が3の倍数でないとき $n$ と $3$ は互いに素である。 $a_i = a_{i+3}$ の関係を繰り返し用いると、$a_1 = a_4 = a_7 = \cdots$ となる。 $n$ と $3$ が互いに素であることから、$1 + 3k$ を $n$ で割った余りは、すべての位置の添字を網羅する。したがって、数列のすべての項は等しくなる。すべての項の値を $c$（$c = 0$ または $1$）とおき、式①に代入すると、

$$ c + c + c \equiv 0 \pmod 2 \iff 3c \equiv 0 \pmod 2 \iff c \equiv 0 \pmod 2 $$

$c \in \{0, 1\}$ より $c = 0$ と定まる。よって、求める数列は $A = \{0, 0, \cdots, 0\}$ のみである。

(II) $n$ が3の倍数のとき $n = 3m$（$m$ は自然数）と表せる。このとき、最初の3項 $a_1, a_2, a_3$ の値を決めれば、$a_i = a_{i+3}$ に従って残りのすべての項が周期的に定まり、同時に周期 $n$ の条件も矛盾なく満たされる。満たすべき条件は、最初の3項に関する式①のみである。

$$ a_1 + a_2 + a_3 \equiv 0 \pmod 2 $$

各項が $0$ または $1$ であるとき、和が偶数になる $(a_1, a_2, a_3)$ の組は以下の4通りである。

和が $0$ になる組：$(0, 0, 0)$
和が $2$ になる組：$(0, 1, 1), (1, 0, 1), (1, 1, 0)$

これらを3項ごとに繰り返した数列が条件を満たす。

解説

操作のルールを「2で割った余りの世界（合同式）」に翻訳できるかが最大のポイントだ。$0$ と $1$ だけで構成される数列や論理回路の問題において、$a \equiv b+c \pmod 2$ のような変換は非常に強力な武器になる。漸化式から「周期3」という性質を見抜いた後は、「周期 $n$」という大前提との擦り合わせを行う。周期に関する問題では、周期同士の最大公約数（今回は互いに素か否か）に着目して場合分けをするのが定石だ。