第3問

整数

n>3

をとる。集合

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

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

n/2

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

p\le \sqrt{n}

を満たす素数

p

について、最小の数が

p

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

p-1

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

ステップ 3/7: 2つの列を比較する

(y+z)x-(y+zx)=(x-1)y>0,\qquad (x+z)y-(x+yz)=(y-1)x>0

詳しい解説

第1の不等式により $(y+z)x$ は $y+zx$ より大きく、第2により $(x+z)y$ は $x+yz$ より大きい。したがって未決定なのは $x+yz$ と $(y+z)x$ の比較だけで、他の値はすべて厳密に順序づけられる。