Maths Olympiad Prep

Library / /41 of 48

Number theory Difficulty 7.8 National olympiad, round 2 Prove it Asia Pacific Mathematics Olympiad (APMO)

Let nn be an integer such that n>3n>3. Suppose that we choose three numbers from the set {1,2,,n}\{1,2, \ldots, n\}. Using each of these three numbers only once and using addition, multiplication, and parenthesis, let us form all possible combinations.

a. Show that if we choose all three numbers greater than n/2n / 2, then the values of these combinations are all distinct.

b. Let pp be a prime number such that pnp \leq \sqrt{n}. Show that the number of ways of choosing three numbers so that the smallest one is pp and the values of the combinations are not all distinct is precisely the number of positive divisors of p1p-1.

Solution

In both items, the smallest chosen number is at least 22: in part (a), n/2>1n / 2 > 1 and in part (b), pp is a prime. So let 1<x<y<z1 < x < y < z be the chosen numbers. Then all possible combinations are
x+y+z,x+yz,xy+z,y+zx,(x+y)z,(z+x)y,(x+y)z,xyz. x + y + z, \quad x + y z, \quad x y + z, \quad y + z x, \quad (x + y) z, \quad (z + x) y, \quad (x + y) z, \quad x y z.

Since, for 1<m<n1 < m < n and t>1t > 1, (m1)(n1)12mn>m+n(m-1)(n-1) \geq 1 \cdot 2 \Longrightarrow m n > m + n, tn+m(tm+n)=(t1)(nm)>0tn+m>tm+nt n + m - (t m + n) = (t-1)(n-m) > 0 \Longrightarrow t n + m > t m + n, and (t+m)n(t+n)m=t(nm)>0(t + m) n - (t + n) m = t(n-m) > 0,
x+y+z<z+xy<y+zx<x+yz x + y + z < z + x y < y + z x < x + y z

and
(y+z)x<(x+z)y<(x+y)z<xyz. (y + z) x < (x + z) y < (x + y) z < x y z.

Also, (y+z)x(y+zx)=(x1)y>0(y+z)x>y+zx(y + z) x - (y + z x) = (x - 1) y > 0 \Longrightarrow (y + z) x > y + z x and (x+z)y(x+yz)=(y1)x>0(x+z)y>x+yz(x + z) y - (x + y z) = (y - 1) x > 0 \Longrightarrow (x + z) y > x + y z. Therefore the only numbers that can be equal are x+yzx + y z and (y+z)x(y + z) x. In this case,
x+yz=(y+z)x(yx)(zx)=x(x1). x + y z = (y + z) x \Longleftrightarrow (y - x)(z - x) = x(x - 1).

Now we can solve the items.

a. If n/2<x<y<zn / 2 < x < y < z then zx<n/2z - x < n / 2, and since yx<zxy - x < z - x, yx<n/21y - x < n / 2 - 1; then
(yx)(zx)<n2(n21)<x(x1), (y - x)(z - x) < \frac{n}{2} \left( \frac{n}{2} - 1 \right) < x(x - 1),

and therefore x+yz<(y+z)xx + y z < (y + z) x.

b. If x=px = p, then (yp)(zp)=p(p1)(y - p)(z - p) = p(p - 1). Since yp<zpy - p < z - p, (yp)2<(yp)(zp)=p(p1)yp<p(y - p)^2 < (y - p)(z - p) = p(p - 1) \Longrightarrow y - p < p, that is, pp does not divide ypy - p. Then ypy - p is a divisor dd of p1p - 1 and zp=p(p1)dz - p = \frac{p(p - 1)}{d}. Therefore,
x=p,y=p+d,z=p+p(p1)d, x = p, \quad y = p + d, \quad z = p + \frac{p(p - 1)}{d},
which is a solution for every divisor dd of p1p - 1 because
x=p<y=p+d<2pp+pp1d=z. x = p < y = p + d < 2p \leq p + p \cdot \frac{p - 1}{d} = z.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.