Differences square

A colleague of mine's son was given the following exercise to do in class, as an exercise in subtracting numbers.

Start with a largish piece of paper and write four random numbers in a square:

2 17


7 9

Then put the positive difference of each corner in the centre of each side, forming a diamond thus:

2..15..17

5.........8

7....2...9


Do the same thing with the diamond thereby forming another, smaller square, and keep going:

2..15..17
..10...7..
5.........8
...3....6..
7....2....9

What happens? The kids were supposed to notice that eventually the process ends up with four zeros.


The questions asked of me were "Does it always end no matter what numbers you start with? And if so, what is the maximum number of iterations it can take"


It appears that eight iterations is the maximum as per the example above, but I couldn't come up with anything like a concrete proof. Anybody got any thoughts, counter examples, etc?

EDIT $%^£ing spacing!

Originally posted by howardbradley
A colleague of mine's son was given the following exercise to do in class, as an exercise in subtracting numbers.

Start with a largish piece of paper and write four random numbers in a square:

2 17


7 9

Then put the positive difference of each corner in the centre of each side, forming a diamond thus:

2..15..17

5...... ...[text shortened]... a concrete proof. Anybody got any thoughts, counter examples, etc?

EDIT $%^£ing spacing!

Just some observations:

An easy way to model this problem is to label the entries for each square in a clockwise manner. Starting top left, you'd have A1, A2, A3 and A4. For the next set of four, label them B1, B2, B3 and B4 such that:

B1 = |A1-A2|
B2 = |A2-A3|
B3 = |A3-A4|
B4 = |A4-A1|

which gives a clockwise pattern for the second set. Continue this for each square using a different letter. It might be possible to draw some conclusions from this type of indexing, but I haven't gotten into it yet because it gets very long very quickly.

I tried running this on Excel a bajillion times, and you always end up with 4 zeros. I think the answer lies somewhere in the parity (evenness/oddness) of the numbers, since the last square always has 4 even numbers or 4 odd numbers. The square before that always has one pair kitty-cornered and another two numbers either paired as well or equidistant from the original pairing (for example, if you have _ 4 _ 4 as the pair, the other two numbers could be [6 (4) 6 (4)] or [6 (4) 2 (4)]).

The length of the chain is usually about 5 or 6, although I've had a few as long as 10 and a few that were 1 or 2. If zeros pop up in the middle, the chain tends to get a bit longer.

That's about it...carry on. 😕

Originally posted by PBE6
Just some observations:

I tried running this on Excel a bajillion times, and you always end up with 4 zeros. I think the answer lies somewhere in the parity (evenness/oddness) of the numbers, since the last square always has 4 even numbers or 4 odd numbers. The square before that always has one pair kitty-cornered and another two numbers either paired as w ...[text shortened]... s pop up in the middle, the chain tends to get a bit longer.

That's about it...carry on. 😕

Yes - I used Excel as well but, try as I might, couldn't get a chain longer than 8 - even by putting really BIG numbers in ;-) Which numbers gave you a chain of ten? I considered parity too - working outward (the reverse of the normal procedure) from the four zeroes. If you assume the step before the zeroes is all odd numbers then you quickly reach an impasse. However if you choose all evens then the same thing does not happen. That's where I got stuck.

Originally posted by howardbradley
Yes - I used Excel as well but, try as I might, couldn't get a chain longer than 8 - even by putting really BIG numbers in ;-) Which numbers gave you a chain of ten? I considered parity too - working outward (the reverse of the normal procedure) from the four zeroes. If you assume the step before the zeroes is all odd numbers then you quickly reach ...[text shortened]... wever if you choose all evens then the same thing does not happen. That's where I got stuck.

After a hard fight with this puzzle (only a few minutes by day), I think I have found the solution. But it is not for the faint of heart.

In fact, you must have high math knowledge. Such as partial derivatives, Jacobians et al.

I've solved it with the help of some coworkers, all of them mathematicians (I am a humble computer programmer).

Then, I search thru Google and find the solution too.

So I can post the url, but I'm not claiming any merit for me.

My rec for a very nice thread!

LB

Originally posted by LittleBear
After a hard fight with this puzzle (only a few minutes by day), I think I have found the solution. But it is not for the faint of heart.

In fact, you must have high math knowledge. Such as partial derivatives, Jacobians et al.

I've solved it with the help of some coworkers, all of them mathematicians (I am a humble computer programmer).

Then, I ...[text shortened]... n post the url, but I'm not claiming any merit for me.

My rec for a very nice thread!

LB

The tension is killing me. 😉

I'm certainly interested in seeing the solution.

It's not exactly pretty but as far as I can tell it does the job:


If a,b,c,d are all positive and non-zero and a is the largest among them then in the next square every number must be smaller than a.

If the square a,b,c,d contains one or more zeros and a is the largest among them then in the next square no number may be greater than a.

Also the following cases and links are true (feel free to check using general examples):

1 ) One number is zero and no adjacent numbers are the same.
If this is the case then the next square will not contain a zero.

2 ) One number is zero and one pair of adjacent numbers are the same (not the number that is zero).
If this is the case then the next square will contain one zero and no numbers the same. We now have case 1.

3 ) One number is zero and all the other numbers are the same.
The next square will contain two non-adjacent zeros. We now have case 4.

4 ) Two non-adjacent numbers are zero.
The next square will contain no zeroes.

5 ) Two adjacent numbers are zero or three numbers are zero.
The next square will contain two non-adjacent zeros. We now have case 4.

Therefore we cannot have a situation where we always have a zero in our square (except in the case of 4 zeros but that is the complete state). This means that over a number of iterations our numbers must decrease and as our differences are defined as positive so must our differences. For this pattern to continue we must at some finite iteration reach a point where our differences are zero.

Originally posted by XanthosNZ
It's not exactly pretty but as far as I can tell it does the job:


If a,b,c,d are all positive and non-zero and a is the largest among them then in the next square every number must be smaller than a.

If the square a,b,c,d contains one or more zeros and a is the largest among them then in the next square no number may be greater than a.

Also the ...[text shortened]... tern to continue we must at some finite iteration reach a point where our differences are zero.

I can't say that your reasoning is ill-oriented. But it is flawed.
The solution of the problem isn't so simple.
As stated at the begining of the thread, it only contemplates natural numbers.
But the solution (justification) can be extended to real numbers.

That takes into the game partial derivative and jacobians.
I don't claim to have found the solution, as I said before (that is, a lot of help from mathematicians coworkers).

Then, I confirmed our solution was right,

I'll post a link in say, 2 days, with the solution (I can't explain it better!)

I don't post it just now for not spoiling the fun of the people that are math-oriented (Math fans I mean),

So, may be on friday, you will have the solution.

At least for me, it is a thrilling! 🙂

LB


P,S,: my rec for you, you deserve it for your honest effort. Keep trying!

Edit(s): Only spelling and grammar. English isn't my mother tongue.
Sorry 🙁

Originally posted by LittleBear
I can't say that your reasoning is ill-oriented. But it is flawed.
The solution of the problem isn't so simple.
As stated at the begining of the thread, it only contemplates natural numbers.
But the solution (justification) can be extended to real numbers.

That takes into the game partial derivative and jacobians.
I don't claim to have found the so trying!

Edit(s): Only spelling and grammar. English isn't my mother tongue.
Sorry 🙁

My solution allows for all positive real numbers and zero. You can quickly see that it also allows for negative real numbers because a square containing negative numbers will have all positive or zero numbers after one iteration (thanks to absolute differences).

And just because you have a proof that takes a lot of higher level maths doesn't mean that an easier solution is not possible. If you believe my solution does not extend to all real numbers then feel free to show why. As of right now I can't see how it doesn't.

Now all my proof does is show that no repeating cycle can be reached and therefore the all zero square must happen in a finite number of steps. That's all that was required. I'm an engineer, never solve a more complicated problem than the minimum required.

I was thinking more on this last night and because of my proof there must exist a maximum number of iterations required to reach the zero square. If you can find what this is you'll have my appreciation.

Originally posted by XanthosNZ
My solution allows for all positive real numbers and zero. You can quickly see that it also allows for negative real numbers because a square containing negative numbers will have all positive or zero numbers after one iteration (thanks to absolute differences).

And just because you have a proof that takes a lot of higher level maths doesn't mean that a quired to reach the zero square. If you can find what this is you'll have my appreciation.

Yes. the solution of the problem seems to be always convergent to a [0,0,0,0] square, in a finite number of iterations. If you are asking me to find a general equation that can predict how many steps it will take, starting from four random numbers, I must say that I didn't think of it. And I believe there isn't a general equation to anticipate it.

The key of the problem. at least as I see it, is to formally demonstrate that the process
- is always convergent
- always converges to zero
- the solution takes a finite number of steps

I have found an article published in an American math journal (May 05) that casts serious doubts on the existence of a formal solution to the (entire) problem.

Oh well, Xanthos. I am not a mathematician after all.
I think it is only one more interesting problem to add to my collection 🙂

Your effort to solve it is welcome.

LB

Edit: Typos and spelling

Originally posted by LittleBear
Yes. the solution of the problem seems to be always convergent to a [0,0,0,0] square, in a finite number of iterations. If you are asking me to find a general equation that can predict how many steps it will take, starting from four random numbers, I must say that I didn't think of it. And I believe there isn't a general equation to anticipate it.

The ...[text shortened]... d to my collection 🙂

Your effort to solve it is welcome.

LB

Edit: Typos and spelling

LittleBear, please stop insinuating my proof isn't correct without explaining why. I feel I have satisfied all of the conditions you mention.

Originally posted by XanthosNZ
I feel I have satisfied all of the conditions you mention.

Look, I agree with you, but there is no need to get emo about it.

For what it's worth, I like Xanthos' solution; it has me convinced (and it's my thread ;-) and has provided an answer to the first part of my question "Does it always end...". Much more fruitful than all the mucking around with odds and evens that I did. In fact I think I *may* be able to extend it to give an answer to the "...maximum number of iterations..." as well - though it will involve a lot tedious checking of various cases. Sadly my employers think I should be working on their problems right now rather than maths problems, so I may not have answer before LittleBear reveals the mathematicians' proof on Friday. I await with anticipation - I had no idea such a simple-seeming puzzle might involve "partial derivatives, Jacobians etc"

Howard pointed out a problem with my proof, case 3 should read:

3 ) One number is zero and all the other numbers are the same.
The next square will contain two adjacent zeros. We now have case 5.

This doesn't affect how the proof works but it did need correcting.

Originally posted by XanthosNZ
(...) Also the following cases and links are true (feel free to check using general examples): (...)

with all due respect:
can you probe that they are true and why?
I don't want to waste the rest of my life checking them using "general examples".
Sincerely, I will appreciate it. May be induction is the key word.
Honestly, I don't know.
I must to confess that my skill at math problems is way too poor.

Regards

- Julia

ps: I'm sure that common sense isn't the answer