Numbers on a Blackboard

[worthawholebean]

Three nonnegative real numbers , , are written on a blackboard. These numbers have the property that there exist integers , , , not all zero, satisfying . We are permitted to perform the following operation: find two numbers , on the blackboard with , then erase and write in its place. Prove that after a finite number of such operations, we can end up with at least one on the blackboard.

[t0rajir0u]

Solution

Every time we perform an operation on the numbers on the blackboard , we perform the corresponding operation on the integers so that continues to hold. (For example, if we replace with then we replace with .)

It's possible to show we can always pick an operation so that is strictly decreasing (this took me three pages of casework, but presumably there's a nicer way). Since it is a strictly decreasing sequence of positive integers, after a finite number of operations we have , so is some permutation of and gives the desired result.

[jb05]

Said nicer way:
Click to reveal hidden content

WLOG and is positive. Then it cannot be true that both and are at least , or else . WLOG . Then we can replace with and with to make smaller.

We also need to take into account the case , but this is essentially the same argument.

[t0rajir0u]

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

[SamE]

Click to reveal hidden content

Instead of the sum of squares, I just considered the difference between the largest and smallest . If , it takes two operations to reduce this, but otherwise, the solution is pretty clean.

[MellowMelon]

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.

[Phelpedo]

[101101101]

Click to reveal hidden content

If you keep track of the in addition to the and always operate on the largest and smallest (one of which is positive, one of which is negative), then at each step you either go from having duplicates to not having duplicates without changing the largest and smallest values, you increase the smallest value without changing the largest, or you decrease the largest value without changing the smallest. You can only do that finitely many times (after any pair of operations the fit in a strictly smaller interval), so eventually all the are non-positive or non-negative, which gives one .

Does that actually work?

[jb05]

[Boy Soprano II]

Hm, I inducted on . I used about three cases, but two of my arguments were identical, I think.

[Xantos C. Guin]

Click to reveal hidden content

I said that since , then there must exist some positive real constant such that are positive integers and that . Since multiplying through by a constant, performing a sequence of operations, then dividing by that constant gives the same numbers as just performing the sequence of operations, we may multiply the initial numbers by . Then we must simply perform the Euclidean Algorithm until one of the numbers is , then subtract repeatedly from another number until that number reaches .

I didn't exactly prove the first part of it though, but if that first part is true, then my solution works, but becomes rather trivial for a #2/5

[Boy Soprano II]

[MellowMelon]

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 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 induction arguments in other solution.

[Boy Soprano II]

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

where all coordinates are rational, and you know that

for all integers . 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 . After all, what properties do irrationals have which rationals don't and would help in solving the problem?

[CatalystOfNostalgia]

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.

[Benjamin Hu]

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?

[MellowMelon]

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 exist, you can let be an irrational such that for integers . I tried working with reducing and 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.

[Boy Soprano II]

[junggi]

[rem]

I used a monovariant on . You can make it decrease all the time unless one of the numbers is .