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

Home > Numbers
neves dda tsuj (Posted on 2004-02-22) Difficulty: 3 of 5
You have a simple (base-ten, whole number) calculator which can perform only two operations: visually reversing a number, and adding seven.

Prove that you can use this calcluator to convert any number to 1.

Notation: use ~ to denote reversal, as in
~53 = 35

No Solution Yet Submitted by DJ    
Rating: 4.5000 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
my solution revisited and revised | Comment 4 of 11 |
Lemma 1 Any digit can be converted into 1 by a chain of only two operations( add7 and reverse).

Proof:
1 =1 0 operations needed
2 4add inv 1add inv 7 operations needed
3 1add inv 2 operations needed
4 8add inv 2add inv 4add inv 1add inv 19 oper,
5 5add inv 8add inv 2add inv 4add inv 1add inv 21 oper
6 2add inv 4add inv 1add inv
7 4add inv 1add inv 2add inv 4add inv 1add inv
17 operations
8 6add inv 5add inv 8add inv 2add inv 4add inv 1add inv 23 oper
9 3add inv 1add inv only 6 operations

Lemma 2, Any n-digit number can be reduced into into another (n-1)-digit number by a chain of only two operations( add7 and reverse).
Proof:
For any number an appropriate multiple of 7 can be added to make the sum divisible by 10.
If the last digit of the original number was 1-
add 7*7,if the last digit of the original number was 2 add 4*7, if 3-1*7 4-5*7 5-5*7 6-2*7 7-9*7
8-6*7,9-3*7.
or:If the last digit of the original number was k-
add t*7 such that k+7*t=0 mod 10.

Applying both lemmas as needed will allow the requested transformation, clearly not optimal as far as the length of the procedure is concerned.

e.g.

4753==>4760==>674==>730==>37==>73==>80==>8==>50==>5==>40==>4==>60==>6==>20==>2==>30==>3==>10==>1

0R:4753==>4760==>674==>730==>37==>100==>1

ady
  Posted by Ady TZIDON on 2004-02-22 22:40:02
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 (7)
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