Said nicer way:

Thank you. I stumbled upon that logic towards the end of my casework, but by then it was already too late

I had basically the same solution as t0rajir0u, which incidentally is similar to the official solution. I'd be impressed with a solution with zero casework.

jb05 wrote: Said nicer way:

That's what I did, but I don't think you can WLOG $ |a_1|>|a_2|$ and $ r_1<r_2$. You don't need the latter, though.

Does that actually work?

Phelpedo wrote: jb05 wrote: Said nicer way:

That's what I did, but I don't think you can WLOG $ |a_1| > |a_2|$ and $ r_1 < r_2$. You don't need the latter, though. Well if $ a_2<\frac{-a_3}{2}$, the exact same argument works (and I said that in my solution). Whatever the case, this solution has essentially no casework, in response to MellowMelon. Granted, $ a_3=0$ is a special case, but that is fairly trivial.

Hm, I inducted on $ |a_1| + |a_2| + |a_3|$. I used about three cases, but two of my arguments were identical, I think.

Xantos C. Guin wrote: I said that since $ a_1r_1 + a_2r_2 + a_3r_3 = 0$, then there must exist some positive real constant $ K$ such that $ Kr_1, Kr_2, Kr_3$ are positive integers and that $ gcd(Kr_1, Kr_2, Kr_3) = 1$. Unfortunately, this isn't true. Take $ r_1 = \sqrt{2}$, $ r_2 = 1$, $ r_3 = 1 + \sqrt{2}$; we can have $ a_1 = a_2 = -a_3 = 1$. There's no way you can find two integers whose ratio is $ r_1/r_2 = \sqrt{2}$.

I have yet to see a working solution that uses rationality/irrationality of the 3 real numbers. It seems like people assume there's more restrictions on $ r_1, r_2, r_3$ than there actually are when using these arguments. Not saying there isn't a correct one, though, but I imagine it would be largely similar to the $ |a_1| + |a_2| + |a_3|$ induction arguments in other solution.

I seriously doubt that there is such a solution. If we use the axiom of choice, we can use the fact that the reals have a basis with respect to the rationals, so you can say \begin{align*} r_1 &= (x_0, x_1, \dotsc) \\ r_2 &= (y_0, y_1, \dotsc) \\ r_3 &= (z_0, z_1, \dotsc) , \end{align*} where all coordinates are rational, and you know that \[ a_1 x_n + a_2 y_n + a_3 z_n = 0 \] for all integers $ n$. I don't know, maybe you can use the Euclidean algorithm then, but it looks really hairy, and I can't imagine producing a valid solution along these lines without Axiom of Choice. I simply don't see how you can get useful information out of the rationality or irrationality of the $ r_i$. After all, what properties do irrationals have which rationals don't and would help in solving the problem?

Is there a solution using Linear Algebra? This resembles Gaussian Elimination, I think. I don't know very much Linear Algebra, so don't take my word for it.

I wrote a (I think) half-valid solution which involved showing that the operation can be used to obtain any linear combination of r_1, r_2, r_3 as long as the value of that linear combination is nonnegative (by proving the contrapositive statement). Is this acceptable?

One of my initial ideas was to assume there was at least one irrational (else Euclidean Algorithm and it's trivial) and then scale the numbers so one was an integer. Then since the $ a_1, a_2, a_3$ exist, you can let $ x$ be an irrational such that $ r_1 = m_1, r_2 = k_2x + m_2, r_3 = k_3x + m_3$ for integers $ m_1, m_2, m_3, k_2, k_3$. I tried working with reducing $ r_2$ and $ r_3$ to get rid of the irrational from one, but the condition that they all have to stay nonnegative kept me from any general argument. I wouldn't say it's impossible this solution could be completed, but I do doubt it.

Benjamin Hu wrote: I wrote a (I think) half-valid solution which involved showing that the operation can be used to obtain any linear combination of r_1, r_2, r_3 as long as the value of that linear combination is nonnegative (by proving the contrapositive statement). Is this acceptable? Well, if I understand you're saying, I don't think your claim is true, because the sum of the numbers on the board decreases with every move you make.

MellowMelon wrote: One of my initial ideas was to assume there was at least one irrational (else Euclidean Algorithm and it's trivial) and then scale the numbers so one was an integer. Then since the $ a_1, a_2, a_3$ exist, you can let $ x$ be an irrational such that $ r_1 = m_1, r_2 = k_2x + m_2, r_3 = k_3x + m_3$ for integers $ m_1, m_2, m_3, k_2, k_3$. I tried working with reducing $ r_2$ and $ r_3$ to get rid of the irrational from one, but the condition that they all have to stay nonnegative kept me from any general argument. I wouldn't say it's impossible this solution could be completed, but I do doubt it. i think this was close to what i wrote for #5 i said something like have $ r_1$ be rational, have $ r_2,r_3$ be irrational since a linear combination of $ r_2,r_3$ is rational $ r_3$ can be written in the form $ k_1r_2+k_2$ where $ k_1,k_2$ are rational then you can apply some similar logic that you use to prove the thing for 2 rationals, so that after a finite # of operations on $ r_2,r_3$ so that in either the second or the third number the coefficient of $ r_2$ becomes 0, and you get left with a rational number $ k$, in which case you have $ r_1,k$ both rational, so now the result follows by euclid thing before i kinda doubt that this works, but i dont know, hope it gets me a couple points

I used a monovariant on $ |a_1|+|a_2|+|a_3|$. You can make it decrease all the time unless one of the numbers $ r_1, r_2, r_3$ is $ 0$.

Well, I just said that the three numbers lie in some two dimensional vector space over $ \mathbb{Q}$, which means that a nontrivial linear dependence has to exist.

101101101 wrote: I just realized that I failed to even state that the $ a_i$ never became identically 0. Its pretty obvious, but it is still an important observation. Did anyone else miss this? I'm hoping its not more than 1 point off. I said that the transformation was invertible, so if the $ a_i$ ever became identically zero it would imply that the original set of $ a_i$ was identically zero, which violates the problem condition. Hamster1800 wrote: Well, I just said that the three numbers lie in some two dimensional vector space over $ \mathbb{Q}$, which means that a nontrivial linear dependence has to exist. All you're given is that the vector space has dimension at most two.

t0rajir0u wrote: Hamster1800 wrote: Well, I just said that the three numbers lie in some two dimensional vector space over $ \mathbb{Q}$, which means that a nontrivial linear dependence has to exist. All you're given is that the vector space has dimension at most two. A one (or zero) dimensional vector space over $ \mathbb{Q}$ is certainly contained in some two dimensional vector space over $ \mathbb{Q}$ Of course, in either of the smaller cases the problem was trivial, so I was assuming it was exactly two dimensional.

Sorry for the revive, but where does the condition a_1r_1+a_2r_2+a_3r_3=0 come into play? I thought showing that the sum of the squares is bounded and monotonically decreasing is enough to show that one of the numbers is eventually 0.

The sum-of-squares monovariant is applied to the $a_i$ themselves, not to the $r_i$. If you don't have that condition, you don't even have any $a_i$ sequence to work with.

Darn, should've used squares. We first show we can decrease the quantity $\left\lvert a_1 \right\rvert + \left\lvert a_2 \right\rvert + \left\lvert a_3 \right\rvert$ as long as $0 \notin \left\{ a_1,a_2,a_3 \right\}$. Assume $a_1 > 0$ and $r_1 > r_2 > r_3$ without loss of generality and consider two cases. (i) $r_2 > 0$ or $r_3 > 0$; these cases are identical. If $r_2 > 0$ then $r_3 < 0$ and get \[ 0 = a_1r_1 + a_2r_2 + a_3r_3 > a_1r_3 + a_3r_3 \implies a_1 + a_3 < 0 \] so $\left\lvert a_1 + a_3 \right\rvert < \left\lvert a_3 \right\rvert$, and hence we perform $(r_1,r_2,r_3) \mapsto (r_1-r_3,r_2,r_3)$. (ii) Both $r_2$ and $r_3$ are less than zero. Assume for contradiction that $\left\lvert a_1+a_2 \right\rvert \ge -a_2$ and $\left\lvert a_1+a_3 \right\rvert \ge -a_3$ both hold (if either fails then we use $(r_1,r_2,r_3) \mapsto (r_1-r_2,r_2,r_3)$ and $(r_1,r_2,r_3) \mapsto (r_1-r_3,r_2,r_3)$, respectively). Clearly $a_1+a_2$ and $a_1+a_3$ are both positive in this case, so we get $a_1 + 2a_2$ and $a_1 + 2a_3 \ge 0$; adding gives $a_1+a_2+a_3 \ge 0$. But \[ 0 = a_1r_1 + a_2r_2 + a_3r_3 > a_1r_2 + a_2r_2 + a_3r_2 = r_2(a_1+a_2+a_3) \implies a_1+a_2+a_3 < 0 \] which is a contradiction. Since this covers all cases, we see that we can always decrease $\left\lvert a_1 \right\rvert + \left\lvert a_2 \right\rvert + \left\lvert a_3 \right\rvert$ whenever $0 \notin \left\{ a_1,a_2,a_3 \right\}$. Because the $a_i$ are integers this cannot occur indefinitely, so eventually one of the $a_i$'s is zero. At this point we can just apply the Euclidean Algorithm, so we're done.

Sorry for the bump but does this work? We can multiply all the numbers on the blackboard by any positive constant since all the numbers in a sequence of operations would just be multiplied by that constant. If a1 = 0, then a2r2 + a3r3 = 0. If a2 = 0 then we're done. If a2 != 0, then multiply all the numbers by a2 so the numbers are (a2r1,a2r2,a2r3) = (a2r1,-a3r3,a2r3). Assuming r3 != 0, we can divide all the numbers by r3 to get two of the numbers being (-a3,a2) which (since they are both positive integers) we can easily get 0 using the euclidean algorithm. Thus assume none of a_i are 0. Assume WLOG that r1 > r2. We have: r1 + a2/a1*r2 + a3/a1*r3 = 0 a1/a2*r1 + r2 + a3/a2*r3 = 0 Subtracting, (r1-r2)*(1-(a2/a1 - a1/a2)) + r3*(a3/a1-a3/a2) = 0. Perform the operation that replaces r1 with r1-r2. Define b1 = (1-(a2/a1 - a1/a2)) and b2 = (a3/a1-a3/a2). If neither of b1 or b2 are 0 we are done since (r1-r2) and r3 are rational multiples of each other. If exactly one of b1 or b2 is 0, then we are also done. Suppose b2 = 0. Since a3 != 0, we have a1 = a2. But then b1 = 1 so (r1-r2) = 0.

I think that should work but someone should double check as I am not good with proofs

Nope it's wrong. You get the wrong expression when you subtract. In fact, you can't pull out an $r_1-r_2$ at all, nonetheless with that quotient. So you can't completely get rid of one of your numbers and use the Euclidean algorithm on them that quickly.

thanks tennis, what a dumb error I made t.t

What, I still don't get it?

Oh I get it now, thanks tennis!

random practice. this is 25 moh and it is 7:22 cst right now. (yay 27 minutes! improvement?) okay here is a sketch i guess; might have infinite monkeyed this by like ignoring ideas and just following this path since triviel moh Idea is a sort of induction-type solution. Suppose the starting numbers are $x$, $y$, and $z$. These correspond to a triplet $(a_1,a_2,a_3)$ with $a_1x+a_2y+a_3z=0$. If we make the move $(x,y,z)\to (x,y-x,z)$ then we will go $(a_1,a_2,a_3)\to (a_1+a_2,a_2,a_3)$. The point is to make these operations to decrease some sort of monovariant. Luckily this isn't hard. While there exists both a positive and negative $a_i$, we combine them. The sum of absolute values of $a_i$ will decrease. Hence at some point we can WLOG $a_1=0$. Also note that $(0,0,0)$ can't be possible, since it would imply that the original triplet was $(0,0,0)$. If one of $a_2$ and $a_3$ is zero, then we are already done since it would imply the nonzero (WLOG $a_3$) has $z=0$. Otherwise one value is positive and one value is negative. Just keep repeating the process until one of $a_2$ and $a_3$ is zero, gg. To conclude: Step one is to run algorithm until one value is zero. Step two is to run algorithm until two values are zero, and finish.

Let $A=\langle a_1, a_2, a_3 \rangle$ and $R=\langle r_1, r_2, r_3 \rangle$. Then, $A\cdot R=0$ is given. After a step, if we do $r_2-r_1$ then we can do simple change $a_1$ to $a_1+a_2$. We claim that we can perform changes on $A$ such that $|A|^2=a_1^2+a_2^2+a_3^2$ is strictly decreasing. Assume $r_1\geq r_2\geq r_3$. So the possible changes are $\langle a_1, a_2, a_3 \rangle$ to either $\langle a_1+a_2, a_2, a_3\rangle$ or $\langle a_1+a_3, a_2, a_3 \rangle$ or $\langle a_1, a_2+a_3, a_3\rangle$. Suppose it was not possible to decrease $|A|^2$. So, we have $|a_1+a_2|>|a_1|, |a_1+a_3|>|a_1|, |a_2+a_3|>|a_2|$. This means 1. $a_1a_2>0$ or $2a_1a_2>-a_2^2$; 2. $a_1a_3>0$ or $2a_1a_3>-a_3^2$; 3. $a_2a_3>0$ or $2a_2a_3>-a_3^2$. Doing some casework we see that is impossible. Hence, $|A|^2$ is strictly decreasing and eventually we have $A=\langle \pm1, 0, 0\rangle$ or a result, which gives the result.

isn't this trivial by EDL?