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

 neves dda tsuj (Posted on 2004-02-22)
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
3 1add inv 2 operations needed
17 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

 Posted by Ady TZIDON on 2004-02-22 22:40:02

 Search: Search body:
Forums (0)