Problem 3

Let

n>3

be an integer. Choose three numbers from

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

. Using each once, together with addition, multiplication, and parentheses, form all possible combinations. (a) Show that if all three chosen numbers are greater than

n/2

, their values are all distinct. (b) Let

p

be a prime with

p\le \sqrt{n}

. Show that the number of choices whose smallest number is

p

and whose combination values are not all distinct is exactly the number of positive divisors of

p-1

Step 5 of 7: Rule out equality in part (a)

Previous step Next step

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

Detailed analysis

If all three numbers exceed $n/2$ , then $z-x<n/2$ and, since $y-x<z-x$ are integers, $y-x<n/2-1$ . Hence $(y-x)(z-x)<(n/2-1)(n/2)<x(x-1)$ , so the criterion in the previous step cannot hold. Thus all values are distinct.