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

Home > Numbers
Unusual binary representation (Posted on 2005-06-14) Difficulty: 3 of 5
Show that every positive integer is an alternating sum of strictly increasing powers of 2.

For example, 5=2^0 -2^2 +2^3 and 8=-2^3 +2^4 are alternating sums of strictly increasing powers of 2 (8=2^3 is ok too).

10=-2^1 -2^2 +2^4 is a strictly increasing sum but not alternating.

4=2^1 -2^1 +2^2 is alternating but not strictly increasing.

(author: prof Dan Shapiro of Ohio State University)

See The Solution Submitted by McWorter    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Proof (Based on what was said earlier) | Comment 6 of 9 |

Based on the idea of using 1 and -1 to prove this, the proof comes easily. (It seems longer than it would need to be in order to explain it robustly.)

Call the "ones" representation of a number similar to binary, but allowing -1 as a digit (for example, (1)(-1)(1)(0)(-1) would be 9) 

All that matters is that the -1 and 1 alternate (with the exception of 0 of course) in the ones representation of a certain number. Considering that this representation is derived from a certain binary representation (called A, with one leading zero) subtracted from A with a 0 at the end (since all the place values are moved over one place because of multiplying by two)

Define a "string" as any number of ones (including zero) with a 0 preceding them. (Because the 0s at the end of the number will simply subtract to 0, they are not important.) When the string is doubled, it will equal the same number with the 0 in front. (Each 1 will move one space over because they have been doubled.) When the string is converted into the ones representation (by subtracting double a string from itself), it will always begin with 1 and end with -1 with 0s in between (for the zeroes cancelling out)

Because of every A greater than 1 contains one or more strings "strung" together, and they can all be dealt with individually, the overall result is always having 1 and -1 alternating.
 

The representation will look something like this:
110 0 10 1110
011 0 01 0111

(1)(0)(-1) (0) (1)(-1) (1)(0)(0)(-1) is the stringbinary representation. Seeing the subtraction, it is understandable why the 1 and -1 alternate.


  Posted by Gamer on 2005-06-15 02:14:45
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 (12)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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