CEMC Banner

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)

©2015 University of Waterloo


    1. 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 10th boxcar (the end of the train) is 10×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.

    2. 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.

    3. 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 2641.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.

    1. The two-digit positive integers AB and BA equal 10A+B and 10B+A, respectively.

      Solving ABBA=72, we get (10A+B)(10B+A)=72 or 9A9B=72 and so AB=8.

      Since A and B are positive digits, then the only possibility for which AB=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 ABBA=9119=72.)

    2. The two-digit positive integers MN and NM equal 10M+N and 10N+M, respectively.

      Solving MNNM=80, we get (10M+N)(10N+M)=80 or 9M9N=80 and so 9(MN)=80.

      Since M and N are positive digits, then MN is an integer and so 9(MN) is a multiple of 9.

      However, 80 is not a multiple of 9 and so 9(MN)80. Therefore, it is not possible that MNNM=80.

    3. The three-digit positive integers PQR and RQP equal 100P+10Q+R and 100R+10Q+P, respectively.

      Simplifying PQRRQP, we get (100P+10Q+R)(100R+10Q+P) or 99P99R or 99(PR).

      Since P and R are positive digits, the maximum possible value of PR 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 PR is 1 (which occurs when P=9 and R=8, for example).

      That is, 1PR8 and so there are exactly 8 possible integer values of PR.

      (Verify for yourself that there are values for P and R so that PR is equal to each of the integers from 1 to 8.)

      Since PQRRQP=99(PR) and there are exactly 8 possible values of PR, then there are exactly 8 possible values of PQRRQP. (We note that the value of PQRRQP does not depend on the value of the digit Q.)

    1. Diagram 1 illustrates that T(3)=9.

      Three line segments. The first two segments intersect in the shape of an X. The third line segment is placed vertically so that it intersects the first and second in one place each.

      Diagram 1

      To determine T(4), add 1 line segment to Diagram 1 as shown in Diagram 2.

      A fourth line segment is placed horizontally so that it intersects teach of the other three line segments once. The new points of intersection are labelled 1, 2, and 3. The endpoints s of the fourth line segment are labelled 4 and 5.

      Diagram 2

      We are told that this new (4th) line segment must intersect each of the existing 3 line segments exactly once, creating 3 new points of intersection (labelled 1,2,3).

      This 4th 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 T(4)=T(3)+3+2=9+3+2=14 Diagram 2 illustrates that T(4)=14.

      To determine T(5), add 1 line segment to Diagram 2 as shown in Diagram 3.

      A fifth line segment is placed so that it intersects each of the other four line segments once. The new points of intersection are labelled 1, 2, 3, and 4 respectively, and the endpoints of the fourth line segment are labelled 5 and 6.

      Diagram 3

      We are told that this new (5th) 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 5th 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 T(5)=T(4)+4+2=14+4+2=20

      Therefore, T(4)=14 and T(5)=20.

    2. As in part (a), consider finding T(n) with the help of (in terms of) T(n1) for any integer n2.

      To determine T(n), add 1 line segment to any illustration of T(n1).

      This new (nth) line segment must intersect each of the existing n1 line segments exactly once, creating n1 new points of intersection.

      This nth line segment also adds 2 new endpoints (distinct from the previous n1 points).

      In addition, each of the points which exist in the illustration of T(n1) 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(n1)+(n1)+2 or T(n)=T(n1)+n+1 and so T(n)T(n1)=n+1 for all n2.

    3. From part (b), T(n)T(n1)=n+1 and so T(n)=T(n1)+n+1.

      That is, the addition of an nth line segment increases T(n1) 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(n1)+n+1,n2
      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(n1)=2+3+4++n for any positive integer n3.

      (Verify that this is true for each of the rows shown in the table.)

      Since the addition of an nth line segment increases T(n1) by n+1, then T(n)=T(n1)+n+1 and so T(n)=(2+3+4++n)+n+1.

      Reorganizing this equation for T(n), we get T(n)=1+2+3+4++n+n. Since the sum of the first n positive integers 1+2+3+4++n is equal to n(n+1)2, then T(n)=n(n+1)2+n.

      Solving T(n)=2015, we get

      n(n+1)2+n=2015n(n+1)+2n=4030n2+3n=4030n2+3n4030=0(n62)(n+65)=0 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.

    1. Since 125=53, then the positive divisors of 125 are 50,51,52,53 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 1a125 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 1a<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 255=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 12525=100 integers in this range that are not multiples of 5. In summary, when the positive integers a with 1a125 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, P(125)=gcd(1,125)+gcd(2,125)++gcd(124,125)+gcd(125,125)=1(125)+4(25)+20(5)+100(1)=425

    2. Since r is a prime number, the positive divisors of r2 are 1,r,r2.

      Since s is a prime number, the positive divisors of s are 1,s.

      Since r and s are different prime numbers, then gcd(r2,s)=1. (There are no common positive divisors other than 1 in these two lists.)

      Therefore, P(r2s)=P(r2)P(s), from the given fact.

      To calculate P(s), we proceed as in (a).

      For each positive integer a with 1as, 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 s1 integers a for which gcd(a,s)=1.

      Therefore,

      P(s)=gcd(1,s)+gcd(2,s)++gcd(s1,s)+gcd(s,s)=1(s)+(s1)1=2s1 In a similar way, there is 1 integer a with 1ar2 for which gcd(a,r2)=r2, and r1 integers a with gcd(a,r2)=r, and r2r integers a with gcd(a,r2)=1.

      Therefore,

      P(r2)=gcd(1,r2)+gcd(2,r2)++gcd(r21,r2)+gcd(r2,r2)=1(r2)+(r1)r+(r2r)1=3r22r=r(3r2) Therefore, P(r2s)=P(r2)P(s)=r(3r2)(2s1), as required.

    3. We prove that P(r2s) can never be equal to a power of a prime number by assuming that P(r2s) equals tn for some prime number t and positive integer n, and obtaining a contradiction.

      From (b), we obtain r(3r2)(2s1)=tn.

      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, 3r2=3t2 must also be a power of t.

      If 3t2=t, then t=1, which is not prime.

      If 3t2=t2 and t is prime, then t23t+2=0 or (t2)(t1)=0 and so t=2 or t=1. Since t is to be a prime number, then if 3t2=t2, we must have t=2.

      This also tells us that if t=2, then 3t2 is only a power of a prime when 3t2=t2.

      Can 3t2=tu for some integer u>2 and prime t>2?

      If u>2, then tu>t2, since t>1.

      If t>2, then t23t+2=(t2)(t1)>0 so t2>3t2.

      Thus, if u>2, then tu>t2>3t2, so 3t2tu.

      Therefore, if 3t2 is a power of t, then t=2.

      If t=2, then t and 3t2 are both powers of t=2. Furthermore, t=2 is the only prime for which this can work.

      But in this case, 2s1 is odd and so cannot be a power of t=2.

      This contradicts our original assumption. Therefore, P(r2s)=r(3r2)(2s1) cannot be the power of a prime number.

    4. We note that 243=35. We try some different possible forms for m.

      Suppose that m=rs for some prime numbers r and s.

      Then P(m)=P(rs)=(2r1)(2s1).

      Are there prime numbers r and s for which (2r1)(2s1)=243?

      Note that if p is prime, then p2 so 2p13.

      Therefore, we could have 2r1=3 and 2s1=81 (which gives r=2 and s=41 which are both prime) or 2r1=9 and 2s1=27 (which gives r=5 (prime) and s=14 (not prime)).

      Therefore, P(82)=P(241)=381=243.

      Since 243 is a power of a prime, then from part (c), P(r2s)243 for all primes r and s.

      Let’s next see if P(r3s) can equal 243.

      Using a similar derivation to that in (a), we can see that P(r3)=1(r3)+(r1)r2+(r2r)r+(r3r2)(1)=4r33r2 Therefore, P(r3s)=P(r3)P(s)=(4r33r2)(2s1)=r2(4r3)(2s1).

      If r2(4r3)(2s1)=243, then since r is prime and a factor of the left side, we must have r=3.

      Therefore, 32(4(3)3)(2s1)=243 or 81(2s1)=243 or 2s1=3, which gives s=2.

      Thus, P(54)=P(332)=243. Therefore, m=82 and m=54 both satisfy P(m)=243.