COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

整数の雑題

理論

鳩の巣原理

 $n$ 個の巣に $n+1$ 羽の鳩が帰るとき, ある巣には複数の鳩が入る. より一般に, $m$ 個の対象を $n$ 個の種類に分けるとき, $m > n$ ならば, 複数の対象が同じ種類に分けられる. この原理は鳩の巣原理(pigeonhole principle)と呼ばれ, 主張が非常にシンプルであるにもかかわらず, 存在定理の証明にしばしば用いられる. この原理を用いるとき, 具体的にどの対象が同じ種類に属するかについては分からない. しかし, 各対象がどの種類に属するかをしらみつぶしに調べて比較するという非効率な検証を必要としないため, 存在定理の強力な証明法を与え得るのである. 鳩の巣原理は, 関数の定義域, 値域を集合に一般化した写像という概念を用いて定式化される.

定理≪鳩の巣原理≫

 有限集合 $S$ から有限集合 $T$ への写像について, $n(S) > n(T)$ が成り立つならば, 同じ値をとる複数の $S$ の要素が存在する.
 鳩の巣原理は, ディリクレの部屋割り論法(Dirichlet's drawer principle)とも呼ばれる.

問題

整数と多項式

問題≪整数の代入値が必ず整数になる多項式≫

 実数係数 $3$ 次多項式 $f(x)$ について, 次の $2$ 条件は同値であることを示せ:
(i)
任意の整数 $n$ に対して, $f(n)$ は整数である.
(ii)
ある整数 $a,$ $b,$ $c,$ $d$ について, \[ f(x) = \dfrac{a}{6}x(x-1)(x-2)+\dfrac{b}{2}x(x-1)+cx+d.\]

解答例

 $f(x)$ を $x(x-1)(x-2)$ で割った商を $\alpha,$ 余りを $r(x)$ とおき, $r(x)$ を $x(x-1)$ で割った商を $\beta,$ 余りを $\gamma x+\delta$ とおくと, 次のように表せる: \[ f(x) = \alpha x(x-1)(x-2)+\beta x(x-1)+\gamma x+\delta \quad \cdots [1].\]
  • よって,
    (i)$\Longrightarrow$ $f(0),$ $f(1),$ $f(2),$ $f(3)$ は整数
    $\Longrightarrow$ $\delta,$ $\gamma +\delta,$ $2\beta +2\gamma +\delta,$ $6\alpha +6\beta +3\gamma +\delta$ は整数
    $\Longrightarrow$ $\delta,$ $\gamma,$ $2\beta,$ $6\alpha$ は整数 $\cdots$ (iii).
  • 逆に, 各整数 $n$ に対して $n(n-1)$ は偶数, $n(n-1)(n-2)$ は $6$ の倍数であることに注意すると, $[1]$ より, (iii) $\Rightarrow$ (i) も成り立つ.
  • $a = 6\alpha,$ $b = 2\beta,$ $c = \gamma,$ $d = \delta$ とおけば, (iii) $\Rightarrow$ (ii) が成り立つ.
  • (ii) を仮定すると, $f(0) = d = \delta,$ $f(1) = c+d = \gamma +\delta,$ $f(2) = b+2c+d = 2\beta +2\gamma +\delta,$ $f(3) = a+3b+3c+d = 6\alpha +6\beta +3\gamma +\delta$ となり, $a = 6\alpha,$ $b = 2\beta,$ $c = \gamma,$ $d = \delta$ となるから, (iii) が成り立つ.
以上より, 題意が示された.

問題≪整数の代入値が必ず整数になる多項式≫

 $f(x)$ を実数係数の $d$ 次多項式とする. 次の $3$ つの条件は同値であることを示せ:
(i)
任意の整数 $n$ に対して $f(n)$ は整数.
(ii)
$f(0)$ は整数で, 任意の整数 $n$ に対して $f(n+1)-f(n)$ は整数.
(iii)
$f(0),$ $\cdots,$ $f(d)$ は整数.

解答例

 (i)$\Longrightarrow$(ii) は明らか.
 (ii) を仮定すると, 任意の自然数 $n$ に対して, \begin{align*} f(n) &= (f(n)-f(n-1))+\cdots \\ &\qquad +(f(1)-f(0))+f(0), \\ f(-n) &= f(0)-(f(0)-f(-1))-\cdots \\ &\qquad -(f(-n+1)-f(-n)) \end{align*} は整数である. よって, (ii)$\Longrightarrow$(i) が成り立つ.
 (ii)$\iff$(iii) を $d$ に関する帰納法で示す.
$d = 0$ のとき. $f(d) = f(0)$ より, 明らかに (ii)$\iff$(iii) が成り立つ.
任意に固定されたある非負整数 $d$ に対して (ii)$\iff$(iii) が成り立つとし,
$f(x)$ の次数が $d+1$ 場合を考える.
$d$ 次多項式 $f(x+1)-f(x)$ について (i)$\iff$(iii) が成り立つことに注意すると, 次の条件は同値:
  • $f(0)$ は整数で, 任意の整数 $n$ に対して $f(n+1)-f(n)$ は整数.
  • $f(0),$ $f(1)-f(0),$ $\cdots,$ $f(d+1)-f(d)$ は整数.
  • $f(0),$ $\cdots,$ $f(d),$ $f(d+1)$ は整数.
以上より, 任意の $d$ 次多項式 $f(x)$ に対して (ii)$\iff$(iii) が成り立つ.

ガウス記号

問題≪ガウス記号の不等式・$n!$ の付値≫

(1)
任意の実数 $a$ に対して, 次が成り立つことを示せ. \[ 0 < b \leqq c \Longrightarrow \left[\frac{a}{c}\right] \leqq \left[\frac{a}{b}\right].\]
(2)
十進法の $100!$ を六進法で表すとき, 末尾に並ぶ $0$ の個数 $e$ を求めよ. 各正の整数 $n,$ $r$ について, $p^r \leqq n < p^{r+1}$ のとき $n!$ が $p$ で割り切れる回数 $e_p$ は \[ e_p = \left[\frac{n}{p}\right] +\dots +\left[\frac{n}{p^r}\right] \quad \cdots [\ast ]\] が成り立つことは証明なしに用いて良い.

解答例

(1)
$0 < b \leqq c$ を仮定する. このとき, $\dfrac{a}{c} \leqq \dfrac{a}{b}.$
(i)
$\dfrac{a}{c} < \left[\dfrac{a}{b}\right] \leqq \dfrac{a}{b}$ のとき. $\left[\dfrac{a}{c}\right] \leqq \dfrac{a}{c}$ より, \[\left[\frac{a}{c}\right] < \left[\frac{a}{b}\right].\]
(ii)
$\left[\dfrac{a}{b}\right] \leqq \dfrac{a}{c} \leqq \dfrac{a}{b}$ のとき. $\left[\dfrac{a}{c}\right]$ の最大性より \[\left[\frac{a}{b}\right] \leqq \left[\frac{a}{c}\right] \leqq \frac{a}{c} \leqq \frac{a}{b}\] となるから, $\left[\dfrac{a}{b}\right]$ の最大性より, \[\left[\frac{a}{c}\right] = \left[\frac{a}{b}\right]\]
(i), (ii) より, すべての場合に求める不等式が成り立つ.
(2)
$e$ は $100!$ が $6$ で割り切れる回数に等しい. 各正の整数 $k$ に対して \[\left[\frac{100}{2^k}\right] \geqq \left[\frac{100}{3^k}\right]\] が成り立つから, $6 = 2\cdot 3$ の各素因数 $p$ が $100!$ を割り切る回数を $e_p$ とおくと, $[\ast ]$ より $e_2 \geqq e_3.$ ゆえに, \begin{align*} e &= e_3 = \left[\frac{100}{3}\right] +\left[\frac{100}{9}\right] +\left[\frac{100}{27}\right] +\left[\frac{100}{81}\right] \\ &= 33+11+3+1 = 48. \end{align*}

問題≪ガウス記号の恒等式≫

 各実数 $a$ に対して, $a$ を超えない最大の整数を $[a]$ で表すとき, 次が成り立つことを示せ: $$[a]+\left[ a+\frac{1}{2}\right] = [2a].$$

解答例

(i)
$[a] \leqq a < [a]+\dfrac{1}{2}$ のとき. \[ [a]+\frac{1}{2} \leqq a+\frac{1}{2} < [a]+1\] より, \[\left[ a+\frac{1}{2}\right] = [a]\] であり, \[ 2[a] \leqq 2a < 2[a]+1\] より \[ [2a] = 2[a]\] だから, \[ [a]+\left[ a+\dfrac{1}{2}\right] = 2[a] = [2a].\]
(ii)
$[a]+\dfrac{1}{2} \leqq a < [a]+1$ のとき. \[ [a]+1 \leqq a+\frac{1}{2} < [a]+\frac{3}{2}\] より \[\left[ a+\frac{1}{2}\right] = [a]+1\] であり, \[ 2[a]+1 \leqq 2a < 2[a]+2\] より \[ [2a] = 2[a]+1\] だから, \[ [a]+\left[ a+\dfrac{1}{2}\right] = 2[a]+1 = [2a].\]
(i), (ii) より, $[a]+\left[ a+\dfrac{1}{2}\right] = [2a].$

問題≪ガウス記号と分数型方程式≫

 各実数 $a$ に対して, $a$ を超えない最大の整数を $[a]$ で表す. $x,$ $y$ を実数, $m,$ $n$ を自然数, $k$ を整数とし, \[\frac{1}{x}+\frac{1}{y} = 1, \quad [mx] = [ny] = k\] が成り立つとする. 次のことを示せ:
(1)
$\dfrac{[mx]}{x} \leqq m < \dfrac{[mx]+1}{x}.$ 
(2)
$m+n = k.$ 
(3)
$x,$ $y$ は有理数.

解答例

(1)
$[a] \leqq a < [a]+1$ に $a = mx$ を代入すると, $[mx] = k$ より, \[ k \leqq mx < k+1\] となるから, \[\frac{k}{x} \leqq m < \frac{k+1}{x} \quad \cdots [1].\]
(2)
(1) と同様にして, \[\frac{k}{y} \leqq n < \frac{k+1}{y} \quad \cdots [2].\] $[1],$ $[2]$ の辺々を加えると, \[ k\left(\frac{1}{x}+\frac{1}{y}\right) \leqq m+n < (k+1)\left(\frac{1}{x}+\frac{1}{y}\right) \quad \cdots [3].\] よって, $\dfrac{1}{x}+\dfrac{1}{y} = 1$ より, \[ k \leqq m+n < k+1 \quad \cdots [4].\] $m,$ $n,$ $k$ は整数だから, $m+n = k.$
(3)
$[4]$ すなわち $[3]$ で等号が成り立ち, $[3]$ で等号が成り立つのは $[1],$ $[2]$ で等号が成り立つときに限るから, \begin{align*} \frac{k}{x} &= m, & \frac{k}{y} &= n. \\ \therefore x &= \frac{k}{m}, & y &= \frac{k}{n}. \end{align*} ゆえに, $x,$ $y$ は有理数である.

解説・方針

  • 次のレイリーの定理(Reyleigh's theorem)の部分的結果を示す応用問題: 与えられた正の数 $x,$ $y$ について, すべての整数が $[mx],$ $[ny]$ ($m,$ $n$: 整数)の形に重複なく表されるためには, $\dfrac{1}{x}+\dfrac{1}{y} = 1$ が成り立ち, $x,$ $y$ が無理数であることが必要十分である.
  • $[a] \leqq a < [a]+1$ の等号成立条件に着目する.

鳩の巣原理

問題≪格子点を結ぶ線分の中点≫

 座標平面上において, 与えられた $5$ 個の格子点を結ぶ $10$ 本の線分のうち, 中点が格子点であるような線分が存在することを示せ. ただし, 各座標が整数であるような点を格子点(lattice point)と呼ぶ.

解答例

 すべての格子点は, 各座標の偶奇によって, 次の $4$ つのタイプに分けられる.
(偶, 偶), (偶, 奇), (奇, 偶), (偶, 偶)
$5$ 個の格子点のうち少なくとも $2$ 点は同じタイプになるから, その $2$ 点を結ぶ線分の中点は格子点である.

問題≪鳩の巣原理の倍数問題への応用≫

 $n$ を正整数とする. $n$ の倍数でない $n+1$ 個の相異なる整数の中には, 必ず和または差が $2n$ の倍数となるような $2$ つの整数が存在することを示せ.

解答例

 $n+1$ 個の相異なる整数に, 符号を入れ替えた整数を付け加えると, $2n+2$ 個の相異なる整数ができる.
これらを $2n$ で割ると, 余りの等しい $2$ 数 $a,$ $b$ が存在するので, それらの差 $a-b$ は $2n$ の倍数になる.
この差 $a-b$ が与えられた数の和または差とならない場合として $a = -b$ の場合が考えられるが, それは $a$ は $n$ の倍数でないという仮定から起こらない.
実際, 整数 $m$ について, $n$ で割った商を $q,$ 余りを $r$ とおくと, \[ m-(-m) = 2m = 2nq+2r, \quad 0 \leqq 2r < 2n\] となるから, $m-(-m)$ が $2n$ の倍数となるのは $2r = 0$ すなわち $r = 0$ つまり $m$ が $n$ の倍数となるときに限るからである.
ゆえに, 題意が示された.

問題≪互いに素な整数のペアの存在≫

(1)
連続する整数 $a,$ $a+1$ は互いに素であることを示せ.
(2)
$n$ を正整数とする. $1$ 以上 $2n$ 以下の $n+1$ 個の整数の中には, 互いに素な $2$ つの整数が存在することを示せ.

解答例

(1)
$1$ より大きい $a$ の任意の約数 $d$ に対して, $a+1$ を $d$ で割った余りは $1$ となるから, $a+1$ は $d$ で割り切れない.
よって, $a,$ $a+1$ は互いに素である.
(2)
$1$ 以上 $2n$ 以下の整数の集合を $\{ 1,\ 2\},$ $\cdots,$ $\{ 2n-1,\ 2n\}$ と $n$ 個の集合に分割する.
与えられた $n+1$ 個の整数のうち, 少なくとも $2$ つは同じ集合に属するから, (1) よりそれらの整数は互いに素である.
ゆえに, 題意が示された.