2016 Fermat Contest
Solutions
(Grade 11)

Wednesday, February 24, 2016
(in North America and South America)

Thursday, February 25, 2016
(outside of North American and South America)

©2015 University of Waterloo

1. Since \(x=3\) and \(y=2x\), then \(y = 2\cdot 3 = 6\).
   Since \(y=6\) and \(z=3y\), then \(z = 3\cdot 6 = 18\).

   Answer: (D)

2. A square-based pyramid has 8 edges: 4 edges that form the square base and 1 edge that joins each of the four vertices of the square base to the top vertex.

   Answer: (C)

3. Evaluating, \(\dfrac{20+16\times20}{20\times 16} = \dfrac{20 + 320}{320} = \dfrac{340}{320} = \dfrac{17}{16}\).
   Alternatively, we could notice that each of the numerator and denominator is a multiple of 20, and so \(\dfrac{20+16\times20}{20\times 16} = \dfrac{20(1+16)}{20\times 16} =\dfrac{1+16}{16}=\dfrac{17}{16}\).

   Answer: (E)

4. The 7th oblong number is the number of dots in retangular grid of dots with 7 columns and 8 rows.
   Thus, the 7th oblong number is \(7 \times 8 = 56\).

   Answer: (C)

5. Solution 1
   Let the coordinates of \(R\) be \((a,b)\).
   Since \(Q\) is the midpoint of \(P\) and \(R\), then the difference between the \(x\)-coordinates of \(Q\) and \(P\) equals the difference between the \(x\)-coordinates of \(R\) and \(Q\).
   In other words, \(a-4 = 4-1\) and so \(a=7\).
   Similarly, \(b - 7 = 7 - 3\) and so \(b = 11\).
   Thus, the coordinates of \(R\) are \((7,11)\).
   
   Solution 2
   Let the coordinates of \(R\) be \((a,b)\).
   The midpoint of \(P(1,3)\) and \(R(a,b)\) has coordinates \(\left(\frac{1}{2}(1+a),\frac{1}{2}(3+b)\right)\).
   Since \(Q(4,7)\) is the midpoint of \(PR\), then \(4 = \frac{1}{2}(1+a)\) (which gives \(7 = 1+a\) or \(a=7\)) and \(14 = \frac{1}{2}(3+b)\) (which gives \(14=3+b\) or \(b=11\)).
   Therefore, the coordinates of \(R\) are \((7,11)\).

   Answer: (B)

6. Each week, Carrie sends 5 messages to her brother on each of 2 days, for a total of 10 messages.
   Each week, Carrie sends 2 messages to her brother on each of the remaining 5 days, for a total of 10 messages.
   Therefore, Carrie sends \(10+10=20\) messages per week.
   In four weeks, Carrie sends \(4 \cdot 20 = 80\) messages.

   Answer: (D)

7. Evaluating, \((-2)^3 - (-3)^2 = -8 - 9 = -17\).

   Answer: (A)

8. Since \(\sqrt{25-\sqrt{n}}=3\), then \(25-\sqrt{n} = 9\).
   Thus, \(\sqrt{n} = 16\) and so \(n = 16^2 = 256\).

   Answer: (E)

9. Solution 1
   Since \(x\%\) of 60 is 12, then \(\dfrac{x}{100}\cdot 60 = 12\) or \(x = \dfrac{12\cdot 100}{60} = 20\).
   Therefore, \(15\%\) of \(x\) is 15% of 20, or \(0.15 \cdot 20 = 3\).
   
   Solution 2
   Since \(x\%\) of 60 is 12, then \(\dfrac{x}{100}\cdot 60 = 12\) or \(\dfrac{60x}{100} = 12\).
   In terms of \(x\), 15% of \(x\) equals \(\dfrac{15}{100}x\) or \(\dfrac{15x}{100}\).
   Since \(\dfrac{60x}{100} = 12\), then \(\dfrac{15x}{100} = \dfrac{1}{4}\left(\dfrac{60x}{100}\right) = \dfrac{1}{4}\cdot 12 = 3\).

   Answer: (D)

10. Solution 1
    Since square \(PQRS\) has side length 2, then \(PQ=QR=RS=SP = 2\).
    Since \(W\), \(X\), \(Y\), \(Z\) are the midpoints of the sides of \(PQRS\), then \(PW = PZ = 1\).
    Since \(\angle ZPW = 90^\circ\), then \(WZ = \sqrt{PW^2 + PZ^2} = \sqrt{1^2+1^2} = \sqrt{2}\).
    Therefore, square \(WXYZ\) has side length \(\sqrt{2}\).
    The area of square \(WXYZ\) is \((\sqrt{2})^2 = 2\) and the area of square \(PQRS\) is \(2^2 = 4\).
    The ratio of these areas is \(2:4\) or \(1:2\).
    
    Solution 2
    Join \(W\) to \(Y\) and \(X\) to \(Z\).

    

    Since \(PQRS\) is a square and \(W\), \(X\), \(Y\), and \(Z\) are the midpoints of its sides, then \(WY\) and \(ZX\) divide the square into four identical squares.
    Each of these four squares is divided into two triangles of equal area by its diagonal. (These diagonals are \(WZ\), \(WX\), \(XY\), \(YZ\).)
    Square \(WXYZ\) is made up of 4 of these triangles of equal area.
    Square \(PQRS\) is made up of 8 of these triangles of equal area.
    Therefore, the ratio of these areas is \(4:8\) or \(1:2\).

    Answer: (A)

11. By the Pythagorean Theorem in \(\triangle PRS\), \[PS = \sqrt{RS^2 - PR^2} = \sqrt{13^2 - 12^2} = \sqrt{169-144} = \sqrt{25} = 5\] since \(PS>0\).
    Thus, \(PQ = PS + SQ = 5 + 11 = 16\).
    By the Pythagorean Theorem in \(\triangle PRQ\), \[RQ = \sqrt{PR^2 + PQ^2} = \sqrt{12^2 + 16^2} = \sqrt{144+256} = \sqrt{400} = 20\] since \(RQ>0\).
    Therefore, the perimeter of \(\triangle QRS\) is \(RS + SQ + RQ = 13+11+20=44\).

    Answer: (B)

12. Since \(128 = 2^7\), its positive divisors are \[2^0=1 \qquad 2^1=2 \qquad 2^2=4 \qquad 2^3=8 \qquad 2^4=16 \qquad 2^5=32 \qquad 2^6=64 \qquad 2^7=128\] Of these, the integers \(1, 4, 16, 64\) are perfect squares, which means that 128 has three positive divisors that are perfect squares larger than 1.

    Answer: (D)

13. Since \(4x,2x-3,4x-3\) form an arithmetic sequence, then the differences between consecutive terms are equal, or \((2x-3) - 4x = (4x-3)-(2x-3)\).
    Thus, \(-2x - 3 = 2x\) or \(4x = -3\) and so \(x = - \frac{3}{4}\).

    Answer: (E)

14. Since the average of the four numbers \(4, a, b, 22\) is 13, then \(\dfrac{4+a+b+22}{4}=13\) and so \(4+a+b+22=52\) or \(a+b=26\).
    Since \(a > 4\) and \(a\) is an integer, then \(a \geq 5\).
    Since \(a+b=26\) and \(a<b\), then \(a\) is less than half of 26, or \(a<13\).
    Since \(a\) is an integer, then \(a \leq 12\).
    Therefore, we have \(5 \leq a \leq 12\).
    There are 8 choices for \(a\) in this range: 5, 6, 7, 8, 9, 10, 11, 12. (Note that \(12-5 + 1 = 8\).)
    These give the pairs \((a,b)=(5,21),(6,20),(7,19),(8,18),(9,17),(10,16),(11,15),(12,14)\).
    Thus, there are 8 possible pairs.

    Answer: (B)

15. When Hicham runs 10 km at an average speed of 12 km/h, he takes \(\frac{10}{12} = \frac{5}{6}\) hours to run this distance.
    Since Hicham runs for a total of 1.5 hours, then he runs the last 6 km in \(\frac{3}{2} - \frac{5}{6} = \frac{9}{6} - \frac{5}{6} = \frac{4}{6} = \frac{2}{3}\) hours.
    Since he runs 6 km in \(\frac{2}{3}\) hours, his average speed for this segment is \(\frac{6}{2/3} = 9\) km/h.

    Answer: (B)

16. Solution 1
    Since \(x=18\) is a solution to the equation \(x^2+12x+c=0\), then \(x=18\) satisfies this equation.
    Thus, \(18^2+12(18)+c=0\) and so \(324+216 + c = 0\) or \(c = -540\).
    Therefore, the original equation becomes \(x^2+12x-540=0\) or \((x-18)(x+30)=0\).
    Therefore, the other solution is \(x=-30\).
    
    Solution 2
    We use the fact that the sum of the roots of an equation of the form \(x^2+bx+c=0\) is \(-b\).
    If the roots of the equation \(x^2+12x+c=0\) are \(18\) and \(r\), then \(18+r=-12\) or \(r = -30\).
    Therefore, the other solution is \(x=-30\).

    Answer: (C)

17. The number of points on the circle equals the number of spaces between the points around the circle.
    Moving from the point labelled 7 to the point labelled 35 requires moving \(35-7=28\) points and so 28 spaces around the circle.
    Since the points labelled 7 and 35 are diametrically opposite, then moving along the circle from 7 to 35 results in travelling halfway around the circle.
    Since 28 spaces makes half of the circle, then \(2\cdot 28 = 56\) spaces make the whole circle.
    Thus, there are 56 points on the circle, and so \(n = 56\).

    Answer: (C)

18. The first equation \(\dfrac{x-y}{x+y}=9\) gives \(x-y = 9x+9y\) and so \(-8x = 10y\) or \(-4x = 5y\).
    The second equation \(\dfrac{xy}{x+y} = -60\) gives \(xy = -60x - 60y\).
    Multiplying this equation by 5 gives \(5xy = -300x - 300y\) or \(x(5y) = -300x - 60(5y)\).
    Since \(5y = -4x\), then \(x(-4x) = -300x - 60(-4x)\) or \(-4x^2 = -60x\).
    Rearranging, we obtain \(4x^2 - 60x = 0\) or \(4x(x-15)=0\).
    Therefore, \(x = 0\) or \(x=15\).
    Since \(y = -\frac{4}{5}x\), then \(y = 0\) or \(y = -12\).
    From the first equation, it cannot be the case that \(x=y=0\).
    We can check that the pair \((x,y)=(15,-12)\) satisfies both equations.
    Therefore, \((x+y)+(x-y)+xy = 3 + 27 + (-180) = -150\).

    Answer: (B)

19. Solution 1
    Suppose that, when the \(n\) students are put in groups of 2, there are \(g\) complete groups and 1 incomplete group.
    Since the students are being put in groups of 2, an incomplete group must have exactly 1 student in it.
    Therefore, \(n = 2g+1\).
    Since the number of complete groups of 2 is 5 more than the number of complete groups of 3, then there were \(g-5\) complete groups of 3.
    Since there was still an incomplete group, this incomplete group must have had exactly 1 or 2 students in it.
    Therefore, \(n = 3(g-5)+1\) or \(n = 3(g-5)+2\).
    If \(n=2g+1\) and \(n = 3(g-5) + 1\), then \(2g+1 = 3(g-5)+1\) or \(2g + 1 = 3g - 14\) and so \(g = 15\).
    In this case, \(n = 2g+1=31\) and there were 15 complete groups of 2 and 10 complete groups of 3.
    If \(n=2g+1\) and \(n = 3(g-5) + 2\), then \(2g+1 = 3(g-5)+2\) or \(2g + 1 = 3g - 13\) and so \(g = 14\).
    In this case, \(n = 2g+1=29\) and there were 14 complete groups of 2 and 9 complete groups of 3.
    If \(n=31\), dividing the students into groups of 4 would give 7 complete groups of 4 and 1 incomplete group.
    If \(n=29\), dividing the students into groups of 4 would give 7 complete groups of 4 and 1 incomplete group.
    Since the difference between the number of complete groups of 3 and the number of complete groups of 4 is given to be 3, then it must be the case that \(n = 31\).
    In this case, \(n^2 - n = 31^2 - 31 = 930\); the sum of the digits of \(n^2-n\) is 12.
    
    Solution 2
    Since the \(n\) students cannot be divided exactly into groups of 2, 3 or 4, then \(n\) is not a multiple of 2, 3 or 4.
    The first few integers larger than 1 that are not divisible by 2, 3 or 4 are 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, and 35.
    In each case, we determine the number of complete groups of each size:

    \(n\)	5	7	11	13	17	19	23	25	29	31	35
    # of complete groups of 2	2	3	5	6	8	9	11	12	14	15	17
    # of complete groups of 3	1	2	3	4	5	6	7	8	9	10	11
    # of complete groups of 4	1	1	2	3	4	4	5	6	7	7	8

    Since the number of complete groups of 2 is 5 more than the number of complete groups of 3 which is 3 more than the number of complete groups of 4, then of these possibilities, \(n=31\) works.
    In this case, \(n^2 - n = 31^2 - 31 = 930\); the sum of the digits of \(n^2-n\) is 12.
    (Since the problem is a multiple choice problem and we have found a value of \(n\) that satisfies the given conditions and for which an answer is present, then this answer must be correct. Solution 1 shows why \(n=31\) is the only value of \(n\) that satisfies the given conditions.)

    Answer: (B)

20. Since points \(Y\), \(W\) and \(Q\) form a straight line segment, then \(\angle YWV = 180^\circ - \angle VWQ\) and so \(\angle YWV = 180^\circ - 125^\circ = 55^\circ\).
    Since \(Q'\) is the final position of \(Q\) after folding, then \(\angle Q'WV\) is the final position of \(\angle QWV\) after folding, and so \(\angle Q'WV = \angle QWV\).
    Thus, \(\angle Q'WV = \angle QWV = 125^\circ\) and so \(\angle Q'WY = \angle Q'WV - \angle YWV = 125^\circ - 55^\circ = 70^\circ\).

    

    Since \(Q'W\) and \(R'Y\) are parallel sides of the piece of paper, then \(\angle R'YW + \angle Q'WY = 180^\circ\), and so \(\angle R'YW = 180^\circ - \angle Q'WY = 180^\circ - 70^\circ = 110^\circ\).
    Finally, \(\angle PYV\) is opposite \(\angle R'YW\) so \(\angle PYV = \angle R'YW = 110^\circ\).

    Answer: (A)

21. When a marble is chosen from Box 1, the probability is \(\frac{1}{2}\) that it will be gold and the probability is \(\frac{1}{2}\) that it will be black.
    Thus, after this choice is made, there is a probability of \(\frac{1}{2}\) that Box 2 contains 2 gold marbles and 2 black marbles, and there is a probability of \(\frac{1}{2}\) that Box 2 contains 1 gold marble and 3 black marbles.
    In the first case (which occurs with probability \(\frac{1}{2}\)), the probability that a gold marble is chosen from Box 2 is \(\frac{2}{4}=\frac{1}{2}\) and the probability that a black marble is chosen from Box 2 is \(\frac{2}{4}=\frac{1}{2}\).
    In the second case (which occurs with probability \(\frac{1}{2}\)), the probability that a gold marble is chosen from Box 2 is \(\frac{1}{4}\) and the probability that a black marble is chosen from Box 2 is \(\frac{3}{4}\).

    

    Therefore, the probability that a gold marble is chosen from Box 2 is \(\frac{1}{2}\cdot \frac{1}{2}+\frac{1}{2}\cdot \frac{1}{4} = \frac{3}{8}\) and the probability that a black marble is chosen from Box 2 is \(\frac{1}{2}\cdot \frac{1}{2}+\frac{1}{2}\cdot \frac{3}{4} = \frac{5}{8}\).
    Thus, after this choice is made, there is a probability of \(\frac{3}{8}\) that Box 3 contains 2 gold marbles and 3 black marbles, and a probability of \(\frac{5}{8}\) that Box 3 contains 1 gold marble and 4 black marbles.
    Finally, the probability that a gold marble is chosen from Box 3 equals the probability that Box 3 contains 2 gold marbles and 3 black marbles times the probability of choosing a gold marble in this situation (that is, \(\frac{3}{8}\cdot \frac{2}{5}\)) plus the probability that Box 3 contains 1 gold marble and 4 black marbles times the probability of choosing a gold marble in this situation.
    In other words, this probability is \(\frac{3}{8}\cdot \frac{2}{5} + \frac{5}{8}\cdot \frac{1}{5} = \frac{11}{40}\).

    Answer: (A)

22. Solution 1
    We expand the given expression to obtain \[(x^2+6x+9) + 2(y^2 - 4y + 4) + 4(x^2 - 14x + 49) + (y^2 + 8y + 16)\] We expand further to obtain \[x^2+6x+9 + 2y^2 - 8y + 8 + 4x^2 - 56x + 196 + y^2 + 8y + 16\] We simplify to obtain \[5x^2 - 50x + 3y^2 + 229\] We remove a common factor of 5 from the first two terms \[5(x^2 - 10x) + 3y^2 + 229\] and then complete the square to obtain \[5(x^2 - 10x + 5^2 - 5^2) + 3y^2 + 229\] This gives \[5(x-5)^2 - 125 + 3y^2 + 229\] or \[5(x-5)^2 + 3y^2 + 104\] Since \((x-5)^2 \geq 0\) for all real numbers \(x\) and \(3y^2 \geq 0\) for all real numbers \(y\), then the minimum value of \(5(x-5)^2 + 3y^2 + 104\) (and hence of the original expression) is \(5(0)+3(0)+104\) or 104.
    We note that this value is actually achieved when \(x = 5\) (which gives \((x-5)^2 = 0\)) and \(y=0\) (which gives \(3y^2 = 0\)).
    
    Solution 2
    We expand the given expression to obtain \[(x^2+6x+9) + 2(y^2 - 4y + 4) + 4(x^2 - 14x + 49) + (y^2 + 8y + 16)\] We expand further to obtain \[x^2+6x+9 + 2y^2 - 8y + 8 + 4x^2 - 56x + 196 + y^2 + 8y + 16\] The terms involving \(x\) are \[x^2+6x+9+ 4x^2 - 56x + 196 = 5x^2 - 50x + 205 = 5x^2-50x+125+80 = 5(x-5)^2 + 80\] The terms involving \(y\) are \[2y^2 - 8y + 8 + y^2 + 8y + 16 = 3y^2 + 24\] Since \((x-5)^2 \geq 0\) for all real numbers \(x\), then the minimum value of \(5(x-5)^2 + 80\) is 80.
    Since \(y^2 \geq 0\) for all real numbers \(y\), then the minimum value of \(3y^2+24\) is 24.
    Since the minimum value of \((x-3)^2 + 4(x-7)^2\) is 80 and the minimum value of \(2(y-2)^2 + (y+4)^2\) is 24, then the minimum value of \((x-3)^2+2(y-2)^2 + 4(x-7)^2 + (y+4)^2\) is \(80 + 24 = 104\).

    Answer: (E)

23. We label the centres of the coins \(A,B,D,E,F,G,H\), as shown, and we join \(AB\), \(AD\), \(AE\), \(AF\), \(AG\), \(AH\), \(BD\), \(DE\), \(EF\), \(FG\), \(GH\), and \(HB\).

    

    The radius of the circles with centres \(D\), \(E\) and \(F\) is 3 cm and the radius of the circles with centres \(A\), \(B\) and \(G\) is 2 cm. (From this point until the very last step of the problem, we will not include the units, which are always centimetres.)
    Let the radius of the circle with centre \(H\) be \(r\). We want to determine \(r\).
    When we join the centres of two circles that are just touching, the resulting line segment passes through the point at which the circles touch and the length of this line segment is the sum of the radii of the two circles.
    Thus, \(AB = 2+2=4\). Similarly, \(AG=4\), \(BD=AD=AE=AF=GF=5\), \(DE=EF=6\), and \(HA=HB=HG=r+2\).
    Now \(\triangle ADE\) and \(\triangle AFE\) each have side lengths 5, 5 and 6, which means that these triangles are congruent.
    Similarly, \(\triangle ADB\) and \(\triangle AFG\) are congruent, and \(\triangle ABH\) and \(\triangle AGH\) are congruent.
    Since corresponding angles in congruent triangles are equal, then \(\angle HAB + \angle BAD + \angle DAE\) is equal to \(\angle HAG + \angle GAF + \angle FAE\).
    But these six angles surround point \(A\), so the sum of these six angles is \(360^\circ\).
    Thus, \(\angle HAB + \angle BAD + \angle DAE = \angle HAG + \angle GAF + \angle FAE = 180^\circ\).
    Now, we remove the circles from the diagram and focus on the top half of the diagram.
    We join \(A\) to \(K\), the midpoint of \(DE\), and \(D\) and \(H\) to \(L\), the midpoint of \(AB\).

    

    Consider \(\triangle ADE\).
    Since \(DE = 6\) and \(K\) is the midpoint of \(DE\), then \(DK = KE = 3\).
    Also, since \(AD = AE = 5\), then \(\triangle ADE\) is isosceles and so \(AK\) is perpendicular to \(DE\) and \(AK\) bisects \(\angle DAE\).
    Similarly, \(\triangle AHB\) is isosceles with \(HA = HB\) and \(\triangle ABD\) is isosceles with \(DA = DB\).
    Since \(L\) is the midpoint of \(AB\) and \(AB=4\), then \(AL=LB=2\) and \(DL\) and \(HL\) are perpendicular to \(AB\) at \(L\).
    We know that \(\angle HAB + \angle BAD + \angle DAE = \angle HAL + \angle LAD + 2\angle EAK = 180^\circ\).
    But \(\sin(\angle EAK) = \dfrac{EK}{AE} = \dfrac{3}{5}\), so \(\angle EAK \approx 36.87^\circ\).
    Also, \(\cos(\angle LAD) = \dfrac{AL}{AD} = \dfrac{2}{5}\), so \(\angle LAD \approx 66.42^\circ\).
    Thus, \(\angle HAL = 180^\circ - \angle LAD - 2\angle EAK \approx 180^\circ - 66.42^\circ - 2(36.87^\circ) \approx 39.84^\circ\).
    Finally, we know that \(\cos(\angle HAL) = \dfrac{AL}{HA} = \dfrac{2}{r+2}\).
    Since \(\cos(39.84^\circ) \approx 0.7679\), then \(\dfrac{2}{r+2} \approx 0.7679\).
    From this we obtain \(r \approx \dfrac{2}{0.7679} - 2.\\[1mm] Since \dfrac{2}{0.7679} - 2 \approx 0.60451\), then of the given choices, this radius is closest to \(0.605\mbox{ cm}\).
    (If more decimal places are carried through from earlier calculations, we obtain \(r \approx 0.60466\), which is still closest to \(0.605\mbox{ cm}\).)

    Answer: (D)

24. We begin by understanding and describing \(\lfloor \sqrt{k} \rfloor\) in a different way.
    Each positive integer \(k\) can be placed between two consecutive perfect squares. More precisely, for each positive integer \(k\), there exists a unique positive integer \(n\) with \(n^2 \leq k < (n+1)^2\).
    Since \(n^2 \leq k < (n+1)^2\), then \(n^2 \leq k < n^2+2n+1\) and \(n \leq \sqrt{k} < n+1\).
    Since \(n\) and \(n+1\) are consecutive integers, then \(\lfloor \sqrt{k} \rfloor = n\).
    In other words, \(n\) is the largest positive integer less than or equal to \(\sqrt{k}\).
    So we want to calculate the sum of all integers \(k\) with \(1 \leq k \leq 999\,999\) for which \(k\) is a multiple of its corresponding \(n\).
    Now \(n^2 = n\cdot n\) and \(n^2 + 2n + 1 = n(n+2)+1\).
    This means that the possible values of \(k\) with \(n^2 \leq k < n^2+2n+1\) are the multiples of \(n\) in this range, or \(k=n\cdot n\), \(k=n(n+1)\), and \(k=n(n+2)\).
    Since \(k \leq 999\,999\), then \(k < 1000^2 = 1\,000\,000\), and so \(n \leq 999\).
    So the given problem is equivalent to determining the sum of \(n^2\), \(n(n+1)\) and \(n(n+2)\) for each \(n\) from 1 to 999.
    Since \(n^2+n(n+1)+n(n+2) = 3n^2+3n\), then we want to determine the sum of \(3n^2+3n\) for \(n=1\) to \(n = 999\) inclusive.
    Thus, \[\begin{aligned} S & = (3(1^2)+3(1)) + (3(2^2)+3(2)) + \cdots + (3(998^2)+3(998)) + (3(999^2)+3(999)) \\ & = 3(1^2 + 2^2 + \cdots + 998^2 + 999^2) + 3(1+2+\cdots+998+999)\end{aligned}\] Since \(1+2+\cdots + (m-1)+m = \dfrac{m(m+1)}{2}\) and \(1^2+2^2 + \cdots + (m-1)^2 + m^2 = \dfrac{m(m+1)(2m+1)}{6}\) for every positive integer \(m\), then \[\begin{aligned} S & = 3 \cdot \dfrac{999(1000)(1999)}{6} + 3\cdot \dfrac{999(1000)}{2} \\ & = \dfrac{3(999)(1000)}{6}(1999 + 3)\\ & = \dfrac{999(1000)}{2}(2002) \\ & = 999(1000)(1001)\end{aligned}\] and so \(S = 999\,999\,000\).

    Answer: (C)

25. We begin by partitioning the set \(A\) into disjoint subsets of the form \[P_b = \{b,3b,9b,\ldots,3^kb \}\] where \(b\) is a positive integer with \(1 \leq b \leq 2045\) and \(k\) is the largest non-negative integer with \(3^kb \leq 2045\).
    The first two of these sets are \(P_1 = \{1,3,9,27,81,243,729\}\) and \(P_2 = \{2,6,18,54,162,486,1458\}\).
    These sets have \(b=1\) and \(b=2\), and thus \(k=6\).
    We will see that each element of \(A\) is an element of exactly one of these sets.
    Since \(3^7 = 2187\), then \(3^7 b \geq 2187 > 2045\) for every positive integer \(b\), so \(k=6\) is the largest possible value of \(k\) that we can have.
    For each \(k\) with \(0 \leq k \leq 6\), we determine the range of values of \(b\) that give that \(k\):

    • \(k=6\): \(1 \leq b \leq 2\) since \(2 \cdot 3^6 = 1458 < 2045\) and \(3\cdot 3^6 = 2187 > 2045\)

    • \(k=5\): \(3 \leq b \leq 8\) since \(8 \cdot 3^5 = 1944 < 2045\) and \(9\cdot 3^5 = 2187 > 2045\)

    • \(k=4\): \(9 \leq b \leq 25\) since \(25 \cdot 3^4 = 2025 < 2045\) and \(26\cdot 3^4 = 2106 > 2045\)

    • \(k=3\): \(26 \leq b \leq 75\) since \(75 \cdot 3^3 = 2025 < 2045\) and \(76\cdot 3^3 = 2052 > 2045\)

    • \(k=2\): \(76 \leq b \leq 227\) since \(227 \cdot 3^2 = 2043 < 2045\) and \(228\cdot 3^2 = 2052 > 2045\)

    • \(k=1\): \(228 \leq b \leq 681\) since \(681 \cdot 3^1 = 2043 < 2045\) and \(682\cdot 3^1 = 2046 > 2045\)

    • \(k=0\): \(682 \leq b \leq 2045\) since \(2045 \cdot 3^0 = 2045\) and \(2046 \cdot 3^0 = 2046 > 2045\)

    Since we want to create disjoint sets \(P_b\) whose union is the set \(A = \{1,2,3,\ldots,2044,2045\}\), then we exclude all \(b\)’s that are multiples of 3. (If \(b\) were a multiple of 3, it would appear as an element of a set \(P_r\) with \(r \leq b\).)
    For each of the ranges above, we count the number of multiples of \(3\) that we need to exclude:

    k	Range of values of \(b\)	# of multiples of 3	# of remaining \(b\)	# of elements in each \(P_b\)
    \(6\)	\(1 \leq b \leq 2\)	0	\(2 - 0 = 2\)	\(7\)
    \(5\)	\(3 \leq b \leq 8\)	2	\(6 - 2 = 4\)	\(6\)
    \(4\)	\(9 \leq b \leq 25\)	\(6\)	\(17 - 6 = 11\)	\(5\)
    \(3\)	\(26 \leq b \leq 75\)	\(17\)	\(50 - 17 = 33\)	\(4\)
    \(2\)	\(76 \leq b \leq 227\)	\(50\)	\(152 - 50 = 102\)	\(3\)
    \(1\)	\(228 \leq b \leq 681\)	\(152\)	\(454 - 152 = 302\)	\(2\)
    \(0\)	\(682 \leq b \leq 2045\)	\(454\)	\(1364 - 454 = 910\)	\(1\)

    Note for example that the range \(26 \leq b \leq 75\) contains \(75 - 25 = 50\) integers and includes the multiples of 3 from \(9\cdot 3\) to \(25 \cdot 3\), inclusive, so includes \(25 - 8 = 17\) multiples of 3, and the range \(228 \leq b \leq 681\) contains \(681 - 227 = 454\) integers and includes the multiples of 3 from \(76\cdot 3\) to \(227 \cdot 3\), inclusive, so includes \(227 - 75 = 152\) multiples of 3.
    An integer \(b\) in \(A\) that is not a multiple of 3 generates a set \(P_b\) and cannot appear in a different set \(P_r\). Any multiple of 3, say \(m\), will appear in exactly one \(P_b\) where the value of \(b\) (which is itself not a multiple of 3) is obtained by dividing out all of factors of 3 from \(m\).
    We note that \(2\cdot 7 + 4 \cdot 6 + 11 \cdot 5 + 33 \cdot 4 + 102 \cdot 3 + 302 \cdot 2 + 910 \cdot 1 = 2045\) so the union of these sets \(P_b\) includes enough elements to be the entire set \(A\). No element of \(A\) appears in more than one \(P_b\), so the union of these sets \(P_b\) is the entire set \(A\).
    Why are these sets useful in the given problem?
    A subset of \(A\) is triple-free if it does not contain two elements, one of which is three times the other.
    This means that a subset of \(A\) is triple-free exactly when it does not contain two consecutive elements of any \(P_b\).
    A triple-free subset \(T\) of \(A\) that contains as many elements as possible will contain as many elements as possible from each of the \(P_b\) defined above.
    Since no two consecutive elements of any \(P_b\) can appear in \(T\), then a \(P_b\) with 7 elements can contribute at most 4 elements to \(T\) (every other element starting with the first), a \(P_b\) with 6 elements can contribute at most 3 elements to \(T\) (it cannot contain 4 elements without having two consecutive elements), and so on.
    For each \(k\) from \(k=7\) to \(k=0\), each \(P_b\) above can contribute at most the following number of elements to \(T\):

    k	# of elements in each \(P_b\)	Number of elements that can be chosen
    6	7	4
    5	6	3
    4	5	3
    3	4	2
    2	3	2
    1	2	1
    0	1	1

    This means that \(T\) can contain at most \(2 \cdot 4 + 4 \cdot 3 + 11 \cdot 3 + 33 \cdot 2 + 102 \cdot 2 + 302 \cdot 1 + 910 \cdot 1 = 1535\) elements. This agrees with the information in the problem statement.
    Where is there choice in creating \(T\)?
    If a \(P_b\) contains 1 element, then this element must be chosen for \(T\).
    If a \(P_b\) contains 3 elements, then there is 1 way to choose 2 elements for \(T\), since in this case the 1st and 3rd elements (in increasing order) must be chosen.
    If a \(P_b\) contains 5 elements, then there is 1 way to choose 3 elements for \(T\), since in this case the 1st, 3rd and 5th elements (in increasing order) must be chosen.
    If a \(P_b\) contains 7 elements, then there is 1 way to choose 4 elements for \(T\), since in this case the 1st, 3rd, 5th and 7th (in increasing order) elements must be chosen.
    If a \(P_b\) contains 2 elements, then there are 2 ways to choose 1 element for \(T\).
    If a \(P_b\) contains 4 elements, then there are 3 ways to choose 2 elements for \(T\). (If we want to choose 2 elements from \(\{A,B,C,D\}\) without choosing consecutive elements, we can choose \(A\) and \(C\), or \(A\) and \(D\), or \(B\) and \(D\).)
    If a \(P_b\) contains 6 elements, then there are 4 ways to choose 3 elements for \(T\). (If we want to choose 3 elements from \(\{A,B,C,D,E,F\}\) without choosing consecutive elements, we can choose \(A\) and \(C\) and \(E\), or \(A\) and \(C\) and \(F\), or \(A\) and \(D\) and \(F\), or \(B\) and \(D\) and \(F\).)
    This means that the number of ways of choosing a triple-free subset \(T\) of \(A\) with as many elements as possible is \(1^2 \cdot 4^4 \cdot 1^{11} \cdot 3^{33} \cdot 1^{102} \cdot 2^{302} \cdot 1^{910}\).
    This is because there are 2 sets \(P_b\) with \(k=6\) and 1 way of choosing 4 elements from each of them (giving \(1^2\) choices in total), 4 set \(P_b\) with \(k=5\) and 4 ways of choosing 3 elements from each of them (giving \(4^4\) choices in total), and so on.
    The seven factors in this product give, from \(k=6\) to \(k=0\), the number of ways of choosing the maximum number of elements from a set \(P_b\) corresponding to that value of \(k\) raised to the power of the number of such sets \(P_b\).
    Therefore, the number of ways equals \(4^4 \cdot 3^{33} \cdot 2^{302} = 2^{310} \cdot 3^{33}\).
    From the statement of the problem, we thus have \(N = 2^2 + 3^2 + 310^2 + 33^2 = 97\,202\).
    The final three digits of this integer are \(202\).

    Answer: (A)