All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
What's the ... (Posted on 2013-06-27) Difficulty: 3 of 5
Start with a vector (ordered quadruplet) of any four integers. Construct a new such vector that is the difference between successive elements of the first, cyclically so that the last difference is that between the last element of the first sequence and the first element of that array. Always take the absolute value when doing the differences. Call this the "diffy" operation.

If we repeat the diffy operation starting with the sequence (3, 7, 1022, 2005) we get the following.

(3, 7, 1022, 2005)
(4, 1015, 983, 2002)
(1011, 32, 1019, 1998)
(979, 987, 979, 987)
(8, 8, 8, 8)
(0, 0, 0, 0)

True or False: Any starting sequence of integers leads to the zero vector in finitely many steps. Offer proof.

No Solution Yet Submitted by Danish Ahmed Khan    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Taking the long route (spoiler) | Comment 1 of 2
There may be more elegant proofs, but this one suffices.

Take any vector and apply the diffy operation once.  Having done this, the resulting vector has no negative terms.  Let m = maximum of the 4 terms in the resulting vector.  If m = 0, then we are all done, so all we need to do is deal with the case where m is positive.  We will prove that if m is positive, then the applying the diffy operation results in a new lower maximum in a finite number of steps.  And since the terms can only be integral, this means that the diffy operation always reaches 0 eventually, in a finite number of steps.

Without loss of generality, let the m be the first term.  The other terms are a, b, c, where a<= M, b <= m, c <= m.  The vector is (m,a,b,c).  There are really just 4 cases to deal with:

1) a > 0, c > 0.  The diffy operation results immediately (one step) in a new lower maximum.

2) a = 0, c > 0.  The diffy operation results in one operation in (m,e,f,g) where e > 0 and g > 0.  This has just become case 1, which we have already covered.

3) a = c = 0.  The diffy operation results in one operation in (m,b,b,m).  This has just become case 1, which we have already covered.

4) a = b = c = 0. The diffy operation results in three steps in (m,m,m,m).  This has just become case 1, which we have already covered.  (For that matter, we are one more diffy away from (0,0,0,0).)

So, after one diffy then we are either done or we have a positive maximum number of terms.  If m is positive, then applying the diffy operation results in a new lower maximum in a finite number of steps.  And since the terms can only be integral, this means that the diffy operation always reaches 0 eventually, in a finite number of steps.

  Posted by Steve Herman on 2013-06-27 19:23:56
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information