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
Sorry, I don't care for that ~ symbol. I'll just use the word "reverse".
The following al-gore-ithm will convert any ***one-digit*** number N to 1:
If N is 3, add 7 and reverse the digits.
For all other values of one-digit whole number N:
LOOP:
N=N+7
If a power of 10, less N, is a multiple of 7, add that multiple to N, reverse the digits to convert N to 1, exit.
Reverse the digits of N.
Repeat the above test.
If you can still can't convert N to 1, go back to LOOP.
E,g. for N=7:
7 -- > 14 --> 41 --> 48 --> 1000 (1000=48+[7*136]) --> 1
So if we can convert any whole number to a one-digit number, we can convert it to 1.
We can convert the rightmost digit of any whole number to 0 by adding the right combination of 7's. If that digit is 1, add 7 seven times. If it is 2, add 7 four times. etc. If the number was originally all 9's, this will add one more digit on the left, with all but two of the digits zero.
Once the rightmost digit is converted to zero, reverse the digits.
Then repeat the steps.
Ultimately you will convert every digit but the leftmost digit to 0.
Then reverse the digits, and you have a one-digit number. Convert the one-digit number to 1, using the method above.
E.g. 999999
add 7*3=21
1000020.
Reverse the digits.
200001
add 7*7=49
200050
Reverse the digits.
50002
Add 7*4=28
50030
Reverse the digits.
3005
add 7*5=35
3040
Reverse the digits.
403
add 7
410
Reverse the digits.
14
add 7*8=56
70
Reverse the digits.
7
Now convert 7 to 1.
7 -- > 14 --> 41 --> 48 --> 1000 (1000=48+[7*136]) --> 1
Edited on February 22, 2004, 4:33 pm
|
Posted by Penny
on 2004-02-22 15:04:25 |