Maths Olympiad Prep

Library / /36 of 44

Algebra Difficulty 6.5 National Olympiad Prove it Slovenia

For a real number xx let [x][x] denote the greatest integer not greater than xx.

a. Prove that for all positive integers aa, bb and cc we have
cabcab. \left\lfloor \frac{\left\lfloor \frac{c}{a} \right\rfloor}{b} \right\rfloor \le \left\lfloor \frac{c}{ab} \right\rfloor.

b. Find an example showing that the above equality does not hold for all positive real numbers aa, bb and cc.

Solution

a. The number cc can be written in the form c=kab+rc = kab + r, where kk is a non-negative integer and r<abr < ab is the remainder of cc when divided by abab. The number rr can be further written as r=ma+nr = ma + n, where mm is a non-negative integer and n<an < a is the remainder of rr when divided by aa. From this it follows that m<bm < b, or we would have rabr \ge ab. We see that
[cab]=[k+rab]=k, \left[ \frac{c}{ab} \right] = \left[ k + \frac{r}{ab} \right] = k,
because 0rab<10 \le \frac{r}{ab} < 1, and
[[ca]b]=[[kb+m+na]b]=[kb+mb]=[k+mb]=k, \left[ \frac{\left[ \frac{c}{a} \right]}{b} \right] = \left[ \frac{\left[ kb + m + \frac{n}{a} \right]}{b} \right] = \left[ \frac{kb + m}{b} \right] = \left[ k + \frac{m}{b} \right] = k,
because 0na<10 \le \frac{n}{a} < 1 and 0mb<10 \le \frac{m}{b} < 1. From here we obtain the desired result.

b. Let a=2a = 2, b=12b = \frac{1}{2} and c=1c = 1. Then [cab]=1\left[ \frac{c}{ab} \right] = 1 and [[ca]b]=0\left[ \frac{[\frac{c}{a}]}{b} \right] = 0.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.