real number and blackboard

[BMAD]

Three nonnegative real numbers r1, r2, r3 are written on a blackboard. These numbers have the property that there exist integers a1, a2, a3, not all zero, satisfying

a1 r1 +a2 r2 +a3 r3 = 0.

We are permitted to perform the following operation: find two numbers x, y on the blackboard with x <= y, then erase y and write y - x in its place. Prove that after a finite number of such operations, we can end up with at least one 0 on the blackboard.

[phil1882]

i have no clue what this question is even asking.

how does the top part, r1, r2, r3, a1, a2, a3, relate to the bottom part, x <= y finite operations the allow y -x = 0.

[BMAD]

x and y are of the three nonnegative real numbers r1 r2 r3

[BMAD]

integers a1, a2, a3, not all zero, satisfying a1 r1 +a2 r2 +a3 r3 = 0.

this hint is for those Linear Algebra fans out there

[phil1882]

we have two possible cases: either x and y share a prime factor, or they don't.

if they do, then easy, the number of operations necessary is y/x.

if they don't then this devolves into the euclidean algorithm.

[plasmid]

Getting things started by solving for cases where {r1, r2, r3} are all rational numbers, but not solved for cases where they're irrational.

Notice that if you have any set of numbers {r1, r2, r3} with which you can find a solution, that solution will also work if the same numbers are multiplied by any scaling factor {k*r1, k*r1, k*r3}.

First I'll consider the case where {r1, r2, r3} are all rational. In that case, you can write them as numerator / denominator of integer terms: r1 = r1n/r1d; r2 = r2n/r2d; r3 = r3n/r3d. Multiply those numbers by r1d*r2d*r3d, so now r1 = r1n*r2d*r3d; r2 = r2n*r1d*r3d; r3 = r3n*r1d*r2d and all of those terms are integers. Now you can find a solution with those integers, and since it only differs from the original {r1, r2, r3} by a scaling factor, the solution with the integers will also work for the original rational numbers.

And it's easy to find a solution if you're dealing with integers. Just take r1 and r2, and let r1 be the smaller of the two. Keep subtracting r1 from r2, and r2 will eventually reach zero (in which case you're done) or will reach some number x smaller than r1, in which case you can repeatedly subtract x from r1 until r1 reaches zero or some number smaller than x, and keep repeating until one of them reaches zero.

I don't have a solution if there are irrational numbers, but this might be a start. Notice that since {r1, r2, r3} are all positive and a1*r1 + a2*r2 + a3*r3 = 0, that means that one or two of the {a1, a2, a3} terms are negative. If two of those terms are negative then you can multiply by the scaling factor -1 to make it so one of the terms is negative. I will use that fact, and without loss of generality say that a3 is the negative term, so I'll rewrite the equation as

a1*r1 + a2*r2 = a3*r3

where now we know that the {a1, a2, a3} terms are all non-negative integers. The r terms might be negative after multiplying by -1.

Now I'll multiply all of the r terms by the scaling factor a3 to generate the set of scaled terms {s1, s2, s3} so that

s1 = a3*r1

s2 = a3*r2

s3 = a3*r3 = a1*r1 + a2*r2.

This is of the from s1 = nx, s2 = ny, s3 = bx + cy, where {n, b, c} are integers. This seems like it's working its way toward a solution, but I don't see how to finish it off from this point.

[plasmid]

Looking through some of the older unsolved problems, I still can't solve this one but might be able to get it to a point where someone who stayed awake through Linear Algebra could maybe easily calculate an Eigenvalue or whatever voodoo that is to solve it.

The solution for cases where all the numbers are rational is in the previous post, so this is just dealing with cases where there are irrational numbers.

One or two of the {a1, a2, a3} terms must be negative for r1*a1+r2*a2+r3*a3 to be zero. Without loss of generality, call a1 the term that is opposite in sign compared to a2 and a3. We then know that

|a1|*r1 = |a2|*r2 + |a3|*r3

To keep from having to write absolute value signs, I'll define {b1, b2, b3} to be the absolute values of {a1, a2, a3} so we have

b1*r1 = b2*r2 + b3*r3

Now scale the r terms by dividing by r1, so the scaled terms {s1, s2, s3} are {1, r2/r1, r3/r1}, and we still have

b1*s1 = b2*s2 + b3*s3

But we now know that b1*s1 is an integer, simply b1.

b2*s2 + b3*s3 = b1

s3 = (b1-s2*b2)/b3

s3 = (-b2/b3)*s2 + (b1/b3)

That's useful because we can now write everything in terms with only one unique irrational number, s2.

s1 = 1

s2 = s2

s3 = (-b2/b3)*s2 + (b1/b3)

Rescale all the terms once more, multiplying all terms by b3, to get {t1, t2, t3}

t1 = b3 + 0*s2

t2 = 0 + b3*s2

t3 = b1 - b2*s2

Where the b terms are all positive integers and s2 is irrational. This seems like it would be the easiest form to work with.

[Barcallica]

Getting things started by solving for cases where {r1, r2, r3} are all rational numbers, but not solved for cases where they're irrational.

Notice that if you have any set of numbers {r1, r2, r3} with which you can find a solution, that solution will also work if the same numbers are multiplied by any scaling factor {k*r1, k*r1, k*r3}.

First I'll consider the case where {r1, r2, r3} are all rational. In that case, you can write them as numerator / denominator of integer terms: r1 = r1n/r1d; r2 = r2n/r2d; r3 = r3n/r3d. Multiply those numbers by r1d*r2d*r3d, so now r1 = r1n*r2d*r3d; r2 = r2n*r1d*r3d; r3 = r3n*r1d*r2d and all of those terms are integers. Now you can find a solution with those integers, and since it only differs from the original {r1, r2, r3} by a scaling factor, the solution with the integers will also work for the original rational numbers.

And it's easy to find a solution if you're dealing with integers. Just take r1 and r2, and let r1 be the smaller of the two. Keep subtracting r1 from r2, and r2 will eventually reach zero (in which case you're done) or will reach some number x smaller than r1, in which case you can repeatedly subtract x from r1 until r1 reaches zero or some number smaller than x, and keep repeating until one of them reaches zero.

I don't have a solution if there are irrational numbers, but this might be a start. Notice that since {r1, r2, r3} are all positive and a1*r1 + a2*r2 + a3*r3 = 0, that means that one or two of the {a1, a2, a3} terms are negative. If two of those terms are negative then you can multiply by the scaling factor -1 to make it so one of the terms is negative. I will use that fact, and without loss of generality say that a3 is the negative term, so I'll rewrite the equation as

a1*r1 + a2*r2 = a3*r3

where now we know that the {a1, a2, a3} terms are all non-negative integers. The r terms might be negative after multiplying by -1.

Now I'll multiply all of the r terms by the scaling factor a3 to generate the set of scaled terms {s1, s2, s3} so that

s1 = a3*r1

s2 = a3*r2

s3 = a3*r3 = a1*r1 + a2*r2.

This is of the from s1 = nx, s2 = ny, s3 = bx + cy, where {n, b, c} are integers. This seems like it's working its way toward a solution, but I don't see how to finish it off from this point.

 

How multiplying r1 = r1n/r1d by r1d*r2d*r3d is r1 = r1n*r2d*r3d. You tried to prove r1, r2, r3 are integers, which is impossible.

[plasmid]

For clarity I probably should have written that using a different variable since I was re-scaling the r terms.

If you're given a set of terms {r1, r2, r3} which are rational, then you can write them in terms of integer numerators and denominators:

r1 = r1n / r1d, r2 = r2n / r2d, r3 = r3n / r3d

You can then multiply each of the terms {r1, r2, r3} by a scaling factor r1d*r2d*r3d to generate a new set of scaled terms {s1, s2, s3} where

s1 = r1 * (r1d*r2d*r3d), s2 = r2 * (r1d*r2d*r3d), s3 = r3 * (r1d*r2d*r3d)

Then s1 = (r1n/r1d) * (r1d*r2d*r3d) = r1n*r2d*r3d, which is the product of three integers, so s1 is an integer, and likewise for the other s terms. Then you can easily solve the problem with the integers {s1, s2, s3}, and since they only differ from the r terms by a scaling factor, the same solution will work for the r terms.

[Barcallica]

For clarity I probably should have written that using a different variable since I was re-scaling the r terms.

If you're given a set of terms {r1, r2, r3} which are rational, then you can write them in terms of integer numerators and denominators:

r1 = r1n / r1d, r2 = r2n / r2d, r3 = r3n / r3d

You can then multiply each of the terms {r1, r2, r3} by a scaling factor r1d*r2d*r3d to generate a new set of scaled terms {s1, s2, s3} where

s1 = r1 * (r1d*r2d*r3d), s2 = r2 * (r1d*r2d*r3d), s3 = r3 * (r1d*r2d*r3d)

Then s1 = (r1n/r1d) * (r1d*r2d*r3d) = r1n*r2d*r3d, which is the product of three integers, so s1 is an integer, and likewise for the other s terms. Then you can easily solve the problem with the integers {s1, s2, s3}, and since they only differ from the r terms by a scaling factor, the same solution will work for the r terms.

Ah! I knew you wouldn't do that. I should have understood the solution before finding error. Nicely done 

Edited August 29, 2014 by Barcallica

[plasmid]

Handling rational numbers was the easy part. Handling the case of irrational numbers looks like it's going to be tricky.

[Barcallica]

t1 = b3 + 0*s2

t2 = 0 + b3*s2

t3 = b1 - b2*s2

Where the b terms are all positive integers and s2 is irrational.

 

 

Isn't it a solution itself? 

we have an integer t1.

we have t2 and t3 who have integer multiplication of s2. Can ged rid of s2 by using t2 and t3. And reach 0 with the help of t1?

[plasmid]

We can't make the coefficients of the irrational terms in t2 and t3 go to zero using the same approach that was used with rational numbers, because the coefficient in t2 is positive and the coefficient in t3 is negative. If you subtract t3 from t2, then t2's coefficient for s2 gets larger; if you subtract t2 from t3, then t3's coefficient for s2 becomes more negative. You could try solving an example: {r1, r2, r3} = {2, 2pi, 4-pi}. Be careful not to let any of the terms become negative during the process.

Edit: changed r2 from 2+2pi to 2pi so it would be the same format as {t1, t2, t3} terms.

Edited September 1, 2014 by plasmid

[plasmid]

Apologies about bumping a topic, but now that BMAD and some newer faces are around, I was wondering if we could get a hint or a fresh set of eyes on this problem.

[BMAD]

consider employing the euclidean algorithm instead.

If two of the ai vanish, say a2 and a3, then r1 must be zero and we are done.  

 

Assume at most one ai vanishes. If any one ai vanishes, say a3, then r2/r1 = −a1/a2 is a nonnegative rational number. Write this number in lowest terms as p/q, and put r = r2/p = r1/q. We can then write r1 = qr and r2 = pr. Performing the Euclidean algorithm on r1 and r2 will ultimately leave r and 0 on the blackboard. Thus we are done again.

 

.... more cases to consider

[karthickgururaj]

 

consider employing the euclidean algorithm instead.

If two of the ai vanish, say a2 and a3, then r1 must be zero and we are done.  

 

Assume at most one ai vanishes. If any one ai vanishes, say a3, then r2/r1 = −a1/a2 is a nonnegative rational number. Write this number in lowest terms as p/q, and put r = r2/p = r1/q. We can then write r1 = qr and r2 = pr. Performing the Euclidean algorithm on r1 and r2 will ultimately leave r and 0 on the blackboard. Thus we are done again.

 

.... more cases to consider

 

I think with that hint and plasmid's earlier work, the solution seems easy..

 

 

If r1/r2 is a rational, where r1 and r2 are real, then the Euclidean algorithm will terminate in finite steps.

 

And with the original constraint on r1, r2 and r3, it is easy to prove that r1/r2, r2/r3 and r3/r1 are all rational.

 

[DejMar]

It is given that a

₁•r₁ + a₂•r₂ + a₃•r₃ = 0 : r_n ∈ R₀⁺ and a_n ∈ Z with at least one of a_n <> 0. (n ∈ N, an index)

Either:
(a) all three real values equal 0;
(b) two of the three real values equal 0 and the coefficient of the other equals 0;
(c ) one of the three real values equals 0, and the two coefficients of the others equal 0;
(d) one of the three real value equal 0, and the two coefficients of the others are of opposite sign and the terms to which they are part of are of equal absolute value;
(e) all three real values are greater than 0 with one of the coefficients being zero and the signs of the other two
are opposite with the absolute values of their terms being equal; or
(f) all three real values are greater than 0, with two of the coefficients negative with the third positive,
and the sum of the terms with the negative coefficients being equal in absolute value to the third term;

For cases (a), (b), (c ) and (d) at least one 0 already appears on the blackboard, thus only cases (e) and (f) need be examined. For (e) and (f), if an irrational value exists, all terms will be a multiple of that irrational value. With the exception for (e), a distinct irrational number can be assigned the 0 coefficient. As these terms can be scaled by dividing by the common multiple of the irrational value, the solution would be the same as if each were rational.
It has already been noted that by using the Euclidean algorithm, that a finite number of operations of substituting Y – X for Y will result in a value of 0 appearing on the blackboard.
It may only need be proved that the proposition made, that "all terms will be a multiple of that irrational value", with the noted exception, is true.

Edited November 13, 2014 by DejMar

[karthickgururaj]

 

consider employing the euclidean algorithm instead.

[spoiler start of proof]

If two of the ai vanish, say a2 and a3, then r1 must be zero and we are done.  

 

Assume at most one ai vanishes. If any one ai vanishes, say a3, then r2/r1 = −a1/a2 is a nonnegative rational number. Write this number in lowest terms as p/q, and put r = r2/p = r1/q. We can then write r1 = qr and r2 = pr. Performing the Euclidean algorithm on r1 and r2 will ultimately leave r and 0 on the blackboard. Thus we are done again.

 

.... more cases to consider

I think with that hint and plasmid's earlier work, the solution seems easy..

 

 

If r1/r2 is a rational, where r1 and r2 are real, then the Euclidean algorithm will terminate in finite steps.

 

And with the original constraint on r1, r2 and r3, it is easy to prove that r1/r2, r2/r3 and r3/r1 are all rational.

 

 

 

I take back the second statement

 

Let a and b be two positive integers, (a>b). We form a new pair, a', b', such that, a' = b, b' = a - q₀.b (q₀ is a positive integer), and a'>b'. If b' == 0, the process stops; else we continue the same way to construct a'' and b'', and so on.

 

The following assertions can be easily proven: The process above will terminate in finite steps. This is essentially the Euclidean algorithm.

 

Now, let r_a and r_b be two real positive numbers (not necessarily rational) such that, r_a/r_b = a/b. We can now form a new pair, r_a', r_b' from a', b' and q₀ (where a', b' and q₀ retain the meaning as earlier) such that, r_a' = r_b,   r_b' = r_a' - q₀.r_b. It is easy to show that r_a'/r_b' = a'/b'. For every step in the process earlier, we can form a new pair with the real numbers, ultimately reducing one of the numbers in the pair to zero in finite steps.

 

[DejMar]

(f) all three real values are greater than 0, with two of the coefficients

negative with the third positive of opposite sign to the third, and the sum of the terms with the negative two coefficients of equal sign being equal in absolute value to the third term;

[plasmid]

I'm not sure those solutions would work, but maybe I just don't completely follow them.

Could you show an example of application to the numbers {2, 2pi, 4-pi}?

[DejMar]

@plasmid, With the givens, I do not believe {2, 2Π, 4 - Π} satisfy the three reals.
 

Substituting your three reals into the equation

a(2) + b(2Π) + c(4 - Π) = 0

...then solving for Π as if it were a variable results in the following equation, which implies that Π would not be trancendental or irrational given a, b, and c are integers:
Π = (2a + 4c)/(1 - 2b)

[plasmid]

(4)*(2) + (-1)*(2pi) + (-2)*(4-pi) = (8) + (-2pi) + (-8 + 2pi) = 0

 

Solving for pi...

a(2) + b(2pi) + c(4-pi) = 0

2a + 2b*pi + 4c - c*pi = 0

2a + 4c + (2b-c)pi = 0

implies 2b-c = 0, which it does

[karthickgururaj]

@plasmid, With the givens, I do not believe {2, 2Π, 4 - Π} satisfy the three reals.

 

Substituting your three reals into the equation

a(2) + b(2Π) + c(4 - Π) = 0

...then solving for Π as if it were a variable results in the following equation, which implies that Π would not be trancendental or irrational given a, b, and c are integers:

Π = (2a + 4c)/(1 - 2b)

 (1-2b) != 0 

 

This is an interesting puzzle..

[DejMar]

Yes, division by zero does create a situation where all values are correct (and thus undefined). In addition to this error, I see where I had an error while calculating. 

There may be less steps, but here goes...

(1) Y=2, X=4 - Π....new Y=Π - 2
(2) Y=2Π, X=4 - Π....new Y=3Π - 4
(3) Y=3Π - 4, X=Π - 2...new Y=2Π - 2
(4) Y=2Π - 2, X=Π - 2...new Y=Π

(5) Y=Π - 2, X =4 - Π...new Y=2Π - 6
(6) Y=Π, X=4 - Π...new Y=2Π - 4
(7) Y=2Π - 4, X=2Π - 6...new Y=2
(8) Y=2, X=4 - Π...new Y = Π - 2
(9) Y=Π - 2, X =4 - Π...new Y = 2Π - 6
(10) Y=2Π - 6, X=2Π - 6...new Y = 0

Edited November 27, 2014 by DejMar

[plasmid]

It's true that it's solvable, but it's meant to be a test case to see if a general algorithm for finding an answer would be able to handle it, and to show how such an algorithm would be implemented in practice. Post 17 spoke of scaling by a common multiple of the irrational value, but in this test case not all terms are a multiple of the irrational value since one of them is just 2.

[DejMar]

Your three reals {2, 2pi, 4-pi} did show that the proposition that all terms will be a multiple of the irrational value if an irrational value did exists is not necessarily true. (Hence a proposition and not an assertion). What you did demonstrate is that not only scaling, the multiplicative aspect, is an operational factor to be considered, but that the additive aspect employed is a factor, as well.

Edited November 28, 2014 by DejMar