real number and blackboard

26 posts in this topic

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Posted · Report post

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
0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted (edited) · Report post

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  :thumbsup:

Edited by Barcallica
0

Share this post


Link to post
Share on other sites

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites

Posted (edited) · Report post

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 by plasmid
0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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
0

Share this post


Link to post
Share on other sites

Posted · Report post

 

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.

 

0

Share this post


Link to post
Share on other sites

Posted (edited) · Report post

It is given that a

1•r1 + a2•r2 + a3•r3 = 0 : rn ∈ R0+ and an ∈ Z with at least one of an <> 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 by DejMar
0

Share this post


Link to post
Share on other sites

Posted · Report post

 

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 - q0.b (q0 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 ra and rb be two real positive numbers (not necessarily rational) such that, ra/rb = a/b. We can now form a new pair, ra', rb' from a', b' and q0 (where a', b' and q0 retain the meaning as earlier) such that, ra' = rb,   rb' = ra' - q0.rb. It is easy to show that ra'/rb' = 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.

 

0

Share this post


Link to post
Share on other sites

Posted · Report post

(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;
0

Share this post


Link to post
Share on other sites

Posted · Report post

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}?

0

Share this post


Link to post
Share on other sites

Posted · Report post

@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)

0

Share this post


Link to post
Share on other sites

Posted · Report post

(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

0

Share this post


Link to post
Share on other sites

Posted · Report post

@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.. :)

0

Share this post


Link to post
Share on other sites

Posted (edited) · Report post

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 by DejMar
0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.