Maths Olympiad Prep

Library / /74 of 101

Algebra Difficulty 6.8 National olympiad Prove it Estonia

The number 2\sqrt{2} is on the computer screen. In one step, Juku can multiply the number currently on the screen by any positive rational number or add any natural number to it. Is there a positive integer nn such that every number that Juku can get after a finite number of steps can be obtained by at most nn steps? If so, find the least suitable nn.

Solution

Any number that can be obtained after a finite number of steps is of the form r2+sr\sqrt{2} + s, where rr is positive and ss is a nonnegative rational number. Indeed, the initial number 2\sqrt{2} is of the form 12+01\sqrt{2} + 0, and if we multiply a number of the form r2+sr\sqrt{2} + s by a positive rational number tt or add a natural number kk to it, the result is rt2+strt\sqrt{2} + st or r2+(s+k)r\sqrt{2} + (s + k) correspondingly, which is of the same form.

Show that any number of the form r2+sr\sqrt{2} + s, where rr is positive and ss is a nonnegative rational number, can be obtained by at most 3 steps. If s>0s > 0 then multiply 2\sqrt{2} by a positive rational number rs\frac{r}{s}, add 1 to the result, and then multiply the result by the positive rational number ss. If s=0s = 0 then it is enough to multiply 2\sqrt{2} by the positive rational number rr.

Finally, we show that 2 steps are not always enough. First, make sure that in the representation r2+sr\sqrt{2} + s of a number, rr and ss are uniquely determined. Indeed, if r2+s=r2+sr\sqrt{2} + s = r'\sqrt{2} + s' then (rr)2=ss(r - r')\sqrt{2} = s' - s. If rr0r - r' \ne 0 then 2=ssrr\sqrt{2} = \frac{s' - s}{r - r'}, which is not possible, because ssrr\frac{s' - s}{r - r'} is a rational number, but 2\sqrt{2} is an irrational number. Hence rr=0r - r' = 0 or r=rr' = r; from (rr)2=ss(r - r')\sqrt{2} = s' - s also s=ss' = s.

Consider the number r2+sr\sqrt{2} + s where r=1r = 1 and ss is an arbitrary fractional number. We cannot get this number by multiplications only, because then ss remains zero, or with additions only, because then ss would be an integer. If we multiply by a rational number tt and add a natural number kk in either order then the result is either t2+kt\sqrt{2} + k or t(2+k)t(\sqrt{2} + k). In both cases we must have t=r=1t = r = 1. But multiplication by 1 does not change the result, and we already saw that by addition only it is not possible to get the result.

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.