2015 Hypatia Contest
Solutions
(Grade 11)
Thursday, April 16, 2015 (in North America and South America)
Friday, April 17, 2015 (outside of North American and South America)
Thursday, April 16, 2015 (in North America and South America)
Friday, April 17, 2015 (outside of North American and South America)
©2015 University of Waterloo
The distance from the end of any car (boxcar or engine car) to the end of the next car is the sum of the 2 m distance between the cars and the 15 m length of a boxcar, or 17 m.
Thus the distance from the end of the engine car to the end of the 10\(^{th}\) boxcar (the end of the train) is \(10\times 17=170\) m. Since the engine car has a length of 26 m, then the total length of a train with 10 boxcars is \(26+170=196\) m.
The total length of a train with \(n\) boxcars is \((26+15n+2n)\) m (one 26 m engine car, \(n\) 15 m boxcars, and a 2 m distance in front of each of the \(n\) boxcars).
That is, the total length of a train with \(n\) boxcars is \((26+17n)\) m.
If a train has a length of 2015 m, then \(26+17n=2015\) or \(17n=1989\) and so \(n=117\). A train with a total length of 2015 m has 117 boxcars.
A train with 14 boxcars has length \(26+17(14)=264\) m.
The length of time during which a portion of the train is in Canada and a portion of the train is in the United States at the same time is equal to the total length of time it takes the train to cross the border. (When the train is crossing the border, portions of the train are in both countries at the same time.)
The train begins to cross the border when the front of the engine car reaches the border. The train finishes crossing the border when the end of the last boxcar reaches the border and so the front is 264 m farther.
That is, the length of time required for the train to cross the border is equal to the length of time it takes the train to travel a distance equal to the length of the train, or 264 m.
Since the train is travelling at a speed of 1.6 m/s, then the time required to travel 264 m is \(\frac{264}{1.6}=165\) s. Therefore, the length of time during which a portion of the train is in Canada and a portion of the train is in the United States at the same time is 165 s.
The two-digit positive integers \(AB\) and \(BA\) equal \(10A+B\) and \(10B+A\), respectively.
Solving \(AB-BA=72\), we get \((10A+B)-(10B+A)=72\) or \(9A-9B=72\) and so \(A-B=8\).
Since \(A\) and \(B\) are positive digits, then the only possibility for which \(A-B=8\) occurs when \(A=9\) and \(B=1\). (Verify for yourself that this is indeed the only possibility.)
Therefore, the positive integer \(AB\) is 91. (We may check that \(AB-BA=91-19=72\).)
The two-digit positive integers \(MN\) and \(NM\) equal \(10M+N\) and \(10N+M\), respectively.
Solving \(MN-NM=80\), we get \((10M+N)-(10N+M)=80\) or \(9M-9N=80\) and so \(9(M-N)=80\).
Since \(M\) and \(N\) are positive digits, then \(M-N\) is an integer and so \(9(M-N)\) is a multiple of 9.
However, 80 is not a multiple of 9 and so \(9(M-N)\neq80\). Therefore, it is not possible that \(MN-NM=80\).
The three-digit positive integers \(PQR\) and \(RQP\) equal \(100P+10Q+R\) and \(100R+10Q+P\), respectively.
Simplifying \(PQR-RQP\), we get \((100P+10Q+R)-(100R+10Q+P)\) or \(99P-99R\) or \(99(P-R)\).
Since \(P\) and \(R\) are positive digits, the maximum possible value of \(P-R\) is 8 (which occurs when \(P\) is as large as possible and \(R\) is as small as possible, or \(P=9\) and \(R=1\)).
Since \(P>R\), the minimum possible value of \(P-R\) is 1 (which occurs when \(P=9\) and \(R=8\), for example).
That is, \(1\leq P-R\leq 8\) and so there are exactly 8 possible integer values of \(P-R\).
(Verify for yourself that there are values for \(P\) and \(R\) so that \(P-R\) is equal to each of the integers from 1 to 8.)
Since \(PQR-RQP=99(P-R)\) and there are exactly 8 possible values of \(P-R\), then there are exactly 8 possible values of \(PQR-RQP\). (We note that the value of \(PQR-RQP\) does not depend on the value of the digit \(Q\).)
Diagram 1 illustrates that \(T(3)=9\).
To determine \(T(4)\), add 1 line segment to Diagram 1 as shown in Diagram 2.
We are told that this new (4\(^{th}\)) line segment must intersect each of the existing 3 line segments exactly once, creating 3 new points of intersection (labelled \(1,2,3\)).
This 4\(^{th}\) line segment also adds 2 new endpoints (labelled \(4\) and \(5\)) distinct from the previous 3 new points.
In addition, each of the points which exist in the illustration of \(T(3)\) (Diagram 1) continue to exist in the illustration of \(T(4)\) (Diagram 2) and are distinct from each of the new points which were added.
Therefore, we get \[\begin{aligned} T(4)& =T(3)+3+2\\ & =9+3+2\\ & =14\end{aligned}\] Diagram 2 illustrates that \(T(4)=14\).
To determine \(T(5)\), add 1 line segment to Diagram 2 as shown in Diagram 3.
We are told that this new (5\(^{th}\)) line segment must intersect each of the existing 4 line segments exactly once, creating 4 new points of intersection (labelled \(1,2,3,4\)).
This 5\(^{th}\) line segment also adds 2 new endpoints (labelled \(5\) and \(6\)) distinct from the previous 4 new points.
In addition, each of the points which exist in the illustration of \(T(4)\) (Diagram 2) continue to exist in the illustration of \(T(5)\) (Diagram 3) and are distinct from each of the new points which were added.
Therefore, we get \[\begin{aligned} T(5)& =T(4)+4+2\\ & =14+4+2\\ & =20\\\end{aligned}\]
Therefore, \(T(4)=14\) and \(T(5)=20\).
As in part (a), consider finding \(T(n)\) with the help of (in terms of) \(T(n-1)\) for any integer \(n\geq2\).
To determine \(T(n)\), add 1 line segment to any illustration of \(T(n-1)\).
This new (\(n^{th}\)) line segment must intersect each of the existing \(n-1\) line segments exactly once, creating \(n-1\) new points of intersection.
This \(n^{th}\) line segment also adds 2 new endpoints (distinct from the previous \(n-1\) points).
In addition, each of the points which exist in the illustration of \(T(n-1)\) continue to exist in the illustration of \(T(n)\) and are distinct from each of the new points which were added. Therefore, we get \(T(n)=T(n-1)+(n-1)+2\) or \(T(n)=T(n-1)+n+1\) and so \(T(n)-T(n-1)=n+1\) for all \(n\geq2\).
From part (b), \(T(n)-T(n-1)=n+1\) and so \(T(n)=T(n-1)+n+1\).
That is, the addition of an \(n^{th}\) line segment increases \(T(n-1)\) by \(n+1\).
For example since \(T(1)=2\), then \(T(2)=T(1)+3=2+3\).
For small values of \(n\), we determine \(T(n)\) in the table below.
| \(n\) | \(T(n)=T(n-1)+n+1, n\geq2\) |
|---|---|
| 2 | \(T(2)=T(1)+3=2+3\) |
| 3 | \(T(3)=T(2)+4=2+3+4\) |
| 4 | \(T(4)=T(3)+5=2+3+4+5\) |
| 5 | \(T(5)=T(4)+6=2+3+4+5+6\) |
| 6 | \(T(6)=T(5)+7=2+3+4+5+6+7\) |
| ⋮ | ⋮ |
We may use the pattern in the table above to establish an equation for \(T(n)\).
What is the pattern?
Consider for example the row for \(n=5\).
\(T(5)\) is the sum of the positive integers from 2 to \(n+1=5+1=6\).
This is true for each of the rows shown in the table.
That is, \(T(n-1)=2+3+4+\dots+n\) for any positive integer \(n\geq3\).
(Verify that this is true for each of the rows shown in the table.)
Since the addition of an \(n^{th}\) line segment increases \(T(n-1)\) by \(n+1\), then \(T(n)=T(n-1)+n+1\) and so \(T(n)=(2+3+4+\dots+n)+n+1\).
Reorganizing this equation for \(T(n)\), we get \[T(n)=1+2+3+4+\cdots+n+n.\] Since the sum of the first \(n\) positive integers \(1+2+3+4+\cdots+n\) is equal to \(\dfrac{n(n+1)}{2}\), then \(T(n)=\dfrac{n(n+1)}{2}+n\).
Solving \(T(n)=2015\), we get
\[\begin{aligned} \dfrac{n(n+1)}{2}+n& =2015\\ n(n+1)+2n& =4030\\ n^2+3n& =4030\\ n^2+3n-4030& =0\\ (n-62)(n+65)& =0\end{aligned}\] and so \(n=62\) (since \(n>0\)). (We could use the quadratic formula if we didn’t see how to factor the quadratic.) Therefore, \(n=62\) is the only value of \(n\) for which \(T(n)=2015\).
Since \(125 = 5^3\), then the positive divisors of \(125\) are \(5^0, 5^1, 5^2, 5^3\) or \(1,5,25,125\).
Therefore, for each positive integer \(a\) from 1 to 125 inclusive, the possible values of \(\gcd(a,125)\) are \(1, 5, 25, 125\).
The \(\gcd(a,125) = 125\) exactly when \(a\) is divisible by 125. Since \(1 \leq a \leq 125\) and there is only one multiple of 125 in this range, then \(\gcd(a,125) = 125\) only when \(a=125\).
\(\gcd(a,125) = 25\) exactly when \(a\) is divisible by 25 and not by 125.
These \(a\) are each of the form \(a=25k\) for some positive integer \(k\).
The possible values of \(a\) in the range \(1 \leq a < 125\) are 25, 50, 75, and 100.
\(\gcd(a,125) = 5\) exactly when \(a\) is divisible by 5 and not by 25.
There are 25 multiples of 5 between 1 and 125, inclusive.
5 of these have a \(\gcd\) with 125 of 25 or 125, as above.
The remaining \(25-5=20\) multiples of 5 must have a \(\gcd\) with 125 of 5.
\(\gcd(a,125)=1\) exactly when \(a\) is not divisible by 5.
Since there are 25 multiples of \(5\) between 1 and 125, inclusive, then there are \(125-25=100\) integers in this range that are not multiples of 5. In summary, when the positive integers \(a\) with \(1 \leq a \leq 125\) are considered, there is/are
1 integer \(a\) for which \(\gcd(a,125)=125\)
4 integers \(a\) for which \(\gcd(a,125)=25\)
20 integers \(a\) for which \(\gcd(a,125)=5\)
100 integers \(a\) for which \(\gcd(a,125)=1\)
Therefore, \[\begin{aligned} P(125) & = \gcd(1,125)+\gcd(2,125)+\cdots + \gcd(124,125)+\gcd(125,125)\\ & = 1(125) + 4(25) + 20(5)+100(1)\\ & = 425\end{aligned}\]
Since \(r\) is a prime number, the positive divisors of \(r^2\) are \(1, r, r^2\).
Since \(s\) is a prime number, the positive divisors of \(s\) are \(1,s\).
Since \(r\) and \(s\) are different prime numbers, then \(\gcd(r^2,s)=1\). (There are no common positive divisors other than 1 in these two lists.)
Therefore, \(P(r^2s) = P(r^2)P(s)\), from the given fact.
To calculate \(P(s)\), we proceed as in (a).
For each positive integer \(a\) with \(1 \leq a \leq s\), the possible values of \(\gcd(a,s)\) are \(1\) and \(s\).
The only multiple of \(s\) in the given range is \(a=s\), so there is only one \(a\) (namely \(a=s\)) for which \(\gcd(a,s)=s\).
There are thus \(s-1\) integers \(a\) for which \(\gcd(a,s)=1\).
Therefore,
\[\begin{aligned} P(s) & = \gcd(1,s)+\gcd(2,s)+\cdots+\gcd(s-1,s)+\gcd(s,s) \\ & = 1(s)+(s-1)1 \\ & = 2s-1\end{aligned}\] In a similar way, there is 1 integer \(a\) with \(1 \leq a \leq r^2\) for which \(\gcd(a,r^2)=r^2\), and \(r-1\) integers \(a\) with \(\gcd(a,r^2)=r\), and \(r^2-r\) integers \(a\) with \(\gcd(a,r^2)=1\).
Therefore,
\[\begin{aligned} P(r^2) & = \gcd(1,r^2)+\gcd(2,r^2)+\cdots+\gcd(r^2-1,r^2)+\gcd(r^2,r^2) \\ & = 1(r^2)+(r-1)r+(r^2-r)1 \\ & = 3r^2 - 2r \\ & = r(3r-2)\end{aligned}\] Therefore, \(P(r^2s)=P(r^2)P(s)=r(3r-2)(2s-1)\), as required.
We prove that \(P(r^2s)\) can never be equal to a power of a prime number by assuming that \(P(r^2s)\) equals \(t^n\) for some prime number \(t\) and positive integer \(n\), and obtaining a contradiction.
From (b), we obtain \(r(3r-2)(2s-1)=t^n\).
Since the right side is a power of a prime number, then the only divisors of the right side are powers of \(t\).
Therefore, each of the factors on the left side must be powers of \(t\).
Since \(r\) is a factor on the left side and \(r\) is itself a prime, then \(r=t\).
Therefore, \(3r-2=3t-2\) must also be a power of \(t\).
If \(3t-2=t\), then \(t=1\), which is not prime.
If \(3t-2=t^2\) and \(t\) is prime, then \(t^2 - 3t+2=0\) or \((t-2)(t-1)=0\) and so \(t=2\) or \(t=1\). Since \(t\) is to be a prime number, then if \(3t-2=t^2\), we must have \(t=2\).
This also tells us that if \(t=2\), then \(3t-2\) is only a power of a prime when \(3t-2=t^2\).
Can \(3t-2 = t^u\) for some integer \(u > 2\) and prime \(t>2\)?
If \(u>2\), then \(t^u > t^2\), since \(t>1\).
If \(t > 2\), then \(t^2 - 3t + 2 = (t-2)(t-1) > 0\) so \(t^2 > 3t-2\).
Thus, if \(u>2\), then \(t^u > t^2 > 3t-2\), so \(3t-2 \neq t^u\).
Therefore, if \(3t-2\) is a power of \(t\), then \(t = 2\).
If \(t=2\), then \(t\) and \(3t-2\) are both powers of \(t=2\). Furthermore, \(t=2\) is the only prime for which this can work.
But in this case, \(2s-1\) is odd and so cannot be a power of \(t=2\).
This contradicts our original assumption. Therefore, \(P(r^2s) = r(3r-2)(2s-1)\) cannot be the power of a prime number.
We note that \(243= 3^5\). We try some different possible forms for \(m\).
Suppose that \(m = rs\) for some prime numbers \(r\) and \(s\).
Then \(P(m)=P(rs)=(2r-1)(2s-1)\).
Are there prime numbers \(r\) and \(s\) for which \((2r-1)(2s-1)=243\)?
Note that if \(p\) is prime, then \(p \geq 2\) so \(2p-1 \geq 3\).
Therefore, we could have \(2r-1=3\) and \(2s-1=81\) (which gives \(r=2\) and \(s=41\) which are both prime) or \(2r-1=9\) and \(2s-1=27\) (which gives \(r=5\) (prime) and \(s=14\) (not prime)).
Therefore, \(P(82) = P(2\cdot 41) = 3\cdot 81 = 243\).
Since \(243\) is a power of a prime, then from part (c), \(P(r^2s) \neq 243\) for all primes \(r\) and \(s\).
Let’s next see if \(P(r^3s)\) can equal 243.
Using a similar derivation to that in (a), we can see that \[P(r^3) = 1(r^3) + (r-1)r^2 + (r^2-r)r + (r^3-r^2)(1) = 4r^3 - 3r^2\] Therefore, \(P(r^3s) = P(r^3)P(s) = (4r^3-3r^2)(2s-1) = r^2(4r-3)(2s-1)\).
If \(r^2(4r-3)(2s-1) = 243\), then since \(r\) is prime and a factor of the left side, we must have \(r=3\).
Therefore, \(3^2 (4(3)-3)(2s-1) = 243\) or \(81(2s-1) = 243\) or \(2s-1=3\), which gives \(s=2\).
Thus, \(P(54) = P(3^3 \cdot 2) = 243\). Therefore, \(m=82\) and \(m=54\) both satisfy \(P(m)=243\).