2019 Fryer Contest
Solutions
(Grade 9)
Wednesday, April 10, 2019
(in North America and South America)
Thursday, April 11, 2019
(outside of North American and South America)
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
The rectangle in Figure A has dimensions \(7\times8\), and thus has perimeter \(2\times7+2\times8\) or 30.
Solution 1
We begin by labelling Figure B as shown.
The width of Figure B is \(PU=7\).
However, the width is also equal to \(QR+ST\).
Since \(QR=3\), then \(ST=7-3=4\).
Similarly, \(PQ+RS=UT=8\) and since \(RS=1\), then \(PQ=7\).
The perimeter of Figure B is \(PQ+QR+RS+ST+TU+UP=7+3+1+4+8+7=30\).
Solution 2
The answer in Solution 1, 30, is equal to the answer inpart (a). Why?
Consider sliding \(RS\) horizontally left to \(QV\), and sliding \(QR\) vertically down to \(VS\), as shown.
Since \(QRSV\) is a rectangle, then \(PVTU\) is a rectangle.
Further, since \(RS=QV\) and \(QR=VS\), then the perimeter of Figure B is equal to the perimeter of rectangle \(PVTU\).
Since \(PV=UT=8\) and \(VT=PU=7\), the perimeter of rectangle \(PVTU\) is 30 (this is the rectangle from part (a)).
Therefore, the perimeter of Figure B is 30.
Following the approach in Solution 2 above, the perimeter of Figure C is equal to the perimeter of a rectangle with side lengths \(k+4\) and \(k+2\).
Since the perimeter of Figure C is 56, then \(2(k+4)+2(k+2)=56\) or \(2k+8+2k+4=56\) and so \(4k=44\) or \(k=11\).
(Alternatively, we could have determined that the two missing lengths in Figure C are each equal to \(k\), and then found the perimeter of Figure C, \(4k+12\), by adding the lengths of the six segments.)
Each of the segments having lengths 4 or 7 may be “pushed out” to show that the perimeter of Figure D is equal to the perimeter of a square with side length \(8n+1\).
That is, the perimeter of Figure D is \(4(8n+1)=32n+4\).
We require the largest integer \(n\) for which \(32n+4<1000\).
Solving this inequality, we get \(32n<996\) or \(n<\frac{996}{32}\) and so \(n<31.125\).
Thus, the largest integer \(n\) for which the perimeter of Figure D is less than 1000 is 31.
In 10 minutes, there are \(10\times 60=600\) seconds.
If the machine is set to make one cut every 8 seconds, then \(\dfrac{600\mbox{ s}}{8\mbox{ s}}=75\) pieces of rope will be cut off in 10 minutes.
Rope is fed into the machine at a constant rate of 2 metres per second.
If the machine is set to make one cut every 3 seconds, then the length of each piece of rope that is cut off is \(2\times3=6\) metres.
Solution 1
Rope is fed into the machine at a constant rate of 2 metres per second, which is equivalent to \(2\times60=120\) metres per minute.
If each piece of rope that is cut off is 30 m long, then the machine is set to make \(\dfrac{120\mbox{ m}}{30\mbox{ m}}=4\) cuts per minute.
Solution 2
Rope is fed into the machine at a constant rate of 2 metres per second.
To cut off a piece of rope 30 m long, the machine must be set to make a cut every \(\dfrac{30}{2}=15\) seconds.
If the machine makes a cut every 15 seconds, then it makes \(\dfrac{60\mbox{ s}}{15\mbox{ s}}=4\) cuts per minute.
Solution 3
In part (b), the machine was set to make one cut every 3 seconds, and so the length of each piece of rope that is cut off is 6 metres.
Since rope is fed into the machine at a constant rate, to cut off a piece of rope that is times longer (30 m is 5 times longer than 6 m), the machine must be set to make each cut 5 times more slowly, or every \(5\times 3=15\) seconds.
If the machine makes a cut every 15 seconds, then it makes \(\dfrac{60\mbox{ s}}{15\mbox{ s}}=4\) cuts per minute.
Solution 1
If the machine is set to make 16 cuts per minute, or 16 cuts every 60 seconds, it will make one cut every \(\dfrac{60\mbox{ s}}{16}=3.75\) seconds. Rope is fed into the machine at a constant rate of metres per second.
Since the machine is set to make one cut every 3.75 seconds, then the length of each piece of rope that is cut off is \(2\times3.75=7.5\) metres.
Solution 2
If the machine is set to make 16 cuts per minute, then every 60 seconds it is set to make 16 cuts.
The rope is fed into the machine at a constant rate of 2 metres per second, and so after 60 seconds, \(60\times2=120\) metres of rope have passed through the machine.
During these 60 seconds, the 120 metres of rope is cut 16 times, and so the length of each piece of rope that is cut off is \(\dfrac{120\mbox{ m}}{16}=7.5\) metres.
Solution 1
In the list of integers beginning at 1, the 6\(^{th}\) multiple of 5 is \(6\times5=30\).
Thus, Tania has listed each of the integers from 1 to 29 with the exception of the positive multiples of 5 less than 30: \(5,10,15,20,25\).
Therefore, just before Tania leaves out the \(6^{th}\) multiple of 5, she has listed \(29-5=24\) integers.
Solution 2
Beginning at 1, each group of five integers has one integer that is a multiple of 5.
For example, the first group of five integers, \(1,2,3,4,5\) has one multiple of 5 (namely 5), and the second group of five integers, \(6,7,8,9,10\) has one multiple of 5 (namely 10).
In Tania’s list of integers, she leaves out the integers that are multiples of 5, and so in every group of five integers, Tania lists four of these integers.
Thus, just before Tania leaves out the \(6^{th}\) multiple of 5, she has listed \(6\times4=24\) integers.
Solution 1
Tania writes 2019 just before leaving out 2020 (since 2020 is a multiple of 5).
Beginning at 1, 2020 is the 404\(^{th}\) multiple of 5 since \(\dfrac{2020}{5}=404\).
That is, the integers from 1 to 2020 contain 404 groups of 5 integers.
Each of these 404 groups contain one integer that is a multiple of 5, and so Tania leaves out 404 integers (including 2020) in the list of all integers from 1 to 2020.
If the \(k^{th}\) integer in Tania’s list is 2019, then \(k=2020-404=1616\).
Solution 2
Tania writes 2019 just before leaving out 2020 (since 2020 is a multiple of 5).
Beginning at 1, 2020 is the 404\(^{th}\) multiple of 5 since \(\dfrac{2020}{5}=404\).
That is, the integers from 1 to 2020 contain 404 groups of 5 integers.
In Tania’s list of integers, she leaves out the integers that are multiples of 5, and so in every group of five integers, Tania lists four of these integers.
If the \(k^{th}\) integer in Tania’s list is 2019, then \(k=404\times4=1616\).
Solution 1
We begin by determining which integers are in Tania’s list.
In each successive group of 5 consecutive integers beginning at 1, Tania lists 4 of the integers (since she leaves out each integer that is a multiple of 5).
That is, in each of these groups of 5 integers, Tania’s list contains \(\dfrac45\) of the integers.
Consider all positive integers from 1 to \(n\), where \(n\) is a multiple of 5.
Of these \(n\) integers, Tania’s list contains \(\dfrac45n\) integers.
Tania’s list contains 200 integers, and so \(\dfrac45n=200\) or \(n=\dfrac{200\times5}{4}=250\).
That is, if Tania lists the positive integers from 1 to 250 and leaves out the integers that are multiples of 5, her list will contain \(\dfrac45\times 250=200\) integers.
We are required to determine the sum, \(1+2+3+4+6+\cdots+244+246+247+248+249\), of the first 250 positive integers with the integers that are multiples of 5 removed.
We will proceed to determine this sum by first calculating the sum of all integers from 1 to 250, and then subtracting from that sum all integers in this list that are multiples of 5.
The sum of the integers from 1 to \(n\) is given by \(\dfrac12n(n+1)\), and so the sum of the integers from 1 to 250 is equal to \(\dfrac12(250)(251)=31\,375\).
The multiples of 5 in this list, \(5+10+15+\cdots+240+245+250\), can be written as \(5(1+2+3+\cdots+48+49+50)\) by removing the common factor 5 (since each is a multiple of 5).
This sum is equal to \(5\times \dfrac12(50)(51)=6375\).
If Tania lists the positive integers, in order, leaving out the integers that are multiples of 5, the sum of the first 200 integers in her list is \(31\,375-6375=25\,000\).
Solution 2
As was shown in Solution 1, the sum of the first 200 integers in Tania’s list is the sum \(1+2+3+4+6+\cdots+244+246+247+248+249\).
The sum of the first and last integers in this list is \(1+249=250\).
The sum of the second integer and the second last integer is \(2+248=250\).
The sum of the third integer and the third last integer is \(3+247=250\).
We continue in this way moving toward the middle of the list.
That is, we move one number to the right of the previous first number, and one number to the left of the previous second number.
Doing so, we recognize that
when the first number in the new pair is one more than the previous first number, then the number it is paired with is one less than the previous second number, and
when the first number in the new pair is two more than the previous first number (as is the case when a multiple of 5 is omitted), then the number it is paired with is two less than the previous second number.
That is, as we continue moving toward the middle of Tania’s list, each pair will continue to have a sum equal to 250.
Since there are 200 numbers in Tania’s list, there are 100 such pairs, each having a sum equal to 250.
Thus, if Tania lists the positive integers, in order, leaving out the integers that are multiples of 5, the sum of the first 200 integers in her list is \(250\times100=25\,000\).
We begin by observing that when \(x=18\), \[12\times 18\times 24=12\times (6\times 3)\times(2\times12)=12\times6\times6\times 12=(12\times 6)^2=72^2.\] Therefore, \(12,18,24\) is a Shonk sequence.
Next, we will show that \(x=18\) is the only value for which \(12,x,24\) is a Shonk sequence.
In order for \(12,x,24\) to be a Shonk sequence, we must have \(12<x<24\).
This means \(x\) is one of \(13,14,15,16,17,18,19,20,21,22,\) and \(23\).
When \(x=13\), the product \(12\times13\times24=3744\) is not a perfect square.
This can be checked on a calculator, but if we can understand why it is not a perfect square, we will be able to apply the reasoning again.
Suppose there is some integer \(n\) so that \(n^2=12\times13\times 24\).
This means \(13\) is a factor of \(n^2\).
However, \(13\) is prime, so this means \(13\) must be a factor of \(n\) itself.
This means \(n^2\) has at least two factors of \(13\), so \(12\times 13\times 24\) must have at least two factors of \(13\).
However, neither \(12\) nor \(24\) has a factor of \(13\), so we conclude that \(12\times13\times 24\) is not a perfect square.
Therefore, \(12,13,24\) is not a Shonk sequence, so \(x\neq 13\).
The key to the reasoning above is that \(13\) is a prime number.
Thus, the same reasoning can be applied to conclude that \(x\neq 17\), \(x\neq 19\), and \(x\neq 23\).
We now suppose \(x=14\). In this case, we have that \(12\times 14\times 24\) has a factor of \(7\).
If \(12\times 14\times 24=n^2\) for some integer \(n\), then \(7\) is a factor of \(n^2\), and since \(7\) is prime, this means \(n\) must have a factor of \(7\).
Therefore, \(n^2=12\times14\times24\) has at least two factors of \(7\), but this is not the case as \(14\) has only one factor of \(7\), and neither \(12\) nor \(24\) has a factor of \(7\).
Thus, \(12\times14\times24\) is not a perfect square, so \(12,14,24\) is not a Shonk sequence and \(x\neq 14\).
Since \(21=3\times 7\), the same reasoning can be applied to show that \(x\neq 21\).
That is, for \(12\times21\times24\) to be a perfect square, it must have at least two factors of \(7\), but it only has one.
We have now reduced the list of possible \(x\) values to \(15,16,18,20\), and \(22\).
Since \(15\) and \(20\) both have a factor of \(5\), the products \(12\times 15\times 24\) and \(12\times 20\times 24\) each have exactly one factor of the prime number \(5\), so they cannot be perfect squares.
This means neither of \(12,15,24\) and \(12,20,24\) are Shonk sequences, so \(x\neq 15\) and \(x\neq 20\).
Since \(22=2\times 11\), we can also conclude that \(x\neq 22\) since \(12\times 22\times 24\) has exactly one factor of the prime number \(11\), so \(12\times 22\times 24\) is not a perfect square, hence, \(12,22,24\) is not a Shonk sequence.
We have now reduced the possibilities to \(x=16\) and \(x=18\).
We will now show that \(12\times 16\times 24\) is not a perfect square.
To do this, we write it as a product of prime numbers: \[12\times 16\times 24=(2\times2\times3)\times(2\times2\times2\times2)\times(2\times2\times2\times3)\] We see that \(12\times16\times24\) is a product of only the primes \(2\) and \(3\).
In particular, there are nine factors of \(2\) and two factors of \(3\).
If \(12\times 16\times 24=n^2\) for some integer \(n\), then \(n^2\) must therefore have exactly nine factors of \(2\).
However, each factor of \(n\) has the same number of factors of \(2\), so \(n^2\) must have an even number of factors of \(2\).
Since \(12\times 16\times 24\) has an odd number of factors of \(2\), we conclude that \(12\times 16\times 24\neq n^2\) for any integer \(n\), so is not a perfect square.
Therefore, \(12,16,24\) is not a Shonk sequence so \(x\neq 16\).
We have ruled out all other possibilities of \(x\), and thus we conclude that \(12,x,24\) is a Shonk sequence when \(x=18\) only.
Building on the reasoning from part (a), we will use the observation that in any perfect square, there are an even number of factors of any given prime number.
For example, \(100\) is a perfect square and \(100=2\times2\times5\times 5\), which is a product with two factors of \(2\) and two factors of \(5\).
The example given in the question has \(18^2=324\), which equals \(2\times2\times3\times3\times3\times3\), which is a product of two factors of \(2\), and four factors of \(3\).
Indeed, if \(n\) is an integer with prime factor \(p\), then there is a “copy" of \(p\) in each factor of \(n\) occurring in \(n^2\).
On the other hand, if a number factors into a product of primes where each prime occurs an even number of times, then the primes can be grouped to see that the number is a perfect square.
For example, the number with four factors of \(2\), two factors of \(3\), and six factors of \(5\) is a perfect square since \[2\times2\times2\times2\times3\times3\times5\times5\times5\times5\times5\times5=(2\times2\times3\times5\times5\times5)^2\]
In order for \(28,y,z,65\) to be a Shonk sequence, we need \(28\times y\times z\times 65\) to be a perfect square.
By factoring \(28\) and \(65\) into primes, we have that \[2\times 2\times 7\times y\times z\times 5\times 13\] must be a perfect square.
The primes 2, \(5\), \(7\), and \(13\) each occur in this factorization.
From the discussion above, there must be an even number of each of these primes if the product is to be a perfect square.
Therefore, there must be another factor of each of the prime numbers \(5,7\), and 13 in the product.
Furthermore, these primes must occur as factors of either \(y\) or \(z\).
This means that one of \(y\) and \(z\) must have a factor of \(5\), one of \(y\) and \(z\) must have a factor of \(7\), and one of \(y\) and \(z\) must have a factor of \(13\).
There are two variables and three primes, so one of \(y\) and \(z\) must have two of these prime factors.
Since \(5\times 13=65\) and \(7\times 13=91\), and \(y\) and \(z\) must each be less than \(65\), then \(5\) and \(13\) cannot occur together as factors of \(y\) or \(z\), as well \(7\) and \(13\) cannot occur together as factors of \(y\) or \(z\).
Therefore, either \(5\) and \(7\) are both factors of \(y\) or \(5\) and \(7\) are both factors of \(z\).
This means one of \(y\) or \(z\) is a multiple of \(5\times7=35\).
Any positive multiple of \(35\) other than \(35\) itself is larger than \(65\), so we actually get that \(y=35\) or \(z=35\).
The variable which is not equal to \(35\) must be a multiple of \(13\) between \(28\) and \(65\).
The only such multiples of \(13\) are \(39\) and \(52\) which are both larger than \(35\).
This forces \(y=35\), and now we know that either \(z=39\) or \(z=52\).
If \(z=39\), we get \[28\times y\times z\times 65=(2\times 2\times 7)\times (5\times 7)\times (3\times 13)\times (5\times 13)\] but this has only one factor of \(3\), so it cannot be a perfect square.
On the other hand, if \(z=52\), we have \[\begin{array}{rcl} 28\times y\times z\times 65&=&(2\times 2\times 7)\times (5\times 7)\times (2\times 2\times 13)\times (5\times 13) \\ &=& (2\times 2\times5\times 7\times 13)^2 \\ &=& 1820^2 \end{array}\]
Therefore, the only Shonk sequence of the form \(28,y,z,65\) has \(y=35\) and \(z=52\).
The longest Shonk sequence each of whose terms is an integer between \(1\) and \(12\) inclusive has length \(9\).
An example of such a sequence is \(1,2,3,4,5,6,8,9,10\).
Each term after the first is greater than the previous term, so we need to verify that the product of all terms is a perfect square.
By splitting each term into a product of primes, we get \[\begin{aligned}
&1\times 2\times 3\times 4\times 5\times 6\times 8\times 9\times 10\\ = & 2\times 3\times (2\times 2)\times 5\times(2\times 3)\times (2\times 2\times 2)\times (3\times 3)\times (2\times 5) \\
= & (2\times 2\times 2\times 2\times 3\times 3\times 5)^2 \\
= & 720^2\end{aligned}\]
We will now show that no Shonk Sequence, each of whose terms is between \(1\) and \(12\) inclusive, can have length greater than \(9\).
First, note that the only number between \(1\) and \(12\) inclusive with a factor of \(7\) is \(7\) itself.
Therefore, if \(7\) were included in the sequence, the product of all terms could not possibly be a perfect square.
Similarly, if \(11\) were included in the sequence, the product could not possibly be a perfect square since no number other than \(11\) between \(1\) and \(12\) inclusive has a factor of \(11\).
This means the sequence must be made up of the numbers \(1,2,3,4,5,6,8,9,10,\) and \(12\).
There are \(10\) numbers in this list, so the only way to have a longer Shonk sequence than the one above is for it to include all \(10\) of these integers.
However, the product \[1\times 2\times 3\times 4\times 5\times 6\times 8\times 9\times 10\times 12\] has five factors of \(3\) (one coming from each of \(3\), \(6\), and \(12\), and two coming from \(9\)).
Therefore, it cannot be a perfect square since a perfect square must have an even number of occurrences of any prime factor.
We need two related facts about perfect squares:
(F1) A positive integer \(n\) is a perfect square exactly when each prime factor occurs an even number of times. (We saw this in (b).)
(F2) Suppose that integers \(r\), \(s\) and \(t\) satisfy \(r = st\). If two of \(r,s,t\) are perfect squares, then the third one is a perfect square. This comes from the fact that the prime factors of two of these occur an even number of times each exactly when the prime factors in their product or (integer) quotient also occur an even number of times.
Suppose that \(m,1176,n,48\,400\) is an SDSS. Then
\(m<1176<n<48\,400\)
\(m \times 1176 \times n\) is a perfect square, and
\(1176 \times n \times 48\,400\) is a perfect square, and
\(m\times1176 \times n \times 48\,400\) is a perfect square.
Since \(1176 \times n \times 48\,400\) is a perfect square, and \(m \times (1176 \times n \times 48\,400)\) is a perfect square, then \(m\) is perfect square (by F2).
Also, since \(48\,400 = 220^2\) and \(1176 = 6 \times 14^2\), then \(1176 \times n \times 48\,400 = (220 \times 14)^2 \times (6 \times n)\) and this is a perfect square exactly when \(6n\) is a perfect square.
Therefore, if \(m,1176,n,48\,400\) is an SDSS, then \(m\) and \(6n\) are both perfect squares.
Further, if \(m\) and \(6n\) are both perfect squares, then \(m \times 1176 \times n\), \(1176 \times n \times 48\,400\), and \(m\times1176 \times n \times 48\,400\) are all perfect squares.
We can now answer the question by counting the number of pairs of positive integers \((m,n)\) satisfying \(1\le m<1176\) and \(1176<n<48\,400\), with \(m\) a perfect square and \(6n\) a perfect square.
Note that \(34^2=1156\) which is smaller than \(1176\), and \(35^2=1225\) which is larger than \(1176\), so the possible values of \(m\) are \(1^2,2^2,3^2,\dots,33^2,34^2\).
There are \(34\) possibilities for the value of \(m\).
We know that \(6\times 14^2=1176\), which is not larger than \(1176\), so the smallest possible value of \(n\) is \(6\times 15^2\).
Observe that \(6\times89^2=47\,526<48\,400\), but \(6\times90^2=48\,600>48\,400\).
Thus, the possible values of \(n\) are \[6\times15^2,6\times16^2,\dots,6\times89^2\] There are \(89-14=75\) such values.
Thus, the number of pairs \((m,n)\) such that \(m,1176,n,48\,400\) an SDSS is \(34\times75=2550\).