2016 Canadian Intermediate
Mathematics Contest
Solutions
Wednesday, November 23, 2016
(in North America and South America)
Thursday, November 24, 2016
(outside of North American and South America)
Wednesday, November 23, 2016
(in North America and South America)
Thursday, November 24, 2016
(outside of North American and South America)
©2016 University of Waterloo
Solution 1
We re-write each of the fractions using the common denominator 24: \[\tfrac{2}{3} = \tfrac{16}{24} \qquad \tfrac{3}{4} = \tfrac{18}{24} \qquad \tfrac{5}{6} = \tfrac{20}{24} \qquad \tfrac{5}{8} = \tfrac{15}{24} \qquad \tfrac{11}{12} = \tfrac{22}{24}\] The smallest of these is \(\tfrac{15}{24}=\tfrac{5}{8}\).
Solution 2
We note that \(\tfrac{2}{3} = 1 - \tfrac{1}{3}\) and \(\tfrac{3}{4} = 1 - \tfrac{1}{4}\) and \(\tfrac{5}{6} = 1 - \tfrac{1}{6}\) and \(\tfrac{11}{12} = 1 - \tfrac{1}{12}\).
The smallest of these four fractions is the one which is equal to 1 minus the largest of the unit fractions \(\frac{1}{3},\frac{1}{4},\frac{1}{6},\frac{1}{12}\). This is \(\tfrac{2}{3} = 1 - \tfrac{1}{3}\).
So we need to compare \(\frac{2}{3}\) and \(\tfrac{5}{8}\), the smaller of which will be the smallest of the five fractions in the list.
Since \(\frac{2}{3} = 0.\overline{6} \approx 0.667\) and \(\tfrac{5}{8} = 0.625\), then \(\tfrac{5}{8}\) is the smallest of the five fractions.
Answer: \(\tfrac{5}{8}\)
Solution 1
From the graph, the numbers of students whose birthday in 2016 is on Sunday, Monday, Wednesday, Thursday, Friday, and Saturday are 4, 4, 2, 2, 8, and 6, respectively.
Therefore, the number of students whose birthday is not on a day beginning with “T” is \(4+4+2+8+6=24\).
Since 25% of the students have their birthday in 2016 on a day beginning with “T”, then \(100\% - 25\% = 75\%\) of the students have their birthday on a day not beginning with “T”.
Since 75% is equivalent to \(\frac{3}{4}\), then 24 students represent \(\frac{3}{4}\) of the class, and so 8 students represent \(\frac{1}{4}\) or 25% of the class.
Since 2 students have their birthday on Thursday and 8 students (25% of the class) have their birthday in 2016 on a day beginning with “T”, then the number of students with a birthday on Tuesday is \(8-2=6\).
Solution 2
Suppose that there were \(t\) students with their birthday on Tuesday.
Then there are \(t+2\) students born on a day beginning with “T".
Also, there are \(4+4+t+2+2+8+6 = 26+t\) students in Ms. Gupta’s class.
We note that \(25\%\) is equivalent to \(\frac{1}{4}\).
Since 25% of the students in Ms. Gupta’s class have their birthday in 2016 on a day beginning with “T", then the total number of students is 4 times the number of students with a birthday on a day beginning with the letter “T".
Thus, \(26+t = 4(t+2)\).
This gives \(26+t = 4t + 8\) or \(18 = 3t\) and so \(t=6\).
In other words, there were 6 students with their birthday in 2016 on a Tuesday.
Answer: 6
Since there are 12 hurdles, then there are 11 gaps between the hurdles, each of length \(d\) metres.
The gap before the first hurdle is 50 metres and the gap after the last hurdle is 55 metres.
Since the race is 600 metres long, then \(50+11d+55 = 600\) or \(11d = 495\) and so \(d=45\).
Answer: \(d=45\)
Solution 1
Dina’s machine works by taking an input, multiplying by 2 and then subtracting 3.
If we have the output and want to obtain the input, we must reverse these operations and so we take the output, add 3 and then divide by 2.
Starting with the second output \(-35\), we obtain \(-35+3=-32\) and then \(\frac{-32}{2}=-16\), which was the second input.
Since the second input was the first output, then the first output was \(-16\).
Starting with the first output \(-16\), we obtain \(-16+3 = -13\) and then \(\frac{-13}{2}\), which was the first input.
Therefore, the first input was \(-\frac{13}{2}\) or \(-6.5\).
Solution 2
Starting with the first input \(x\), Dina’s machine multiplies it by 2 to obtain \(2x\) and then subtracts 3 to obtain \(2x-3\).
Dina inputs this output back into the machine.
The machine multiplies the input by 2 to obtain \(2(2x-3)=4x-6\) and then subtracts \(3\) to obtain \(4x-9\).
Since the second output is \(-35\), then \(4x-9=-35\) or \(4x = -26\) and so \(x = \tfrac{-26}{4} = -\tfrac{13}{2}\) or \(-6.5\).
Answer: \(-\tfrac{13}{2}\)
Solution 1
Since the distance from \(P\)’s initial position to \(X\) along the circle is 8 m, then after travelling 8 m, \(P\) will be at \(X\).
Since the circumference of the circle is \(8+16+16=40\) m, then after travelling any additional multiple of 40 m, \(P\) will again be at \(X\).
In other words, \(P\) is at \(X\) after travelling 8 m, 48 m, 88 m, 128 m, 168 m, and so on.
Similarly, since the distance from \(Q\)’s initial position to \(X\) along the circle is 16 m, then \(Q\) is at \(X\) after travelling 16 m, 56 m, 96 m, 136 m, 176 m, and so on.
We now make two charts that list possible distances travelled by \(P\) and \(Q\) to arrive at \(X\) and the corresponding times that these distances take. We are looking for the same lengths of time to appear in both tables, as this would indicate times when \(P\) and \(Q\) are both at \(X\).
| Distance for \(P\) (m) | Time (s) (rounded to the nearest hundredth) |
|---|---|
| 8 | 2.67 |
| 48 | 16 |
| 88 | 29.33 |
| 128 | 42.67 |
| 168 | 56 |
| 208 | 69.33 |
| 248 | 82.67 |
| 288 | 96 |
| Distance for \(Q\) (m) | Time (s) (rounded to the nearest hundredth) |
|---|---|
| 16 | 4.57 |
| 56 | 16 |
| 96 | 27.43 |
| 136 | 38.86 |
| 176 | 50.29 |
| 216 | 61.71 |
| 256 | 73.14 |
| 296 | 84.57 |
| 336 | 96 |
In each case, we determine the time by taking the distance travelled and dividing by the appropriate constant speed (3 m/s for \(P\) and 3.5 m/s for \(Q\)). For example, \(Q\) travels 56 m in \(\dfrac{56\mbox{ m}}{3.5\mbox{ m/s}} = 16\mbox{ s}\).
From the tables, we see that \(P\) and \(Q\) meet at \(X\) after 16 s (having travelled \(16 \cdot 3 = 48\) m and \(16 \cdot 3.5 = 56\) m, respectively) and then again after 96 s (having travelled \(96 \cdot 3 = 288\) m and \(96 \cdot 3.5 = 336\) m, respectively).
Therefore, \(P\) and \(Q\) meet at \(X\) for the second time after 96 s.
Solution 2
The circumference of the circle is \(8+16+16=40\) m.
Since \(P\) starts 8 m from \(X\), then \(P\) is at \(X\) after moving \(8+40p\) metres, for each integer \(p \geq 0\). (The variable \(p\) represents the number of complete times that \(P\) has moved around the circle after reaching \(X\) for the first time.)
Similarly, since \(Q\) starts 16 m from \(X\), then \(Q\) is at \(X\) after moving \(16+40q\) metres, for each integer \(q \geq 0\).
Suppose that \(P\) and \(Q\) meet at \(X\) after moving for \(t\) seconds. We want to determine the second smallest possible value of \(t\).
Since \(P\) moves at 3 m/s, then after \(t\) seconds, \(P\) has moved \(3t\) metres.
Since \(Q\) moves at 3.5 m/s, then after \(t\) seconds, \(Q\) has moved \(3.5t\) metres.
For \(P\) and \(Q\) to be at \(X\) after \(t\) seconds, we need \(3t = 8+40p\) and \(3.5t = 16+40q\) for some integers \(p,q \geq 0\).
Multiplying the first of these equations by 7 and the second of these equations by 6, we obtain \(21t = 56 + 280p\) and \(21t = 96 + 240q\).
Equating the expressions equal to \(21t\), we obtain \(56+ 280p = 96 + 240q\).
Manipulating this equation, we obtain the equivalent equations \(280p = 40 + 240q\) and \(7p = 1 + 6q\).
Since we are looking for the second smallest possible value of \(t\), then we look for the second smallest pair of integers \(p\) and \(q\) with \(p,q\geq 0\) that satisfy this equation.
We do this by listing values of \(q\) and the corresponding values of \(1+6q\) until we obtain the second \(q\) for which \(1+6q\) is a multiple of 7:
| \(q\) | \(1+6q\) | Multiple of 7? |
|---|---|---|
| 1 | 7 | Y |
| 2 | 13 | N |
| 3 | 19 | N |
| 4 | 25 | N |
| 5 | 31 | N |
| 6 | 37 | N |
| 7 | 43 | N |
| 8 | 49 | Y |
Answer: 96
Every line is determined by any two points on the line.
We use \(\mathcal{L}\) to denote the line with equation \(x+y=1\).
We use \(\ell\) to denote the line with equation \(y=kx\) and \(\ell'\) to denote the line obtained after reflecting \(\ell\) in \(\mathcal{L}\).
We determine the slope and \(y\)-intercept of \(\ell'\) by finding two points on \(\ell'\) and then using these points to determine the slope, equation, and \(y\)-intercept.
The first point that we choose is the point, \(P\), of intersection between the original line, \(\ell\), \(y=kx\), and the line of reflection, \(\mathcal{L}\).
We note that the line of reflection can be re-written as \(y=-x+1\), which has slope \(-1\).
Since \(k \neq -1\), then \(\ell\) is not parallel to \(\mathcal{L}\) and so there is indeed a point of intersection.
Since \(P\) is on \(\ell\), then its reflection will be on the resulting line.
Since \(P\) is on \(\mathcal{L}\), then its reflection will be itself.
In other words, \(P\) is also on \(\ell'\).
To find the \(x\)-coordinate of \(P\), we substitute \(y=kx\) into \(x+y=1\) to obtain \(x + kx = 1\) or \(x(k+1)=1\) and so \(x = \dfrac{1}{k+1}\).
Since \(P\) is on \(\ell\), which has equation \(y=kx\), then \(y = k\cdot \dfrac{1}{k+1} = \dfrac{k}{k+1}\).
Thus, the coordinates of \(P\) are \(\left(\dfrac{1}{k+1},\dfrac{k}{k+1}\right)\).
Consider next the point \(O(0,0)\) which is on \(\ell\).
Let \(Q\) be the reflection of \(O\) in \(\mathcal{L}\).
Since \(Q\) is the reflection of \(O\) in \(\mathcal{L}\), then \(OQ\) is perpendicular to \(\mathcal{L}\).
Since \(\mathcal{L}\) has slope \(-1\), then any line perpendicular to \(\mathcal{L}\) has slope equal to \(-\frac{1}{-1}=1\).
Therefore, \(OQ\) has slope 1.
Since \(O\) is the origin \((0,0)\), then the line through \(O\) and \(Q\) has equation \(y=x\).
Thus, \(Q\) has coordinates \((q,q)\) for some real number \(q\).
In addition to \(OQ\) being perpendicular to \(\mathcal{L}\), we also need the midpoint of \(OQ\) to lie on \(\mathcal{L}\).
The midpoint of \(O(0,0)\) and \(Q(q,q)\) has coordinates \((\frac{1}{2}(0+q),\frac{1}{2}(0+q))=(\frac{1}{2}q,\frac{1}{2}q)\).
Since this point lies on the line with equation \(x+y=1\), then \(\frac{1}{2}q+\frac{1}{2}q=1\) or \(q=1\).
Thus, \(Q\) has coordinates \((1,1)\).
Therefore, \(\ell'\) passes through \(Q(1,1)\) and \(P\left(\dfrac{1}{k+1},\dfrac{k}{k+1}\right)\).
The slope of \(\ell'\) is thus \(\dfrac{1-\frac{k}{k+1}}{1-\frac{1}{k+1}} = \dfrac{\frac{k+1}{k+1}-\frac{k}{k+1}}{\frac{k+1}{k+1}-\frac{1}{k+1}} = \dfrac{\frac{1}{k+1}}{\frac{k}{k+1}} = \dfrac{1}{k}\). (Note that \(k \neq 0\).)
Therefore, \(\ell'\) has equation \(y = \dfrac{1}{k}x+b\) for some \(b\).
Since \(Q(1,1)\) lies on \(\ell'\), then \(1 = \dfrac{1}{k}+b\) or \(b = \dfrac{k-1}{k}\).
Therefore, the slope of \(\ell'\) is \(\dfrac{1}{k}\) and its \(y\)-intercept is \(\dfrac{k-1}{k}\).
Answer: Slope is \(\dfrac{1}{k}\); \(y\)-intercept is \(\dfrac{k-1}{k}\)
\(\triangle ABC\) is right-angled at \(B\).
Also, \(AB=2\) and \(BC=3\).
Since \(\triangle ABC\) is right-angled at \(B\), the area of \(\triangle ABC\) is \(\frac{1}{2}AB \cdot BC = \frac{1}{2}(2)(3)=3\).
We extend \(DE\) and \(GF\) to meet at \(P\), as shown.
Then figure \(DEFGH\) can be viewed as rectangle \(DHGP\) with \(\triangle EPF\) removed.
In fact, \(DHGP\) is a square since \(DH=5\) and \(HG=5\).
Also, \(\triangle EPF\) is congruent to \(\triangle ABC\), since it has height 2 and base 3.
Therefore, the area of \(DEFGH\) equals the area of \(DHGP\) minus the area of \(\triangle EPF\), which equals \(5^2 - 3 = 22\).
We draw lines through \(J\), \(K\) and \(L\) that are horizontal and vertical (that is, that are along the rows and columns of dots) to form rectangle \(QLRS\), as shown above.
The area of \(\triangle JKL\) can be calculated by taking the area of rectangle \(QLRS\) and subtracting the areas of \(\triangle JSK\), \(\triangle LQJ\) and \(\triangle LRK\).
Here, \(QLRS\) is a square with side length 5.
Also, \(\triangle JSK\) is congruent to \(\triangle ABC\) and so has area 3.
\(\triangle LQJ\) is right-angled at \(Q\) and has \(LQ=5\) and \(JQ=3\).
Thus, its area is \(\frac{1}{2}LQ \cdot JQ = \frac{1}{2}(5)(3) = \frac{15}{2}\).
\(\triangle LRK\) is right-angled at \(R\) and has \(LR=5\) and \(KR=2\).
Thus, its area is \(\frac{1}{2}LR \cdot KR = \frac{1}{2}(5)(2) = 5\).
Finally, this tells us that the area of \(\triangle JKL\) is \(25 - 3 - \frac{15}{2}-5 = \frac{19}{2}\).
(This can also be solved using a result called Pick’s Theorem, which involves counting the number of grid dots that occur on the boundary and in the interior of the shape.)
One way of arranging these integers is \(1,3,5,2,4\).
The positive differences between the pairs of adjacent integers are \(2,2,3,2\).
There are many other ways of arranging these integers so that the desired property is true.
(We note that this property is equivalent to arranging the five integers so that no two consecutive integers are adjacent.)
In any arrangement, the integer 10 must be placed next to at least one other integer.
From the list \(1,2,3,\ldots,20\), the integers “furthest away” from 10 are 1 and 20.
The positive differences between 10 and these integers are 9 and 10.
In other words, the positive difference between 10 and every other integer in the list is less than or equal to 10.
Therefore, in any arrangement, there must be a positive difference that is at most 10, and so \(N\) (the smallest of these differences) is less than or equal to 10, which means that \(N\) cannot be 11 or larger.
Consider the following arrangement: \[10, 20, 9, 19, 8, 18, 7, 17, 6, 16,\] \[5, 15, 4, 14, 3, 13, 2, 12, 1, 11\] The positive differences between the pairs of adjacent integers are \[10, 11, 10, 11, 10, 11, 10, 11, 10, 11,\] \[10, 11, 10, 11, 10, 11, 10, 11, 10\] The smallest of these positive differences is 10.
Consider the integer 14, which is the middle integer in the list \(1,2,3,\ldots,25,26,27\).
The maximum possible positive difference between 14 and another number from this list is 13.
Therefore, in any arrangement, there must be a positive difference that is no larger than 13.
This tells us that \(N\), the smallest of the positive differences, is less than or equal to 13.
To show that the maximum possible value of \(N\) is 13, we need to show that there actually exists an arrangement with \(N=13\), since it is possible that, for some other reason, we could not make a list with \(N=13\).
Here is such an arrangement: \[14,27,13,26,12,25,11,24,10,23,9,22,\] \[8,21,7,20,6,19,5,18,4,17,3,16,2,15,1\] The positive differences between the pairs of adjacent integers are \[13,14,13,14,13,14,13,14,13,14,13,14,13,\] \[14,13,14,13,14,13,14,13,14,13,14,13,14\] Therefore, the maximum possible value of \(N\) is 13.
To see why the Murray number of 6 is 12, we need to argue that
there exist one or more distinct integers greater than 6 and less than or equal to \(M=12\) such that the product of this list of integers times 6 is a perfect square, and
\(M=12\) is the smallest \(M>6\) with this property.
First, we note that \(6 \times 8 \times 12 = 576 = 24^2\) and so the first bullet is satisfied.
Second, for 6 times a product of one or more integers to be a perfect square, this product must include an odd number of factors of 3. This is because 6 includes exactly an odd number of factors of 3 and a perfect square must include an even number of factors of 3. For a product to include an odd number of factors of 3, not all of the integers in the product can include an even number of factors of 3, so one of the integers in the product must include an odd number of factors of 3. Since the first two multiples of 3 larger than 6 are 9 and 12, and 9 includes an even number of factors of 3, then the product must include a multiple of 3 that is at least as large as 12. In other words, we need to have \(M \geq 12\).
These two statements explain why 12 is the Murray number of 6.
The Murray number of 8 is 15.
While no justification is required for full marks on this part, we present a justification modelled after the solution in (a).
First, \(8 \times 10 \times 12 \times 15 = 14\,400 = 120^2\) which is a perfect square.
The statement in the previous sentence shows that \(M \leq 15\).
Is it possible that \(M < 15\)?
Since 8 includes an odd number of factors of 2, then the Murray product must include another integer with an odd number of factors of 2.
Since \(M \leq 15\) already, we only need to consider integers between 8 and 15 with an odd number of factors of 2. These integers are 10 and 14.
If 10 is in the Murray product, then, because 10 includes an odd number of factors of 5, we need to include another multiple of 5, which must be at least 15.
If 14 is in the Murray product, then, because 14 includes an odd number of factors of 7, we would need to include another multiple of 7, which must be at least 21, which is too large.
Therefore, it is not possible that \(M < 15\), which tells us that \(M =15\).
Let \(k\) be a positive integer and consider \(n=8k^2 = 2(2k)^2\).
We see that \(n\) cannot be a perfect square since \((2k)^2\) is itself a perfect square and so includes an even number of factors of 2, and so \(n=8k^2 = 2(2k)^2\) includes an odd number of factors of 2.
The product \(8k^2 \times 10k^2 \times 12k^2 \times 15k^2 = 14\,400k^8 = (120k^4)^2\) is a perfect square.
This shows that the Murray number of \(n=8k^2\) is at most \(15k^2\), which is less than \(2n=16k^2\).
Since there are infinitely many possible values for \(k\), then there are infinitely many such positive integers \(n\), as required.
(There are many other ways to solve this problem.)
Solution 1
Let \(n\) be a positive integer.
First, we prove that the Murray number of \(n\) exists.
Since \(n \times 4n = 4n^2 = (2n)^2\), then there does exist a set of one or more distinct integers larger than \(n\) whose product times \(n\) is a perfect square.
Thus, the Murray number \(M\) of \(n\) exists and satisfies \(n < M \leq 4n\). The fact that \(n \times 4n\) is a perfect square does not necessarily tell us that \(4n\) is the Murray number. Since the integer \(4n\) has the correct property to be the Murray number, then the question that must be answered is whether or not there is an integer smaller than \(4n\) (but still larger than \(n\)) with this property; if not, then \(4n\) is the Murray number.
Next, we prove that the Murray number of \(n\) is greater than or equal to \(n+3\).
To do this, we prove that the Murray number of \(n\) cannot be less than \(n+3\).
Since the Murray number of \(n\) is greater than \(n\), then the only possibilities less than \(n+3\) are \(n+1\) and \(n+2\).
Case 1: Can the Murray number of \(n\) be \(n+1\)?
If this were the case, then there would exist one or more distinct integers greater than \(n\) and less than or equal to \(n+1\) whose product times \(n\) is a perfect square.
Since \(n+1\) is the only integer that satisfies these restrictions, then for \(n+1\) to be the Murray number of \(n\), it must be the case that \(n(n+1)\) is a perfect square.
We note that \(n^2\) and \((n+1)^2 = n^2+2n+1\) are consecutive perfect squares.
Since \(n\) is a positive integer then, \(n^2 = n \times n < n(n+1)\).
Also, \(n(n+1) < (n+1)(n+1)=(n+1)^2\).
In other words, \(n^2 < n(n+1) < (n+1)^2\).
Since \(n(n+1)\) is between two consecutive perfect squares, then \(n(n+1)\) cannot itself be a perfect square.
This tells us that \(n+1\) cannot be the Murray number of \(n\).
Case 2: Can the Murray number of \(n\) be \(n+2\)?
If this were the case, then there would exist one or more distinct integers greater than \(n\) and less than or equal to \(n+2\) whose product times \(n\) is a perfect square.
Since \(n+1\) and \(n+2\) are the only integers that satisfy these restrictions, then for \(n+2\) to be the Murray number of \(n\), it must be the case that \(n(n+2)\) is a perfect square or \(n(n+1)(n+2)\) is a perfect square. (The product must include \(n+2\) itself as a factor otherwise the Murray number would be less than \(n+2\). Also, the product either includes \(n+1\) or it does not.)
Now, \(n^2 < n(n+2)\) and \(n(n+2) = n^2 + 2n < n^2 + 2n + 1 = (n+1)^2\).
Thus, \(n^2 < n(n+2) < (n+1)^2\), and a similar argument to that in the previous case shows that \(n(n+2)\) is not a perfect square.
To conclude our argument, we must show that \(n(n+1)(n+2)\) cannot be a perfect square.
To show this, we will use the following three facts:
(F1) The difference between two positive perfect squares cannot equal 1.
Suppose \(a \geq 1\) and \(a^2\) is the smaller of a pair of positive perfect squares.
The closest larger perfect square is \((a+1)^2\), and so the smallest possible difference between \(a^2\) and a larger perfect square equals \((a+1)^2 - a^2\) or\(a^2+2a+1-a^2\) or \(2a+1\) which is at least 3 since \(a \geq 1\).
Therefore, the difference between two positive perfect squares cannot equal 1.
(F2) The largest possible common divisor that two of \(n,n+1,n+2\) can share is 2.
Suppose that two integers are multiples of \(d\).
Then their difference must also be a multiple of \(d\).
Among the three integers \(n,n+1,n+2\), the possible differences between pairs are 1 and 2.
Thus, the possible positive common divisors are the positive divisors of 1 and 2, which are 1 and 2.
Therefore, the largest possible common divisor that two of \(n,n+1,n+2\) can share is 2.
(F3) If the product of two or more positive integers is a perfect square and each pair of these positive integers has no common divisor larger than 1, then each of these positive integers must be a perfect square.
Consider a prime number \(p\) that is a factor of the product.
Since the product is a perfect square, then the product includes an even number of factors of \(p\).
Now \(p\) cannot divide into more than one of the integers that make up the product, so it must be included an even number of times in one of the integers and cannot be included in any of the other integers.
Since this is true for any prime number \(p\) that is a factor of the product, then each of integers that make up the product must be a perfect square.
We now consider \(n(n+1)(n+2)\) and assume that it is a perfect square.
If \(n\) is odd, then \(n+1\) is even and \(n+2\) is odd.
Since the maximum possible common divisor of any pair of these is 2 (by (F2)) and only one of these integers is even, then no pair of these integers has a common divisor larger than 1.
By (F3), each of \(n,n+1,n+2\) must be a perfect square.
But by (F1), no two perfect squares differ by 1.
Thus, \(n\) cannot be odd.
If \(n\) is even, then \(n+1\) is odd and \(n+2\) is even.
By the arguments above, every prime factor other than 2 of one of these three integers is not included in either of the other integers. Also, this factor must be included an even number of times in the integer in which it appears.
Since \(n+1\) is odd, it has no factors of 2, and so must be a perfect square since all of its other prime factors will occur in pairs.
By (F1), neither \(n\) nor \(n+2\) can be a perfect square.
Thus, \(n=2b^2\) and \(n+2=2c^2\) for some positive integers \(b\) and \(c\). This is because each is even, any other prime factor occurs in pairs, and neither can include an even number of factors of 2 (otherwise it would be a perfect square).
In this case, we have \(2 = (n+2)-n = 2c^2 - 2b^2\) and so \(c^2 - b^2 = 1\), which contradicts (F1).
Thus, \(n\) cannot be even, and so \(n(n+1)(n+2)\) cannot be a perfect square.
Therefore, the Murray number of \(n\) exists and cannot be \(n+1\) or \(n+2\), and so must be greater than or equal to \(n+3\).
Solution 2
Let \(n\) be a positive integer.
First, we prove that the Murray number of \(n\) exists.
Since \(n \times 4n = 4n^2 = (2n)^2\), then there does exist a set of one or more distinct integers larger than \(n\) whose product times \(n\) is a perfect square.
Thus, the Murray number \(M\) of \(n\) exists and satisfies \(n < M \leq 4n\). The fact that \(n \times 4n\) is a perfect square does not necessarily tell us that \(4n\) is the Murray number. Since the integer \(4n\) has the correct property to be the Murray number, then the question that must be answered is whether or not there is an integer smaller than \(4n\) (but still larger than \(n\)) with this property; if not, then \(4n\) is the Murray number.
To show that the Murray number of \(n\) is at least \(n+3\), we first show that if \(j\) is a positive integer, then neither \(j(j+1)\) nor \(j(j+2)\) can be a perfect square:
We note that \(j^2\) and \((j+1)^2 = j^2+2j+1\) are consecutive perfect squares.
Since \(j\) is a positive integer then, \(j^2 = j \times j < j(j+1) < j(j+2)\).
Also, \(j(j+1) < (j+1)(j+1)=(j+1)^2\) and \(j(j+2) = j^2+2j < j^2+2j+1 = (j+1)^2\)
In other words, \(j^2 < j(j+1) < j(j+2) < (j+1)^2\).
Since \(j(j+1)\) and \(j(j+2)\) are between two consecutive perfect squares, then neither \(j(j+1)\) nor \(j(j+2)\) can be a perfect square.
To prove that the Murray number of \(n\) is greater than or equal to \(n+3\), we prove that the Murray number of \(n\) cannot be less than \(n+3\).
Since the Murray number of \(n\) is greater than \(n\), then the only possibilities less than \(n+3\) are \(n+1\) and \(n+2\).
Case 1: Can the Murray number of \(n\) be \(n+1\)?
If this were the case, then there would exist one or more distinct integers greater than \(n\) and less than or equal to \(n+1\) whose product times \(n\) is a perfect square.
Since \(n+1\) is the only integer that satisfies these restrictions, then for \(n+1\) to be the Murray number of \(n\), it must be the case that \(n(n+1)\) is a perfect square.
Applying the fact above with \(j=n\) tells us that this cannot be true, and so \(n+1\) cannot be the Murray number of \(n\).
Case 2: Can the Murray number of \(n\) be \(n+2\)?
If this were the case, then there would exist one or more distinct integers greater than \(n\) and less than or equal to \(n+2\) whose product times \(n\) is a perfect square.
Since \(n+1\) and \(n+2\) are the only integers that satisfy these restrictions, then for \(n+2\) to be the Murray number of \(n\), it must be the case that \(n(n+2)\) is a perfect square or \(n(n+1)(n+2)\) is a perfect square. (The product must include itself \(n+2\) otherwise the Murray number would be less than \(n+2\). Also, the product either includes \(n+1\) or it does not.)
Applying the fact above with \(j=n\) shows us that \(n(n+2)\) cannot be a perfect square.
To conclude our argument, we must show that \(n(n+1)(n+2)\) cannot be a perfect square.
Suppose that \(n(n+1)(n+2)\) is a perfect square. (We will show that this cannot be true.)
If \(n\) is itself a perfect square, then \(\dfrac{n(n+1)(n+2)}{n} = (n+1)(n+2)\) is also a perfect square. But this cannot be true, which we see by applying the fact above with \(j=n+1\).
Thus, \(n\) cannot itself be a perfect square in this case.
This means that there is a prime number \(p\) which divides \(n\) an odd number of times. (This is true because an integer larger than 1 is a perfect square exactly when every prime factor is included an even number of times.)
Since \(n(n+1)(n+2)\) is a perfect square, then \(p\) divides into \(n(n+1)(n+2)\) an even number of times, and so \(p\) divides into \(n+1\) or into \(n+2\).
If \(n+1\) and \(n\) are both multiples of \(p\), then their difference is a multiple of \(p\). In other words, \(1\) is a multiple of \(p\), which is not possible.
Thus, \(n+2\) is a multiple of \(p\). But again, \(p\) must divide into the difference between \(n+2\) and \(n\), which is 2. In other words, we must have \(p=2\).
This means that \(p=2\) is the only prime number that divides into each of \(n\) and \(n+2\) an odd number of times, and so each of \(n\) and \(n+2\) equals 2 times a perfect square.
Thus, \(n=2b^2\) and \(n+2=2c^2\) for some positive integers \(b\) and \(c\) with \(b<c\).
In this case, \(2 = (n+2)-n = 2c^2 - 2b^2\), and so \(1 = c^2 - b^2 = (c+b)(c-b)\).
Since \(c\) and \(b\) are positive integers with \(c>b\) and \((c+b)(c-b)=1\), then \(c+b=c-b=1\), which gives \(c=1\) and \(b=0\), which is a contradiction.
Finally, this means that \(n(n+1)(n+2)\) cannot be a perfect square, and so \(n+2\) is not the Murray number of \(n\).
Therefore, the Murray number of \(n\) exists and cannot be \(n+1\) or \(n+2\), and so must be greater than or equal to \(n+3\).