Torsten Sillke, 2001-07-01 Problem: LENINGRAD MATHEMATICAL OLYMPIADS 1991 One may perform the following two operations on the natural numbers: (a) multiply it by any natural number; (b) delete zeros in its decimal representation. Prove that for any natural number n, one can perform a sequence of these operations that will transform n to a one-digit number. Solution: We develop a scheme that uses four multiplications. Helmut Postl showed that two are sufficient! We use the following fact: Lemma: For any integer n one can find a number consisting of digits 1 followed by some (or null) digits 0 only that is a multiple of n. Now let n be an arbitrary natural number. Multiplying n by the appropriate number, we can obtain a number containing only digits 1 followed by some digits 0 in its decimal representation. Delete the zeroes at then end. Now the chain of the following operation leads to the desired result. scheme I: [D. Fomin and A. Kirichenko] 11111111 x 82 911111102 91111112 x 9 820000008 828 x 25 20700 27 x 4 108 18 x 5 90 9 The appendix gives reductions of 828 with two multiplications. scheme II: [D. Fomin and A. Kirichenko] modified 11111111 x 82 911111102 91111112 x 9*25 20500000200 252 x 4 1008 18 x 5 90 9 Note that if you start with 11 you get 20700 after the second multiplication. Then the rest looks like the scheme I. The numbers 27 and 252 are two cases of the more general case 25*10^k + 2 which reduces as (25*10^k + 2)*4 = 10*(k+2) + 8. scheme III: [Sillke] 11111111 x 55 611111105 61111115 x 9*2 1100000070 117 x 6 702 72 x 125 9000 9 Example n=99: __________________ 1/(9*99) = 0.001122334455667789 = 1122334455667789/999999999999999999 therefore 1/99 = 1122334455667789/111111111111111111 99 x 1122334455667789 111111111111111111 x 55 6111111111111111105 611111111111111115 x 18 11000000000000000070 117 x 6 702 72 x 125 9000 9 Faster reduction of 99 (2 multiplications) 99 x 9294 920106 9216 x 5^10 90000000000 9 Problem Base 3: One may perform the following two operations on the natural numbers: (a) multiply it by any natural number; (b) delete zeros in its base 3 representation. Prove that for any natural number n, one can perform a sequence of these operations that will transform n to 11 (base 3). Solution Base 3: All numbers in the following are in base 3. 11111111 x 12 211111102 21111112 x 11 1010000002 112 x 2 1001 11 Problem Base 4: One may perform the following two operations on the natural numbers: (a) multiply it by any natural number; (b) delete zeros in its base 4 representation. Prove that for any natural number n, one can perform a sequence of these operations that will transform n to 3. Solution Base 4: All numbers in the following are in base 4. 11111111 x 22 311111102 31111112 x 3 220000002 222 x 11 3102 312 x 103 100002 12 x 2 30 3 Impossible transformations: (1) 111 is no divisor of 10^n + 2*10^m. Proof: 10^n (mod 111) = 1,2,4 (mod 111) for all n>=0. 2*10^m (mod 111) = 1,2,4 (mod 111) for all m>=0. Therefore 10^n + 2*10^m (mod 111) != 0 (mod 111) for all n,m>=0. And 222 can not be transformed with one multiplication to 12. Solution Base 5: All numbers in the following are in base 5. 11111111 x 32 411111102 41111112 x 4 320000003 323 x 3 2024 224 x 2 1003 13 Solution Base 6: All numbers in the following are in base 6. 11111111 x 42 511111102 51111112 x 5 420000004 424 x 13 10400 14 x 3 50 5 11111111 x 33 411111103 41111113 x 5*2 1100000030 113 x 4 500 5 Solution Base 7: All numbers in the following are in base 7. 11111111 x 52 611111102 61111112 x 6 520000005 525 x 362 300003 33 x 21 note 33 | 525 1023 123 x 51244 10000005 15 Impossible transformations: (1) 2^3 is no divisor of 10^n + 5*10^m. Proof: 10^n (mod 2^3) = 1,7 (mod 2^3) for all n>=0. 5*10^m (mod 2^3) = 2,5 (mod 2^3) for all m>=0. Therefore 10^n + 5*10^m (mod 2^3) != 0 (mod 2^3) for all n,m>=0. And 33 can not be transformed with one multiplication to 15. Solution Base 8: All numbers in the following are in base 8. 11111111 x 62 711111102 71111112 x 7 620000006 626 x 36210144706 30000000000004 34 x 2 70 7 11111111 x 44 511111104 51111114 x 7*2 1100000050 115 x 24 3004 34 x 2 70 7 Solution Base 9: All numbers in the following are in base 9. 11111111 x 72 811111102 81111112 x 8 720000007 727 x 130325 107000008 178 x 1053 200006 26 x 3 80 8 Impossible transformations: (1) 2^4 is no divisor of 2*10^n + 6*10^m. Proof: 2*10^n (mod 2^4) = 2 (mod 2^4) for all n>=0. 6*10^m (mod 2^4) = 6 (mod 2^4) for all m>=0. Therefore 2*10^n + 6*10^m (mod 2^4) = 8 (mod 2^4) for all n,m>=0. And 727 can not be transformed with one multiplication to 26. Solution Base 16: All numbers in the following are in base 16. 11111111 x 88 911111108 91111118 x F*2 11000000D0 11D x E6 1000E 1E x 8 F0 F Problem Base 2: One may perform the following two operations on the natural numbers: (a) multiply it by any natural number; (b) delete zeros in its base 2 representation. Prove that for any natural number n, one can perform a sequence of these operations that will transform n to 11 (base 2). Solution Base 2: All numbers in the following are in base 2. For binary numbers we need a new trick as a multiple of an all 1 number don't has fewer 1s in its binary representation. This time we use the observation 1010101 * 11 = 11111111. So 10101011 * 11 = 1000000001. 111111 x 11 10111101 1011111 x 11 100011101 101111 x 11 10001101 10111 x 11 1000101 1011 x 11 100001 11 We can fasten the reduction by using the step 1 01 01 01 x 11 a b c d 101 001 001 001 01 a-1 b-1 c-1 d-2 101 01 01 01 a-1 b-1 c-1 d-1 References: - D. Fomin and A. Kirichenko; LENINGRAD MATHEMATICAL OLYMPIADS 1987-1991 Westford, MD: MathPro Press, 1994 (Contests in Mathematics Series, vol 1) 202pp ISBN 0-9626401-4-X (Review: Jozsef Pelikan; Crux Mathematicorum 23 (1997) 78-80 This review shows this problem with solution.) Appendix: Table of factors to transform x to y for all multiples of 9 lower then 90. The only uncovered two digit case is 99. But this cannot be transformed into any other two digit number of digital root 9 as these are not divisible by 11. \ y 9 18 27 36 45 54 63 72 81 x +---------------------------------------------- 9 | 1 2 3 4 5 6 7 8 9 18 | 5 1 15 2 25 3 35 4 45 27 | - 4 1 - 15 2 - 26 3 36 | 25 3 75 1 125 15 175 2 225 45 | 2 4 6 8 1 12 14 16 18 54 | - 2 5 - 75 1 - 13 15 63 | - 16 - 4762 635 8 1 - 127 72 |125 15 375 5 625 7 875 1 1125 81 | - A 247 - 5 B - 8642 1 A = 1234568 B = 617284 Example: 81 -> 18 81 x 1234568 = 100000008 Impossible transformations: (1) 27 is no divisor of 3*10^n + 6*10^m. Proof: 3*10^n (mod 27) = 3 (mod 27) for all n>=0. 6*10^m (mod 27) = 6 (mod 27) for all m>=0. Therefore 3*10^n + 6*10^m (mod 27) = 9 (mod 27) for all n,m>=0. (2) 7 is no divisor of 2*10^n + 7*10^m. Proof: 2*10^n (mod 7) != 0 (mod 7) for all n>=0. 7*10^m (mod 7) = 0 (mod 7) for all m>=0. 2*10^n + 7*10^m (mod 7) != 0 (mod 7) for all n,m>=0. Reductions to 1: This is possible if 3 is not a divisor of n. 2 x 5 10 1 4 x 25 100 1 5 x 2 10 1 7 x 142858 1000006 16 x 5^4 10000 1 7 x 4286 30002 32 x 5^5 100000 1 7 x 285715 2000005 25 x 4 100 1 8 x 125 1000 1 10 1 11 x 928 10208 128 x 5^7 10000000 1 13 x 15385 200005 25 x 4 100 1 14 x 71429 1000006 16 x 5^4 10000 1 16 x 625 10000 1 17 x 11765 200005 25 x 4 100 1 19 x 158 3002 32 x 5^5 100000 1 20 x 5 100 1 1000001 x 7 999993 000007 000002 8 000001 000000 000009 000002 8192 x 5^13 10^13 1 Faster reduction of 828 (2 multiplications) 828 x 12077294686 10000000000008 18 x 5 90 9 828 x 12077343 10000040004 144 x 625 90000 9 828 x 60395 50007060 576 x 15625 9000000 9 828 x 1209 1001052 1152 x 78125 90000000 9 828 x 4830917875 4000000000500 45 x 2 90 9 828 x 2417875 2002000500 225 x 4 900 9 828 x 132875 110020500 1125 x 8 9000 9 414 x 241546 100000044 144 x 625 90000 9 414 x 13575 5620050 5625 x 16 90000 9 414 x 12079 5000706 576 x 15625 9000000 9 414 x 2418 1001052 1152 x 78125 90000000 9 414 x 2179 902106 9216 x 5^10 90000000000 9 Two Steps: Helmut Postl showed that it is possible to reduce a string of 9s with one multiplication and a zero deletion step to 9 times a power of 2. The list shows possible target numbers. This uses the casting 9 rule. As 92+01+06 = 99 we have 99 | 920106. 9216 <- 92 01 06 - 9 621 -> 2*9 As 2+094+901+002 = 999 we habe 999 | 2094901002. 294912 <- 2 094 901 002 - 9 9 4221 -> 3*9 2359296 <- 203 0500 9296 - 9 9 63 522 -> 4*9 150994944 <- 150 99409 00440 - 9 9 9 54 441 -> 5*9 1236950581248 <- 10 230000 069000 500581 200408 - 9 81 81 63 54 522 -> 6*9 10133099161583616 <- 10 0000013 0000300 9916010 0000050 0083616 - 9 9 81 63 63 63 51111 -> 7*9 2533274790395904 - 9 9 9 72 72 54 54 333 -> 8*9 19791209299968 - 9 9 9 9 9 9 81 72 621 -> 9*9 332041393326771929088 - 9 9 9 81 81 72 72 63 432 333 -> 10*9 43521329506126650289422336 - 9 9 81 63 63 63 63 54 54 522 22221 -> 11*9 -- http://www.mathematik.uni-bielefeld.de/~sillke/ mailto:Torsten.Sillke@uni-bielefeld.de