整数解の個数 - RPGツクールと数学のブログ

過去ブログの転載です。

今回は整数解の個数に関する以下の証明をしてみます。

実数 $\displaystyle a, b$ があるとき、次の範囲を満たす整数 $\displaystyle n$ の個数をそれぞれ与える。
$\displaystyle a \le n \le b \Rightarrow \left( \left\lfloor b \right\rfloor - \left\lceil a \right\rceil + 1 \right)$ 個
$\displaystyle a \lt n \le b \Rightarrow \left( \left\lfloor b \right\rfloor - \left\lfloor a \right\rfloor \right)$ 個
$\displaystyle a \le n \lt b \Rightarrow \left( \left\lceil b \right\rceil - \left\lceil a \right\rceil \right)$ 個
$\displaystyle a \lt n \lt b \Rightarrow \left( \left\lceil b \right\rceil - \left\lfloor a \right\rfloor - 1 \right)$ 個
ただし、 $\displaystyle \left\lfloor \cdot \right\rfloor, \left\lceil \cdot \right\rceil$ はそれぞれ床関数、天井関数。（それぞれ正の数に対する切り捨て、切り上げに相当）

例えば $\displaystyle 2.5 \lt n \le 5$ を満たす $\displaystyle n$ は $\displaystyle 3, 4, 5$ の3個、 $\displaystyle 2.5 \le n \lt 5$ を満たす $\displaystyle n$ は $\displaystyle 3, 4$ の2個です。

それぞれ式に当てはめてみると、
$\displaystyle \left\lfloor 5 \right\rfloor-\left\lfloor 2.5 \right\rfloor=5-2=3$ 個
$\displaystyle \left\lceil 5 \right\rceil-\left\lceil 2.5 \right\rceil=5-3=2$ 個

となって、確かに合っていることが確認できます。

終端から始端を引き算しているだけですから、ちょっと操作してみたら割と当たり前なように感じるのですが、細かく証明してみたいと思います。

解の個数について

そもそも解の個数はどのようなものであるか確認しておきます。

例えば $\displaystyle x^{2}+3x+2=0$ は $\displaystyle x=-1, -2$ の2個の解を持ちます。これは、 $\displaystyle x$ に対して $\displaystyle x^{2}+3x+2=0$ となるような $\displaystyle x$ の集合の要素数として表現することが可能です。

集合 $\displaystyle X=\{x | x^{2}+3x+2=0\}$ としたときの $\displaystyle |X|$ が解の個数に相当するというわけです。

この場合の解の個数とは、零点集合の要素数と言い換えられますね。

同様にして、集合 $\displaystyle N=\{n | a \le n \le b\}$ と置いたときの $\displaystyle |N|$ が、 $\displaystyle a\le n\le b$ の範囲内にある整数 $\displaystyle n$ の個数、と言うことが出来ます。
従って、冒頭の4つの関係は次のように表現出来ます。

$\displaystyle |\{n \in Z | a \le n \le b\}|=\left\lfloor b \right\rfloor - \left\lceil a \right\rceil + 1$
$\displaystyle |\{n \in Z | a \lt n \le b\}|=\left\lfloor b \right\rfloor - \left\lfloor a \right\rfloor$
$\displaystyle |\{n \in Z | a \le n \lt b\}|=\left\lceil b \right\rceil - \left\lceil a \right\rceil$
$\displaystyle |\{n \in Z | a \lt n \lt b\}|=\left\lceil b \right\rceil - \left\lfloor a \right\rfloor - 1$

これらを証明しましょう。

整数間の範囲に修正する

次の式がそれぞれ成り立ちます。

$\displaystyle |\{n \in Z | a \le n \le b\}|= |\{n \in Z | \left\lceil a \right\rceil \le n \le \left\lfloor b \right\rfloor\}|$
$\displaystyle |\{n \in Z | a \lt n \le b\}|=|\{n \in Z | \left\lfloor a \right\rfloor + 1 \le n \le \left\lfloor b \right\rfloor\}|$
$\displaystyle |\{n \in Z | a \le n \lt b\}|=|\{n \in Z | \left\lceil a \right\rceil \le n \le \left\lceil b \right\rceil - 1\}|$
$\displaystyle |\{n \in Z | a \lt n \lt b\}|=|\{n \in Z | \left\lfloor a \right\rfloor + 1 \le n \le \left\lceil b \right\rceil - 1\}|$

左辺は実数間の範囲ですが、右辺は整数間の範囲になっています。まず、これらを示します。

全部やるのはめんどくさいので、 $\displaystyle a \le n \le b$ の場合のみ確認します。

これらを示す際に、床関数と天井関数の性質を用います。これらは定義式から直ちに導かれます。

$\displaystyle \left \lfloor x \right \rfloor = n \Leftrightarrow n \le x \lt n+1$
$\displaystyle \left \lceil x \right \rceil = n \Leftrightarrow n-1 \lt x \le n$

（1） $\displaystyle a \le n \le b$ を満たす $\displaystyle n$ の個数は、 $\displaystyle a \le n \le \left \lfloor b \right \rfloor$ を満たす $\displaystyle n$ の個数に一致する

$\displaystyle a \le n \le b$ を二つの範囲に分割します。 $\displaystyle a \le n \le \left \lfloor b \right \rfloor$ と $\displaystyle \left \lfloor b \right \rfloor \lt n \le b$ です。

$\displaystyle \left \lfloor b \right \rfloor \lt n \le b$ を満たす $\displaystyle n$ が存在しないことを示せばOKです。

全辺 $\displaystyle \left \lfloor b \right \rfloor$ を引けば

$\displaystyle 0 \lt n - \left \lfloor b \right \rfloor \le b - \left \lfloor b \right \rfloor$ となり、床関数の性質から $\displaystyle b - \left \lfloor b \right \rfloor \lt 1$ なので、
$\displaystyle 0 \lt n - \left \lfloor b \right \rfloor \lt 1$ となります。
$\displaystyle n - \left \lfloor b \right \rfloor$ は整数ですが、これを満たす整数は存在しません。よって、題意が示されました。

（2） $\displaystyle a \le n \le \left \lfloor b \right \rfloor$ を満たす $\displaystyle n$ の個数は、 $\displaystyle \left \lceil a \right \rceil \le n \le \left \lfloor b \right \rfloor$ を満たす $\displaystyle n$ の個数に一致する

同様にすればよいです。 $\displaystyle a \le n \lt \left \lceil a \right \rceil$ と $\displaystyle \left \lceil a \right \rceil \le n \le \left \lfloor b \right \rfloor$ に分割し、
$\displaystyle a - \left \lceil a \right \rceil \le n - \left \lceil a \right \rceil \lt 0$ とすると天井関数の性質から $\displaystyle -1 \lt a - \left \lceil a \right \rceil$ なので、
$\displaystyle -1 \lt n - \left \lceil a \right \rceil \lt 0$ となりますが、これを満たす整数はないので、題意が示されます。

残りも同様に導くことが可能なはずです。

整数間の範囲の解の個数を求める

次に、整数 $\displaystyle p, q$ による整数間の範囲の解の個数を求めます。これは次のようになります。
$\displaystyle |\{n \in Z | p \le n \le q\}|=q-p+1$
これを示せれば、もう導けたも同然です。

簡単のため、次のように範囲を変形します。
$\displaystyle p\le n\le q$ の全辺から $\displaystyle p$ を引いて
$\displaystyle 0\le n-p \le q-p$ とすると、 $\displaystyle n-p$ , $\displaystyle q-p$ は整数なので、それぞれ $\displaystyle k, r$ と置けば
$\displaystyle 0 \le k \le r$ となります。
$\displaystyle |\{n \in Z | p \le n \le q \}|=|\{k \in Z | 0 \le k \le r\}|$ となります。
もうここまできたら、さすがに明らかですね。
$\displaystyle |\{k \in Z | 0\le k\le r\}|=r+1$ を数学的帰納法で示しましょう。

$\displaystyle r=0$ のとき $\displaystyle 0\le k\le 0$ になりますが、 $\displaystyle k=0$ のみ満たすので
$\displaystyle |\{k \in Z | 0\le k\le 0\}|=1$ となります。
$\displaystyle r=m$ のとき $\displaystyle |\{k \in Z | 0 \le k \le m\}|=m+1$ と仮定すると
$\displaystyle r=m+1$ のとき
$\displaystyle |\{k \in Z | 0 \le k \le m+1\}|$
$\displaystyle =|\{k \in Z | 0 \le k \le m\}|+|\{k \in Z | m\lt k\le m+1\}|$
$\displaystyle =m+1+|\{k \in Z | m \lt k\le m+1\}|$
$\displaystyle m\lt k\le m+1$ の全辺を $\displaystyle m$ 引けば
$\displaystyle 0\lt k-m \le1$ より、 $\displaystyle k-m=k'$ とおくと $\displaystyle 0\lt k'\le 1$ となります。
これを満たす整数 $\displaystyle k'$ は $\displaystyle k'=1$ しかないので、
$\displaystyle |\{k \in Z | m\lt k\le m+1\}|=1$ が言えることから、
$\displaystyle =m+2$ となります。
以上より、数学的帰納法から $\displaystyle |\{k \in Z | 0\le k\le r\}|=r+1$ が示されました。

$\displaystyle |\{k \in Z | 0\le k \le r\}|=r+1$ から、 $\displaystyle r=q-p$ より
$\displaystyle |\{n \in Z | p\le n\le q\}|=q-p+1$ が言えて、 $\displaystyle q=\left\lfloor b \right\rfloor, p=\left\lceil a \right\rceil$ とすれば
$\displaystyle |\{n \in Z | \left\lceil a \right\rceil \le n \le \left\lfloor b\right\rfloor\}|=\left\lfloor b \right\rfloor - \left\lceil a \right\rceil +1$
左辺は $\displaystyle |\{n \in Z | a \le n \le b\}|$ に等しいので、
$\displaystyle |\{n \in Z | a \le n \le b\}|= \left\lfloor b \right\rfloor - \left\lceil a \right\rceil+1$ を導くことができました。
ほかの式も同様に求められます。

すごいまどろっこしいですけど、これでちゃんと示せましたね。たぶん……

R-Z存在定理

実数定数 $\displaystyle a, b,$ 未知数整数 $\displaystyle x$ があるとき、 $\displaystyle a\lt x\lt a+b$ が常に解を持つことは、 $\displaystyle b\gt 1$ と同値である。

これに対して私はR-Z存在定理という臭い名前をつけました。今回きちんと求めた解の個数の式を使えば、これは簡単に示せます。

上の定理はより一般に、次のように言うことができます。

実数定数 $\displaystyle a, b,$ 未知数整数 $\displaystyle x$ があるとき、 $\displaystyle a \lt x \lt a+b$ の解の個数の下限は $\displaystyle ( \left \lceil b \right \rceil -1)$ 個である。

$\displaystyle b \gt 1$ であれば $\displaystyle \left \lceil b \right \rceil -1 \gt 0$ なので、確かに常に解をもつことが言えます。これを示しましょう。

まず、 $\displaystyle a \lt x \lt a+b$ の解の個数は $\displaystyle \left\lceil a+b \right \rceil - \left \lfloor a \right \rfloor-1$ です。

これが $\displaystyle ( \left \lceil b \right \rceil -1)$ 以上であることを言えればいいので、
$\displaystyle \left \lceil a+b \right \rceil - \left \lfloor a \right \rfloor-1-(\left \lceil b \right \rceil -1)$ が非負になることを示せばOKです。
$\displaystyle =\left \lceil a+b \right \rceil - \left \lfloor a \right \rfloor - \left \lceil b \right \rceil$ となります。

① $\displaystyle a$ が整数のとき
$\displaystyle \left \lceil a+b \right \rceil - \left \lfloor a \right \rfloor - \left \lceil b \right \rceil$
$\displaystyle =a + \left \lceil b \right \rceil - a - \left \lceil b \right \rceil$
$\displaystyle =0 \ge 0$ より、 $\displaystyle b$ に無関係に成立

② $\displaystyle b$ が整数のとき
$\displaystyle \left \lceil a+b \right \rceil - \left \lfloor a \right \rfloor - \left \lceil b \right \rceil$
$\displaystyle =\left \lceil a \right \rceil + b - \left \lfloor a \right \rfloor - b$
$\displaystyle =\left \lceil a \right \rceil - \left \lfloor a \right \rfloor \ge 0$ より、成立

③ $\displaystyle a, b$ が非整数だが、 $\displaystyle a+b$ が整数のとき
$\displaystyle a+b=n$ （ $\displaystyle n$ は整数）とおくと、 $\displaystyle b=n-a$ と表されるので
$\displaystyle \left \lceil a+b \right \rceil - \left \lfloor a \right \rfloor - \left \lceil b \right \rceil$
$\displaystyle =\left \lceil n \right \rceil - \left \lfloor a \right \rfloor - \left \lceil n-a \right \rceil$
$\displaystyle =n - \left \lfloor a \right \rfloor - n - \left \lceil -a \right \rceil$
$\displaystyle =n - \left \lfloor a \right \rfloor - n + \left \lfloor a \right \rfloor$
$\displaystyle =0 \ge 0$ より、成立

④ $\displaystyle a, b$ も $\displaystyle a+b$ も非整数
$\displaystyle \left \lceil a＋b \right \rceil \ge a+b$ が成り立つので、③の値よりも大きくなることが確認できるから、成立

以上からすべての場合で成り立つので、常に非負です。
よって、解の個数の下限は $\displaystyle \left \lceil b \right \rceil - 1$ であると言えます。
$\displaystyle a$ が何か分からなくても、 $\displaystyle b$ の値だけで解の下限が分かるのですね。