2020 Galois Contest
Solutions
(Grade 10)

Wednesday, April 15, 2020
(in North America and South America)

Thursday, April 16, 2020
(outside of North American and South America)

©2020 University of Waterloo

1. 1. The number of letters in each row after the first is twice the number of letters in the previous row.

      Since Row 4 has 8 letters, then Row 5 has $2\times 8=16$ letters, and Row 6 has $2\times 16=32$ letters.

      Alternatively, we can continue the pattern to Row 6 as shown.

      Row 1	$A$
      Row 2	$BB$
      Row 3	$A$$A$$A$$A$
      Row 4	$BBBBBBBB$
      Row 5	$A$$A$$A$$A$$A$$A$$A$$A$$A$$A$$A$$A$$A$$A$$A$$A$
      Row 6	$BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB$

   2. If the pattern consists of 6 rows, the total number of letters is $1+2+4+8+16+32=63$.

   3. Solution 1

      If the total number of letters in the pattern is 63, then there are 6 rows in the pattern (as we saw in part (b)).

      Counting, we get that there are $1+4+16=21$ $A$’s, and $2+8+32=42$ $B$’s.

      Solution 2

      Notice that in Row 2 there are twice as many $B$’s as there are $A$’s in Row 1, and in Row 4 there are twice as many $B$’s as there are $A$’s in Row 3.

      Further, the rows alternate between $A$’s and $B$’s and the number of letters in each row is twice the number of letters in the previous row, and so this pattern continues.

      Thus, if there are an even number of rows in the pattern, then the total number of $B$’s in the pattern is twice the total number of $A$’s, and so in this case $\frac{1}{3}$ of the letters in the pattern are $A$’s and $\frac{2}{3}$ of the letters are $B$’s.

      If the total number of letters in the pattern is 63, then there are 6 rows in the pattern (as we saw in part (b)), and so the number of $A$’s in the pattern is $\frac{1}{3}\times 63=21$ and the number of $B$’s is $\frac{2}{3}\times 63=2\times 21=42$.

   4. Solution 1

      We begin by determining the number of rows in the pattern given that the total number of letters is 4095.

      We may do this by counting the number of $A$’s and $B$’s in each row and keeping a running total of the number of letters in the pattern after each complete row.

      Row Number	1	2	3	4	5	6	7	8	9	10	11	12
      Number of $A$’s	1	0	4	0	16	0	64	0	256	0	1024	0
      Number of $B$’s	0	2	0	8	0	32	0	128	0	512	0	2048
      Number of Letters	1	3	7	15	31	63	127	255	511	1023	2047	4095

      If the pattern has 12 complete rows, there are a total of 4095 letters, of which $1+4+16+64+256+1024=1365$ are $A$’s and $2+8+32+128+512+2048=2730$ are $B$’s.

      Thus, if there are 4095 letters in the pattern, the difference between the number of $A$’s and the number of $B$’s is $2730-1365=1365$.

      Solution 2

      We begin by determining the number of rows in the pattern given that the total number of letters is 4095.

      Since $4095=1+2+4+8+16+32+64+128+256+512+1024+2048$ and the sum on the right side of this equation has 12 terms, then a pattern with 4095 letters contains exactly 12 complete rows.

      Since 12 is an even number of rows, we may use the result from Solution 2 in part (c) to determine that the pattern has $\frac{1}{3}\times 4095=1365$ $A$’s and $\frac{2}{3}\times 4095=2\times 1365=2730$ $B$’s.

      Thus, if there are 4095 letters in the pattern, the difference between the number of $A$’s and the number of $B$’s is $2730-1365=1365$.

      (Alternatively, we may have concluded that if $\frac{2}{3}$ of the letters are $B$’s and $\frac{1}{3}$ are $A$’s, then the difference between the number of $A$’s and $B$’s is $\frac{2}{3}-\frac{1}{3}=\frac{1}{3}$ of the total number of letters, or $\frac{1}{3}\times 4095=1365$.)

2. 1. The surface area of a rectangular prism is given by the formula $A=2\ell w+2\ell h+2wh$.

      Thus, the rectangular prism with length 2 cm, width 5 cm, and height 9 cm has surface area $2(2)(5)+2(2)(9)+2(5)(9)=20+36+90=146$ cm${}^2$.

   2. The volume of a rectangular prism is given by the formula $V=\ell wh$.

      If the rectangular prism has a square base, then $\ell =w$ and so $V={\ell }^{2}h$.

      Substituting $V=160$ cm${}^3$ and $h=10$ cm, we get $160={\ell }^2(10)$ or ${\ell }^2=16$, and so $\ell =4$ cm (since $\ell >0$).

      Therefore, the side length of the square base of a rectangular prism with height 10 cm and volume 160 cm${}^3$ is 4 cm.

   3. If a rectangular prism has a square base, then $\ell =w$.

      Since the area of the base is 36 cm${}^2$, then $36=\ell \cdot w={\ell }^2$, and so $\ell =w=\sqrt{36}=6$ cm (since $\ell >0$).

      If the surface area of this prism is 240 cm${}^2$, then substituting, we get $240=2(6)(6)+2(6)h+2(6)h$ or $240=72+24h$, and so $h={\displaystyle \frac{240-72}{24}}=7$ cm.

      Thus, the volume of the prism is $\ell wh=(6)(6)(7)=252$ cm${}^3$.

   4. Substituting into the formula for volume, we get $x=k(2k)(3k)$ or $x=6k^3$.

      Substituting into the formula for surface area, we get $x=2(k)(2k)+2(k)(3k)+2(2k)(3k)$ or $x=4k^2+6k^2+12k^2=22k^2$.

      Equating the two expressions that are each equal to $x$ and solving, we get $$\begin{array}{rl}6k^3& =22k^2\\ 6k^3-22k^2& =0\\ 2k^2(3k-11)& =0\end{array}$$ Since $k>0$, then $3k-11=0$ and so $k={\displaystyle \frac{11}{3}}$.

3. 1. The original product is $2\times 8=16$.

      If we add 1 to each of 2 and 8, we get 3 and 9 and a new product of $3\times 9=27$.

      The ones digit of this new product is 1 more than the ones digit of the original product ($7-6=1$).

      The tens digit of this new product is 1 more than the tens digit of the original product ($2-1=1$).

      Since the positive integer $d=1$ satisfies the required conditions, $(2,8)$ is a RadPair.

   2. The original product is $3\times 6=18$.

      If we add 1 to each of 3 and 6, we get 4 and 7 and a new product of $4\times 7=28$.

      The ones digit of this new product is not 1 more than the ones digit of the original product ($8-8\ne 1$), and thus $d=1$ does not satisfy the required conditions for $(3,6)$ to be a RadPair.

      If we add 2 to each of 3 and 6, we get 5 and 8 and a new product of $5\times 8=40$.

      The ones digit of this new product is not 2 more than the ones digit of the original product ($0-8\ne 2$), and thus $d=2$ does not satisfy the required conditions for $(3,6)$ to be a RadPair.

      Adding 3 to each of 3 and 6, we get 6 and 9 and a new product of $6\times 9=54$.

      The ones digit of this new product is not 3 more than the ones digit of the original product ($4-8\ne 3$), and thus $d=3$ does not satisfy the required conditions for $(3,6)$ to be a RadPair.

      Adding 4 to each of 3 and 6, we get 7 and 10 and a new product of $7\times 10=70$.

      The ones digit of this new product is not 4 more than the ones digit of the original product ($0-8\ne 4$), and thus $d=4$ does not satisfy the required conditions for $(3,6)$ to be a RadPair.

      Adding 5 to each of 3 and 6, we get 8 and 11 and a new product of $8\times 11=88$.

      The ones digit of this new product is not 5 more than the ones digit of the original product ($8-8\ne 5$), and thus $d=5$ does not satisfy the required conditions for $(3,6)$ to be a RadPair.

      Adding 6 to each of 3 and 6, we get 9 and 12 and a new product of $9\times 12=108$.

      Since this new product is not a two-digit integer, then $d=6$ does not satisfy the required conditions for $(3,6)$ to be a RadPair.

      All integer values of $d>6$ will give products that are greater than 108, and thus $(3,6)$ is not a RadPair.

   3. Solution 1

      In part (b) we showed that $(3,6)$ was not a RadPair.

      If $x=1$, then the product $1\times 6=6$ is not a two-digit integer and so $(1,6)$ is also not a RadPair.

      For each of the remaining values, $x=2,4,5,6$, we try different values for $d$ (as was done in part (b)), to determine if $(x,6)$ is a RadPair.

      We summarize this work in the table that follows.

      $\mathbf{(}\mathit{x}\mathbf{,}\mathbf{6}\mathbf{)}$	Original Product $\mathbf{6}\mathit{x}$	$\mathit{d}$	New Product	RadPair?
      $(2,6)$	12	3	$(2+3)\times (6+3)=45$	Yes, since $4-1=5-2=3$
      $(4,6)$	24	1	$(4+1)\times (6+1)=35$	Yes, since $3-2=5-4=1$
      $(5,6)$	30			No $d$ satisfies the conditions.
      $(6,6)$	36			No $d$ satisfies the conditions.

      Therefore, the positive integers $x\le 6$ for which $(x,6)$ is a RadPair are $x=2$ and $x=4$.

      Solution 2

      If $(x,6)$ is a RadPair, then the original product $6x$ is a two-digit integer and thus can be written as $10m+n$ for some integers $1\le m\le 9$ and $0\le n\le 9$.

      That is, $6x=10m+n$ and so $m$ is the tens digit of the original product $6x$ and $n$ is the ones digit.

      Further, if $(x,6)$ is a RadPair, then there exists a positive integer $d$ such that

      • the product $(x+d)(6+d)$ is a two-digit integer, and

      • the ones digit of the product $(x+d)(6+d)$ equals $d$ plus the ones digit, $n$, of the product $6x$, and

      • the tens digit of the product $(x+d)(6+d)$ equals $d$ plus the tens digit, $m$, of the product $6x$.

      The second bullet gives that the ones digit of the product $(x+d)(6+d)$ equals $n+d$.

      The third bullet gives that the tens digit of the product $(x+d)(6+d)$ equals $m+d$.

      Since the product $(x+d)(6+d)$ has tens digit $m+d$ and ones digit $n+d$, we have $(x+d)(6+d)=10(m+d)+(n+d)$.

      Expanding each side of this equation and using the earlier fact that $6x=10m+n$, we get $$\begin{array}{rl}(x+d)(6+d)& =10(m+d)+(n+d)\\ 6x+xd+6d+d^2& =10m+10d+n+d\\ 6x+xd+6d+d^2& =10m+n+11d\\ 6x+xd+6d+d^2& =6x+11d\text{(since }6x=10m+n\text{)}\\ xd+6d+d^2& =11d\\ xd+d^2& =5d\end{array}$$ Since $d>0$, we may divide this final equation by $d$ to give $x+d=5$.

      If $(x,6)$ is a RadPair, then $x+d=5$.

      That is, the condition $x+d=5$ is necessary for $(x,6)$ to be a RadPair, but it does not guarantee that $(x,6)$ is a RadPair.

      We saw an example of this in part (b) when we showed that $(3,6)$ was not a RadPair.

      If $x=3$ and $x+d=5$, then $d=2$.

      However $3\times 6=18$ and $(3+2)\times (6+2)=40$ and since $4-1\ne 2$, then the condition $x+d=5$ ($x=3$ and $d=2$) did not produce a RadPair.

      As we saw in Solution 1, $(1,6)$ is not a RadPair since $1\times 6=6$ is not a two-digit integer, and thus we are left to check $x=2,4,5,6$.

      If $x=2$, then $d=5-2=3$ and so $(2,6)$ may be a RadPair with $d=3$.

      If $x=4$, then $d=5-4=1$ and so $(4,6)$ may be a RadPair with $d=1$.

      If $x=5$, then $d=5-5=0$, but $d>0$ and so $(5,6)$ is not a RadPair.

      If $x=6$, then $d=5-6=-1$, but $d>0$ and so $(6,6)$ is not a RadPair.

      We can verify that each of $(2,6)$ and $(4,6)$ is indeed a RadPair (see Solution 1).

      The positive integers $x\le 6$ for which $(x,6)$ is a RadPair are $x=2$ and $x=4$.

   4. As in part (c) Solution 2, we will proceed algebraically to determine a condition that is required for $(a,b)$ to be a RadPair, but that does not guarantee that $(a,b)$ is a RadPair.

      To then obtain an accurate count of the number of RadPairs, we will need to show that a specific value for $d$ satisfies each of the given requirements.

      If $(a,b)$ with $a\le b$ is a RadPair, then the original product $ab$ is a two-digit integer and thus can be written as $10h+k$ for some integers $1\le h\le 9$ and $0\le k\le 9$.

      That is, $ab=10h+k$ and so $h$ is the tens digit of the original product $ab$ and $k$ is the ones digit.

      Further, if $(a,b)$ is a RadPair, then there exists a positive integer $d$ such that

      • the product $(a+d)(b+d)$ is a two-digit integer, and

      • the ones digit of the product $(a+d)(b+d)$ equals $d$ plus the ones digit, $k$, of the product $ab$, and

      • the tens digit of the product $(a+d)(b+d)$ equals $d$ plus the tens digit, $h$, of the product $ab$.

      The second bullet gives that the ones digit of the product $(a+d)(b+d)$ equals $k+d$.

      The third bullet gives that the tens digit of the product $(a+d)(b+d)$ equals $h+d$.

      Therefore, the product $(a+d)(b+d)$ has tens digit $h+d$ and ones digit $k+d$, and thus $(a+d)(b+d)=10(h+d)+(k+d)$.

      Expanding each side of this equation and using the earlier fact that $ab=10h+k$, we get $$\begin{array}{rl}(a+d)(b+d)& =10(h+d)+(k+d)\\ ab+ad+bd+d^2& =10h+10d+k+d\\ ab+ad+bd+d^2& =10h+k+11d\\ ab+ad+bd+d^2& =ab+11d\\ ad+bd+d^2& =11d\end{array}$$ Since $d>0$, we may divide this final equation by $d$ to give $a+b+d=11$.

      If $(a,b)$ is a RadPair, then $a+b+d=11$.

      Again, this condition $a+b+d=11$ is necessary for $(a,b)$ to be a RadPair, but it does not guarantee that $(a,b)$ is a RadPair.

      When $a=1$, there is no value for the digit $b$ such that $ab$ is a two-digit integer.

      Thus, there are no RadPairs $(a,b)$ with $a=1$.

      When $a\ge 6$, then $a+b>11$ (since $a\le b$).

      If $a+b>11$ and $a+b+d=11$, then $d<0$ which is not possible.

      Thus, there are no RadPairs $(a,b)$ with $a\ge 6$.

      In the table below, we use the condition $a+b+d=11$ and the definition of a RadPair to determine all RadPairs $(a,b)$ with $a\le b$.

      We may exclude checking some pairs by recalling that:

      • $ab\ge 10$ and so we may omit pairs such as $(1,8)$ and $(2,4)$

      • $a+b<11$ and so we may omit pairs such as $(2,9)$ and $(3,9)$

      • we have previously shown that $(3,6)$ is not a RadPair

      $\mathbf{(}\mathit{a}\mathbf{,}\mathit{b}\mathbf{)}$	$\mathit{d}$	$\mathit{a}\mathit{b}$	$\mathbf{(}\mathit{a}\mathbf{+}\mathit{d}\mathbf{)}\mathbf{(}\mathit{b}\mathbf{+}\mathit{d}\mathbf{)}$	Check
      $(2,5)$	4	10	$(2+4)\times (5+4)=54$	$5-1=4-0=4$
      $(2,6)$	3	12	$(2+3)\times (6+3)=45$	$4-1=5-2=3$
      $(2,7)$	2	14	$(2+2)\times (7+2)=36$	$3-1=6-4=2$
      $(2,8)$	1	16	$(2+1)\times (8+1)=27$	$2-1=7-6=1$
      $(3,4)$	4	12	$(3+4)\times (4+4)=56$	$5-1=6-2=4$
      $(3,5)$	3	15	$(3+3)\times (5+3)=48$	$4-1=8-5=3$
      $(3,7)$	1	21	$(3+1)\times (7+1)=32$	$3-2=2-1=1$
      $(4,4)$	3	16	$(4+3)\times (4+3)=49$	$4-1=9-6=3$
      $(4,5)$	2	20	$(4+2)\times (5+2)=42$	$4-2=2-0=2$
      $(4,6)$	1	24	$(4+1)\times (6+1)=35$	$3-2=5-4=1$
      $(5,5)$	1	25	$(5+1)\times (5+1)=36$	$3-2=6-5=1$

      These are the only possibilities satisfying the given requirements, and so there are exactly 11 RadPairs.

4. Throughout the solution to this question, we will represent a path as a sequence of moves, down ($D$), up ($U$), right ($R$), left ($L$), between adjacent vertices, begining at $A$, ending at $B$.

   1. Every path in a $2\times 2$ grid contains a minimum of 2 moves down and 2 moves right (since $B$ is 2 edges down and 2 edges right from $A$).

      Thus, every path can be represented by a sequence containing at least 2 $D$’s and 2 $R$’s, and has a length of at least 4 moves.

      We begin by determining the number of paths in a $2\times 2$ grid whose length is exactly 4.

      

      There are 6 such paths, as shown, and these paths can be represented by the sequences of moves $DDRR$, $DRDR$, $DRRD$, $RDDR$, $RDRD$, $RRDD$, respectively.

      We note that these are the only possible arrangements of exactly 2 $D$’s and 2 $R$’s.

      Can a path in a $2\times 2$ grid have length 5?

      If in addition to the required 2 moves down and 2 moves right, a path contained a move up, then this move would need to be “undone” by a move in the opposite direction, down.

      That is, the net result of every path must be 2 $D$’s and 2 $R$’s, and so each $U$ must be paired with an additional $D$. Similarly, each $L$ must be paired with an additional $R$.

      To summarize, every path in a $2\times 2$ grid must contain 2 $D$’s, 2 $R$’s, and any additional moves must occur in pairs of opposite moves, $U$/$D$ or $L$/$R$.

      Thus, every path in a $2\times 2$ grid contains 4 moves (2 $D$’s, 2 $R$’s) and possibly additional pairs of moves, and thus has an even length.

      A path of length 5 is not possible.

      Next, we determine the number of paths whose length is 6.

      Each of these paths contains 2 $D$’s, 2 $R$’s, and either 1 $U$/$D$ pair or 1 $L$/$R$ pair.

      How many arrangements are there of 3 $R$’s, 1 $L$ and 2 $D$’s which give a path from $A$ to $B$?

      To begin, consider the number of arrangements of the 3 $R$’s and the 1 $L$ (the horizontal moves).

      The $L$ cannot appear before the first $R$ and it cannot appear after the last $R$ since each of these sequences ($LRRR$ and $RRRL$) leaves the $2\times 2$ grid.

      Thus, there are 2 possible arrangements of these 4 letters, namely $RLRR$ and $RRLR$.

      Next, we count the number of possible placements of the 2 $D$’s among each of the above sequences.

      A path must pass through each vertex at most once, and so the $L$ cannot be followed by an $R$ and vice versa ($RL$ or $LR$ would mean “backtracking”).

      For this reason, 1 $D$ must be placed on each side of the $L$.

      Thus, there are 2 possible arrangements of 3 $R$’s, 1 $L$ and 2 $D$’s which give a path from $A$ to $B$, namely $RDLDRR$ and $RRDLDR$.

      A similar argument can be made for the arrangement of 3 $D$’s, 1 $U$ and 2 $R$’s, and so there are 4 paths of length 6 from $A$ to $B$.

      

      These 4 paths, respectively represented by the sequences of moves $DDRURD$, $DRURDD$, $RDLDRR$, $RRDLDR$, are shown.

      Finally, we determine the number of paths whose length is 8.

      

      There are 2 such paths, as shown, and these paths can be represented by the sequences of moves $DDRUURDD$, $RRDLLDRR$, respectively.

      Can you justify why these are the only paths of length 8?

      Is a path of length 10 or greater possible?

      The first edge of a path touches two vertices, and each additional edge touches one new vertex.

      Thus, a path of length 8 passes through $2+7=9$ vertices (as seen in the two grids above), and a path of length 10 (or greater) would pass through at least $2+9=11$ vertices.

      However, a path must pass through each vertex at most once, and since a $2\times 2$ grid contains $3\times 3=9$ vertices, it is not possible to have a path of length 10 or greater.

      In a $2\times 2$ grid, the number of paths of any length from $A$ to $B$ is $6+4+2=12$.

   2. Following the reasoning in part (a), a path from $A$ to $B$ in a $10\times 10$ grid contains a minimum of 10 moves down and 10 moves right (since $B$ is 10 edges down and 10 edges right from $A$).

      Further, any additional moves must occur in opposite pairs ($U$ and $D$ or $L$ and $R$), and so every path in a $10\times 10$ grid contains 20 moves (10 $D$’s, 10 $R$’s) and possibly additional pairs of moves, and thus has an even length.

   3. Solution 1

      In a $4\times 4$ grid, a path from $A$ to $B$ has at least 4 moves down (4 $D$’s) and at least 4 moves right (4 $R$’s).

      Thus, each path of length 10 has these 8 moves and exactly one additional pair of opposite moves, either left paired with right or up paired with down.

      That is, each path has exactly 4 vertical moves ($U$/$D$) and 6 horizontal moves ($L$/$R$), or it has exactly 4 horizontal moves and 6 vertical moves.

      By symmetry, each of these two cases will give an equal number of paths from $A$ to $B$, and so we count the number of paths for one of the cases and double that number to determine the total.

      Assume that a path from $A$ to $B$ contains 4 vertical moves and 6 horizontal moves.

      Each of the 4 vertical moves must be down.

      The 6 horizontal moves must be 5 right and 1 left (4 moves right and 1 left/right opposite pair).

      Thus, each path may be given by a string of 10 letters (4 $D$’s, 5 $R$’s and 1 $L$), and we may determine the number of paths by counting the number of arrangements of these 10 letters that correspond to a path from $A$ to $B$.

      To begin, consider the number of arrangements of the 5 $R$’s and the 1 $L$ (the horizontal moves).

      Since $L$ cannot be the first move and it cannot be the last move, there are 4 possible arrangements of these 6 letters, namely $RLRRRR$, $RRLRRR$, $RRRLRR$, and $RRRRLR$.

      Next, we count the number of possible placements of the 4 $D$’s within each of the above sequences.

      A path must pass through each vertex at most once, and so the $L$ cannot be followed by an $R$ and vice versa ($RL$ or $LR$ would mean “backtracking”).

      For this reason, 1 $D$ must be placed on each side of the $L$ which gives the 4 sequences $RDLDRRRR$, $RRDLDRRR$, $RRRDLDRR$, and $RRRRDLDR$.

      In each of these sequences, there are 2 $D$’s remaining to be placed.

      The 2 $D$’s can be placed in each of the above 4 sequences in one of two ways: adjacent to one another or not adjacent to one another.

      How many ways can the 2 $D$’s be placed if they are adjacent?

      The 2 $D$’s can be placed before the first $R$ or after the last $R$ (so 2 locations), between any adjacent pair of $R$’s (there are 3 of these in each sequence), between the $R$ and $D$ (1 location), or between the $D$ and $R$ (1 location).

      Note that placing the 2 $D$’s between the $D$ and $L$ (or between the $L$ and $D$) gives the same sequence as when the 2 $D$’s are placed between the $R$ and $D$ (or between the $D$ and $R$).

      Thus, there are $2+3+1+1=7$ ways that 2 adjacent $D$’s can be placed into each of the 4 sequences $RDLDRRRR$, $RRDLDRRR$, $RRRDLDRR$, and $RRRRDLDR$.

      How many ways can the 2 $D$’s be placed if they are not adjacent?

      One of the $D$’s must be placed into any one of the 7 locations previously given (for the same reason), and the second $D$ can be placed into any of the remaining 6 locations (so that it is not adjacent to the first $D$).

      These 2 $D$’s are identical and so switching these $D$’s within the arrangement gives the same sequence, and thus we must divide by 2.

      Therefore, there are ${\displaystyle \frac{7\times 6}{2}}=21$ ways that 2 non-adjacent $D$’s can be placed into each of the 4 sequences.

      In total, there are $7+21=28$ ways to place the 2 $D$’s into each of 4 sequences, and so there are $28\times 4=112$ arrangements of 4 $D$’s, 5 $R$’s and 1 $L$.

      In a $4\times 4$ grid, the number of paths from $A$ to $B$ having 4 vertical moves and 6 horizontal moves is thus $112$.

      A similar argument can be made for the arrangement of 4 $R$’s, 5 $D$’s and 1 $U$, and so there are an additional 112 paths having 4 horizontal moves and 6 vertical moves.

      Thus, the total number of paths of length 10 from $A$ to $B$ in a $4\times 4$ grid is $112\times 2=224$.

      Solution 2

      In a $4\times 4$ grid, a path from $A$ to $B$ has at least 4 moves down (4 $D$’s) and at least 4 moves right (4 $R$’s).

      Thus, each path of length 10 has these 8 moves and exactly one additional pair of opposite moves, either left paired with right or up paired with down.

      That is, each path has exactly 4 vertical moves ($U$/$D$) and 6 horizontal moves ($L$/$R$), or it has exactly 4 horizontal moves and 6 vertical moves.

      By symmetry, each of these two cases will give an equal number of paths from $A$ to $B$, and so we count the number of paths for one of the cases and double that number to determine the total.

      Assume that a path from $A$ to $B$ contains 4 vertical moves and 6 horizontal moves.

      Each of the 4 vertical moves must be down.

      The 6 horizontal moves must be 5 right and 1 left (4 moves right and 1 left/right opposite pair).

      Thus, each path may be given by a string of 10 letters (4 $D$’s, 5 $R$’s and 1 $L$), and we may determine the number of paths by counting the number of arrangements of these 10 letters that correspond to a path from $A$ to $B$.

      A path must pass through each vertex at most once, and so the $L$ cannot be followed by an $R$ and vice versa ($RL$ or $LR$ would mean “backtracking”).

      Further, $L$ cannot be the first move and it cannot be the last move.

      Thus the $L$ cannot have an $R$ on either side of it, and it cannot be the first or last letter, and so each arrangement must contain the string $DLD$.

      How many arrangements of 5 $R$’s, 2 $D$’s, and 1 $DLD$ are there?

      We treat $DLD$ as a single letter, and so there are 8 letters for which there would be $8!$ possible arrangements if the 8 letters were all distinct.

      However, the 5 $R$’s are identical, and thus each of the $5!$ arrangements of the $R$’s within the 8 letters gives the same sequence of moves and so we must divide $8!$ by $5!$.

      Similarly, the 2 $D$’s are identical and so switching these $D$’s within the arrangement gives the same sequence, and thus we must also divide by 2.

      The total number of arrangements of 5 $R$’s, 2 $D$’s, and 1 $DLD$ is ${\displaystyle \frac{8!}{(5!)(2)}}={\displaystyle \frac{8\cdot 7\cdot 6}{2}}=168$.

      Are each of these 168 paths possible?

      A sequence of edges that revisit a vertex is not permitted, however forcing the path to contain the moves $DLD$ ensures that this cannot happen.

      A sequence of edges that leaves the grid is also not permitted.

      Since each sequence contains exactly 4 $D$’s and no $U$’s, it is not possible that the path leaves the top or the bottom of the grid.

      However, each sequence of moves contains 5 $R$’s, and if these each appear before $DLD$ (before a move left), then our path will leave the right side of the $4\times 4$ grid.

      Similarly, if the $DLD$ appears in the sequence before an $R$, then the path leaves the left side of the grid.

      Since each of these is possible within the arrangements counted above, some of the 168 arrangements are not possible.

      We can count the number of such arrangements which leave the grid and subtract this number from the total number 168.

      There are exactly 2 ways that a path leaves the grid: all 5 $R$’s appear in the sequence before $DLD$, or all 5 $R$’s appear after $DLD$ (the $L$ occurs before the first $R$).

      By symmetry, each of these two cases gives an equal number of paths, and thus we count one case and double the result.

      How many of the 168 sequences have 5 $R$’s before $DLD$?

      We can count these paths by considering the following three cases.

      Case (i): the 5 $R$’s and the 2 $D$’s occur before $DLD$

      The number of such paths is equal to the number of arrangements of 5 $R$’s and 2 $D$’s, which is ${\displaystyle \frac{7!}{(5!)(2)}}={\displaystyle \frac{7\cdot 6}{2}}=21$.

      Case (ii): the 5 $R$’s and 1 $D$ occur before $DLD$ (1 $D$ occurs after the $DLD$)

      The number of such paths is equal to the number of arrangements of 5 $R$’s and 1 $D$ (since the location of the other $D$ is forced), which is ${\displaystyle \frac{6!}{5!}}=6$.

      Case (iii): the 5 $R$’s occur before $DLD$ and the 2 $D$’s occur after

      In this case, there is only 1 only such path.

      Thus, there are a total of $21+6+1=28$ paths with 5 $R$’s before $DLD$ and 28 more with 5 $R$’s following $DLD$, for a total of 56 paths which leave the grid.

      In a $4\times 4$ grid, the number of paths from $A$ to $B$ having 4 vertical moves and 6 horizontal moves is thus $168-56=112$.

      Since there are an additional 112 paths having 4 horizontal moves and 6 vertical moves, the total number of paths of length 10 from $A$ to $B$ in a $4\times 4$ grid is $112\times 2=224$.