第3問

整数

n>3

をとる。集合

\{1,2,\ldots,n\}

から3個の数を選び、それぞれを1回ずつ使って、加法・乗法・括弧による可能なすべての式を作る。(a) 選んだ3数がすべて

n/2

より大きいなら、得られる値はすべて異なることを示せ。(b)

p\le \sqrt{n}

を満たす素数

p

について、最小の数が

p

で、式の値がすべて異なるわけではない選び方の数が、

p-1

の正の約数の個数に等しいことを示せ。

ステップ 5/7: (a)で等式を排除する

n/2<x<y<z\Longrightarrow (y-x)(z-x)<(n/2-1)(n/2)<x(x-1)

詳しい解説

3数がすべて $n/2$ より大きければ、 $z-x<n/2$ であり、整数 $y-x<z-x$ から $y-x<n/2-1$ となる。よって $(y-x)(z-x)<(n/2-1)(n/2)<x(x-1)$ で、前段の条件は成立しない。したがって値はすべて異なる。