Questions and Answers #9 Decimals

Questions and Answers Sheet 9 Decimals Question #1 Is there any way to find the number of zeroes at the end of n! for 𝑛 ≥ 5 ? Answer: You have only counted the 5 of numbers like 25,125,250,1000 etc. once each. But these have more than one 5 in their factorisations. The correct method is as follows: Count one 5 from each of these numbers once: 5,10,15,20,25,30, ⋯ ⋯ 1000 We get ⌊ 1000 5 ⌋ = 200 of these 5's Now count another 5 from each multiple of 25 (note that we have already counted one 5 from each of these!) 25,50,75,100, ⋯ ⋯ 1000 We get ⌊ 1000 25 ⌋ = 40 of these 5's Now count another 5 from each multiple of 125 (we have already counted two 5s from each) 125,250,375, ⋯ ⋯ 1000 We get ⌊ 1000 125 ⌋ = 8 of these 5's Finally, count another 5 from each multiple of 625 (we have already counted three 5s from them) 625 We get ⌊ 1000 625 ⌋ = 1 of these 5's Adding all of these up, the maximum power of 5 in 1000! is 200+40+8+1=249. Obviously, the maximum power of 2 is much more, so we won't bother about it. The maximum power of 10 is therefore equal to the maximum power of 5, that is 249. So 1000! has 249 zeroes at the end. Question #2 𝑚 Last digit in ∑999 (olympiad question) 𝑘=1 𝑘 Answer: You can add 1000𝑚 to the sum as it will not change the last digit as its last digit is 0. Last digits of 1𝑚 , 11𝑚 , 21𝑚 , ⋯ , 991𝑚 are the same. Similarly for 2𝑚 , 12𝑚 , ⋯ , 992𝑚 and so on till 10𝑚 , 100𝑚 , ⋯ . 1000𝑚 . So the ones digit of 1𝑚 + 2𝑚 + ⋯ + 10𝑚 is the same as that of 11𝑚 + 12𝑚 + ⋯ + 20𝑚 and so on. There are 100 10s in 1000, so the ones digit of the sum is (1𝑚 + 2𝑚 + ⋯ + 10𝑚 ) × 100 𝑚𝑜𝑑 10 which is 0. Question #3 Let 𝛼 ∈ [0,9]. Is the set of real numbers such that the average of the digits of each of these numbers = 𝛼, countable or uncountable? Answer: Given: 𝛼 ∈ [0,9] , for 𝑛 ∈ 𝑁 let 𝑥𝑛 = ⌊𝑛𝛼⌋ − ⌊(𝑛 − 1)𝛼⌋. Note that 𝑥𝑛 is a non-negative integer and ≤ 9 , so can be used as a decimal digit. Let 𝐴 ⊆ N be an arbitrary set (so there are continuum-many choices for A). Then consider the number 𝑋𝛼,𝐴 = 0. 𝑑1 𝑑2 𝑑3 … that has (no integer part and) as nth decimal digit 1  ( d n = 0 x  n−k n = 2k , k  A n = 2k , k in A) 2k  n  2k +1 Then one verifies quickly that the average digit is 𝛼 Question #4 Modular Numbers: Not Accounting for Decimal Portion in Decimal Expansion Let 𝑛 = 10, 𝑠 = 4 . [ s ] = {s  z | s ~ s} = {s  z |10 | s − 4} = {10k + 4 | k  z} = {s  z | decimal expansion of s' ends in a 4 if s' is pos, ends in a 6 if s' is neg Answer: The term "decimal expansion" here is just the way you would write an integer as 267456 or 127 or any other string of digits - where there are no decimal points at all to worry about. It's the ordinary way of writing an integer. Formally, the idea is that the notation 83521 is really just shorthand for: 8 ⋅ 104 + 3 ⋅ 103 + 5 ⋅ 102 + 2 ⋅ 10 + 1 where we have a sum over powers of 10 times digits from {0,1,2,3,4,5,6,7,8,9} . Every non-negative integer can be uniquely expressed in this form (and every negative integer is just the negation of some positive integer) - and, when you're talking only about integers, this is what is meant by "decimal expansion." There's a generalization of this that applies to all real numbers, where something like 13.1415 … = 1 ⋅ 101 + 3 + 1 ⋅ 10−1 + 4 ⋅ 10−2 + 1 ⋅ 10−3 + 5 ⋅ 10−4 + … where we allow negative exponents of 10 as well (indicated by the decimal point) and also allow infinitely many terms with these negative exponents if we desire. Some numbers can be represented in multiple ways in this notation since 0.999 … = 1.000 … . If people are talking about real numbers, this is what "decimal expansion" would mean - but it's not what your professor is referring to. (Note: The word "decimal" here refers to the fact that we write a number as a sum of powers of ten which is probably what you were going to do anyways. Other bases can be indicated in the same terminology - for instance, the term "ternary expansion" refers to writing a number as a sum of powers of 3 times values in {0,1,2} and generalizes in the same ways) Question #5 Nth root as value inside the root symbol is less than 1 𝐿 ≔ lim+ 𝑥 𝑎 = 0 𝑥→0 (a>0) Answer: For any fixed positive a the function given by 𝑓(𝑥) = 𝑥 𝑎 is a continuous increasing function of x, with f(0)=0 . One way to see that is to note that its derivative 𝑓 ′ (𝑥) = 𝑎𝑥 𝑎−1 > 0 for x>0 The fact that a-1<0 when a<1 means that the graph of f is tangent (from the right) to the y-axis at the origin. So the slope is badly behaved there, but the function itself has limit 0. Look at the graph of 𝑦 = √𝑥 to see what is going on. Question #6 Numbers of the kind 0. 𝑎𝑎𝑎 … = 1 𝑎𝑎𝑎…𝑎 Answer: I think a complete answer should cover all bases (no pun intended). We will have: 𝑎= 𝑏 𝑑 −1 √𝑏 𝑘𝑑 −1 for any base b. However for 𝑘 ≥ 2 ∶ √𝑏 𝑘𝑑 − 1 ≥ √𝑏 2𝑑 − 1 = √(𝑏 𝑑 − 1)(𝑏 𝑑 + 1) ≥ 𝑏 𝑑 − 1 forcing a<1 . Hence we must have k=1 , with 𝑎 = √𝑏 𝑑 − 1 or 𝑏 𝑑 − 𝑎2 = 1 By Catalan's conjecture (or Mihăilescu's theorem, or if you are interested, this 1 + 𝑎2 = 𝑏 𝑑 is a special case proven by V. A. Lebesgue using Gaussian integers), if 𝑑 ≥ 2 there are no solutions. This forces d=1, and we have only the uninteresting case: 1 + 𝑎2 = 𝑏 so our choice of b must be one more than some square. For base 10, 1 10 = 1 + 32 , so 0. 3̇ = 3 Question #7 On the decimal expansion of 𝑘 ∏∞ 𝑘=1 ∑l=1 9 10l Answer: In general, (𝑞; 𝑞)∞ = 1 − 𝑞 − 𝑞 2 + 𝑞 5 + 𝑞 7 − ⋯ which is explained in the Wikipedia articles Euler function, q-Pochhammer symbol, and Pentagonal number theorem. In your particular case, q=0.1 which explains the decimal expansion you are asking about since some powers of q are added and some subtracted. Question #8 Out of the original girls and boys at a carnival party 40% of the girls and 10% of the boys left early, 3 4 of them decided to hang out and enjoy the festivities. There were 18 more boys than girls in the party. How many girls were there to begin with? Answer: If 3 4 stayed then 1 4 = 25% left early. If we represent the original number of girls as g and the original number of boys as b 40% × 𝑔 + 10% × 𝑏 = 25% × (𝑔 + 𝑏) ⇒ 40𝑔 + 10𝑏 = 25𝑔 + 25𝑏 ⇒ 15𝑔 = 15𝑏 ⇒𝑔=𝑏 but we are told 𝑏 = 𝑔 + 18 Question #9 P-Adic Expansion of Rational Number (Reverse Direction) 5−1 + 1 + 2 ∗ 5 + 52 + (4 ∗ 53 + 2 ∗ 54 + 3 ∗ 55 + 2 ∗ 57 + 58 ) + (4 ∗ 59 + 2 ∗ 510 + 3 ∗ 511 + 2 ∗ 513 + 514 ) + (4 ∗ 515 + 2 ∗ 516 + 3 ∗ 517 + 2 ∗ 519 + 520 ) + ⋯ Answer: Given: 𝑥 = ⋯ 120324121.15 and then add/subtract the appropriate finite base-5 fraction to make it a pure repeating number ending at the ones: 𝑥 − 1.15 = ⋯ 1203241205 = … 3241205 Then the I can convert that to a fraction essentially like one does for an ordinary decimal fraction, except that the analogue of 0.999 …10 = 1 is now … 4445 = −1 6 𝑥 − = 3241205 ⋅ … 0000015 5 = 3241205 ⋅ … 4444445 4444445 =− ⇒ 3241205 4444445 6 3241205 5 4444445 𝑥= − 6 11160 5 15624 = − = 37944 78120 = 17 35 Alternatively you could start with 𝑥−121.15 53 = … 1203245 and convert the right-hand side of that to a fraction in the same way. Question #10 Period length in the decimal expansion of fractions 1 7 is 1 × 6 digits repeating, 1 13 1 𝑛 is 2 × 6 digits repeating. Why? Answer: Step 1 For ' p co' to 10 you have by Fermat's little theorem that p | [(10) p − 1]. This means that there exists an integer of the form 𝑑𝑝−1 (10)𝑝−1 + 𝑑𝑝−2 (10)𝑝−2 + ⋯ + 𝑑0 (10)0 where 𝑑𝑝−1 , 𝑑𝑝−2 , ⋯ 𝑑0 ∈ {0,1, ⋯ ,9} such that 1 𝑝 = 𝑑𝑝−1 (10)𝑝−1 +𝑑𝑝−2 (10)𝑝−2 +⋯+𝑑0 (10)0 (10)𝑝 −1 Further, any fraction of the form 𝑑𝑝−1 (10)𝑝−1 +𝑑𝑝−2 (10)𝑝−2 +⋯+𝑑0 (10)0 (10)𝑝 −1 . will have a decimal representation of 0. 𝑑𝑝−1 ~𝑑𝑝−2 ~ ⋯ ~𝑑0 . 1 Therefore, for any ' (p) co' to (10), the (infinite) decimal representation of ( ) will either have a period of 𝑝 (p-1) , or a period of k, where k divides (p-1) The only time that the period will be k<(p-1) is if p happens to divide [(10)𝑘 − 1] (7) (for example) is not a divisor of either (99) or (999). However, (13) which you know has to be a divisor of [(10)(12) − 1] also happens to be a divisor of (103 + 1) This implies that (13) is a divisor of (103 + 1)(103 − 1) = (106 − 1). This explains why the decimal representation of 1 13 has a period of (6), rather than (12). Step 2 An example of an unusual way of using the above analysis is to use it to indirectly conclude that the 1 fraction ( ) has a period of (2). 11 This can be reasoned directly simply by noting that 11|99 1 The (convoluted) indirect way is to notice that the period of ( ) must either be (10) or a divisor k of (10). 11 Further, you know that 11 | [(10) + 1]. 3 This implies that 11 | [(10) − 1]. 6 1 This means that the period k of ( ) must be a common divisor of both (6) and (10). This allows you to 11 indirectly conclude that (k)=2. Question #11 Problem regarding a MST proof of 0.99999 ⋯ = 1 Answer: There is a problem with this proof, but it's not where you're looking for it. Its logic is supposed to be: assume both numbers are different, then, there must be a number strictly between them ("...between two distinct real numbers, there's always another one..."), and that leads to a contradiction. The way the contradiction is reached is faulty, though: "The decimal representation of x must have ..." is implicitly assuming that there is a unique decimal representation of x, while proving that 0.9999 ⋯ = 1.0000 ⋯ i.e. that decimal representation is not always unique. A proof proving its own invalidity is a rare specimen. Question #12 Proof for how 0.9999999 ⋯ = 1 Answer: The given number is a geometric series in disguise: 0.999 … −𝑛 = 9 ∑∞ 𝑛=1 10 = 9 10 ( 1 1 10 1− ) =1 which converges because its ratio is 0.1 < 1 Question #13 Prove 10 𝑃(𝑛) 2 + 1 is divisible by n Answer: Step 1 Consider n=21 then 1 21 = 0. 047619 thus 𝑃(21) = 6 . However 103 + 1 ≡ 14 𝑚𝑜𝑑 21 Step 2 Another example is 𝑛 = 13 ⋅ 17 = 221 , then 𝑃(221) = 48 and 1024 + 1 ≡ 119 𝑚𝑜𝑑 221 Step 3 However, the statement is true if n is ', different from 2 or 5. This is because 𝑃(𝑛) = 𝑜𝑟𝑑𝑛 (10) (from the definition of multiplicative order, also see this post and this). From (1) in your post 10 P ( n )  1 ( mod n )  n | (10 P(n) 2 + 1)  (10 Using Euclid's lemma, if we assume n |10 P(n) 2 P(n) 2 − 1) − 1 , then 𝑃(𝑛) 2 ≥ 𝑜𝑟𝑑𝑛 (10) = 𝑃(𝑛) which is a contradiction. As a result n |10 P(n) 2 +1 Question #14 Prove that every real number 𝑥 ∈ [0, 1] has a "certain" binary representation Answer: However, if you don't want to just copy an existing proof, you can define 𝑏𝑖 exactly like so: −𝑘 Let 𝑛 ∈ 𝑁 be arbitrary. Now, define 𝑥𝑛−1 = ∑𝑛−1 𝑘=1 𝑏𝑘 2 Now, define 0 if (bn =  1 if x − xn −1  2− n ) x − xn  2− n and you can then prove that, by construction, 𝑥𝑛 converges to x. Question #15 Prove that ∑∞ 𝑛=1 𝜇(𝑛) 10𝑛 is irrational Answer: The central concern about this problem is to determine whether 1 + 𝜇(𝑛) is periodic. If it is periodic, we can soon conclude that this number is rational. We will prove the irrationality by contradicting this statement. If 1 + 𝜇(𝑛) is periodic, then within each period T, there should be only a fixed number of occurences of 1 + 𝜇(𝑛) = 1 . This indicates that there should be a fixed number of non square-free integers within the period. However, if we were to let 𝑝𝑘 be k'th ', we can show that for any M>o the following system of congruences n  n + 1  (n + 2    n + M 0 ( mod p ) ( mod p ) ( mod p ) 0 ( mod p ) 0 0 2 k 2 k +1 2 k +2 2 k +M always has solution by the Chinese remainder theorem, which means that it is possible to have arbitrarily large consecutive non square-free sequence of integers, contradicting our assumption. Therefore, the series ∑∞ 𝑛=1 𝜇(𝑛) 10𝑛 converges to an irrational number. Question #16 3 4 of the books in the library are English books and the rest are Chinese books. There are 2849 more English books than Chinese books. What is the total number of books in the library? Answer: Working with fractions, we know the following: 3 4 are English books. 1 4 are Chinese books. The difference between the fractions is: 3 1 2 1 − = = 4 4 4 2 The difference between the number of books is 2849. So if half of the number of books is 2849, the total number of books is; 2849 × 2 = 5698 or: 1 × 𝑥 = 2849 2 𝑥 = 2 × 2849 = 5698 Question #17 Question which looks something similar to decimal expansion Let 𝐴 = {∑∞ 𝑛=1 𝑎𝑖 5𝑖 : 𝑎𝑖 = 0,1,2,3 or 4} What is set A? Answer: You are right. Actually, if 𝑥 ∈ [0, 1] and if you write x in base 5, then 𝑥 = 0. 𝑎1 𝑎2 𝑎3 … ; besides, 1 = 0.444444444 … Note that if 𝑥 ∈ [0, 1] you can define a1 = 5 x  . Then a2 = 52 x − 5a1 ,  a3 = 53 x − 52 a1 − 5a2  and so on. Then 𝑥 = ∑∞ 𝑛=1 𝑎𝑛 5𝑛 . Question #18 Repeating decimals in converted fractions, why these increments? a) 1 31 = 0.032258064516129 ⋯ ., the repetend is 032258064516129 which can be broken into the numbers 032258, 064516, 129032 that are related by multiples of 2: b) 1 13 = 0.076923 ⋯ . , the repetend is 076923 which can be broken into 0769, 2307 that are related by multiplying by 3: c) 1 17 = 0.0588235294117647 ⋯ , the repetend is 0588235294117647 which can be broken into the numbers 5882352941, 11764705882 that are related by multiplying by 2: d) 1 19 = 0.052631578947368421 ⋯ , the repetend is 052631578947368421 which can be broken into the numbers 05263 , 15789 , 47367 , 142101 (think of the initial 1 in 142101 being removed from the 8 in the preceding 47368) that are related by multiples of 3: e) 1 21 = 0.047619 ⋯, the repetend is 047619 which can be broken into the numbers 0476, 1904 that are related by multiplying by 4: Answer: The first thing to think about is finding the repeating decimal by long division. Taking 1 17 for example, your first division starts with a remainder 1. You append a 0 to it and try to divide 17 into 10. It goes 0 times, which gives the leading 0 in the repeat. You then pass a remainder of 10 to the next digit. You pull down another 0, getting 100, divide 17 into it getting 5 with a remainder of 15. The 5 is the second digit of the repeat and the 15 goes on for the next digit. If you have a full length repeat like 17, you must use each of the remainders from 1 to 17-1 once. When you repeat a remainder you have finished the repeat. For 13, which has only a six digit repeat you only use six remainders. This explains all the relationships you show. After the 𝑛𝑡ℎ digit the remainder is 10𝑛 𝑚𝑜𝑑 17 . We can find that 1010 ≡ 2 𝑚𝑜𝑑 17 That means after 10 digits you pass a remainder of 2 to the next digit. The repeat from there will clearly be twice the repeat starting from the front, where the remainder is 1. Question #19 S(n) properties Recently, while reading a number theory textbook for Olympiads, i came across the following property: 𝑆(𝑛1 + 𝑛2 ) ≤ 𝑆(𝑛1 ) + 𝑆(𝑛2 ) Answer: When you add two numbers, the sum of two facing digits is preserved, unless there is a carry. In this case, the sum is diminished by 9. 1234 +5678 6912 4+8⇒2+1 3+7⇒0+1 2+6⇒8, 1+5⇒6. Question #20 Simplify (1 − 𝑥)3 + 2𝑦 3 − 3(1 − 𝑥)𝑦 2 = 0𝑡𝑜 − (𝑥 − 2𝑦 − 1)(𝑥 + 𝑦 − 1)2 = 0 Answer: Use 𝑎3 − 𝑏 3 = (𝑎 − 𝑏)(𝑎2 + 𝑎𝑏 + 𝑏 2 ) and 𝑎2 − 𝑏 2 = (𝑎 − 𝑏)(𝑎 + 𝑏) (1 − x)3 + 2 y 3 − 3(1 − x) y 2 = (1 − x)3 − y 3 + 3 y 3 − 3(1 − x) y 2 = (1 − x)3 − y 3 + 3 y 2 ( y − 1 + x) = (1 − 𝑥 − 𝑦)[(1 − 𝑥)2 + (1 − 𝑥)𝑦 + 𝑦 2 ] − 3𝑦 2 (1 − 𝑥 − 𝑦) = (1 − 𝑥 − 𝑦)[(1 − 𝑥)2 + (1 − 𝑥)𝑦 − 2𝑦 2 ] = (1 − 𝑥 − 𝑦)[(1 − 𝑥)2 − 𝑦 2 + (1 − 𝑥)𝑦 − 𝑦 2 ] = (1 − 𝑥 − 𝑦)[(1 − 𝑥 − 𝑦)(1 − 𝑥 + 𝑦) + 𝑦{(1 − 𝑥) − 𝑦}] = (1 − 𝑥 − 𝑦)2 (1 − 𝑥 + 2𝑦)