Understand the problem

Azambuja writes a rational number $q$ on a blackboard. One operation is to delete $q$ and replace it by $q+1$; or by $q-1$; or by $\frac{q-1}{2q-1}$ if $q \neq \frac{1}{2}$. The final goal of Azambuja is to write the number $\frac{1}{2018}$ after performing a finite number of operations. Show that if the initial number written is $0$, then Azambuja cannot reach his goal.

Source of the problem
Brazilian national mathematical olympiad 2018
Topic
Invariance
Difficulty Level
Easy
Suggested Book
Problem Solving Strategies by Arthur Engel

Start with hints

Do you really need a hint? Just try it yourself!

It is always a good idea to try using the invariance principle in such problems.
Make a change of variables to see patterns.
Note that the operation is restricted to rational numbers. Hence, writing q=\frac{r}{s}=(r,s) could help.
Let us denote by q_n the number on the board at the nth step. We shall use the new variable a_n=2q_n-1 (just to simplify the denominator). Clearly, a_{n+1} is either a_n\pm 2 or -\frac{1}{a_n}. Writing a_n=(r_n,s_n), this means that (r_{n+1},s_{n+1}) is either (r_n \pm 2s_n,s_n) or (-s_n,r_n). Thus, we need to find out if (-1008,1009) is reachable starting from (-1,1). However, (odd, odd) pairs can produce only other (odd,odd) pairs under this operation, and (-1008,1009) is an (even, even) pair. Hence \frac{1}{2018} cannot be reached starting from 0.

Watch the video (Coming Soon)

Connected Program at Cheenta

Math Olympiad Program

Math Olympiad is the greatest and most challenging academic contest for school students. Brilliant school students from over 100 countries participate in it every year. Cheenta works with small groups of gifted students through an intense training program. It is a deeply personalized journey toward intellectual prowess and technical sophistication.

Similar Problems

Ratio with the sum of digits

Understand the problemFind the 3-digit number whose ratio with the sum of its digits is minimal.Albania TST 2013 Number Theory, Inequalities. Easy Problem Solving Strategies by Arthur Engel Start with hintsDo you really need a hint? Try it first!Suppose that the...

Does there exist a Magic Rectangle?

Magic Squares are infamous; so famous that even the number of letters on its Wikipedia Page is more than that of Mathematics itself. People hardly talk about Magic Rectangles. Ya, Magic Rectangles! Have you heard of it? No, right? Not me either! So, I set off to...

Coincident Nine-point Circles

Understand the problemLet be a triangle, its circumcenter, its centroid, and its orthocenter. Denote by , and the centers of the circles circumscribed about the triangles , and , respectively. Prove that the triangle is congruent to the triangle and that the...

An inequality with unit coefficients

Understand the problemLet be positive real numbers. Show that there exist such that:Iberoamerican olympiad 2011InequalitiesEasyInequalities: An Approach Through Problems by B.J. VenkatachalaStart with hintsDo you really need a hint? Try it first!Try using...

An integer with perfect square digits

Understand the problemFind all positive integers that have 4 digits, all of them perfect squares, and such that is divisible by 2, 3, 5 and 7. Centroamerican olympiad 2016 Number theory Easy An Excursion in Mathematics Start with hintsDo you really need a hint? Try...

Euler’s theorem and an inequality

Understand the problemLet be the circumcenter and be the centroid of a triangle . If and are the circumcenter and incenter of the triangle, respectively,prove thatBalkan MO 1996 Geometry Easy Let $latex I$ be the incentre. Euler's theorem says that $latex...

A trigonometric relation and its implication

Understand the problemProve that a triangle is right-angled if and only ifVietnam National Mathematical Olympiad 1981TrigonometryMediumChallenge and Thrill of Pre-college MathematicsStart with hintsDo you really need a hint? Try it first!Familiarity with the...

A polynomial equation and roots of unity

Understand the problemFind all polynomials with real coefficients such that divides .Indian National Mathematical Olympiad 2018AlgebraEasyProblem Solving Strategies by Arthur EngelStart with hintsDo you really need a hint? Try it first!Show that, given a zero of...

Bicentric quadrilaterals inside a triangle

Understand the problemLet be a triangle and be cevians concurrent at a point . Suppose each of the quadrilaterals and has both circumcircle and incircle. Prove that is equilateral and coincides with the center of the triangle.Indian team selection test...

Trilinear coordinates and locus

Understand the problemLet be an equilateral triangle and in its interior. The distances from to the triangle's sides are denoted by respectively, where . Find the locus of the points for which can be the sides of a non-degenerate triangle.Romanian Master in...