2021 Fryer Contest
Solutions
(Grade 9)
April 2021
(in North America and South America)
April 2021
(outside of North American and South America)
April 2021
(in North America and South America)
April 2021
(outside of North American and South America)
©2021 University of Waterloo
Each business card has dimensions 5 cm \(\times\) 9 cm and thus has area \(5\textrm{ cm}\times9\textrm{ cm}=45\) cm\(^2\).
Each single page with dimensions 20 cm \(\times\) 27 cm has area \(20\textrm{ cm}\times27\textrm{ cm}=540\) cm\(^2\). Each business card has area 45 cm\(^2\).
The entire page is used with no waste and so the number of business cards that can be printed without overlap is \(\dfrac{540 \textrm{ cm}^2}{45 \textrm{ cm}^2}= 12\).
We begin by first considering the portrait page layout.
The width of each card is 5 cm and the width of the page is 19 cm. Since 3 adjacent cards give a combined width of 15 cm (less than 19 cm) and 4 adjacent cards give a combined width of 20 cm (greater than 19 cm), then the greatest number of adjacent cards that can be printed horizontally across the page in this layout is 3.
The height of each card is 9 cm and the height of the page is 29 cm. Since 3 adjacent cards give a combined height of 27 cm (less than 29 cm) and 4 adjacent cards give a combined height of 36 cm (greater than 29 cm), then the greatest number of adjacent cards that can be printed vertically on the page in this layout is 3.
Thus the portrait page layout allows a maximum of \(3\times3=9\) business cards to be printed on a single page, as shown in the diagram below.
Next, we consider the landscape page layout.
The width of each card is 9 cm and the width of the page is 19 cm. Since 2 adjacent cards give a combined width of 18 cm (less than 19 cm) and 3 adjacent cards give a combined width of 27 cm (greater than 19 cm), then the greatest number of adjacent cards that can be printed horizontally across the page in this layout is 2.
The height of each card is 5 cm and the height of the page is 29 cm. Since 5 adjacent cards give a combined height of 25 cm (less than 29 cm) and 6 adjacent cards give a combined height of 30 cm (greater than 29 cm), then the greatest number of adjacent cards that can be printed vertically on the page in this layout is 5.
Thus the landscape page layout allows a maximum of \(2\times5=10\) business cards to be printed on a single page, as shown.
Throughout the solution to this problem, all coordinates represent lengths in metres.
Let the point \(A\) be positioned at \((240,0)\). Then \(OA\) represents a horizontal distance of 240 m, \(AF\) represents a vertical distance of 100 m, and \(\triangle OAF\) is right-angled at \(A\), as shown.
On Monday, Franklin walks from school straight home (a distance of 260 m) at a constant speed of 80 m/min. Since time equals distance divided by speed, it takes Franklin \(\dfrac{260 \textrm{ m}}{80 \textrm{ m/min}}=\dfrac{13}{4}\) (or 3.25) minutes to walk home on Monday.
Points \(F\) and \(G\) have the same \(x\)-coordinate, and so the distance between Franklin’s home and Giizhig’s home equals the difference in their \(y\)-coordinates, or 80 m, as shown.
Thus, it takes Franklin \(\dfrac{13}{4}+\dfrac12=\dfrac{15}{4}\) (or 3.75) minutes to walk from the school to his home and then to the halfway point between their two homes.
Since Giizhig leaves the school at the same time as Franklin, and they meet halfway between the two homes, then it also takes Giizhig \(\dfrac{15}{4}\) minutes to walk from the school to her home and then to the halfway point between their homes.
As in part (a), \(\triangle OAG\) is right-angled at \(A\), and so by the Pythagorean Theorem,
\(GO^2=OA^2+AG^2\) or \(GO^2=(240\textrm{ m})^2+(180\textrm{ m})^2=90\,000\textrm{ m}^2\) and so \(GO=\sqrt{90\,000\textrm{ m}^2}=300\textrm{ m}\).
Therefore, the distance along the straight path from the school to Giizhig’s home to the halfway point between the two homes is \(300 \textrm{ m} + 40 \textrm{ m} = 340 \textrm{ m}\).
Since Giizhig’s speed, \(g\) m/min, equals distance divided by time, then
\(g=340 \div\dfrac{15}{4} =340\times\dfrac{4}{15} =\dfrac{272}{3}\) or \(90\dfrac{2}{3}\).
When \(R_3\) is performed on the list \(5,2,3,1,4,6\), the order of the first three numbers in the list is reversed, and so the new list is \(3,2,5,1,4,6\).
The two Reverse Operations change the order of the first four numbers in the list, \(1,2,3,4\), while the last two numbers, 5 and 6, do not change. Thus, it is reasonable to consider that the first Reverse Operation may be \(R_4\).
After performing \(R_4\) on the original list, the list becomes \(4,3,2,1,5,6\).
Performing \(R_2\) on this list gives the final list \(3,4,2,1,5,6\).
Thus, the two Reverse Operations are \(R_4\) followed by \(R_2\).
(It is worth noting that there are no other ways to do this using exactly two Reverse Operations.)
Each Reverse Operation, with the exception of \(R_6\), does not change the number in the last position of the list. Further, \(R_6\) reverses the order of the entire list and so the first number in the list becomes the last number in the list.
That is, the number 3 moves to the last position only when \(R_6\) is performed on a list in which 3 is in the first position.
Is it possible to perform a Reverse Operation on the original list that moves 3 to the first position of the list?
If \(R_3\) is performed on the original list, \(1,2,3,4,5,6\), the list becomes \(3,2,1,4,5,6\).
If \(R_6\) is then performed on this list, the list becomes \(6,5,4,1,2,3\), as required.
Thus, performing \(R_3\) followed by \(R_6\) results in 3 ending up in the last position of the list and so 2 Reverse Operations achieve the desired result.
Since in (i) we found a way to achieve the desired result using 2 Reverse Operations, we need only to explain why performing 1 Reverse Operation is not possible.
As described in (i), the number 3 moves to the last position only when \(R_6\) is performed on a list in which 3 is in the first position. Since 3 is not in the first postion of the original list, then performing 1 Reverse Operation can never achieve the desired result.
Together, (i) and (ii) show that the minimum number of Reverse Operations that need to be performed on the list \(1,2,3,4,5,6\) so that 3 ends up in the last position is 2.
Performing the Reverse Operations \(R_5\), \(R_2\), \(R_6\), in order, changes the original list from \(1,2,3,4,5,6\) to \(5,4,3,2,1,6\), and then to \(4,5,3,2,1,6\), and finally to \(6,1,2,3,5,4\).
Thus, 3 Reverse Operations can achieve a list of the desired form.
Can the desired result be achieved by performing fewer than 3 Reverse Operations?
As similarly demonstrated in (c), performing the Reverse Operations \(R_4\) and \(R_6\), in order on the original list, will move the number 4 to the last position in the list.
This is the minimum number of Reverse Operations needed to move 4 to the last position in the list and further, these are the only 2 Reverse Operations that move 4 to the last position in the list. (Can you see why?)
However, performing \(R_4\) and \(R_6\), in order, changes the original list from \(1,2,3,4,5,6\) to \(4,3,2,1,5,6\), and then to \(6,5,1,2,3,4\). The second last number in this list is not 5, and so it is not possible to achieve the desired result in 2 Reverse Operations.
Since it is clearly not possible to achieve the desired result in 1 Reverse Operation, then the minimum number of Reverse Operations is 3.
The 3 Reverse Operations \(R_6\), \(R_3\), \(R_6\) also achieves a list of the desired form. Performing \(R_6\), \(R_3\), \(R_6\), in order, changes the original list from \(1,2,3,4,5,6\) to \(6,5,4,3,2,1\) to \(4,5,6,3,2,1\), and finally to \(1,2,3,6,5,4\).
The \(SF\) path that passes through each vertex except \(X\) and \(Y\) is shown.
We begin by labelling the vertices as shown.
Thus, it must be that if an \(SF\) path is to pass through \(C\), it does so by first proceeding from \(S\) to \(C\).
From \(C\), the path must proceed to \(X\) (since it cannot return to \(S\)), and so every \(SF\) path that passes through \(C\) must begin \(S-C-X\). Continuing from this point \(X\), there are exactly 3 directions in which the path may proceed: up to \(A\), right to \(Y\), or down to \(W\). Next, we consider each of these three possible cases separately.
Proceeding up to \(A\) with a goal of passing through \(A\) and \(B\), the path must proceed \(X-A-Z-Y-B-W\). Each edge from \(W\) leads to a vertex that has already been visited and so proceeding up from \(X\) to \(A\) is not possible, as shown.
Proceeding from \(X\) to \(Y\) with a goal of passing through \(A\) and \(B\), the path must proceed \(X-Y-Z-A\) or \(X-Y-B-W\). Each edge from \(A\) leads to a vertex that has already been visited, as does each edge from \(W\), and so proceeding right from \(X\) to \(Y\) is not possible, as shown.
Finally, proceeding down from \(X\) to \(W\) with a goal of passing through \(A\) and \(B\), the path must proceed \(X-W-B-Y-Z-A\). Each edge from \(A\) leads to a vertex that has already been visited and so proceeding down from \(X\) to \(W\) is not possible, as shown.
Therefore, there is no \(SF\) path that passes through all three of the vertices \(A\), \(B\) and \(C\).
We define the “middle column” by labelling the points \(P,Q,R,T,U,V\), as shown.
Each \(SF\) path must pass through at least one of \(Q\) or \(R\), and must also pass through at least one of \(T\) or \(U\).
Each \(SF\) path “enters” the middle column by coming into \(Q\) from the left or by coming into \(R\) from the left.
Each \(SF\) path “leaves” the middle column by going out of \(T\) to the right or by going out of \(U\) to the right.
Each \(SF\) path through the middle column falls into exactly one of four groups of paths. We define these four groups as follows:
\(QT\) path: The portion of an \(SF\) path that comes into \(Q\) from the left and goes out of \(T\) to the right.
\(QU\) path: The portion of an \(SF\) path that comes into \(Q\) from the left and goes out of \(U\) to the right.
\(RT\) path: The portion of an \(SF\) path that comes into \(R\) from the left and goes out of \(T\) to the right.
\(RU\) path: The portion of an \(SF\) path that comes into \(R\) from the left and goes out of \(U\) to the right.
There are exactly 3 \(QT\) paths. These are: \(Q-P-T\), \(Q-U-T\) and \(Q-R-V-U-T\).
There are exactly 3 \(QU\) paths. These are: \(Q-U\), \(Q-P-T-U\) and \(Q-R-V-U\).
There are exactly 4 \(RT\) paths. These are: \(R-Q-P-T\), \(R-Q-U-T\), \(R-V-U-T\), and \(R-V-U-Q-P-T\).
There are exactly 3 \(RU\) paths. These are: \(R-Q-U\), \(R-Q-P-T-U\) and \(R-V-U\).
In each of these cases, the left endpoint (\(Q\) or \(R\)) and the right endpoint (\(T\) or \(U\)) is attached to a horizontal path segment of the adjacent square.
This leaves exactly 18 squares on each side of the middle column through which the path travels.
In the first 18 squares, an \(SF\) path can proceed horizontally either along the bottom edge of a square or along its top edge. For example, the diagram below shows a possible selection of top and bottom edges for the first 8 squares.
These choices of top or bottom edges uniquely determine the path since it is forced to proceed along vertical edges exactly when the path through two adjacent squares has different horizontal segments (one follows a top edge and the other a bottom).
The diagram below shows where these vertical edges must be added to the previous example. There is no choice in the selection of vertical edges once the horizontal edges have been chosen.
It is worth noting that a path cannot proceed along both the top and bottom edges of a given square since such a path would visit a vertex more than once.
Two choices (top or bottom edge) in each of the first 18 squares gives \(2^{18}\) paths.
Let \(M\) be the point left of \(Q\) and let \(N\) be the point left of \(R\), as shown.
The \(2^{18}\) paths finish at either \(M\) or \(N\), and in each case they arrive at the point from the left. That is, the vertical segment \(MN\) is not included in each of the \(2^{18}\) paths.
How many of these 2\(^{18}\) paths “connect” to a \(QT\) path (for example)?
Each of the paths arriving at \(N\) (from the left) may proceed to \(M\) and then to \(Q\), and each of the paths arriving at \(M\) (from the left) may proceed directly to \(Q\).
Thus, there are exactly \(2^{18}\) paths that enter the middle column through \(Q\) (from the left) or \(2^{18}\) paths begin at \(S\) and arrive at \(Q\) from the left.
Similarly, there are \(2^{18}\) that paths begin at \(S\) and arrive at \(R\) (from the left).
Similar arguments show that there are 2\(^{18}\) paths through the last 18 squares, and so there are \(2^{18}\) paths that leave \(T\) to the right, and end at \(F\), and \(2^{18}\) paths that leave \(U\) to the right, and end at \(F\).
From our earlier analysis, there are exactly 3 \(QT\) paths, and so there are \(2^{18}\cdot3\cdot2^{18}=3\cdot2^{36}\) \(SF\) paths that proceed through a \(QT\) path.
There are \(3\cdot2^{36}\) \(SF\) paths that proceed through a \(QU\) path, \(4\cdot2^{36}\) through an \(RT\) path, and \(3\cdot2^{36}\) through an \(RU\) path.
Thus, there is a total of \(2^{36}(3+3+4+3)\) or \(13\cdot2^{36}\) \(SF\) paths.