2015/02/18

レイリーの定理とその自然な証明

分野: 整数問題  レベル: 最難関大学

レイリー(Rayleigh)の定理:
$\dfrac{1}{r}+\dfrac{1}{s}=1$ を満たす正の無理数 $r,s$ に対して以下が成立する。
全ての正の整数は二つの数列
$\lfloor mr\rfloor \:(m=1,2,3\cdots)$
$\lfloor ns\rfloor \:(n=1,2,3\cdots)$
のいずれかに必ず一回だけ登場する。


ただし,$\lfloor x\rfloor$ は $x$ の整数部分を表します。→ガウス記号の定義と3つの性質
非常に美しい整数の定理です。レイリーの定理を背景とする入試問題もあった気がします。

具体例

定理の主張を理解するために具体例で計算しましょう。実際に計算してみたら感動すること間違いなしです。

無理数として $r=\sqrt{5}=2.2360\cdots$ を選んでみます。
すると,$s=\dfrac{1}{1-\frac{1}{r}}=\dfrac{5+\sqrt{5}}{4}=1.809\cdots$ となります。

このとき数列 $\lfloor mr\rfloor$ は,$m=1$ から順番に,
$2,4,6,8.11,13,15,17,20,22,24,26\cdots$

同様に,数列 $\lfloor ns\rfloor$ は,$n=1$ から順番に,
$1,3,5,7,9,10,12,14,16,18,19,21,23,25\cdots$

となり確かに全ての正の整数がどちらか一方に一回だけ現れています!

証明(ダブらないこと)

レイリーの定理の証明は見かけよりは簡単です!

まず,$r,s > 1$ なので片方の数列に同じ正の整数が登場することはありません。そこで,レイリーの定理は以下の二つに分解できます。

全ての正の整数は,
1.二つの数列両方には登場しない。
2.どちらかの数列には必ず登場する

(いくつか証明方法があると思いますが、僕は二つに分けて証明するのが自然だと感じました)

ガウス記号の条件を不等式で書き換えるだけです!

1の証明

$N$ が両方の数列に存在すると仮定すると,
ある正の整数 $m,n$ が存在して
$N <mr <N+1$ かつ $N <ns <N+1$
($r,s$ は無理数なので $\leq$ ではなく$ <$が成立)

$\dfrac{1}{r}+\dfrac{1}{s}=1$ を使うために,一つ目の式の各辺を $r$ で割って二つ目の式の各辺を $s$ で割って辺々加える:
$N <m+n <N+1$
$m,n,N$ はいずれも整数なので矛盾。背理法により1は示された。

証明(網羅すること)

こちらもほぼ同様に背理法で証明できます。

2の証明

$N$ がどちらの数列にも登場しないと仮定すると,
($N$ から $N+1$ の区間を飛び越えてしまうので)ある正の整数 $m,n$ が存在して
$mr <N,\:N+1 <(m+1)r$
$ns <N,\:N+1 <(n+1)s$
それぞれの左の不等式より,
$m+n <\dfrac{N}{r}+\dfrac{N}{s}=N$

それぞれの右の不等式より,
$(m+1)+(n+1) > \dfrac{N+1}{r}+\dfrac{N+1}{s}=N+1$
つまり $m+n+1 > N$

以上より $m+n <N <m+n+1$
$m,n,N$ はいずれも整数なので矛盾。

レイリーの定理に登場する数列のことビーティー数列(Beatty sequence)と言います。Beautyですね。
分野: 整数問題  レベル: 最難関大学