Maths Olympiad Prep

Library / /13 of 24

Algebra Difficulty 8.5 Shortlist Prove it Romania

Determine the sets SS of positive integers satisfying the following two conditions:

a) For any positive integers a,b,ca, b, c, if ab+bc+caab + bc + ca is in SS, then so are a+b+ca + b + c and abcabc;

b) The set SS contains an integer N160N \ge 160 such that N2N - 2 is not divisible by 4.

Solution

We will prove that SS is the set of all positive integers. The argument hinges on the three facts below:

(1) The set SS contains an integer M40M \ge 40 divisible by 4.

(2) If 4k4k belongs to SS for some integer k2k \ge 2, then so does 4m4m for all positive integers m<km < k.

(3) The set SS contains 4k4k for all integers k10k \ge 10.

Assume the three for the moment and argue as follows: By (1) and (2), SS contains all positive multiples of 4 at most 40, and by (3) it contains all multiples of 4 at least 40, so SS contains all positive multiples of 4.

Let a=3a = 3 and let b=c=1b = c = 1. As 7 is in SS, so is 3, by (a). Repeat the argument for a=b=c=1a = b = c = 1 to deduce that SS contains 1.

Finally, let a=2a = 2 and let again b=c=1b = c = 1. As 5 lies in SS, so does 2. Combining with the previous paragraphs, it follows that SS exhausts all positive integers, as stated.

Proof of (1):

If NN is divisible by 4, choose M=NM = N. If N=4k+1N = 4k + 1, set a=2ka = 2k and b=c=1b = c = 1 in (a) to deduce that 2k2k and 2k+22k + 2 are both in SS. As N160N \ge 160, the numbers 2k2k and 2k+22k + 2 are both at least 80>4080 > 40. Note that exactly one of 2k2k and 2k+22k + 2 is divisible by 4 and let MM be that number.

Proof of (2):

Let b=c=2b = c = 2. By (a), if 4a+44a + 4 is in SS, then so is 4a4a. Beginning with MM provided by (1), statement (2) now follows by backward recursion.

Proof of (3):

We first prove that SS contains an integer P40P \ge 40 divisible by 4. By (1), SS contains an integer M40M \ge 40 divisible by 4. If MM is divisible by 8, let P=MP = M. Otherwise, M44M \ge 44 and M4M - 4 is divisible by 8. By (2), M4M - 4 is in SS, so P=M4P = M - 4 fits the bill.

Let b=c=4b = c = 4. By (a), if 8a+168a + 16 is in SS, then so is 16a16a. Note that 16a>8a+1616a > 8a + 16 for a3a \ge 3. Thus, if SS contains an integer k40k \ge 40 divisible by 8, then it also contains an integer k>kk' > k divisible by 8. Hence, starting with PP, we can generate arbitrarily large multiples of 8 lying in SS. Reference to (2) concludes the proof and completes the solution.

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.