第3問

整数

n>3

をとる。集合

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

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

n/2

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

p\le \sqrt{n}

を満たす素数

p

について、最小の数が

p

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

p-1

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

ステップ 1/7: 選んだ数に名前を付け、組合せを列挙する

1<x<y<z,\qquad x+y+z,\ x+yz,\ xy+z,\ y+zx,\ (x+y)z,\ (z+x)y,\ (y+z)x,\ xyz

詳しい解説

両方の場合で選んだ数の最小値は少なくとも $2$ である。(a) では $n/2>1$ 、(b) では $p$ が素数だからである。3数を $1<x<y<z$ と書く。可換性を同一視すれば、可能な値は上に示した8つの式である。