Maths Olympiad Prep

Library / AustriaMO /28 of 33

AustriaMO

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:=⌊na⌋k := \lfloor \frac{n}{a} \rfloor and l:=⌊n+ba⌋l := \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 k≤na<k+1 and l−1<n+ba≤l. 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
ka≤n<(k+1)a and (b+k−1)a<n+b≤a(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
ka≤n≤(k+1)a−1 and (b+k−1)a+1−b≤n≤a(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+k−1)a+1−b=ka+(a−1)(b−1)≥ka (b+k-1)a+1-b = ka+(a-1)(b-1) \ge ka
and
a(b+k)−b=(k+1)a−1+(a−1)(b−1)≥(k+1)a−1, 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+k−1)a+1−b≤n≤(k+1)a−1(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+k−1)a+1−b≤(k+1)a−1(b+k-1)a+1-b \le (k+1)a-1, that is 0≥ab−2a+2−b=(a−1)(b−2)0 \ge ab-2a+2-b = (a-1)(b-2). Thus it suffices to consider the following cases:

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

* If b=1b=1, (1) means ka≤n≤(k+1)a−1ka \le n \le (k+1)a-1 and this is always satisfied for k=⌊na⌋k = \lfloor \frac{n}{a} \rfloor. Hence all natural numbers n≥0n \ge 0 are solutions.

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

* For a≥2a \ge 2 and b≥3b \ge 3 there is no solution.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.