§C5.3極端原理

二数を選ぶので、$S$は二つ以上の要素をもつ。$S$の要素を小さい順に$s_1<s_2<\cdots<s_k$と並べる。二数$s_i<s_j$の差$s_j-s_i$が、$S$の相異なる二数の差のうちで最小であるとする。

$j\ge i+2$と仮定する。このとき$s_i<s_{i+1}<s_j$であるから、

であり、二数$s_i,s_{i+1}$の差は$s_j-s_i$より小さい。これは$s_j-s_i$の最小性に反する。したがって$j=i+1$であり、差が最小となる二数は小さい順に並べたときに隣り合う。▨

グラフを$G=(V,E)$とし、平均次数を$\bar d=\dfrac{1}{|V|}\displaystyle\sum_{v\in V}\deg(v)$とする。$V$は空でない有限集合であるから、次数が最大となる頂点$u$と、次数が最小となる頂点$w$が存在する。

すべての頂点$v$について$\deg(v)\le\deg(u)$であるから、

である。よって$u$は次数が平均次数以上の頂点である。同様に、すべての頂点$v$について$\deg(w)\le\deg(v)$であるから$|V|\deg(w)\le\displaystyle\sum_{v\in V}\deg(v)$、すなわち$\deg(w)\le\bar d$であり、$w$は次数が平均次数以下の頂点である。▨

主張の反例が存在すると仮定し、反例全体の集合を$C$とする。$C$は自然数の空でない部分集合であるから、最小元$n$をもつ。$1=2^0$であるから$n\ne1$、すなわち$n\ge2$である。

$2^k\le n$を満たす非負整数$k$は、$k=0$を含み、$2^k\le n<2^n$から$k<n$を満たすので有限個である。その最大のものを$k$とする。$k$の最大性により$n<2^{k+1}$である。$n=2^k$なら$n$は一つの$2$の非負整数乗の和として表されるので、反例ではない。したがって$n>2^k$であり、$m=n-2^k$と置くと$1\le m<n$である。

$n$の最小性により$m$は反例ではないので、$m$は相異なる$2$の非負整数乗の和に表される。また$m=n-2^k<2^{k+1}-2^k=2^k$であるから、$m$の表示に現れる各項は$m$以下であり、$2^k$より小さい。したがって、$m$の表示に$2^k$を加えた和は、相異なる$2$の非負整数乗の和であり、その値は$n$である。これは$n\in C$に反する。ゆえに反例は存在しない。

ここで用いた$n<2^n$は、$n=1$で$1<2$が成り立ち、$n<2^n$から$n+1\le2^n<2^n+2^n=2^{n+1}$が従うので、数学的帰納法によりすべての正の整数$n$について成り立つ。▨

$n$を$0$以上の整数とする。最大値は$n+1$である。

奇数全体の集合$\{1,3,\ldots,2n+1\}$は連続する二整数を含まず、要素数は$n+1$である。したがって最大値は$n+1$以上である。

連続する二整数を同時に含まない空でない部分集合を$A=\{a_1<a_2<\cdots<a_k\}$とする。各$i<k$について、$a_{i+1}$は$a_i$より大きい整数であり、$a_i+1$ではないので、$a_{i+1}\ge a_i+2$である。$i$についての数学的帰納法により$a_i\ge2i-1$を示す。$a_1\ge1$であり、$a_i\ge2i-1$ならば$a_{i+1}\ge a_i+2\ge2i+1=2(i+1)-1$である。とくに$2k-1\le a_k\le2n+1$であるから、$k\le n+1$である。空集合の要素数$0$も$n+1$以下である。

よって、条件を満たすすべての部分集合の要素数は$n+1$以下であり、先の構成と合わせて最大値は$n+1$である。▨