2017 Cayley Contest
Solutions
(Grade 10)
Tuesday, February 28, 2017
(in North America and South America)
Wednesday, March 1, 2017
(outside of North American and South America)
Tuesday, February 28, 2017
(in North America and South America)
Wednesday, March 1, 2017
(outside of North American and South America)
©2016 University of Waterloo
Evaluating, \(6 \times 111 - 2\times 111 = 666 - 222 = 444\).
Alternatively, we note that \(6 \times 111 - 2 \times 111 = (6 - 2)\times 111 = 111(4) = 444\).
Answer: (C)
Evaluating, \(\dfrac{5^2 - 9}{5-3} = \dfrac{25-9}{2} = \dfrac{16}{2} = 8\).
Alternatively, we note that \(5^2 - 9 = 5^2 - 3^2 = (5-3)(5+3)\) and so \[\dfrac{5^2 - 9}{5-3} = \dfrac{(5-3)(5+3)}{5-3} = 5+3 = 8\]
Answer: (D)
The height of the snowman equals the sum of the lengths of the diameters of the three spheres.
Since the radii of the spheres are 10 cm, 20 cm and 30 cm, then the lengths of their diameters are 20 cm, 40 cm and 60 cm.
Thus, the height of the snowman is \(20\mbox{ cm}+40\mbox{ cm}+60\mbox{ cm} = 120\) cm.
Answer: (D)
We write each of the choices in lowest terms: \[\frac{44444}{55555} = \frac{4(11111)}{5(11111)} = \frac{4}{5} \qquad
\frac{5555}{6666} = \frac{5(1111)}{6(1111)} = \frac{5}{6} \]
\[\frac{666}{777} = \frac{6(111)}{7(111)} = \frac{6}{7} \qquad
\frac{77}{88} = \frac{7(11)}{8(11)} = \frac{7}{8} \qquad
\frac{8}{9}\] (The last choice was already in lowest terms.)
Next, we note that \(\frac{4}{5} = 1 - \frac{1}{5}\) and \(\frac{5}{6} = 1 - \frac{1}{6}\) and \(\frac{6}{7} = 1 - \frac{1}{7}\) and \(\frac{7}{8} = 1 - \frac{1}{8}\) and \(\frac{8}{9} = 1 - \frac{1}{9}\).
The fraction with the greatest value will be the one that is equal to 1 minus the smallest fraction.
Since \(\frac{1}{9} < \frac{1}{8} < \frac{1}{7} < \frac{1}{6} < \frac{1}{5}\), then the fraction with the greatest value is \(\frac{8}{9}\).
Answer: (E)
Since 300 litres drains in 25 hours, then the rate at which water is leaving the tank equals \(\dfrac{300\mbox{ L}}{25\mbox{ h}}\) or \(12\mbox{ L/h}\).
Answer: (A)
When Penelope folds the paper in half, the number of layers doubles.
Starting with 4 layers of paper, then after the next three folds, there are 8 and then 16 and then 32 layers of paper. Additional folds create more layers.
Of the given choices (which are all less than 32), only 16 is a possible number of layers.
Answer: (D)
By definition, \(2 \Diamond 7 = 2^2(7) - 2(7^2) = 4(7) - 2(49) = 28 - 98 = -70\).
Answer: (B)
In option (A), the first and third cards have 0 numbers in common, so (A) is not correct.
In option (B), the second and third cards have 2 numbers in common, so (B) is not correct.
In option (C), the first and third cards have 2 numbers in common, so (C) is not correct.
In option (E), the first and third cards have 2 numbers in common, so (E) is not correct.
In option (D), the first and second cards share exactly 1 number (namely, 4), the first and third cards share exactly one number (namely, 7), and the second and third cards share exactly one number (namely, 2). Thus, (D) is correct.
Answer: (D)
Since the bill including a 13% tip was $226, then $226 is 113% of the bill before tax.
Thus, the bill before tax was \(\frac{\$226}{1.13} = \$200\) before tax.
The amount of the tip is 15% of the bill before tax, or \(\$200 \times 0.15 = \$30\).
Answer: (C)
Since \(PQR\) is a straight angle, then \(\angle PQT + \angle RQT = 180^\circ\).
Therefore, \(x^\circ + (x-50)^\circ = 180^\circ\) and so \(2x - 50 = 180\) or \(2x = 230\), which gives \(x = 115\).
Therefore, \(\angle TUR = (x+25)^\circ = 140^\circ\).
Since \(TU\) and \(PS\) are parallel, then \(\angle URS\) and \(\angle TUR\) are alternating angles, which means that \(\angle URS = \angle TUR = 140^\circ\).
Answer: (B)
Since 10 identical squares have a total area of \(160\mbox{ cm}^2\), then the area of each square is \(\dfrac{160\mbox{ cm}^2}{10}\) or \(16\mbox{ cm}^2\).
Since the area of each of the 10 identical squares is \(16\mbox{ cm}^2\), then the side length of each of these squares is \(\sqrt{16\mbox{ cm}^2} = 4\mbox{ cm}\).
The perimeter of the given figure equals 22 square side lengths (4 on the left side, 4 on the bottom, 4 on the right side, 2 separate ones on the top, and 8 in the “U” shape in the middle).
Therefore, the perimeter of the figure is \(4\mbox{ cm} \times 22 = 88\mbox{ cm}\).
Answer: (C)
Since the mean of \(p\), \(q\) and \(r\) is 9, then \(\dfrac{p+q+r}{3}=9\) and so \(p+q+r=27\).
Since the mean of \(s\) and \(t\) is 14, then \(\dfrac{s+t}{2}=14\) or \(s+t=28\).
Therefore, the mean of the five integers is \(\dfrac{p+q+r+s+t}{5} = \dfrac{(p+q+r)+(s+t)}{5} = \dfrac{27+28}{5}\), which equals \(11\).
Answer: (A)
First, we consider the column of units (ones) digits.
From this column, we see that the units digit of \(Z+Z+Z\) (or \(3Z\)) must be 5.
By trying the possible digits from 0 to 9, we find that \(Z\) must equal 5.
When \(Z=5\), we get \(3Z=15\), and so there is a “carry” of 1 to the column of tens digits.
From this column, we see that the units digit of \(1+Y+Y+Y\) (or \(3Y+1\)) must be 7.
By trying the possible digits from 0 to 9, we find that \(Y\) must equal 2.
There is no carry created when \(Y=2\).
Looking at the remaining digits, we see that \(2X = 16\) and so \(X=8\).
Checking, if \(X=8\) and \(Y=2\) and \(Z=5\), we obtain \(825+825+25\) which equals 1675, as required.
Therefore, \(X+Y+Z=8+2+5=15\).
Answer: (B)
Since Igor is shorter than Jie, then Igor cannot be the tallest.
Since Faye is taller than Goa, then Goa cannot be the tallest.
Since Jie is taller than Faye, then Faye cannot be the tallest.
Since Han is shorter than Goa, then Han cannot be the tallest.
The only person of the five who has not been eliminated is Jie, who must thus be the tallest.
Answer: (E)
Since there are 32 red marbles in the bag and the ratio of red marbles to blue marbles is \(4:7\), then there are \(\frac{7}{4}(32) = 56\) blue marbles in the bag.
Since there are 56 blue marbles in the bag and the ratio of blue marbles to purple marbles is \(2:3\), then there are \(\frac{3}{2}(56) = 84\) purple marbles in the bag.
Since the bag contains only red, blue and purple marbles, then there are \(32+56+84 = 172\) marbles in the bag.
Answer: (E)
Since \(x+2y=30\), then \[\begin{aligned} \dfrac{x}{5}+\dfrac{2y}{3}+ \dfrac{2y}{5}+\dfrac{x}{3} & = \dfrac{x}{5}+ \dfrac{2y}{5}+\dfrac{x}{3}+\dfrac{2y}{3} \\ & = \dfrac{1}{5}x + \dfrac{1}{5}(2y) + \dfrac{1}{3}x + \dfrac{1}{3}(2y) \\ & = \dfrac{1}{5}(x+2y) + \dfrac{1}{3}(x+2y) \\ & = \dfrac{1}{5}(30) + \dfrac{1}{3}(30) \\ & = 6 + 10 \\ & = 16\end{aligned}\]
Answer: (B)
First, we factor \(1230\) as a product of prime numbers: \[1230 = 2 \times 615 = 2 \times 5 \times 123 = 2 \times 5 \times 3 \times 41\] We are looking for three positive integers \(r,s,t\) with \(r \times s \times t = 1230\) and whose sum is as small as possible. We note that all of the possibilities given for the smallest possible value of \(r+s+t\) are less than 60.
Since 41 is a prime factor of 1230, then one of \(r,s,t\) must be a multiple of 41.
Since all of the possibilities given for the minimum sum \(r+s+t\) are less than 60 and the second smallest multiple of 41 is 82, then the multiple of 41 in the list \(r,s,t\) must be 41 itself.
Thus, we can let \(t = 41\).
Now we are looking for positive integers \(r\) and \(s\) with \(r \times s = 2 \times 3 \times 5 = 30\) and whose sum \(r+s\) is as small as possible. (Since \(t\) is now fixed, then minimizing \(r+s+t\) is equivalent to minimizing \(r+s\).)
The possible pairs of values for \(r\) and \(s\) in some order are \(1,30\) and \(2,15\) and \(3,10\) and \(5,6\).
The pair with the smallest sum is \(5,6\).
Therefore, we set \(r=5\) and \(s=6\). This gives \(r+s+t=5+6+41=52\).
Answer: (B)
Since \(\dfrac{1}{7}\) is positive and \(\dfrac{1}{7} \leq \dfrac{6}{n}\), then \(\dfrac{6}{n}\) is positive and so \(n\) is positive.
Since \(\dfrac{1}{7} = \dfrac{6}{42}\) and \(\dfrac{1}{4} = \dfrac{6}{24}\), then the given inequality is equivalent to \(\dfrac{6}{42} \leq \dfrac{6}{n} \leq \dfrac{6}{24}\).
Since the fractions are all positive and \(n > 0\), then this is true when \(24 \leq n \leq 42\). (If two fractions have the same numerator, then the larger fraction has a smaller denominator.)
Since \(n\) is an integer, then there are \(42 - 24 + 1 = 19\) possible values for \(n\). (We could count the integers from 24 to 42, inclusive, to confirm this.)
Answer: (C)
We start by drawing a graph that includes the point \((1,1)\), the lines with slopes \(\frac{1}{4}\) and \(\frac{5}{4}\) that pass through this point, the vertical line with equation \(x=5\), and the horizontal line \(y=1\) (which passes through \((1,1)\) and is perpendicular to the vertical line with equation \(x=5\)).
We label the various points of intersection (\(A\), \(B\), \(C\)) as shown.
We want to determine the area of \(\triangle PBC\).
Since \(P\) has coordinates \((1,1)\) and \(A\) has coordinates \((5,1)\), then \(PA=4\).
Since the slope of \(PB\) is \(\frac{1}{4}\) and \(PA=4\), then thinking about slope as “rise over run”, we see that \(AB = 1\).
Since the slope of \(PC\) is \(\frac{5}{4}\) and \(PA=4\), then \(AC=5\).
Since \(AC=5\) and \(AB=1\), then \(BC=AC-AB=5-1=4\).
We can view \(\triangle PBC\) as having base \(BC\) and perpendicular height \(PA\). (This is because the length of \(PA\) is the perpendicular distance from the line through \(B\) and \(C\) to the point \(P\).)
Therefore, the area of this triangle is \(\frac{1}{2}(4)(4)\) which equals 8.
Alternatively, we could note that the area of \(\triangle PBC\) equals the area of \(\triangle PAC\) minus the area of \(\triangle PAB\).
\(\triangle PAC\) has base \(PA=4\) and height \(AC = 5\) and so has area \(\frac{1}{2}(4)(5)=10\).
\(\triangle PAB\) has base \(PA=4\) and height \(AB = 1\) and so has area \(\frac{1}{2}(4)(1)=2\).
Thus, the area of \(\triangle PBC\) is \(10-2=8\).
Answer: (C)
Since there are 60 seconds in 1 minute, then \(t\) seconds is equivalent to \(\dfrac{t}{60}\) minutes.
Since there are 60 minutes in 1 hour, then \(\dfrac{t}{60}\) minutes is equivalent to \(\dfrac{t}{60\times 60}\) hours or\(\dfrac{t}{3600}\) hours.
Consider the distances that Car X and Car Y travel between the instant when the front of Car Y is lined up with the back of Car X and the instant when the back of Car Y is lined up with the front of Car X.
Since the length of Car X is 5 m and the length of Car Y is 6 m, then during this interval of time, Car Y travels \(5+6=11\) m farther than Car X. (The front of Car Y must, in some sense, travel all of the way along the length of the Car X and be 6 m ahead of the front of Car X so that the back of Car Y is lined up with the front of Car X.)
Since there are 1000 metres in 1 km, then 11 m is equivalent to \(0.011\) km.
Since Car X travels at 90 km/h, then in \(\dfrac{t}{3600}\) hours, Car X travels \(\dfrac{90t}{3600}\) km.
Since Car Y travels at 91 km/h, then in \(\dfrac{t}{3600}\) hours, Car Y travels \(\dfrac{91t}{3600}\) km.
Therefore, \(\dfrac{91t}{3600} - \dfrac{90t}{3600} = 0.011\), or \(\dfrac{t}{3600} = 0.011\) and so \(t = 3600\times 0.011 = 36 \times 1.1 = 39.6\).
Answer: (A)
We label the remaining unknown entries as \(a,b,c,d\), as shown.
Now \(a,b,c,d,x\) must equal \(2,3,4,5,6\) in some order, with the restriction that no two integers that differ by 1 may be in squares that share an edge.
In particular, we see first that \(a \neq 2\). Therefore, \(a\) can equal 3, 4, 5, or 6.
If \(a = 3\), then neither \(b\) nor \(d\) can equal 2 or 4.
Thus, \(b\) and \(d\) equal 5 and 6 in some order.
In this case, \(c\) cannot be 4 (since one of \(b\) and \(d\) is 5) so \(c=2\) and so \(x=4\).
If \(a = 4\), then neither \(b\) nor \(d\) can equal 3 or 5.
Thus, \(b\) and \(d\) equal 2 and 6 in some order.
In this case, \(c\) cannot equal 3 or 5, since it is adjacent to 2 and 6, so this case is not possible.
If \(a=5\), then neither \(b\) nor \(d\) can equal 4 or 6.
Thus, \(b\) and \(d\) equal \(2\) and \(3\) in some order.
In this case, \(c\) cannot be 4 (since one of \(b\) and \(d\) is 3) so \(c=6\) and so \(x=4\).
If \(a = 6\), then neither \(b\) nor \(d\) can equal 5.
Thus, \(b\) and \(d\) equal two of 2, 3 or 4 in some order.
If \(b\) and \(d\) are 2 and 4, then \(c\) cannot be 3 or 5 (the remaining numbers), so there is no solution.
If \(b\) and \(d\) are 3 and 4, then \(c\) cannot be 2 or 5 (the remaining numbers), so there is no solution.
If \(b\) and \(d\) are 2 and 3, then we can have \(c=5\), in which case we must have \(x=4\), which is not possible.
Having considered all possible cases, we see that there is only one possible value for \(x\), namely \(x=4\).
Answer: (A)
Suppose that the height of the top left rectangle is \(2x\).
Since square \(PQRS\) has side length 42, then the bottom rectangle has height \(42-2x\).
Since the width of the bottom rectangle is 42 (the side length of the square), then the perimeter of the bottom rectangle is \(2(42)+2(42-2x) = 168 - 4x\).
Suppose that the width of the top left rectangle is \(y\).
Since each of the small rectangles has the same perimeter, then \(2(2x)+2y = 168-4x\). (That is, the perimeter of the top left rectangle equals the perimeter of the bottom rectangle.)
Thus, \(2y = 168-8x\) or \(y = 84 - 4x\).
Since the side length of the square is 42, then the width of the top right rectangle is \(42 - (84-4x) = 4x - 42\).
Since the two rectangles on the top right have the same perimeter and the same width, then they must have the same height, which is equal to half of the height of the top left rectangle.
Thus, the height of each of the two rectangles on the right is \(x\).
Finally, the perimeter of the top right rectangle must equal also equal \(168-4x\).
Thus, \(2(4x-42)+2x = 168-4x\) or \(8x - 84 + 2x = 168 - 4x\) and so \(14x = 252\) or \(x = 18\).
This tells us that the shaded rectangle has dimensions \(x = 18\) by \(4x - 42 = 4(18)-42=30\) and so its area is \(18 \times 30 = 540\).
(We can check by substitution that the resulting rectangles in the original diagram are \(6 \times 42\), \(36 \times 12\) and \(30 \times 18\), which all have the same perimeter.)
Answer: (E)
To solve this problem, we need to use two facts about a triangle with positive area and side lengths \(a \leq b \leq c\):
\(a+b>c\). This is called the Triangle Inequality and is based on the fact that the shortest distance between two points is a straight line. In this case, the shortest distance between the two vertices of the triangle at opposite ends of the side with length \(c\) is this length \(c\). Any other path between these paths is longer. In particular, travelling between these two points along the other two sides is longer. This path has length \(a+b\) and so \(a+b>c\). (This is where the condition of “positive area” is used.)
If the triangle is obtuse, then \(a^2+b^2 < c^2\); if the triangle is acute, \(a^2+b^2>c^2\). This makes sense from the given examples and the fact that if \(a^2+b^2=c^2\), the triangle is right-angled. We justify these facts further at the end.
Suppose that the unknown side length \(x\) of the obtuse triangle is the longest side length; that is, suppose that \(10 \leq 17 \leq x\).
Here, we must have \(10+17 > x\) and \(10^2+17^2 < x^2\).
From the first inequality, \(x< 27\). Since \(x\) is an integer, then \(x \leq 26\).
From the second inequality, \(x^2 > 389\) and so \(x > \sqrt{389}\). Since \(\sqrt{389} \approx 19.72\) and \(x\) is an integer, then \(x \geq 20\). This gives the possible values \(x=20,21,22,23,24,25,26\)
Suppose that the unknown side length \(x\) of the obtuse triangle is not the longest side length. That is, \(x \leq 17\). (We know that \(10 \leq 17\) as well. Note also that the relative size of \(10\) and \(x\) is not important.)
Here, we must have \(x + 10 > 17\) and \(10^2+x^2 < 17^2\).
From the first inequality, \(x > 7\). Since \(x\) is an integer, then \(x \geq 8\).
From the second inequality, \(x^2 < 189\) and so \(x < \sqrt{189}\). Since \(\sqrt{189} \approx 13.75\) and \(x\) is an integer, then \(x \leq 13\). This gives the possible values \(x=8,9,10,11,12,13\).
Therefore, the possible values of \(x\) are \(8, 9, 10, 11, 12, 13, 20, 21, 22, 23, 24, 25, 26\).
The sum of these possible values is \(224\).
We still need to justify the second fact. We show that if the triangle is obtuse, then \(a^2+b^2 < c^2\). The second half of the fact can be shown in a similar way. While we could use the cosine law to justify this statement, we show this using angles and side lengths:
Consider \(\triangle ABC\) with \(\angle ACB\) obtuse and with \(AB=c\), \(AC=b\) and \(BC=a\).
At \(C\), draw a perpendicular line segment \(CD\) with length \(b\). Draw \(DB\) and \(DA\).
Since \(\triangle BCD\) is right-angled at \(C\), then \(BD = \sqrt{BC^2+CD^2} = \sqrt{a^2+b^2}\), by the Pythagorean Theorem.
Now \(\triangle ACD\) is isosceles with \(CA=CD\).
Thus, \(\angle CDA = \angle CAD\).
But \(\angle BDA > \angle CDA = \angle CAD > \angle BAD\).
Since \(\angle BDA > \angle BAD\), then in \(\triangle BDA\), we have \(BA > BD\).
This means that \(c = BA > BD = \sqrt{a^2+b^2}\) and so \(c^2 > a^2+b^2\), as required.
Answer: (E)
We think of each allowable sequence of moves as a string of X’s, Y’s and Z’s. For example, the string ZZYXZ would represent moving Z one space to the right, then Z, then Y, then X, then Z.
For each triple \((x,y,z)\) of integers with \(0 \leq x \leq 3\) and \(0 \leq y \leq 3\) and \(0 \leq z \leq 3\), we define \(S(x,y,z)\) to be the number of sequences of moves which result in X moving \(x\) spaces to the right and Y moving \(y\) spaces to the right and Z moving \(z\) spaces to the right.
For example, \(S(1,0,0)=0\) and \(S(0,1,0)=0\) since X and Y are not allowable sequences, and \(S(0,0,1)=1\) since Z is allowable and is only sequence of 1 move.
We want to find \(S(3,3,3)\).
Next, we note that if \(x>y\) or \(y>z\) or \(x>z\), then \(S(x,y,z)=0\), since any allowable sequence has to have at least as many Z’s as Y’s and at least as many Y’s as X’s, because no coin can jump another coin. In other words, we need to have \(0 \leq x \leq y \leq z \leq 3\).
We now make the key observation that if \(0 \leq x \leq y \leq z \leq 3\), then \[S(x,y,z) = S(x-1,y,z)+S(x,y-1,z)+S(x,y,z-1)\] where we use the convention that if \(x=0\), then \(S(x-1,y,z)=0\), and if \(y=0\), then \(S(x,y-1,z)=0\), and if \(z=0\), then \(S(x,y,z-1)=0\).
This rule is true because:
Every allowable sequence counted by \(S(x,y,z)\) ends with X, Y or Z.
If an allowable sequence counted by \(S(x,y,z)\) ends in X, then the sequence formed by removing this X was allowable and is counted by \(S(x-1,y,z)\).
Furthermore, if \(x-1 \leq y \leq z\) (that is, there are sequences consisting of \(x-1\) X’s, \(y\) Y’s and \(z\) Z’s, making \(S(x-1,y,z) > 0\)) and \(x \leq y \leq z\), then every sequence counted by \(S(x-1,y,z)\) can have an X put on the end to make a sequence counted by \(S(x,y,z)\) ending in an X.
The last two bullets together tell us that the number of sequences counted by \(S(x,y,z)\) and ending in X is exactly equal to \(S(x-1,y,z)\).
Similarly, the sequences counted by \(S(x,y,z)\) and ending in \(Y\) is \(S(x,y-1,z)\) and the number of sequences counted by \(S(x,y,z)\) and ending in \(Z\) is \(S(x,y,z-1)\).
Therefore, \(S(x,y,z) = S(x-1,y,z)+S(x,y-1,z)+S(x,y,z-1)\).
Using this rule, we can create tables of values of \(S(x,y,z)\). We create one table for each of \(z=1\), \(z=2\) and \(z=3\).
In each table, values of \(y\) are marked along the left side and values of \(x\) along the top. In each table, there are several 0s in spots where \(x>y\) or \(x>z\) or \(y>z\).| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 |
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 |
| 1 | 2 | 3 | 0 | 0 |
| 2 | 2 | 5 | 5 | 0 |
| 3 | 0 | 0 | 0 | 0 |
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 |
| 1 | 3 | 6 | 0 | 0 |
| 2 | 5 | 16 | 21 | 0 |
| 3 | 5 | 21 | 42 | 42 |
The non-zero entries are filled from top to bottom and left to right, noting that each entry is the sum of the entries (if applicable) to the left in the same table (this is \(S(x-1,y,z)\)), above in the same table (this is \(S(x,y-1,z)\)), and in the same position in the previous table (this is \(S(x,y,z-1)\)).
Also, \(S(0,0,1)=1\) (the sequence Z), \(S(0,1,1)=1\) (the sequence ZY), and \(S(1,1,1)=1\) (the sequence ZYX.
From these tables, we see that \(S(3,3,3)=42\) and so the number of different sequences is 42.
Answer: (C)
We proceed using several steps.
Step 1: Least common multiples
For each positive integer \(n \geq 3\) and positive integer \(x<n\), we define \(L(n,x)\) to be the least common multiple of the \(n-2\) integers \(1,2,3,\ldots,x-2,x-1,x+2,x+3,\ldots,n-1,n\).
One way to calculate the least common multiple of a list of integers is to determine the prime factorization of each of the integers in the list and then to create the product of the largest of each of the prime powers that occurs among the integers in the list.
For example, if \(n=9\) and \(x=6\), then \(L(9,6)\) is the least common multiple of the five integers \(1,2,3,4,5,8,9\).
The prime factorizations of the integers larger than 1 in this list are \(2=2^1\), \(3=3^1\), \(4=2^2\), \(5=5^1\), \(8=2^3\), \(9=3^2\) and so \(L(9,6)=2^3 3^2 5^1 = 360\). In this case, \(L(9,6)\) is not divisible by \(x+1=7\) but is divisible by \(x=6\).
We note that, for any list of integers, a common multiple, \(m\), of all of the integers in this list is always itself a multiple of their least common multiple \(l\). This is because if \(p\) is a prime number and \(a\) is a positive integer for which \(p^a\) is a factor of \(l\), then there must be an integer in the list that is a multiple of \(p^a\). For \(m\) to be a common multiple of every number in the list, \(p^a\) must also be a factor of \(m\). Since this is true for every prime power \(p^a\) that is a factor of \(l\), then \(m\) is a multiple of \(l\).
Step 2: Connection between \(m\) and \(L(n,x)\)
We show that \(n\) is a Nella number with corresponding \(x\) exactly when \(L(n,x)\) is not divisible by \(x\) or \(x+1\).
Suppose that \(n\) is a Nella number with corresponding \(x\) and \(m\).
Then \(m\) must be divisible by each of \(1,2,3,\ldots,x-2,x-1,x+2,x+3,\ldots,n-1,n\).
From Step 1, \(m\) is a multiple of \(L(n,x)\).
Since \(m\) is a multiple of \(L(n,x)\) and \(m\) is not divisible by \(x\) or \(x+1\), then \(L(n,x)\) is not either.
Since \(L(n,x)\) is divisible by every other positive integer from between 1 and \(n\), inclusive, then \(L(n,x)\) satisfies the required conditions for \(m\) in the definition of a Nella number.
Also, if \(n\) and \(x\) are positive integers with \(n \geq 3\) and \(x<n\) and \(L(n,x)\) has the two required conditions in the definition of a Nella number, then \(n\) is indeed a Nella number.
Putting this together, \(n\) is a Nella number with corresponding \(x\) exactly when \(L(n,x)\) is not divisible by \(x\) or \(x+1\).
Step 3: Re-statement of problem
Based on Step 2, we now want to find all positive integers \(n\) with \(50 \leq n \leq 2017\) for which there exists a positive integer \(x\) with \(x<n\) with the property that \(L(n,x)\) is not divisible by \(x\) and \(x+1\).
Step 4: If \(n\) is a Nella number with corresponding \(x\), then \(x\) and \(x+1\) are both prime powers
Suppose that \(n\) is a Nella number with corresponding \(x\).
Further, suppose that \(x\) is not a prime power.
Then \(x = p^a b\) for some prime number \(p\), positive integer \(a\) and positive integer \(b>1\) that is not divisible by \(p\).
In this case, \(p^a < x\) and \(b<x\) and so \(p^a\) and \(b\) are both in the list \(1,2,3,\ldots,x-2,x-1\), which means that \(L(n,x)\) is a multiple of both \(p^a\) and \(b\) and so is a multiple of \(p^a b = x\). (It is important here that \(p^a\) and \(b\) have no common prime factors.) This is a contradiction.
This means that if \(n\) is a Nella number, then \(x\) is a prime power.
Similarly, \(x+1\) must also be a prime power. To see this, we use the same argument with the additional observation that, because \(x+1\) and \(x\) are consecutive, they cannot have any common divisor larger than 1 and so if \(x+1=p^c d\), then \(x\) cannot equal \(p^c\) or \(d\) and therefore both \(p^c\) and \(d\) are indeed in the list \(1,2,3,\ldots,x-1\).
Step 5: Further analysis of \(x\) and \(x+1\)
Suppose that \(n\) is a Nella number with corresponding \(x\).
From Step 4, both \(x\) and \(x+1\) are prime powers.
Since \(x\) and \(x+1\) are consecutive, then one is even and one is odd.
In other words, one of \(x\) and \(x+1\) is a power of 2 and the other is a power of an odd prime.
Furthermore, we know that \(L(n,x)\) is not divisible by \(x\) or \(x+1\).
This means that the list \(x+2,x+3,\ldots,n-1,n\) cannot contain a multiple of \(x\) or \(x+1\).
This means that \(x < n < 2x\) and \(x+1 \leq n < 2(x+1)\), because the “next” multiple of \(x\) is \(2x\) and the next multiple of \(x+1\) is \(2(x+1)\).
Since one of \(x\) and \(x+1\) is a power of 2, then 2 times this power of 2 (that is, \(2x\) or \(2(x+1)\)) is the next power of 2, and so the inequalities tell us that \(n\) is smaller than the next power of 2, and so \(x\) or \(x+1\) has to be the largest power of 2 less than (or less than or equal to, respectively) \(n\).
Step 6: Second re-statement of problem
We want to find all positive integers \(n\) with \(50 \leq n \leq 2017\) for which there exists a positive integer \(x\) with \(x<n\) with the property that \(L(n,x)\) is not divisible by \(x\) and \(x+1\).
From Step 5, we know that either \(x\) is the largest power of 2 less than \(n\) or \(x+1\) is the largest power of 2 less than or equal to \(n\).
This means that we want to find all positive integers \(n\) with \(50 \leq n \leq 2017\) for which at least one of the following two statements is true for some positive integer \(x<n\):
If \(x\) is the largest power of 2 less than \(n\), then \(x+1\) is also a prime power.
If \(x+1\) is the largest power of 2 less than or equal to \(n\), then \(x\) is also a prime power.
Step 7: Determining Nella numbers
We make two separate tables, one where \(x<n\) is a power of 2 and one where \(x+1 \leq n\) is a power of 2. In each case, we determine whether \(x+1\) or \(x\) is also a prime power.
| Range of \(n\) | Largest power of 2 less than \(n\) | \(x\) | \(x+1\) | Prime power? | Nella? |
|---|---|---|---|---|---|
| \(50 \leq n \leq 64\) | 32 | 32 | 33 | No (\(33 = 3 \cdot 11\)) | No |
| \(65 \leq n \leq 128\) | 64 | 64 | 65 | No (\(65 = 5 \cdot 13\)) | No |
| \(129 \leq n \leq 256\) | 128 | 128 | 129 | No (\(129 = 3 \cdot 43\)) | No |
| \(257 \leq n \leq 512\) | 256 | 256 | 257 | Yes | See below |
| \(513 \leq n \leq 1024\) | 512 | 512 | 513 | No (\(513 = 3 \cdot 171\)) | No |
| \(1025 \leq n \leq 2017\) | 1024 | 1024 | 1025 | No (\(1025 = 5 \cdot 205\)) | No |
Note that \(257\) is a prime number since it is not divisible by any prime number less than \(\sqrt{257} \approx 16.03\). (These primes are \(2,3,5,7,11,13\).)
For each \(n\) with \(257 \leq n \leq 511\), \(L(n,256)\) is not divisible by 256 or 257, so each of these \(n\) (there are \(511-257+1=255\) of them) is a Nella number.
For \(n = 512\), \(L(n,256)\) is divisible by 256 (since 512 is divisible by 256), so \(n=512\) is not a Nella number as this is the only possible candidate for \(x\) in this case.
| Range of \(n\) | Largest power of 2 at most \(n\) | \(x+1\) | \(x\) | Prime power? | Nella? |
|---|---|---|---|---|---|
| \(50 \leq n \leq 63\) | 32 | 32 | 31 | Yes | See below |
| \(64 \leq n \leq 127\) | 64 | 64 | 63 | No (\(63 = 3 \cdot 21\)) | No |
| \(128 \leq n \leq 255\) | 128 | 128 | 127 | Yes | See below |
| \(256 \leq n \leq 511\) | 256 | 256 | 255 | No (\(255 = 5 \cdot 51\)) | No |
| \(512 \leq n \leq 1023\) | 512 | 512 | 511 | No (\(511 = 7 \cdot 73\)) | No |
| \(1024 \leq n \leq 2017\) | 1024 | 1024 | 1023 | No (\(1023 = 3 \cdot 341\)) | No |
Note that \(31\) and \(127\) are prime.
For each \(n\) with \(50 \leq n \leq 61\), \(L(n,31)\) is not divisible by 31 or 32, so each of these \(n\) (there are \(61-50+1=12\) of them) is a Nella number.
For \(n = 62, 63\), \(L(n,31)\) is divisible by 31 (since 62 is divisible by 31), so neither is a Nella number as this is the only possible candidate for \(x\) in this case.
For each \(n\) with \(128 \leq n \leq 253\), \(L(n,127)\) is not divisible by 127 or 128, so each of these \(n\) (there are \(253-128+1=126\) of them) is a Nella number.
For \(n = 254, 255\), \(L(n,127)\) is divisible by 127 (since 254 is divisible by 127), so neither is a Nella number as this is the only possible candidate for \(x\) in this case.
Step 8: Final tally
From the work above, there are \(255+12+126=393\) Nella numbers \(n\) with \(50 \leq n \leq 2017\).
Answer: (A)
