Math Contest Round Two Solutions Chapter 1

Math Contest Round Two Solutions 1. Solution by CwH. Let 𝑣! = Kim’s speed and 𝑣! = Cara’s speed. Since it takes Kim twice as long to run 2,255 decimeters as it takes Cara to run 1/10 of a mile and since !!".! !"#.! 2,255 decimeter = 225.5 m and 1 mile = 1,609.344 m, we have = 2× or, 𝑣! = !"#.! !!".! 𝑣! , where the relation 𝑡𝑖𝑚𝑒 = them to meet will be 𝑡 = !,!!! !! ! !! = !,!!! !! (!! !"#$%&'( !"#$%&'( !"#.! ) !!".! Kim would have traveled will be 𝑣! 𝑡 = = !,!!! !.!"# !! !! has been used. The time it takes for !,!!! !! (!.!"#) . In the meantime, the distance = 412.03 m. The answer is (B). 1. Second solution by MF. Note for Chemistry students. Some Chemistry instructors wish to emphasize the accuracy of measurements, which is determined by the number of significant figures in a result. The number 2255 decimeters has four significant figures, and the number 1/10 mile is to be regarded as 0.1000, if it is meant to be at the same level of accuracy. Conversion factors, such as 1 mile = 1.61 km are regarded as “exact” numbers, so even though the conversion 1.61 has only three significant figures, we are allowed to express the answer to this problem using four significant figures. Technically, since Kim and Cara are given as starting 1 km apart, which has only one significant figure, then if this were a Chemistry problem, we should express our answer using only one significant figure! So the answer would have to be a rounded number like 300, 400, 500 or 600 meters. These rounded numbers have only one significant figure. Please note that some Chemistry instructors would mark your answer wrong unless you rounded to one significant figure in this problem! However, here, we will assume that “1km” really means 1.000km, and our answer will have four significant figures. In Chemistry, this problem is called an exercise in “factor label analysis” or “dimensional analysis”, although the phrase “dimensional analysis” also refers to another more advanced technique. Here is the solution: First convert decimeters into km: 2255 𝑑𝑒𝑐𝑖𝑚𝑒𝑡𝑒𝑟 1 𝑚𝑒𝑡𝑒𝑟 10 𝑑𝑒𝑐𝑖𝑚𝑒𝑡𝑒𝑟𝑠 1𝑘𝑚 = 0.2255 𝑘𝑚 1000 𝑚𝑒𝑡𝑒𝑟𝑠 (1) Now convert one-tenth mile into km: 0.1000 𝑚𝑖𝑙𝑒 1.61 𝑘𝑚 = 0.1610 𝑘𝑚 1 𝑚𝑖𝑙𝑒 (2) Now use the formula: 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒 = 𝑟𝑎𝑡𝑒 𝑡𝑖𝑚𝑒 (3) We write equation (3) for Kim and for Cara: and 0.2255 = 𝑣!"# 2𝑡 (4) 0.1610 = 𝑣!"#" 𝑡 (5) where t is the time it takes Cara to run her distance, and vKim and vCara are their respective rates. Note the presence of the factor (2t) in equation (4), which incorporates the condition that it takes Kim twice as long to run her distance. Now eliminate the unknown time t between equations (4) and (5) with the result: 𝑣!"#" = 1.428𝑣!"# (6) Now we see that if Kim and Cara start 1.000 km apart and run towards each other, if Kim runs x meters, then Cara will run 1.428 x meters, due to her rate being faster by this factor. The sum of their distances must add up to 1.000 km, since they start that distance apart and meet somewhere in the middle. This yields the equation: 𝑥 + 1.428𝑥 = 1 7 which has the solution: x = 0.4119 km. In meters, this is 411.9 meters, which is closest to answer (B), 412 meters. 2. Solution by GM. Replace each letter in ONE + ONE = TWO with a base-10 digit so that identical letters are replaced by identical digits and different letters are replaced with different digits, T is the only odd digit, and O cannot be zero. What is the value of N? Solution: For convenience, let’s use Ō to represent the variable O in the original statement problem to distinguish it from the digit zero. If 0 ≤ E < 5 then 0 ≤ 2E < 10; and if 5 ≤ E ≤ 9 then 10 ≤ 2E ≤ 18. Thus the two E’s from the left side of the original equation must sum to: (Case 1) 2E = Ō or (Case 2) 2E = 10 + Ō. In the same way, we also have: If 0 ≤ N < 5 then 0 ≤ 2N < 10; and if 5 ≤ N ≤ 9 then 10 ≤ 2N ≤ 18. Thus the two N’s from the left side of the original equation must sum to: 2N = W or 2N = 10 + W (if Case 1 above is true. Here W is even); or 2N = W − 1 or 2N = 10 + W − 1 (if Case 2 above is true. Here W is odd). Since T is the only odd number, then W must be an even number, which means that (Case 3) 2N = W or (Case 4) 2N = 10 + W; and also 2E = Ō. From the original equation, we also have: If 0 ≤ Ō < 5 then 0 ≤ 2Ō < 10; and if 5 ≤ Ō ≤ 9 then 10 ≤ 2Ō ≤ 18. Thus the two Ō’s from the left side of the original equation must sum to: 2Ō = T or 2Ō = 10 + T (if Case 3 above is true. Here T is even); or 2Ō = T − 1 or 2Ō = 10 + T − 1 (if Case 4 above is true. Here T is odd). Since T is the only odd number, then 2Ō = T − 1 or 2Ō = 10 + T − 1, (and Case 4 must be true). However, ONE + ONE = TWO, and there is no carry-over digit into the thousands place. Therefore, 2Ō = T − 1, or rewritten, 2Ō + 1 = T. In summary so far, we have: 2E = Ō, 2N = 10 + W, 2Ō + 1 = T. The largest odd digit T can be is 9, which means that Ō must be 4, which means E must be 2. There is no smaller positive even number possibility for E than 2. Thus T = 9, Ō = 4, and E = 2. W and N are positive even digits (we are told) different from all the other digits. Possibilities left for W and N are 6 or 8. They solve the equation: 2N = 10 + W. W = 6 and N = 8 are the only combinations that work. Thus: The solution is: (E), N = 8. 2. Second solution by CwH. Given that ONE + ONE = TWO and O is not zero, we conclude that E cannot be zero and O must be a nonzero even digit. We contend that O = 4. For if O is 6 or 8, then the sum of two O’s in the hundredth digits would need to have a carry over, which is not the case. On the other hand, if O = 2, then since E is a nonzero even digit, E must then be 6. Then the sum of two tenth digits of two N’s plus a “1” from the unit digit carried would have forced W to be an odd digit. This would contradict the assumption that T is the only odd digit. Thus, O = 4 and E = 2, and Since T is the only odd digit, we may conclude that N and W will have to be the remaining two even digits, 6 and 8. With a quick trial we see that N = 8 and W = 6 will work. The answer is (E). 3. Solution by MF. Note to calculator users. If you solve this problem using a calculator, then note that you should take the natural (or base ten or any other base if you wish) log of each number first and compare the logs. Why? Try entering a number such as 6500 directly into your calculator. Some calculators will simply give an error message because the number is too big. If you have a TI-89 calculator, it will actually give a result, but that result greatly overflows the size of the calculator display, and you will have trouble trying to compare the different numbers, all of which overflow the display. Why is it OK to take the log and compare the logs? Because the function 𝑦 = 𝑙𝑜𝑔! 𝑥 is a strictly increasing function for any base b. This means that if 𝑥 > 𝑦, then 𝑙𝑜𝑔! 𝑥 > 𝑙𝑜𝑔! 𝑦. So take the natural log of each number, with the results: ln(21000) = 1000 ln(2) = 693.1 100 ln(50) = 391.2 and 500 ln(6) = 895.9 200 ln(30) = 680.2 75 ln(1000) = 518.1 It can be seen that ln (6500) = 500 ln(6) is the largest value, so 6500 is the largest number and the answer is (B). Solution without calculator: If you forgot to bring your calculator to this test, does it mean you cannot do this problem? Not at all! Just proceed as in the two solutions below: 3. Second solution by CwH. Determine which of the following numbers is greatest: (a) 2!""" , ( b) 6!"" , ( c) 30!"" , ( d) 50!"" , (e) 1000!" . We first note that 6!"" = 2!"" 3!"" > 2!"" 2!"" = 2!""" . We then contend that all the other numbers are less than 2!""" . This is because 30!"" = 2!"" 15!"" < 2!"" 16!"" = 2!"" (2! )!"" = 2!""" . 50!"" = (5! )!"" 2!"" = 5!"" 2!"" < 8!"" 2!"" = (2! )!"" 2!"" < 2!""" . 1000!" = 10!!" = 2!!" 5!!" < 2!!" 8!!" = 2!!" 2!"# < 2!""" . Thus, among these numbers 6!"" is the greatest. The answer is (B). 3. Third solution by GM. Problem #3: Which of the following numbers has the greatest value? A. 21000 B. 6500 C. 30200 D. 50100 E. 100075 Solution: 21000 = 22×500 = (22)500 = 4500 < 6500. Thus selection A can be eliminated. 6500 = 65×100 = (65)100 = 7776100. And 30200 = 302×100 = (302)100 = 900100. Since 7776100 > 900100 and 7776100 > 50100, C and D can be eliminated. 6500 = 65×100 = (65)100 = 7776100 > 1000100 > 100075. Thus E can be eliminated. The solution is: (B), 6500 . 4. Solution by CwH. We are told that the equation 𝑎! + 𝑏 ! + 𝑐 ! = 2019 has only one solution in positive integers a, b, and c, and we are supposed to find the value of 𝑎 + 𝑏 + 𝑐 for this solution. Clearly, if 𝑎 = 43, 𝑏 = 13, 𝑐 = 1 the equation will be satisfied. To show how we obtain this solution and why this is the only possible solution, we need to do some work. First, a few preliminaries: a) The square of an odd positive integer always has a remainder 1 when divided by 8. This can be seen as follows: If 𝑛 = 2𝑘 + 1 is an odd integer, then 𝑛! = 4𝑘 ! + 4𝑘 + 1 = 4𝑘 𝑘 + 1 + 1. But for any integer k, one of the two consecutive integers k and k+1 must be even, and thus, 𝑛! is in fact, a multiple of 8 plus 1. b) The square of an even positive integer always has a remainder of 4 when divided by 8. An even positive integer n can always be written in one of the following forms: 𝑛 = 8𝑘, 𝑛 = 8𝑘 + 2, 𝑛 = 8𝑘 + 4, and 𝑛 = 8𝑘 + 6. We need only check that in each case, 𝑛! can always be written as a multiple of 8 plus 0 or 4. c) The square of a positive integer, when divided by 5, can only have a remainder of 0, 1 or 4. We can prove this the same way as above. An integer can always be written in the form as 𝑛 = 5𝑘 + 𝑖, where 𝑖 = 0, 1, 2, 3 or 4. We need only show that in each case when we divide 𝑛! by 5, the remainder is always 0, 1 or 4. Now consider the equation 𝑎! + 𝑏 ! + 𝑐 ! = 2019. Since 5! is already greater than 2019, c can only be 1, 2, 3, or 4. First consider the case for 𝑐 = 4. Since 4! = 1024, the equation 𝑎! + 𝑏 ! + 𝑐 ! = 2019 becomes 𝑎! + 𝑏 ! = 2019 − 1024 or 𝑎! + 𝑏 ! = 995. Since 995 is an odd integer, one of a and b is odd and the other is even. But this is impossible because if we divide both sides of the equation by eight, the remainder for the numbers on the left side of the equation can only be 1 plus 0 or 4, but the remainder of 995, when divided by 8 is 3. They can never be equal. Thus c cannot be 4. What if 𝑐 = 3. Since 3! = 243, the equation 𝑎! + 𝑏 ! + 𝑐 ! = 2019 becomes 𝑎! + 𝑏 ! = 2019 − 243, or 𝑎! + 𝑏 ! = 1776. In this case either both a and b are even or both a and b are odd. Consider remainders obtained by dividing both sides of the equation by eight, we can easily see that a and b cannot both be odd. Hence, a and b are both even. Say, 𝑎 = 2𝑚 and 𝑏 = 2𝑛 for some integers m and n and the equation 𝑎! + 𝑏 ! = 1776 becomes 4𝑚! + 4𝑛! = 1776, or 𝑚! + 𝑛! = 444. Using the same argument again, we may conclude that m and n are both even. Say, 𝑚 = 2𝑝 and 𝑛 = 2𝑞 for some integers p and q and the equation 𝑚! + 𝑛! = 444 can now be reduced to 𝑝! + 𝑞 ! = 111. In this case, one of p and q is even and the other is odd. Again, this is impossible, since the remainder of 111, when divided by 8, is 7, and the remainder for 𝑝! + 𝑞 ! can only be 1 plus either 0 or 4. They can never be equal. Thus, c cannot be 3. The case for 𝑐 = 2 is similar since in this case, the equation 𝑎! + 𝑏 ! + 𝑐 ! = 2019 can be reduced to 𝑎! + 𝑏 ! = 2019 − 2! , or 𝑎! + 𝑏 ! = 1987. In this case, again one of a and b is even and the other is odd. This is impossible, since the remainder of 1987, when divided by 8, is 3, and the remainder for 𝑎! + 𝑏 ! can only be 1 plus either 0 or 4. They can never be equal. Thus, c cannot be 2 either. The only possibility is then for 𝑐 = 1, and the equation can be reduced to 𝑎! + 𝑏 ! = 2018. First note that both a and b are even or both. Considering the remainders when both sides are divided by 8, we can rule out the case that both a and b are even. Hence, we may assume that both a and b are odd. Continuing with the remainders with 8 would not bring us any new information; we now consider the remainders when both sides are divided by 5. The square of a number can leave only remainders 0, 1, or 4 when divided by five, since the possible remainders of the un-squared number are 0, 1, 2, 3 and 4. Squaring each of these remainders gives 0, 1, 4, 9, and 16, which leave 0, 1, or 4 as remainder. Since the remainder of 2018, when divided by 5 is three, we conclude that both 𝑎! and 𝑏 ! must have a remainder of 4 when they are divided by 5 (this is the only way their sum can have a remainder of 3 when divided by 5). For an integer, whose square has a remainder of 4, the integer itself must have a remainder of 2 or 3, when divided by 5, again since 22 = 4 and 32 = 9, which both leave remainder 4. Since a and b are also odd integers, it follows that both a and b can only be one of the following seven integers: (With remainder 2): 7, 17, 27, 37; (With remainder 3): 3, 13, 23, 33, 43. We don’t have to consider integers greater than 43 because the next highest odd integer, 45, has a square greater than 2018. Trying these nine integers, we can find quickly that the only possible solutions for a and b are 13 and 43. If we insist that 𝑎 > 𝑏, then 𝑎 = 43, 𝑏 = 13, 𝑐 = 1 are the only possible solution. In this case, 𝑎 + 𝑏 + 𝑐 = 57 and the answer is (B). 4. Second solution by MF. In grade school, students are taught the concept of division with remainder. For example if 20 is divided by 3, we can write: 20 = (6) 3 + 2. In this case, the quotient is 6 and the remainder is 2. Note that the only possible remainders are zero, one and two, because if we had a remainder of three or higher, we could just increase the quotient to absorb the extra factors of three. It is shown in Discrete Mathematics that any integer can be uniquely expressed in quotient and remainder form. So if we use divisor three, then any integer N can be uniquely expressed as: 𝑁 =3 𝑞 +𝑟 1 where q is the quotient, r is the remainder, and 0 ≤ 𝑟 < 3. It is not hard to show that if an integer N is not a multiple of three, so that 𝑁 = 3 𝑞 + 1 or 𝑁 = 3 𝑞 + 2, then N2 or N5 cannot be multiples of three either because if you take, for example, 3 𝑞 + 2 ! , every term except the last will have at least one factor of three in it, and the last term will be 25 = 32, which leaves remainder 2. If we work this statement around the other way using logic (in technical terms, the contrapositive), we can say that if N5 or N2 is a multiple of three, then N itself must be too. Note that 2019 is a multiple of three, so the given equation: 𝑎! + 𝑏 ! + 𝑐 ! = 2019 can be written as: 3𝑞! + 𝑟! + 3𝑞! + 𝑟! + 3𝑞! + 𝑟! = 3 673 + 0 2 3 Equation (3) can be re-written as: 3 𝑞! + 𝑞! + 𝑞! − 673 = 𝑟! + 𝑟! + 𝑟! (4) Since the left side of equation (4) is a multiple of three, the right side must be as well. It follows that the sum of the three remainders must be a multiple of three. It is straightforward to show that the square of any number can leave only remainder zero or one when divided by three. This follows from the fact that the square of zero is zero, the square of one is one, and the square of two is four, which leaves remainder one. One the other hand, the fifth power of a number can leave all remainders, 0, 1 and 2, since 25 leaves remainder two. From equation (2) above, we see that a2 and b2 can leave remainder either zero or one, while c5 can leave zero, one or two. This means there are three possible cases: Case 1: All three remainders on the left side of equation (3) are zero. Case 2: All three remainders are one. Case 3: In equation 3, the first remainder is one, the second is zero, and the third is two. (This is equivalent to the case where the first remainder is zero, the second is one, and the third is two.) Let us examine case 1: If the sum of remainders is zero, then each remainder is zero, meaning that each term in equation (2) is a multiple of three. But from our argument above, it follows that the integers a, b, and c themselves would have to be multiples of three. We now show that this leads to a contradiction: If a, b, and c are all multiples of three, then we can write: 𝑎 = 3𝑖, 𝑏 = 3𝑗, and 𝑐 = 3𝑘, where i, j, and k are integers. We make these substitutions into equation (2) with the result: 3𝑖 ! + 3𝑗 ! + 3𝑘 ! = 3 673 (5) Divide both sides of equation (5) by three, factor out a second factor of three on the left side and collect terms with the result: 3 𝑖 ! + 𝑗 ! + 3! 𝑘 ! = 673 (6) Observe that the left side of equation (6) is a multiple of three, while the right side, 673, is not, so we have a contradiction. This means that case 1 above cannot occur. Notice that we have learned something interesting about the three numbers a, b, and c: they cannot all be multiples of three, without having yet solved the problem. We move on to case 2: Case 2: Assume that all three remainders in equation (3) are equal to one. To begin a search, we first need to compute the largest possible value of c in equation (2). We find that 55 > 2019, so the largest value of c with remainder one when divided by three is 𝑐 = 4. So put 𝑐 = 4 in equation (2), and the equation with rearrangement of terms becomes: 𝑎! = 995 − 𝑏 ! (7) 5 where we computed: 995 = 2019 – 4 . Since 995 < 32, the largest value of b we can use is 𝑏 = 31. Recall that b must leave remainder one when divided by three under the assumptions of this case, so we successively try 𝑏 = 31, 28, 25, ⋯ 7, 4, 1 in equation (7) and look for a perfect square on the left side. None of these choices for b in equation (7) yielded a perfect square. Recall that we have been using 𝑐 = 4, so now we choose the next available value of c, leaving remainder one, which is 𝑐 = 1. With this substitution, equation (2) now becomes: 𝑎! = 2018 − 𝑏 ! (8) Since 2018 < 45, the largest available value of b leaving remainder one is 𝑏 = 43. The plan now is to substitute 𝑏 = 43, 40, 37, ⋯ 7, 4, 1 into equation (8) and look for a perfect square on the left side. Here we catch a piece of luck, because the very first choice 𝑏 = 43 yields the following result: 13! = 2018 − 43! (9) So we have a solution. The problem specifies that 𝑎 > 𝑏, so we choose 𝑎 = 43, 𝑏 = 13, and 𝑐 = 1. Then we compute 𝑎 + 𝑏 + 𝑐 = 57, and the answer is (B). 4. Third solution by GM. The equation a2 + b2 + c5 = 2019 has exactly one solution where a, b, and c are positive integers with a > b. Find a + b + c for this solution. Solution: A simple check will reveal that the only possible values for c are 1, 2, 3, or 4. Let’s begin with c = 1. We then solve a2 + b2 + 15 = 2019, or more simply: a2 + b2 = 2018. Using modular arithmetic with modulus 4, this problem becomes a matter of finding integers a and b for which: a2 + b2 ≡ 2018 (modulo 4) or more simply: a2 + b2 ≡ 2 (modulo 4). Since every perfect square is either a multiple of 4 or else one more than a multiple of 4, then the only possible solution is that a and b are both odd numbers. Using modular arithmetic with modulus 5, the problem also becomes a matter of finding integers a and b for which: a2 + b2 ≡ 2018 (modulo 5) or more simply: a2 + b2 ≡ 3 (modulo 5). The squares modulo 5 are 0, 1, and 4. The only combination that works is: (a2, b2) ≡ (4, 4) modulo 5. This means that a and b are congruent to 2 or 3 modulo 5. Values of a and b should be found among: 2, 3, 7, 8, 12, 13, 17, 18, ... Since a and b must also be odd integers, we may therefore use trial and error using only the numbers: 3, 7, 13, 17, ... Upon using trial and error, after trying b = 3 and 7, we find that b = 13 works, with a value of a = 43 being the other value. Since the problem statement says that the original equation has exactly one solution with a > b, then: (a, b, c) = (43, 13, 1) is the only solution, and therefore a + b + c = 57, and: The solution is: (B), a + b + c = 57 is the answer 5. Solution by CwH. If M is the smallest positive integer that has a remainder of 2 when divided by 3 and has remainder of 4 when divided by 5, we can find M easily by first looking at numbers of the form: 5𝑘 + 4: 4, 9, 14, …. We see quickly that 𝑀 = 14 is the smallest integer having a remainder of 2 when it is divided by 3. Thus, 𝑀 = 14. Now, N is the smallest positive integer that has a remainder of 6 when divided by 7 and has remainder of 8 when divided by 9. We can find N the same way as above. But let us try a different method. From the given conditions, we may represent N as: 𝑁 = 7𝑝 + 6 and 𝑁 = 9𝑞 + 8. Multiply the first equation by 9 and the second equation by 7 and subtract to get 2𝑁 = 63 𝑝 − 𝑞 − 2. Note that both 2𝑁 and 2 are even integers, so 𝑝 − 𝑞 must be an even integer. Let 𝑝 − 𝑞 = 2𝑘 and the above equation can be reduced to 𝑁 = 63𝑘 − 1. The smallest such N is when 𝑘 = 1 and 𝑁 = 62. Thus, 𝑀 + 𝑁 = 14 + 62 = 76. The answer is (D). 5. Second solution by GM. Let M be the smallest positive integer that has a remainder of 2 when divided by 3 and has a remainder of 4 when divided by 5. Let N be the smallest positive integer that has a remainder of 6 when divided by 7 and has a remainder of 8 when divided by 9. Find M+N. Solution: The problem can be framed in terms of modular arithmetic: First, a quick definition. The notation 𝑀 ≡ 2 𝑚𝑜𝑑𝑢𝑙𝑜 3 means that the integer M leaves remainder 2 when divided by 3. So for example, the following numbers: 2,5,8,11,14, ⋯ are all congruent to 2 modulo three since they all leave remainder 2 when divided by 3. They are all in the same equivalence class. We are given the following four conditions: M ≡ 2 (modulo 3) and M ≡ 4 (modulo 5) N ≡ 6 (modulo 7) and N ≡ 8 (modulo 9). All 4 congruences can be restated as: M + 1 ≡ 0 (modulo 3) and M + 1 ≡ 0 (modulo 5) N + 1 ≡ 0 (modulo 7) and N + 1 ≡ 0 (modulo 9). Note that when 𝑀 + 1 ≡ 𝑚𝑜𝑑𝑢𝑙𝑜 3 , it means that 𝑀 + 1 is a multiple of three, leaving remainder zero, so: 𝑀 + 1 = 0,3,6,9,12, ⋯ These are easily solved since M and N must be the smallest positive integers satisfying the four conditions. We find: M + 1 = 3 × 5 = 15 and N + 1 = 7 × 9 = 63. M = 14 and N = 62. Thus: The solution is: (D), M + N = 76 6. Solution by CwH. We are told that the student 1 opens all the doors of 200 lockers, the student 2 closes the doors of all the even numbered lockers, and student 3 reverses the door of all the lockers whose number is a multiple of 3, and so on for all the 200 students. The question is how many lockers are left open at the end of this process. We first note that for the nth locker, the number d student will touch its door if and only if d is a divisor of n (including the case when 𝑑 is 𝑛 𝑜𝑟 1). Since the first student opens all the lockers, we note that a locker will remain open at the end if and only if it is touched by an odd number of students. Thus, in mathematical terms, we need only find those positive integers with an odd number of divisors. A moment’s reflection will convince us that only a perfect square will have an odd number of divisors since the factors of a positive integer 𝑁 always come in pairs: whenever 𝑁 = 𝑎𝑏, one of the two factors a and b, will be greater than 𝑁, and the other less than 𝑁, unless when 𝑁 is a perfect square. In that case a and b may be the same number. Since 15! = 225 is greater than 200, there can only be 14 perfect squares less than 200: the squares of 1, 2, 3, …, 14. Thus, 14 lockers will remain open and the answer is (A). 6. Second solution by GM. There are 200 closed lockers numbered 1-200 in a locker room. Student 1 goes in and opens each locker, then student 2 goes in and closes every other locker (2, 4, 6, 8…). Student 3 then changes the state (opens it if it is closed, closes it if it is open) of every third locker (3, 6, 9, 12…), then student 4 does the same for every fourth locker (4, 8, 12, 16…). This continues until 200 students have gone through, with the nth student changing the state of all lockers numbered with a multiple of n. How many lockers are open at the end? Solution: At the start, every locker is closed. The d-th student will change the state of the locker (open it if it is closed, or close it if it is open) when d is a factor of the locker number n. If the locker number n is factored into a prime power factorization: ! ! ! ! 𝑛 = 𝑝!! 𝑝!! 𝑝!! ⋯ 𝑝!! where the 𝑝! are distinct primes and the 𝑒! are the exponents on those primes, then I claim that the total number of factors of n is given by: 𝑓! = 𝑒! + 1 𝑒! + 1 ⋯ 𝑒! + 1 (1) To see this, consider a number whose factorization has just two primes: 𝑛 = 𝑞 ! 𝑝! where q and p are the two primes and a and b are positive integers. There are 𝑎 + 1 factors of n that include only q: 𝑞 ! , 𝑞! , 𝑞 ! , ⋯ 𝑞 ! and similarly there are 𝑏 + 1 factors containing only p. To get all possible factors, we multiply each factor in the “q” list in turn with each factor in the “p” list. This gives a total of 𝑎 + 1 𝑏 + 1 factors. This can be extended to three primes. Suppose the third prime has exponent c. By taking the number of possible factors involving two primes and multiplying it by the number 𝑐 + 1 of factors involving only the third prime, giving the result: 𝑎 + 1 𝑏 + 1 𝑐 + 1 . This pattern can be continued to any number of prime factors, so by informal inductive proof, equation (1) is valid. In order for the door of locker number n to remain open after 200 students change the state of the locker, fn in equation (1) must be an odd number. Otherwise the door of locker number n will be closed. We claim that fn will be odd only when each factor of the right side of equation (1) is an odd number. This requires all of e1, e2, e3, ... em to be even. If e1, e2, e3, ... em are all even, then n is a perfect square. Consequently, the door of locker number n will remain open at the end, precisely when n is a perfect square, and will remain closed when n is not a perfect square. There are 14 perfect squares from 1 through 200. Therefore, exactly 14 locker doors will remain open. The solution is: (A), 14 7. Solution by CwH. A function 𝑓 is defined to be linear if 𝑓 𝑎𝑥 = 𝑎𝑓 𝑥 𝑎𝑛𝑑 𝑓 𝑥 + 𝑦 = 𝑓 𝑥 + 𝑓 𝑦 . According to this definition, 𝑓! 𝑥 = 3𝑥 is linear since it satisfies both required conditions; 𝑓! 𝑥 = 3𝑥 + 2 is not linear since it violates the condition 𝑓 𝑥 + 𝑦 = 𝑓 𝑥 + 𝑓 𝑦 . 𝑓! 𝑥 = 2 is not linear since it violates the condition 𝑓(𝑎𝑥) = 𝑎𝑓 𝑥 . 𝑓! 𝑥 = 0 is linear since it satisfies both required conditions. Thus, only two of the four functions are linear. The answer is (C). 7. Second solution by GM. In some contexts, a function is defined to be linear if for all elements x and y in the domain and for all real numbers a, f(a·x) = a·f(x) and f(x + y) = f(x) + f(y). Using this definition of linear, how many of the following functions from ℝ to ℝ are linear? f1(x) = 3x, f2(x) = 3x + 2, f3(x) = 2, f4(x) = 0 Solution: Since f2(0) = 3·0 + 2 = 2 and f2(0) + f2(0) = 2 + 2 = 4. Therefore f2(0) = f2(0 + 0) does not equal f2(0) + f2(0), and thus f2(x) is not linear. The same argument applies to f3(x). f3(0) = 2 and f3(0) + f3(0) = 2 + 2 = 4. Therefore f2(0) = f2(0 + 0) does not equal f2(0) + f2(0), and thus f3(x) is not linear. However, with f1(x) = 3x, f1(a·x) = 3a·x = a(3x) = a·f1(x). Thus the first requirement is met. And f1(x + y) = 3(x + y) = 3x + 3y = f1(x) + f1(y). And the second requirement is met. The domain for f1(x) is all real numbers, thus none of the values computed are computed outside its domain. Therefore, f1(x) is linear by definition. Also, for f4(x) = 0, f4(a·x) = 0 = a(0) = a·f4(x). Thus the first requirement is met. And f4(x + y) = 0 = 0 + 0 = f4(x) + f4(y). And the second requirement is met. The domain for f4(x) is all real numbers, thus none of the values computed are computed outside its domain. Therefore, f4(x) is linear by definition. The solution is: (C), 2. [f1(x) and f4(x)] 8. Solution by CwH. Find the sum of all eight digits base-10 numbers consisting of digits 0 and 1, but the leading digit is not allowed to by zero. Since the leading digit is not allowed to be zero, all the numbers allowed in this problem will contain a leading 1, but the digits at all the other 7 remaining positions can be either a zero or a one. With 2 possible choices for digits in all the other 7 positions, there are 2! such numbers. Since the leading 1 is the highest digit in these 8-digit numbers, it carries a place value of 10! . Thus, when we sum up all the 8 digits numbers their leading one will contribute a value of 2! 10! = 1,280,000,000 towards the sum. How many numbers possess a 1 at the second position? Since the leading digit has to be a 1 and now the second digit is also a 1, but we still have free choices for any of the remaining digits: 2 choices for each of the remaining 6 positions. Thus, there are 2! such numbers. Since the 1 at the second position carries a place value of 10! , when we sum up all the numbers these 1’s at the second place will contribute a value of 2! 10! . Note that the numbers with a 1 at the second place are also included among the numbers with a leading one, but in the sum of 2! 10! we considered only the contribution from the leading digits, and not from any other digits. The same argument works for a 1 in the other places. A 1 at the leading place and at the place considered, but we have free choices in any of the other remaining 6 places. There are again 2! numbers with a 1 at any given place, however, the place value may be of a lower power of 10. Thus, when we sum up all these numbers, the total sum will then be: 2! 10! + 2! 10! + 10! + ⋯ + 10! + 10 + 1 = 2! 10! + 2! !"! !! !"!! = 2! 10! + 2! 1,111,111 = 1,280,000,000 + 71.111,104 = 1,351,111,104. The answer is (D). 8. Second solution by MF. First, we have to find out how many eight-digit numbers there can be using only zero’s and one’s and with the leading digit a one. So the leading slot can be filled in only one way, while the other seven slots can each be filled in two ways. This gives the possible number of eight-digit numbers as: 2! = 128 1 Visualize these numbers placed in a vertical list with the places lined up into vertical columns. Consider the sum of the one’s places in the sum of all 128 of these numbers. By symmetry, one-half of the one’s places in the numbers will be ones and the other half will be zeros, so the sum of the column of one’s places will add up to 64. In doing the addition, you will place a “4” in the one’s place of the sum and carry the “6”. Again by symmetry, the sum of the column of ten’s places will also be 64, but we add six from the carry, so the ten’s column adds up to 70. So the ten’s place in the sum will be a “0” and we carry the “7”. So far, the last two digits of the desired sum are “04”. Now for the hundred’s column, which also sums to 64, we add the “7” from the ten’s place carry to get 71. It follows that the hundred’s place in the desired sum will be a “1” and the last three digits of our sum is now “104”. But now note that we are in a repeating pattern, since the thousand’s place will add up to 71, as will the ten thousand’s place, etc. because the column adds to 64 and we keep having a “7” carried from the previous column. This means that our sum will have “1”s until we reach the leading column. So the last seven digits of the sum must be like this: 1111104 2 Since the leading column is all ones, it must add up to 128, but we have carried a “7” from the previous column, so the sum is 128 + 7 = 135. So the first three digits of the desired sum must be “135”. We put this to the left of the seven digits we found in equation (2) and the final sum is: 1351111104 (3) and the answer is (D). 8. Third solution by GM. Find the sum of all base-10 eight-digit (the first digit cannot be zero) numbers that contain no digits other than 0 or 1 (for example: 10100101, 10000000, 11111111). Solution: All of the eight-digit base-10 numbers must begin with a 1 (in what I will refer to as the first position). The remaining 7 digits are combinations of zeros and ones. There are two choices (0 or 1) for the digit in each of the remaining 7 positions. Thus, there are 27 = 128 many eight-digit base-10 numbers with a 1 in the first position. In the n-th position (2 ≤ n ≤ 8), 64 of those numbers have a 1 in that position and the remaining 64 numbers have a 0 in the n-th position. The tally of just the digits of all 128 of those numbers in the n-th position (2 ≤ n ≤ 8) is of course 64. The tally of the first digit of all 128 of those numbers is 128. Thus, the sum of all 128 eight-digit base-10 numbers is: 128 × (10,000,000) + 64 × (1,111,111) = 1,351,111,104 The solution is: D, 1,351,111,104.