CEMC Banner

2022 Galois Contest
Solutions
(Grade 10)

Tuesday, April 12, 2022
(in North America and South America)

Wednesday, April 13, 2022
(outside of North American and South America)

©2022 University of Waterloo


    1. The ratio of Alice’s contribution to Bello’s contribution was 3:8.
      This means that for every $3+$8=$11 contributed to starting the business, Bello contributed $8, and so Bello contributed 811 of the cost of starting the new business.
      If the cost of starting the new business was $9240, then Bello’s contribution to this cost was 811×$9240=$6720.

    2. The ratio of Alice’s share of the first year profits to Bello’s share was 3:8.
      This means that for every $3+$8=$11 of profit in the first year, Alice’s share was $3.
      Let the first year profit be $P.
      Since Alice’s share of the first year profit was $1881, then 311×P=1881 or P=1881×113, and so P=206913=6897.
      The total profit of the business for the first year was $6897.

    3. The ratio of Alice’s share of the second year profits to Bello’s share was 3:(8+x).
      This means that for every $3+$(8+x)=$(11+x) of profit in the second year, Bello’s share was $(8+x).
      Since Bello’s share of the second year profit was $5440, and the profit that year was $6400, then (8+x)(11+x)×6400=5440.
      Solving this equation, we get (8+x)(11+x)×6400=54406400(8+x)=5440(11+x)20(8+x)=17(11+x)(dividing both sides by 320)160+20x=187+17x3x=27 and so x=9.

    1. Line L1 has equation y=32x+k, and thus has slope 32.
      Since L2 is perpendicular to L1, then its slope is 23.

    2. Since L1 has equation y=32x+k, its y-intercept is k.
      Line L2 has the same y-intercept as L1 (which is at P(0,k)).
      Thus, L2 has slope 23 and y-intercept k, and so it has equation y=23x+k.
      Since L2 intersects the x-axis at Q, the x-coordinate of point Q is the x-intercept of L2.
      Setting y=0 in the equation for L2 and solving for x, we get 0=23x+k or 23x=k, and so x=3k2.
      Written in terms of k, the x-coordinate of point Q is 3k2.

    3. From part (b), the coordinates of P are (0,k), and the coordinates of Q are (3k2,0).
      To determine an expression for the area of PQR, we first need to determine the coordinates of point R.
      L3 is parallel to L1 and thus has slope 32 and equation y=32x+b, for some y-intercept b.
      Line L3 passes through point Q(3k2,0), and so 0=32(3k2)+b or b=9k4.
      Therefore the y-intercept of L3 is 9k4 and so R has coordinates (0,9k4).

      If we call the origin O(0,0), then the area of PQR is given by 12×PR×OQ, since height OQ is perpendicular to the base PR.
      Since PR=k(9k4)=13k4 and OQ=3k2, then the area of PQR is 12×13k4×3k2=39k216.
      The area of PQR is 351, and so 39k216=351 or k2=351×1639 or k2=144, and so k=12 (since k>0).

    1. We begin by recognizing that a number is a perfect square if the exponent on each prime factor in its prime factorization is even, and conversely that the prime factorization of every perfect square has an even exponent on each prime factor.
      The prime factorization of 84 is 22×3×7.
      For the product 84×k=22×3×7×k to be a perfect square, k must at least include 3 and 7 as prime factors (since the exponent on each is an odd number), and so k must be divisible by 21.
      If k=3×7, then 84×k is a perfect square because 84×3×7=22×32×72=(2×3×7)×(2×3×7). Thus, the smallest value of the positive integer k for which 84×k is a perfect square is k=3×7=21.

    2. The prime factorization of 572 is 22×11×13, and so must at least include 11 and 13 as prime factors (since the exponent on each is an odd number).
      Since 572× is a perfect square, then any factor of in addition to 11 and 13 must be a perfect square.
      That is, is a number of the form 11×13×n2 for some positive integer n, because 572×=572×11×13×n2=(2×11×13×n)×(2×11×13×n). Since =11×13×n2=143n2 and <6000, then 143n2<6000, and so n2<600014341.96.
      The greatest value of the positive integer n for which n241 is n=6.
      Therefore, the greatest possible value of is 11×13×62=5148.

    3. The prime factorization of 525 000 is 23×3×55×7, and so if 525000×m is a perfect square, then m must at least include 2,3,5, and 7 as prime factors (since the exponent on each is an odd number).
      If m includes the prime factors 2, 3, 5, and 7, then m is greater than or equal to 2×3×5×7=210.
      Therefore, if m is a positive integer less than 200, then 525000×m cannot be a perfect square.

    4. Suppose that the three powers of 10 chosen from the list are 10a,10b, and 10c, where a,b,c are odd positive integers between 1 and 99 inclusive, and a<b<c.
      Since a<b and a<c, the sum of these three powers, S=10a+10b+10c, can be factored so that S=10a(1+10ba+10ca).
      Since ba is a positive integer, then 10ba is an even positive integer.
      Similarly, 10ca is an even positive integer, and so 1+10ba+10ca is an odd positive integer.
      Thus for some odd positive integers a,b,c, and d, S=10a(1+10ba+10ca)=10a×d=(2×5)a×d=2a×5a×d Since d is an odd integer, then 2 is not a prime factor of d, and so the prime factor 2 occurs an odd number of times in the prime factorization of S (since a is odd).
      Therefore, the sum of every choice of three different powers of 10 from the list is not a perfect square.

    1. Solution 1

      For each Bauman string of length 5 in which the first and last letters are both A, the second and fourth letters are not A.
      For such Bauman strings, either the third letter is A, or the third letter is not A.

      Case 1: The third letter is A.

      In this case, the string is of the form AAA.
      There are 4 choices for the second letter (B,C,D, or E) and 4 choices for the fourth letter, and so there are 4×4=16 such Bauman strings.

      Case 2: The third letter is not A.

      In this case, the string is of the form AxA, where the third letter x is B,C,D, or E, and so there are 4 choices for the third letter.
      The second letter must be different than the third letter and must not be A, and so there are 3 choices for the second letter.
      Similarly, there are 3 choices for the fourth letter, and so there are 4×3×3=36 such Bauman strings.

      In total, the number of Bauman strings of length 5 in which the first and last letters are both A is 16+36=52.

      Solution 2

      For each Bauman string of length 5 in which the first and last letters are both A, either the second and fourth letters are the same, or they are different.

      Case 1: The second and fourth letters are the same.

      In this case, the string is of the form AxxA.
      There are 4 choices for the second letter (B,C,D, or E) and 1 choice for the fourth letter since it is the same as the second letter.
      The third letter must be different than the second and fourth letters (which are the same) and so there are 4 choices for the third letter.
      Thus, there are 4×1×4=16 such Bauman strings.

      Case 2: The second and fourth letters are different.

      In this case, the string is of the form AxyA, where x and y represent different letters.
      There are 4 choices for the second letter (B,C,D, or E) and 3 choices for the fourth letter (it is different than the second letter and not A).
      The third letter must be different than the second and fourth letters (which are different) and so there are 3 choices for the third letter.
      Thus, there are 4×3×3=36 such Bauman strings.

      In total, the number of Bauman strings of length 5 in which the first and last letters are both A is 16+36=52.

    2. Solution 1

      We may determine the number of Bauman strings of length 6 that contain more than one B indirectly.
      That is, we may subtract the number of Bauman strings that contain 0 B’s and the number of Bauman strings that contain exactly 1 B from the total number of Bauman strings of length 6.

      For a Bauman string of length 6 (with no restrictions), there are 5 choices for the first letter and 4 choices for each of the remaining letters, and so there are a total of 5×45=5120 such strings.

      For a Bauman string of length 6 that contains 0 B’s, there are 4 choices for the first letter and 3 choices for each of the remaining letters, and so there are a total of 4×35=972 such strings.

      Next, we count the number of Bauman strings that contain exactly 1 B.
      If the first letter of the string is a B, then there are 4 choices for the second letter and 3 choices for each of the remaining four letters.
      Similarly, if the last letter is a B, then there are 4 choices for the letter adjacent to the B and 3 choices for each of the remaining four letters.
      Thus, there are 1×4×34=324 strings that begin with a B and 324 strings that end with a B.
      If the second letter of the string is a B, then there are 4 choices for the first letter, 4 choices for the third letter, and 3 choices for each of the fourth, fifth and sixth letters.
      Thus, there are 4×1×4×33=432 such strings.
      Similarly, if the third, fourth or fifth letter in the string is a B, then there are 432 such strings.

      In total, there are 51209722×3244×432=1772 Bauman strings of length 6 that contain more than one B.
      Solution 2

      A Bauman string of length 6 cannot contain more than 3 B’s (confirm for yourself why this is true before proceeding).
      We may determine the number of Bauman strings of length 6 that contain more than one B directly.
      That is, we may count the number of strings that contain exactly 3 B’s and the number of strings that contain exactly 2 B’s.
      Thus, there are two cases to consider.

      Case 1: The Bauman string has exactly 3 B’s

      In this case, the string must take one of four possible forms: BBB,  BBB,  BBB,  BBB. We begin by counting the number of strings of the form BBB.
      There are 4 choices for the second letter (A,C,D, or E), 4 choices for the fourth letter, and 4 choices for the sixth letter, and so there are 43=64 such strings.
      Similarly, there are 43=64 strings of the form BBB.
      It is worth noting that BBB and BBB have identical forms when one is read left to right and the other right to left.
      We may call such pairs of forms symmetric, and recognize that under the same restrictions, symmetric forms have an equal number of Bauman strings.

      For strings of the form BBB, there are 4 choices for the second letter, 4 choices for the fourth letter, and 3 choices for the fifth letter (since the fifth letter must be different than B and different than the fourth letter, which is not B), and so 42×3=48 such strings.
      Since BBB is symmetric to BBB, there are similarly 42×3=48 strings of this form.
      Thus, there are 2×64+2×48=224 Bauman strings with exactly 3 B’s.

      Case 2: The Bauman string has exactly 2 B’s

      In this case, the string must take one of ten possible forms.
      Eight of these occur in one of the following four symmetric pairs BB and BBBB and BB, BB and BBBB and BB and the final two forms (which are not a symmetric pair) are BB and  BB. We begin by counting the number of strings of the form BB.
      There are 4 choices for the second letter (A,C,D, or E), 4 choices for the fourth letter, 3 choices for each of the fifth and sixth letters, and so there are 42×32=144 such strings.
      Similarly, there are 42×32=144 strings for each of the next five forms listed above, BB,BB,BB,BB, and BB.

      For strings of the form BB, there are 4 choices for the first letter, 4 choices for the third letter, 4 choices for the fifth letter, and 3 choices for the sixth letter, and so there are 43×3=192 such strings.
      Since BB is symmetric to BB, there are similarly 43×3=192 strings of this form.

      Finally, there are 4×33=108 strings of the form BB, and 43×3=192 strings of the form BB.
      Thus, there are 6×144+2×192+108+192=1548 Bauman strings with exactly 2 B’s.

      In total, there are 224+1548=1772 Bauman strings of length 6 that contain more than one B.

    3. Solution 1

      Consider all Bauman strings of length n that begin with C.
      There are 4 choices for each of the remaining n1 letters, and so there are 4n1 such Bauman strings.
      Each of these strings either ends with D, or it does not end with D.
      We call those that end with D, dn, and we define |dn| to be the number of such strings.
      Similarly, we call those that do not end in D, xn, and we define |xn| to be the number of such strings.
      For example, d1 represents the Bauman strings of length 1 that begin with C and end with D, and since no such string exists, then |d1|=0.
      Similarly, x1 represents the Bauman strings of length 1 that begin with C and do not end with D, and so |x1|=1 (the string is C).
      We may confirm that 4n1=|dn|+|xn| when n=1, since 411=|d1|+|x1|=0+1.
      Further, we know that |d2|=1 (the string is CD), and |x2|=3 (the strings are CA, CB, CE), and again confirm that 421=1+3.

      Next, consider the Bauman strings of length n that begin with C and do not end with D, that is, xn.
      Each of these strings could have a D added to its end to form a Bauman string of length n+1 that begins with C and ends with D, or dn+1.
      Since adding a D to the end of every string xn gives all possible strings dn+1, then |dn+1|=|xn|.
      From our earlier work, we may confirm that |d2|=|x1|=1.

      Further, |xn+1|=4|dn|+3|xn|. Why is this true?
      Every Bauman string of length n+1 that begins with C and does not end with D, that is xn+1, is either a string dn with an A, B, C, or E added to its end, or it is a string xn that has a choice of 3 letters added to its end (the letter added can not be D and it can not be the last letter of xn, leaving 3 possibilities).
      The number of strings dn that have A, B, C, or E added to its end is 4|dn|.
      The number of strings xn that have a choice of 3 letters added to its end is 3|xn|.
      Therefore, we conclude that |xn+1|=4|dn|+3|xn|.
      From our earlier work, we may confirm that |x2|=4|d1|+3|x1|=4(0)+3(1)=3.
      We use these two formulas |dn+1|=|xn| and |xn+1|=4|dn|+3|xn|, which are equivalent to |dn|=|xn1| and |xn|=4|dn1|+3|xn1|, to build the table below.

      n |dn|=|xn1| |xn|=4|dn1|+3|xn1|
      1 |d1|=0 |x1|=1
      2 |d2|=1 |x2|=3
      3 |d3|=|x2|=3 |x3|=4|d2|+3|x2|=4(1)+3(3)=13
      4 |d4|=|x3|=13 |x4|=4|d3|+3|x3|=4(3)+3(13)=51
      5 |d5|=51 |x5|=4(13)+3(51)=205
      6 |d6|=205 |x6|=4(51)+3(205)=819
      7 |d7|=819 |x7|=4(205)+3(819)=3277
      8 |d8|=3277 |x8|=4(819)+3(3277)=13107
      9 |d9|=13107 |x9|=4(3277)+3(13107)=52429
      10 |d10|=52429 not needed

      Therefore, the number of Bauman strings of length 10 in which the first letter is C and the last letter is D is 52 429.

      Solution 2

      Let Sn be the set of Bauman strings of length n in which the first letter is C and the last letter is D.
      Further, we define |Sn| to be the number of such strings.
      For example, S2={CD} and so |S2|=1, and S3={CAD,CBD,CED} and so |S3|=3.
      Each string in S10 is of the form CD or CT8D where T8 is a Bauman string of length 8 that does not begin with C and does not end with D.
      Therefore, |S10|=|T8|. The number of such strings, |T8|, is equal to the total number of Bauman strings of length 8the number of Bauman strings of length 8 that begin with Cthe number of Bauman strings of length 8 that end with D+the number of Bauman strings of length 8 that begin with C and end with D In the above, we note that strings beginning with C include those that end with D, as well as others.
      Similarly, strings that end with D include those that begin with C, as well as others.
      Since we have subtracted the number of strings that begin with C and end with D twice from the total, we conclude by adding the number of such strings.

      For a Bauman string of length 8, there are 5 choices for the first letter and 4 choices for each of the remaining 7 letters.
      Thus, the total number of Bauman strings of length 8 is equal to 5×47.
      For a Bauman string of length 8 that begins with C, there is 1 choice for the first letter and 4 choices for each of the remaining 7 letters.
      Thus, the total number of Bauman strings of length 8 that begin with C is equal to 1×47.
      Also, the total number of Bauman strings of length 8 that end with D is equal to 1×47.
      The number of Bauman strings of length 8 that begin with C and end with D is equal to |S8|.
      Therefore, we get |S10|=|T8|=5×471×471×47+|S8|=3×47+|S8| and so the number of Bauman strings of length 10 that begin with C and end with D is dependent on the number of Bauman strings of length 8 that begin with C and end with D.
      At this point, we could repeat the process above to determine |S8|, however it may be more efficient to generalize the work above to determine a formula for |Sn|.

      For integers n3, each string in Sn is of the form CTn2D where Tn2 is a Bauman string of length n2 that does not begin with C and does not end with D.
      The number of such strings, |Tn2|, is equal to the total number of Bauman strings of length n2the number of Bauman strings of length n2 that begin with Cthe number of Bauman strings of length n2 that end with D+the number of Bauman strings of length n2 that begin with C and end with D For a Bauman string of length n2, there are 5 choices for the first letter and 4 choices for each of the remaining n3 letters.
      Thus, the total number of Bauman strings of length n2 is equal to 5×4n3.
      For a Bauman string of length n2 that begins with C, there is 1 choice for the first letter and 4 choices for each of the remaining n3 letters.
      Thus, the total number of Bauman strings of length n2 that begin with C is equal to 1×4n3.
      Also, the total number of Bauman strings of length n2 that end with D is equal to 1×4n3.
      The number of Bauman strings of length n2 that begin with C and end with D is equal to |Sn2|.
      Therefore, we get |Sn|=|Tn2|=5×4n31×4n31×4n3+|Sn2|=3×4n3+|Sn2|, for integers n3. Using this recursive formula and the fact that |S2|=1, we get |S4|=3×443+|S42|=3×4+|S2|=13|S6|=3×463+|S62|=3×43+|S4|=205|S8|=3×483+|S82|=3×45+|S6|=3277|S10|=3×4103+|S102|=3×47+|S8|=52429 The number of Bauman strings of length 10 in which the first letter is C and the last letter is D is 52 429.