2019 Galois Contest
Solutions
(Grade 10)

Wednesday, April 10, 2019
(in North America and South America)

Thursday, April 11, 2019
(outside of North American and South America)

©2019 University of Waterloo

1. 1. The total of the listed prices is $\mathrm{\$}7.50+\mathrm{\$}5.00+\mathrm{\$}3.00=\mathrm{\$}15.50$.

      Sales tax of 10% on $\mathrm{\$}15.50$ is equal to $\mathrm{\$}15.50\times 0.10=\mathrm{\$}1.55$.

      After sales tax is included, the total of Becky’s bill is $\mathrm{\$}15.50+\mathrm{\$}1.55=\mathrm{\$}17.05$.

      Alternately, we could add 10% sales tax directly to Becky’s bill by multiplying$\mathrm{\$}15.50\times 1.10=\mathrm{\$}17.05$.

   2. After 10% sales tax is included, the cost of one $6.00 burrito is $\mathrm{\$}6.00\times 1.10=\mathrm{\$}6.60$.

      At a cost of $6.60 for each burrito, the total cost of 7 burritos is $\mathrm{\$}6.60\times 7=\mathrm{\$}46.20$, and the total cost of 8 burritos is $\mathrm{\$}6.60\times 8=\mathrm{\$}52.80$.

      Since Jackson has $50.00, the greatest number of burritos that he can buy is 7.

   3. On Monday, Chase spent $\mathrm{\$}5.00+\mathrm{\$}4.50=\mathrm{\$}9.50$ plus 10% tax for two hotdogs.

      Including tax, Chase spent $\mathrm{\$}9.50\times 1.10=\mathrm{\$}10.45$ on Monday.

      On Tuesday, Chase spent $\mathrm{\$}5.00+\mathrm{\$}5.00=\mathrm{\$}10.00$ plus 5% tax for two hotdogs.

      Including tax, Chase spent $\mathrm{\$}10.00\times 1.05=\mathrm{\$}10.50$ on Tuesday.

      Thus, Chase spent less money on Monday.

2. 1. The $y$-intercept of the line with equation $y=-2x+12$ is 12 and so $OA=12$.

      The $x$-intercept of this line is determined by letting $y=0$ and solving for $x$. We get $0=-2x+12$ or $2x=12$ and so $x=6$.

      The $x$-intercept is 6, and so $OB=6$.

      The area of $\mathrm{△}AOB$ is ${\displaystyle \frac{1}{2}}(OB)(OA)={\displaystyle \frac{1}{2}}(6)(12)=36$.

      

   2. Solution 1

      We begin by determining the equation of the line passing through $O$ and $C$.

      This line is perpendicular to the line with equation$y=-2x+12$, and so its slope is the negative reciprocal of $-2$, which is ${\displaystyle \frac{1}{2}}$.

      This line passes through the origin and so it has $y$-intercept 0 and equation $y={\displaystyle \frac{1}{2}}x$.

      

      Point $C$ is the point of intersection of the lines $y={\displaystyle \frac{1}{2}}x$ and $y=-2x+12$.

      Substituting the equation of the first line into the second, we get ${\displaystyle \frac{1}{2}}x=-2x+12$ or ${\displaystyle \frac{5}{2}}x=12$ and so $x={\displaystyle \frac{24}{5}}$.

      When $x={\displaystyle \frac{24}{5}}$, the equation $y={\displaystyle \frac{1}{2}}x$ gives $y={\displaystyle \frac{1}{2}}\left({\displaystyle \frac{24}{5}}\right)={\displaystyle \frac{12}{5}}$, and so the coodinates of $C$ are $({\displaystyle \frac{24}{5}},{\displaystyle \frac{12}{5}})$.

      Solution 2

      As in Solution 1, we begin by recognizing that the line passing through $O$ and $C$ has slope ${\displaystyle \frac{1}{2}}$.

      Point $C$ lies on the line with equation $y=-2x+12$ and so if the $x$-coordinate of $C$ is $a$, then the $y$-coordinate is $-2a+12$.

      The slope of the line through $O(0,0)$ and $C(a,-2a+12)$ is ${\displaystyle \frac{-2a+12}{a}}$ and must equal ${\displaystyle \frac{1}{2}}$.

      

      Solving, we get ${\displaystyle \frac{-2a+12}{a}}={\displaystyle \frac{1}{2}}$ or $2(-2a+12)=a$ or $24=5a$, and so $a={\displaystyle \frac{24}{5}}$.

      When $a={\displaystyle \frac{24}{5}}$, we get $-2a+12=-2\left({\displaystyle \frac{24}{5}}\right)+12=-{\displaystyle \frac{48}{5}}+12={\displaystyle \frac{12}{5}}$, and so the coordinates of $C$ are $({\displaystyle \frac{24}{5}},{\displaystyle \frac{12}{5}})$.

   3. From part (b) Solution 1, the equation of the line passing through $O$ and $C$ is $y={\displaystyle \frac{1}{2}}x$. Point $D$ lies on this line and so if the $x$-coordinate of $D$ is $n$, then the $y$-coordinate of $D$ is ${\displaystyle \frac{1}{2}}n$, so $D$ has coordinates $(n,{\displaystyle \frac{1}{2}}n)$.

      

      Point $E$ lies vertically below $D$ and thus has the same $x$-coordinate as $D$.

      That is, the coordinates of $E$ are $(n,0)$ and so $OE=n$.

      Similarly, $F$ is positioned horizontally from $D$ and thus has the same $y$-coordinate as $D$.

      That is, the coordinates of $F$ are $(0,{\displaystyle \frac{1}{2}}n)$ and so $OF={\displaystyle \frac{1}{2}}n$.

      The area of $DEOF$ is 1352, and so $(OE)(OF)=1352$ or $n\left({\displaystyle \frac{1}{2}}n\right)=1352$ or $n^2=2704$, and so $n=\sqrt{2704}=52$ (since $n>0$), and ${\displaystyle \frac{1}{2}}n=26$.

      If the area of $DEOF$ is 1352, the coordinates of $D$ are $(52,26)$.

3. 1. This question is asking for the greatest number of factors of 2 in 9!.

      Expressing 9! as a product of prime factors, we get $$9!=9(8)(7)(6)(5)(4)(3)(2)(1)=(3^2)(2^3)(7)(2\cdot 3)(5)(2^2)(3)(2)(1).$$ Simplifying, $9!=7(5)(3^4)(2^7)$ and so 7 is the largest positive integer $m$ for which $2^m$ is a divisor of 9!.

   2. To be divisible by $7^2$, $n!$ must have at least two factors of 7.

      Multiples of 7 are the only integers which have a factor of 7.

      The smallest positive multiples of 7 are 7 and 14, and each of these contributes exactly one 7 to the prime factorization of 14!, and so if $n\le 13$, then $n!$ cannot possibly have two factors of 7.

      Thus, the smallest value of $n$ for which $n!$ is divisible by $7^2$ is 14.

   3. A positive integer equal to $n!$ is divisible by $7^7$ but not by $7^8$ if it has exactly seven 7s in its prime factorization (in addition to having other prime factors).

      Multiples of 7 are the only integers which have a factor of 7.

      The first six positive multiples of 7 $(7,14,21,28,35,42)$, each have exactly one factor of 7, and thus each contributes exactly one 7 to the prime factorization of 42!.

      That is, 42! is divisible by $7^6$ but not by $7^7$ and so $n>42$.

      The next value of $n>42$ which is a multiple of 7 (and thus contributes 7s to its prime factorization) is 49.

      However, 49 contributes two additional 7s to the prime factorization of 49! (since $49=7^2$), and so 49! is divisible by $7^{6+2}=7^8$.

      For each positive integer $n\ge 49$, $n!$ is divisible by $7^8$ and possibly some higher power of 7.

      For each positive integer $n<49$, the greatest power of 7 that divides $n!$ is at most $7^6$.

      Thus, there is no positive integer $n$ for which $n!$ is divisible by $7^7$ but is not divisibleby $7^8$.

   4. Multiples of 13 are the only integers which have a factor of 13.

      Since $n!$ has two factors of 13, then $n$ must be at least 26 (one factor from 13 and a second from 26).

      Since 29 is a prime number and does not appear in the prime factorization of $n!$, then $n\le 28$.

      We note that for each of the possible values $n=26,27$ and $28$, $n!$ has two factors of 11, two factors of 13, and one factor of each of 17,19 and 23, as required.

      In the table below, we determine the number of factors of $2,3,5$, and 7 in $26!$.

      Numbers containing factors of 2	2	4	6	8	10	12	14	16	18	20	22	24	26
      Number of factors of 2 in each	1	2	1	3	1	2	1	4	1	2	1	3	1

      Numbers containing factors of 3	3	6	9	12	15	18	21	24
      Number of factors of 3 in each	1	1	2	1	1	2	1	1

      Numbers containing factors of 5	5	10	15	20	25
      Number of factors of 5 in each	1	1	1	1	2

      Numbers containing factors of 7	7	14	21
      Number of factors of 7 in each	1	1	1

      Recall that $n!=2^a\cdot 3^b\cdot 5^c\cdot 7^d\cdot {11}^2\cdot {13}^2\cdot 17\cdot 19\cdot 23$, and $a+b+c+d=45$.

      Since $n!$ has $a$ factors of 2, then counting in the table above, $a=23$ when $n=26$.

      Similarly, $26!$ has $b=10$, $c=6$, and $d=3$, and so $a+b+c+d=23+10+6+3=42$, and so $n\ne 26$.

      Next, we determine the values of $a,b,c,d$ for $27!$.

      Since $27!$ has all of the prime factors that $26!$ has, in addition to the prime factors of $27=3^3$, then $a+b+c+d=23+(10+3)+6+3=45$, as required.

      Finally, we determine the values of $a,b,c,d$ for $28!$.

      Since $28!$ has all of the prime factors that $27!$ has, in addition to the prime factors of $28=2^2\cdot 7$, then $a+b+c+d=(23+2)+13+6+(3+1)=48$, and so $n\ne 28$.

      Therefore, $n=27$ is the only positive integer for which $n!=2^a\cdot 3^b\cdot 5^c\cdot 7^d\cdot {11}^2\cdot {13}^2\cdot 17\cdot 19\cdot 23$, and $a+b+c+d=45$.

4. 1. In order for a positive integer to be divisible by 10, its ones digit must be $0$.

      For a positive integer to be digit-balanced, we need each digit $d$ to appear at most $d$ times.

      In the case that $d=0$, this means a digit balanced number has at most $0$ zeros.

      This means the number of zeros must be $0$.

      Since a multiple of $10$ has at least one digit which is $0$ (the ones digit), it cannot be digit balanced.

   2. Every four-digit positive integer has digits: $x,x,x,x$ or $x,x,x,y$ or $x,x,y,y$ or $x,x,y,z$ or $x,y,z,w$ for some distinct digits $w,x,y,z$.

      In this part, we exclude the possibility that a digit could equal 0.

      A positive integer with distinct digits $w,x,y,z$ is always digit-balanced since no digit appears more than once.

      A positive integer with digits $x,x,x,x$ is not digit-balanced if $x=1$ or $x=2$ or $x=3$. There are 3 such integers.

      A positive integer with digits $x,x,x,y$ is not digit-balanced if $x=1$ or $x=2$, with $y$ being any non-zero digit not equal to $x$.

      There are 2 choices for $x$, 8 choices for $y$ (any non-zero digit not equal to $x$), and 4 possible locations for the digit $y$ (thousands, hundreds, tens, or ones digit), after which the digits $x$ are placed without further choice.

      Thus, in this case, there are $2\times 8\times 4=64$ integers that are not digit-balanced.

      A positive integer with digits $x,x,y,y$ is not digit-balanced if either $x=1$ or $y=1$. Assume that $x=1$ and $y\ne 1$.

      There are 8 choices for $y$ and 6 choices of positions for $x$. (If the integer has digits $abcd$, then $x$ could be positions $a,b$ or $a,c$ or $a,d$ or $b,c$ or $b,d$ or $c,d$.)

      Thus, in this case, there are $8\times 6=48$ integers that are not digit-balanced.

      A positive integer with digits $x,x,y,z$ is not digit-balanced if $x=1$. Here, we assume that $y\ne 1$ and $z\ne 1$ and $y\ne z$.

      There 6 choices of positions for the two $x$’s. (If the integer has digits $abcd$, then $x$ could be positions $a,b$ or $a,c$ or $a,d$ or $b,c$ or $b,d$ or $c,d$.)

      There are then 8 choices for the left-most of the other digits (any non-zero digit other than 1) and 7 choices for the remaining digit (any non-zero digit other than 1 or $y$).

      Thus, in this case, there are $6\times 8\times 7=336$ integers that are not digit-balanced.

      In total, there are $336+48+64+3=451$ four-digit integers with all non-zero digits that are not digit-balanced.

   3. We assume $n$ and $m$ are digit-balanced $k$-digit numbers so that $m+n={10}^k$ where $k$ is as large as possible. First, we will deduce that $k\le 21$. After that, we will explain how to produce digit-balanced integers with $k$ digits whose sum is ${10}^k$ for any $k$ with $1\le k\le 21$, which will show that the answer to the problem is $21$.

      We set $n=n_k{n}_{k-1}{n}_{k-2}\cdots n_2{n}_1$ and $m=m_k{m}_{k-1}{m}_{k-2}\cdots m_2{m}_1$ so that $n_k,n_{k-1},\dots ,n_1$ and $m_k,m_{k-1},\dots ,m_1$ are the digits of $n$ and $m$, respectively. We argued in part (a) that a digit-balanced number cannot have any digits which are $0$, so the digits of $m$ and $n$ are all between $1$ and $9$ inclusive.

      Using the condition that $m+n={10}^k$, we note that $m_1+n_1$ must end in $0$ and hence, be a multiple of $10$. Since $1\le m_1\le 9$ and $1\le n_1\le 9$, we have that $2\le m_1+n_1\le 18$. The only multiple of $10$ in this range is $10$ itself, so it must be that $m_1+n_1=10$. This means there is a carry in the addition:

      

      Looking at the tens digit, we need $n_2+m_2+1$ to be a multiple of $10$. Like the situation above, $1\le n_2\le 9$ and $1\le m_2\le 9$, so $2\le n_2+m_2\le 18$, which means $3\le n_2+m_2+1\le 19$. The only multiple of $10$ in this range is $10$ itself, which means $n_2+m_2+1=10$ or $n_2+m_2=9$.

      Continuing the addition, we have

      

      Following the same reasoning, we have that $n_3+m_3=9$, $n_4+m_4=9$, and so on.

      For now, we will not worry about the units digit of $n$. Instead, we will focus on the digits $n_k$ through $n_2$. We will refer to these as the “first $k-1$ digits" of $n$. Similarly, we will refer to $m_k$ through $m_2$ as the first $k-1$ digits of $m$.

      Since each of $n$ and $m$ is digit-balanced, no more than one of the first $k-1$ digits of $n$ or $m$ can be $1$.

      Similarly, at most two of the first $k-1$ digits of $m$ and $n$ are $2$, at most three of the first $k-1$ digits are $3$, and at most four of the first $k-1$ digits are $4$.

      Suppose $n_r=5$ for some $r>1$. Then we must have $m_r=4$ since $n_r+m_r=9$. Since at most four of the first $k-1$ digits of $m$ are $4$, this means at most four of the first $k-1$ digits of $n$ are $5$.

      If $n_r=6$ for some $r>1$, then $m_r=3$ since $n_r+m_r=9$. Since $m$ is digit-balanced, this means at most three of the first $k-1$ digits of $n$ are $6$.

      Similarly, at most two of the first $k-1$ digits of $n$ are $7$ and at most one of the first $k-1$ digits of $n$ are $8$.

      If $n_r=9$ for some $r>1$, we have $m_r=0$, but $m$ is digit-balanced, so it does not have any digits which are $0$. Therefore, none of the first $k-1$ digits of $n$ can be $9$.

      The following table summarizes the maximum number of occurrences of each digit in the first $k-1$ digits of $n$:

      digit	maximum number of occurrences in $n$
      1	1
      2	2
      3	3
      4	4
      5	4
      6	3
      7	2
      8	1
      9	0

      Since every digit of $n$ must be between $1$ and $9$, this means $k-1$ is no larger than $$1+2+3+4+4+3+2+1+0=20$$ This means $k-1\le 20$, so $k\le 21$. This establishes that if $n$ and $m$ are both digit-balanced, each have $k$ digits, and $m+n={10}^k$, then $k\le 21$. We will now explain how to construct digit-balanced numbers with $k$ digits for each $k$ satisfying $1\le k\le 21$.

      To construct digit-balanced numbers $n$ and $m$ which each have $21$ digits and whose sumis $m+n={10}^{21}$, we must use the maximum number of each digit in the first $20$ digits.

      If the units digits are $n_1=m_1=5$, this satisfies $n_1+m_1=10$, and each of $m$ and $n$ only has four digits which are $5$ in the first $20$ digits, so having the units digits equal to $5$ will result in $m$ and $n$ being digit-balanced. Can you see why the units digits of $m$ and $n$ must equal 5 for $k=21$?

      Taking $n_1=m_1=5$ will give us what we want. For example, we could take: $$n=877666555544443332215\text{and}m=122333444455556667785$$

      Indeed, each of these numbers has $21$ digits, is digit-balanced, and their sum is ${10}^{21}$.

      To produce pairs $m$ and $n$ of digit-balanced integers with $k$ digits whose sum is ${10}^k$ with $k$ smaller than $21$, we can simply remove digits from the left of $n$ and $m$ one at a time. For example, $$n=77666555544443332215\text{and}m=22333444455556667785$$ is a pair of digit-balanced numbers which each have twenty digits and whose sum is ${10}^{20}$.

      The pair $$n=44443332215\text{and}m=55556667785$$ is a pair of digit-balanced numbers which each have eleven digits and whose sum is ${10}^{11}$.

      The pair $n=5$ and $m=5$ is a pair of digit-balanced numbers which each have one digit and whose sum is $10={10}^1$.

      There exist digit-balanced positive integers $m$ and $n$, where $m+n={10}^k$ and $m$ and $n$ each have $k$ digits for all integer values of $k$ from $1$ to $21$ inclusive.

      Thus, the number of possible values of $k$ is $21$.