Maths Olympiad Prep

Library / /14 of 16

Algebra Difficulty 6.5 National olympiad Prove it Austria

By x\lfloor x \rfloor we denote the largest integer that is smaller or equal to xx and by x\lceil x \rceil we denote the smallest integer that is greater or equal to xx.

For every given pair (a,b)(a, b) of positive natural numbers find all natural numbers nn with
b+na=n+ba. b + \lfloor \frac{n}{a} \rfloor = \lfloor \frac{n+b}{a} \rfloor.

Solution

We set k:=nak := \lfloor \frac{n}{a} \rfloor and l:=n+bal := \lfloor \frac{n+b}{a} \rfloor. We thus have to find all nonnegative integers nn such that there exist integers kk and ll satisfying
b+k=l and kna<k+1 and l1<n+bal. b+k=l \text{ and } k \le \frac{n}{a} < k+1 \text{ and } l-1 < \frac{n+b}{a} \le l.
By substituting l=b+kl = b+k we get the equivalent inequalities
kan<(k+1)a and (b+k1)a<n+ba(b+k). ka \le n < (k+1)a \text{ and } (b+k-1)a < n+b \le a(b+k).
Since all variables are integers we also have the equivalent relations
kan(k+1)a1 and (b+k1)a+1bna(b+k)b. ka \le n \le (k+1)a-1 \text{ and } (b+k-1)a+1-b \le n \le a(b+k)-b.
Taking into account
(b+k1)a+1b=ka+(a1)(b1)ka (b+k-1)a+1-b = ka+(a-1)(b-1) \ge ka
and
a(b+k)b=(k+1)a1+(a1)(b1)(k+1)a1, a(b+k)-b = (k+1)a-1+(a-1)(b-1) \ge (k+1)a-1,
we see that the desired values of nn are exactly those satisfying
(b+k1)a+1bn(k+1)a1(1) (b+k-1)a+1-b \le n \le (k+1)a-1 \quad (1)
for some kk. From (1) we conclude that for some kk we must have (b+k1)a+1b(k+1)a1(b+k-1)a+1-b \le (k+1)a-1, that is 0ab2a+2b=(a1)(b2)0 \ge ab-2a+2-b = (a-1)(b-2). Thus it suffices to consider the following cases:

* If a=1a=1, (1) means knkk \le n \le k and therefore all natural numbers n0n \ge 0 are solutions.

* If b=1b=1, (1) means kan(k+1)a1ka \le n \le (k+1)a-1 and this is always satisfied for k=nak = \lfloor \frac{n}{a} \rfloor. Hence all natural numbers n0n \ge 0 are solutions.

* If b=2b=2, (1) means (k+1)a1n(k+1)a1(k+1)a-1 \le n \le (k+1)a-1 and therefore necessarily n=(k+1)a1n = (k+1)a-1. Such a kk can be found if and only if n1(moda)n \equiv -1 \pmod a, which are all the solutions in this case. (Note that for a=1a=1 all integers n0n \ge 0 are solutions in accordance with the above.)

* For a2a \ge 2 and b3b \ge 3 there is no 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.