2023 Euclid Contest
Solutions
(Grade 12)
Tuesday, April 4, 2023
(in North America and South America)
Wednesday, April 5, 2023
(outside of North American and South America)
Tuesday, April 4, 2023
(in North America and South America)
Wednesday, April 5, 2023
(outside of North American and South America)
©2023 University of Waterloo
Since the average of the 5 numbers \(n\), \(2n\), \(3n\), \(4n\), and \(5n\) is 18, we obtain the equation \(\dfrac{n+2n+3n+4n+5n}{5} = 18\).
Therefore, \(\dfrac{15n}{5} = 18\) and
so \(3n = 18\) or \(n = 6\).
Solution 1
Adding the equations \(2x + y = 5\)
and \(x + 2y = 7\), we obtain \((2x+y)+(x+2y)=5+7\) and so \(3x + 3y=12\).
Therefore, the average of \(x\) and
\(y\) is \(\dfrac{x+y}{2} = \dfrac{3x+3y}{6} = \dfrac{12}{6}
= 2\).
Solution 2
Since \(2x + y = 5\), then \(4x + 2y = 10\).
Subtracting the second equation, we obtain \((4x+2y)-(x+2y) = 10-7\) which gives \(3x = 3\) and so \(x = 1\).
Thus, \(y = 5-2x =3\).
The average of \(x\) and \(y\) is thus \(\dfrac{1+3}{2} = 2\).
Since the average of the three numbers \(t^2\), \(2t\) and \(3\) is 9, then \(\dfrac{t^2 + 2t + 3}{3} = 9\).
Therefore, \(t^2 + 2t + 3 = 27\) and so
\(t^2 + 2t - 24 = 0\) which gives \((t + 6)(t - 4) = 0\).
Since \(t<0\), then \(t = -6\).
Since \(Q(5,3)\) is the midpoint
of \(P(1,p)\) and \(R(r,5)\), then \(\dfrac{1+r}{2} = 5\) and \(\dfrac{p + 5}{2} = 3\).
Thus, \(1+r = 10\) which gives \(r = 9\), and \(p
+ 5 = 6\) which gives \(p =
1\).
Therefore, \(p=1\) and \(r=9\).
Solution 1
The point with coordinates \(P(3,6)\) is 6 units above the \(x\)-axis.
A line with slope 3 moves 2 units to the right as it moves 6 units up.
Therefore, to move from \(P(3,6)\) to
the \(x\)-axis along a line with slope
3 results in a move of 6 units down and \(2\) units left. Thus, its \(x\)-intercept is \(3 - 2=1\).
A line with slope \(-1\) moves 6 units
to the left as it moves 6 units up. Therefore, to move from \(P(3,6)\) to the \(x\)-axis along a line with slope \(-1\) results in a move of 6 units down and
6 units right. Thus, its \(x\)-intercept is \(3+6=9\).
The distance between these \(x\)-intercepts is \(9 - 1 = 8\).
Solution 2
The line with slope \(3\) that
passes through \(P(3,6)\) has equation
\(y - 6 = 3(x - 3)\) or \(y = 3x - 3\).
The \(x\)-intercept of this line has
\(y = 0\) and so \(0 = 3x - 3\) or \(3x = 3\), which gives \(x = 1\).
The line with slope \(-1\) that passes
through \(P(3,6)\) has equation \(y - 6 = (-1)(x - 3)\) or \(y = -x + 9\).
The \(x\)-intercept of this line has
\(y = 0\) and so \(0 = -x + 9\) or \(x = 9\).
The distance between these \(x\)-intercepts is \(9 - 1 = 8\).
The line with equation \(y = 2x +
7\) has slope 2.
The line with equation \(y = tx + t\)
has slope \(t\).
Since these lines are perpendicular, the product of their slopes is
\(-1\) and so \(2t = -1\) which gives \(t = -\frac{1}{2}\).
We now need to find the point of intersection of the lines with
equations \(y = 2x + 7\) and \(y = -\frac{1}{2}x - \frac{1}{2}\).
Equating expressions for \(y\), we
obtain \(2x + 7 = -\frac{1}{2}x -
\frac{1}{2}\) or \(\frac{5}{2}x =
-\frac{15}{2}\), which gives \(x =
-3\).
Therefore, \(y = 2x + 7 = 2(-3) + 7 =
1\), and so the point of intersection of these lines is \((-3, 1)\).
Since \(64 = 2^6\), its positive
divisors are 1, 2, 4, 8, 16, 32, and 64.
The sum of these divisors is \(1 + 2 + 4 + 8 +
16 + 32 + 64 = 127\).
Suppose that the four consecutive integers that Fionn originally
wrote on the blackboard were \(x\),
\(x+1\), \(x+2\), and \(x+3\).
When Lexi erases one of these integers, the sum of the remaining three
integers is equal to one of the following: \[\begin{align*}
(x+1) + (x+2) + (x+3) & = 3x + 6 \\
x + (x+2) + (x+3) & = 3x + 5 \\
x + (x+1) + (x+3) & = 3x + 4 \\
x + (x+1) + (x+2) & = 3x + 3\end{align*}\] We are told that
the sum of these integers is 847.
We note that \(847 = 3 \cdot 282 + 1\),
which is one more than a multiple of 3. Since \(3x+3\) and \(3x+6\) are always multiples of 3 and \(3x+5\) is 2 more than a multiple of 3, then
we must have \(3x + 4 = 847\) and so
\(3x = 843\) or \(x = 281\). (Alternatively, we could have
set each of the four sums above equal to 847 to determine in which case
or cases we obtained an integer solution for \(x\).)
Therefore, the original integers were 281, 282, 283, 284 and Lexi erased
\(x + 2 = 283\).
From the given information, the 7 terms in the
arithmetic sequence are \[d^2,~~d^2 + d,~~d^2
+ 2d,~~d^2 + 3d,~~d^2 + 4d,~~d^2 + 5d,~~d^2 + 6d\] Since the sum
of these 7 terms is 756, we obtain the following equivalent equations:
\[\begin{align*}
d^2 + (d^2 + d) + (d^2 + 2d) + (d^2 + 3d) + (d^2 + 4d) + (d^2 + 5d) +
(d^2 + 6d) & = 756 \\
7d^2 + 21d & = 756 \\
d^2 + 3d & = 108 \\
d^2 + 3d - 108 & = 0 \\
(d + 12)(d - 9) & = 0\end{align*}\] and so \(d = -12\) or \(d
= 9\).
The corresponding arithmetic sequences are \[144, 132, 120, 108, 96, 84, 72 ~~\text{ and } ~~
81, 90, 99, 108, 117, 126, 135\]
In 1 hour, Liang paints \(\frac{1}{3}\) of the room.
Thus, in 2 hours, Liang paints \(\frac{2}{3}\) of the room.
Edmundo needs to paint \(1 - \frac{2}{3} = \frac{1}{3}\) of the room.
In 1 hour, Edmundo paints \(\frac{1}{4}\) of the room.
Since \(\frac{1}{4} = \frac{3}{12}\) and \(\frac{1}{3} = \frac{4}{12}\), this means that Edmundo paints for \(\frac{1}{3} \div \frac{1}{4} = \frac{4}{12} \div \frac{3}{12} = \frac{4}{3}\) of an hour.
Therefore, Edmundo paints for 80 minutes.
When converted to a fraction, \(A\%\) is equal to \(\dfrac{A}{100}\).
When an amount is increased by \(A\%\), we can find its new value by multiplying by \(1 + \dfrac{A}{100}\).
When an amount is decreased by \(A\%\), we can find its new value by multiplying by \(1 - \dfrac{A}{100}\).
When $400 is increased by \(A\%\),
the amount becomes \(\$400\left(1 +
\dfrac{A}{100}\right)\).
When this value is decreased by \(A\%\), the amount becomes \(\$400\left(1 + \dfrac{A}{100}\right)\left(1 -
\dfrac{A}{100}\right)\).
Therefore, \[\begin{align*}
\$400\left(1 + \dfrac{A}{100}\right)\left(1 - \dfrac{A}{100}\right)
& = \$391 \\
\left(1 + \dfrac{A}{100}\right)\left(1 - \dfrac{A}{100}\right) & =
\dfrac{391}{400} \\
1 - \dfrac{A^2}{100^2} & = 1 - \dfrac{9}{400} \\
\dfrac{A^2}{100^2} & = \dfrac{9}{400} \\
\dfrac{A^2}{100^2} & = \dfrac{3^2}{20^2} \\
\dfrac{A}{100} & = \dfrac{3}{20} ~~ \text{(since $A > 0$)} \\
A & = 100 \cdot \dfrac{3}{20} = 15\end{align*}\] Therefore,
\(A = 15\).
The quadratic function \(f(x) = x^2 +
(2n-1)x + (n^2 - 22)\) has no real roots exactly when its
discriminant, \(\Delta\), is
negative.
The discriminant of this function is \[\begin{align*}
\Delta & = (2n-1)^2 - 4(1)(n^2 - 22) \\
& = (4n^2 - 4n + 1) - (4n^2 - 88) \\
& = -4n + 89\end{align*}\] We have \(\Delta < 0\) exactly when \(-4n + 89 < 0\) or \(4n > 89\).
This final inequality is equivalent to \(n
> \frac{89}{4} = 22\frac{1}{4}\).
Therefore, the smallest positive integer that satisfies this inequality,
and hence for which \(f(x)\) has no
real roots, is \(n = 23\).
Using the cosine law in \(\triangle
PQR\), \[\begin{align*}
PR^2 & = PQ^2 + QR^2 - 2 \cdot PQ \cdot QR \cdot \cos(\angle PQR) \\
21^2 & = a^2 + b^2 - 2ab\cos(60^\circ) \\
441 & = a^2 + b^2 - 2ab\cdot \tfrac{1}{2} \\
441 & = a^2 + b^2 - ab\end{align*}\] Using the sine law in
\(\triangle STU\), we obtain \(\dfrac{ST}{\sin(\angle TUS)} =
\dfrac{TU}{\sin(\angle TSU)}\) and so \(\dfrac{a}{4/5} =
\dfrac{b}{\sin(30^\circ)}\).
Therefore, \(\dfrac{a}{4/5} =
\dfrac{b}{1/2}\) and so \(a =
\tfrac{4}{5} \cdot 2b = \tfrac{8}{5}b\).
Substituting into the previous equation, \[\begin{align*}
441 & = \left(\tfrac{8}{5}b\right)^2 + b^2 -
\left(\tfrac{8}{5}b\right)b \\
441 & = \tfrac{64}{25}b^2 + b^2 - \tfrac{8}{5}b^2 \\
441 & = \tfrac{64}{25}b^2 + \tfrac{25}{25}b^2 - \tfrac{40}{25}b^2 \\
441 & = \tfrac{49}{25}b^2 \\
225 & = b^2\end{align*}\] Since \(b > 0\), then \(b = 15\) and so \(a = \tfrac{8}{5}b = \tfrac{8}{5} \cdot 15 =
24\).
Solution 1
We make two copies of the given triangle, labelling them \(\triangle ABC\) and \(\triangle DEF\), as shown:
The combined area of these two triangles is \(2 \cdot 770\text{ cm}^2 = 1540\text{
cm}^2\), and the shaded area in each triangle is the same.
Next, we rotate \(\triangle DEF\) by
\(180^\circ\):
and join the two triangles together:
We note that \(BC\) and \(AE\) (which was \(FE\)) are equal in length (since they were
copies of each other) and parallel (since they are \(180^\circ\) rotations of each other). The
same is true for \(AB\) and \(EC\).
Therefore, \(ABCE\) is a
parallelogram.
Further, \(ABCE\) is divided into 11
identical parallelograms (6 shaded and 5 unshaded) by the horizontal
lines. (Since the sections of the two triangles are equal in height, the
horizontal lines on both sides of \(AC\) align.)
The total area of parallelogram \(ABCE\) is \(1540\text{ cm}^2\).
Thus, the shaded area of \(ABCE\) is
\(\frac{6}{11} \cdot 1540\text{ cm}^2 =
840\text{ cm}^2\).
Since this shaded area is equally divided between the two halves of the
parallelogram, then the combined area of the shaded regions of \(\triangle ABC\) is \(\frac{1}{2} \cdot 840\text{ cm}^2 = 420\text{
cm}^2\).
Solution 2
We label the points where the horizontal lines touch \(AB\) and \(AC\) as shown:
We use the notation \(|\triangle
ABC|\) to represent the area of \(\triangle ABC\) and use similar notation
for the area of other triangles and quadrilaterals.
Let \(\mathcal{A}\) be equal to the
total area of the shaded regions.
Thus, \[\mathcal{A} = |\triangle AB_1C_1| +
|B_2B_3C_3C_2| + |B_4B_5C_5C_4| + |B_6B_7C_7C_6| + |B_8B_9C_9C_8| +
|B_{10}BCC_{10}|\] The area of each of these quadrilaterals is
equal to the difference of the area of two triangles. For example, \[|B_2B_3C_3C_2| = |\triangle AB_3C_3| - |\triangle
AB_2C_2| = - |\triangle AB_2C_2| + |\triangle AB_3C_3|\]
Therefore, \[\begin{align*}
\mathcal{A}
& = |\triangle AB_1C_1| - |\triangle AB_2C_2| + |\triangle AB_3C_3|
- |\triangle AB_4C_4| + |\triangle AB_5C_5| \\
&
- |\triangle AB_6C_6| + |\triangle AB_7C_7|- |\triangle AB_8C_8| +
|\triangle AB_9C_9| - |\triangle AB_{10}C_{10}| + |\triangle
ABC|\end{align*}\] Each of \(\triangle
AB_1C_1\), \(\triangle
AB_2C_2\), \(\ldots\), \(\triangle AB_{10}C_{10}\) is similar to
\(\triangle ABC\) because their two
base angles are equal due.
Suppose that the height of \(\triangle
ABC\) from \(A\) to \(BC\) is \(h\).
Since the height of each of the 11 regions is equal in height, then the
height of \(\triangle AB_1C_1\) is
\(\frac{1}{11}h\), the height of \(\triangle AB_2C_2\) is \(\frac{2}{11}h\), and so on.
When two triangles are similar, their heights are in the same ratio as
their side lengths:
To see this, suppose that \(\triangle PQR\) is similar to \(\triangle STU\) and that altitudes are drawn from \(P\) and \(S\) to \(V\) and \(W\).
Since \(\angle PQR = \angle STU\), then \(\triangle PQV\) is similar to \(\triangle STW\) (equal angle; right angle), which means that \(\dfrac{PQ}{ST} = \dfrac{PV}{SW}\). In other words, the ratio of sides is equal to the ratio of heights.
Since the height of \(\triangle AB_1C_1\) is \(\frac{1}{11}h\), then \(B_1C_1 = \frac{1}{11}BC\).
Therefore, \(|\triangle AB_1C_1| = \frac{1}{2} \cdot B_1C_1 \cdot \frac{1}{11}h = \frac{1}{2} \cdot \frac{1}{11}BC \cdot \frac{1}{11}h = \frac{1^2}{11^2} \cdot \frac{1}{2} \cdot BC \cdot h = \frac{1^2}{11^2} |\triangle ABC|\).
Similarly, since the height of \(\triangle AB_2C_2\) is \(\frac{2}{11}h\), then \(B_2C_2 = \frac{2}{11}BC\).
Therefore, \(|\triangle AB_2C_2| = \frac{1}{2} \cdot B_2C_2 \cdot \frac{2}{11}h = \frac{1}{2} \cdot \frac{2}{11}BC \cdot \frac{2}{11}h = \frac{2^2}{11^2} \cdot \frac{1}{2} \cdot BC \cdot h = \frac{2^2}{11^2} |\triangle ABC|\).
This result continues for each of the triangles.
Therefore, \[\begin{align*}
\mathcal{A}
& = \tfrac{1^2}{11^2}|\triangle ABC| - \tfrac{2^2}{11^2}|\triangle
ABC| + \tfrac{3^2}{11^2}|\triangle ABC| - \tfrac{4^2}{11^2}|\triangle
ABC| + \tfrac{5^2}{11^2}|\triangle ABC| \\
&
- \tfrac{6^2}{11^2}|\triangle ABC| + \tfrac{7^2}{11^2}|\triangle ABC| -
\tfrac{8^2}{11^2}|\triangle ABC| + \tfrac{9^2}{11^2}|\triangle ABC| -
\tfrac{10^2}{11^2}|\triangle ABC| + \tfrac{11^2}{11^2}|\triangle ABC|\\
& = \tfrac{1}{11^2}|\triangle ABC| (11^2 - 10^2 + 9^2 - 8^2 + 7^2 -
6^2 + 5^2 - 4^2 + 3^2 - 2^2 + 1) \\
& = \tfrac{1}{11^2}(770\text{ cm}^2) ((11+10)(11-10) + (9+8)(9-8) +
\cdots + (3+2)(3-2) + 1) \\
& = \tfrac{1}{11^2}(770\text{ cm}^2) (11+10+9+8+7+6+5+4+3+2+1) \\
& = \tfrac{1}{11}(70\text{ cm}^2) \cdot 66 \\
& = 420\text{ cm}^2\end{align*}\] Therefore, the combined
area of the shaded regions of \(\triangle
ABC\) is \(420\text{
cm}^2\).
Solution 1
We label five additional points in the diagram:
Since \(PQ=QR=RS=1\), then \(PS = 3\) and \(PR
= 2\).
Since \(\angle PST = 90^\circ\), then
\(PT = \sqrt{PS^2 + ST^2} = \sqrt{3^2 + 1^2} =
\sqrt{10}\) by the Pythagorean Theorem.
We are told that \(ABCD\) is a
square.
Thus, \(PT\) is perpendicular to \(QC\) and to \(RB\).
Thus, \(\triangle PDQ\) is right-angled
at \(D\) and \(\triangle PAR\) is right-angled at \(A\).
Since \(\triangle PDQ\), \(\triangle PAR\) and \(\triangle PST\) are all right-angled and
all share an angle at \(P\), then these
three triangles are similar.
This tells us that \(\dfrac{PA}{PS} =
\dfrac{PR}{PT}\) and so \(PA = \dfrac{3
\cdot 2}{\sqrt{10}}\). Also, \(\dfrac{PD}{PS} = \dfrac{PQ}{PT}\) and so
\(PD = \dfrac{1 \cdot
3}{\sqrt{10}}\).
Therefore, \[DA = PA - PD =
\dfrac{6}{\sqrt{10}} - \dfrac{3}{\sqrt{10}} =
\dfrac{3}{\sqrt{10}}\] This means that the area of square \(ABCD\) is equal to \(DA^2 = \left(\dfrac{3}{\sqrt{10}}\right)^2 =
\dfrac{9}{10}\).
Solution 2
We add coordinates to the diagram as shown:
We determine the side length of square \(ABCD\) by determining the coordinates of \(D\) and \(A\) and then calculating the distance between these points.
The slope of the line through \((0,3)\) and \((3,2)\) is \(\dfrac{3-2}{0-3} = -\dfrac{1}{3}\).
This equation of this line can be written as \(y = -\dfrac{1}{3}x + 3\).
The slope of the line through \((0,0)\)
and \((1,3)\) is 3.
The equation of this line can be written as \(y = 3x\).
The slope of the line through \((1,0)\)
and \((2,3)\) is also 3.
The equation of this line can be written as \(y = 3(x-1) = 3x - 3\).
Point \(D\) is the intersection point
of the lines with equations \(y =
-\dfrac{1}{3}x + 3\) and \(y =
3x\).
Equating expressions for \(y\), we obtain \(-\dfrac{1}{3}x + 3 = 3x\) and so \(\dfrac{10}{3}x = 3\) which gives \(x = \dfrac{9}{10}\).
Since \(y = 3x\), we get \(y = \dfrac{27}{10}\) and so the coordinates
of \(D\) are \(\left(\dfrac{9}{10},
\dfrac{27}{10}\right)\).
Point \(A\) is the intersection point
of the lines with equations \(y =
-\dfrac{1}{3}x + 3\) and \(y = 3x -
3\).
Equating expressions for \(y\), we obtain \(-\dfrac{1}{3}x + 3 = 3x - 3\) and so \(\dfrac{10}{3}x = 6\) which gives \(x = \dfrac{18}{10}\).
Since \(y = 3x - 3\), we get \(y = \dfrac{24}{10}\) and so the coordinates
of \(A\) are \(\left(\dfrac{18}{10},
\dfrac{24}{10}\right)\). (It is easier to not reduce these
fractions.)
Therefore, \[DA = \sqrt{\left(\dfrac{9}{10} -
\dfrac{18}{10}\right)^2 + \left(\dfrac{27}{10} -
\dfrac{24}{10}\right)^2}
= \sqrt{\left(-\dfrac{9}{10}\right)^2 + \left(\dfrac{3}{10}\right)^2} =
\sqrt{\dfrac{90}{100}} = \sqrt{\dfrac{9}{10}}\] This means that
the area of square \(ABCD\) is equal to
\(DA^2 = \left(\sqrt{\dfrac{9}{10}}\right)^2 =
\dfrac{9}{10}\).
Each possible order in which Akshan removes the marbles
corresponds to a sequence of 9 colours, 3 of which are red and 6 of
which are blue.
We write these as sequences of 3 R’s and 6 B’s.
Since are told that the first marble is red and the third is blue, we
would like to consider all sequences of the form \[R~\underline{\hspace{7mm}}~B~\underline{\hspace{7mm}}~\underline{\hspace{7mm}}~\underline{\hspace{7mm}}~\underline{\hspace{7mm}}~\underline{\hspace{7mm}}~\underline{\hspace{7mm}}\]
The 7 blanks must be filled with the remaining 2 R’s and 5 B’s.
There are \(\displaystyle\binom{7}{2} =
\dfrac{7 \cdot 6}{2} = 21\) ways of doing this, because 2 of the
7 blanks must be chosen in which to place the R’s. (We could count these
21 ways directly by working systematically through the possible pairs of
blanks.)
Of these 21 ways, some have the last two marbles being blue.
These correspond to the sequences of the form \[R~\underline{\hspace{7mm}}~B~\underline{\hspace{7mm}}~\underline{\hspace{7mm}}~\underline{\hspace{7mm}}~\underline{\hspace{7mm}}~B~B\]
In these sequences, the 5 blanks must be filled with the remaining 2 R’s
and 3 B’s.
There are \(\displaystyle\binom{5}{2} =
\dfrac{5 \cdot 4}{2} = 10\) ways of doing this, because 2 of the
5 blanks must be chosen in which to place the R’s.
Therefore, 10 of the 21 possible sequences end in two B’s, and so the
probability that the last two marbles removed are blue is \(\dfrac{10}{21}\).
Factoring the first equation, we obtain \[ac + ad + bc + bd = a(c+d) + b(c+d) =
(a+b)(c+d)\] We now have the equations \[\begin{align*}
(a+b)(c+d) & = 2023 \\
(a+b) + (c+d) & = 296\end{align*}\] If we let \(s = a+b\) and \(t
= c+d\), we obtain the equations \[\begin{align*}
st & = 2023 \\
s + t & = 296\end{align*}\] Noting that \(s\) and \(t\) are integers since \(a\), \(b\), \(c\), and \(d\) are integers, we look for divisor pairs
of 2023 whose sum is 296.
To find the divisors of 2023, we first find its prime factorization:
\[2023 = 7 \cdot 289 = 7 \cdot 17^2\]
Therefore, the divisors of 2023 are 1, 7, 17, 119, 289, 2023.
This means that the divisor pairs of 2023 are \[2023 = 1 \cdot 2023 = 7 \cdot 289 = 17 \cdot
119\] The one divisor pair with a sum of 296 is 7 and 289.
(Alternatively, we could have found these by substituting \(t = 206 - s\) into \(st = 2023\) and using the quadratic
formula.)
Since \(a< b< c< d\), then
\(a+b < c+d\) and so \(s = a+b = 7\) and \(t = c+d = 289\).
Since \(a\) and \(b\) are positive integers with \(a<b\) and \(a+b=7\), then the possible pairs \((a,b)\) are \[(a,b) = (1,6), (2,5), (3,4)\] We know that
\(c\) and \(d\) are positive integers with \(c<d\) and \(c+d=289\), but also with \(b<c<d\).
When \((a,b) = (1,6)\), this means that
the possibilities are \[(c,d) = (7,282),
(8,281), (9,280), \ldots, (143,146), (144,145)\] There are \(144 - 7 + 1 = 138\) such pairs.
When \((a,b) = (2,5)\), the
possibilities are \[(c,d) = (6,283), (7,282),
(8,281), (9,280), \ldots, (143,146), (144,145)\] There are \(138 + 1 = 139\) such pairs.
When \((a,b) = (3,4)\), the
possibilities are \[(c,d) = (5,284), (6,283),
(7,282), (8,281), (9,280), \ldots, (143,146), (144,145)\] There
are \(139 + 1 = 140\) such pairs.
In total, there are \(138 + 139 + 140 =
417\) possible quadruples \((a,b,c,d)\).
Since \(\triangle ABC\) is
right-angled at \(B\), then \[\begin{align*}
BC^2 & = AC^2 - AB^2 \\
& = \left((n+1)(n+4)\right)^2 - \left(n(n+1)\right)^2 \\
& = (n+1)^2 (n+4)^2 - n^2 (n+1)^2 \\
& = (n+1)^2 \left( (n+4)^2 - n^2 \right) \\
& = (n+1)^2 \left( n^2 + 8n + 16 - n^2 \right) \\
& = (n+1)^2 (8n + 16) \\
& = 4(n+1)^2 (2n+4)\end{align*}\] The length of \(BC\) is an integer exactly when \(4(n+1)^2 (2n+4)\) is a perfect
square.
Since \(4(n+1)^2\) is a perfect square,
then \(BC\) is an integer exactly when
\(2n+4\) is a perfect square.
We note that \(2n + 4 \geq 6\) (since
\(n \geq 1\)) and that \(2n+4\) is even.
Since \(n < 100\,000\), then \(6 \leq 2n+4 < 200\,004\), and so we need
to count the number of even perfect squares between 6 and 200 004.
The smallest even perfect square in this range is \(4^2 = 16\).
Since \(\sqrt{200\,004} \approx
447.2\), the largest even perfect square in this range is \(446^2\).
Therefore, the number of even perfect squares in this range is \(\dfrac{446}{2} - 1 = 222\).
Thus, there are 222 positive integers \(n\) for which the length of \(BC\) is an integer.
Let \(f(x) = \sqrt{\log_2 x \cdot
\log_2 (4x) + 1} +
\sqrt{\log_2 x \cdot \log_2\left(\dfrac{x}{64}\right) +
9}\).
Using logarithm laws, \[\begin{align*}
\log_2 x \cdot \log_2 (4x) + 1
& = \log_2 x (\log_2 4 + \log_2 x) + 1\\
& = \log_2 x (2 + \log_2 x) + 1 ~~ \text{(since $2^2 = 4$)}\\
& = (\log_2 x)^2 + 2 \cdot \log_2 x + 1 \\
& = (\log_2 x + 1)^2\end{align*}\] and \[\begin{align*}
\log_2 x \cdot \log_2\left(\dfrac{x}{64}\right) + 9
& = \log_2 x (\log_2 x - \log_2 64) + 9 \\
& = \log_2 x (\log_2 x - 6) + 9 ~~ \text{(since $2^6 = 64$)}\\
& = (\log_2 x)^2 - 6\log_2 x + 9 \\
& = (\log_2 x - 3)^2 \end{align*}\] Therefore, \[f(x) = \sqrt{\log_2 x \cdot \log_2 (4x) + 1} +
\sqrt{\log_2 x \cdot \log_2\left(\dfrac{x}{64}\right) + 9}
= \sqrt{(\log_2 x + 1)^2} + \sqrt{(\log_2 x - 3)^2 }\] Before
proceeding, we recall that if \(a \leq
0\), then \(\sqrt{a^2} = -a\)
and if \(a > 0\), then \(\sqrt{a^2} = a\).
When \(\log_2 x \leq -1\), we know that
\(\log_2 x + 1 \leq 0\) and \(\log_2 x - 3 < 0\), and so \[f(x) = -(\log_2 x + 1) -(\log_2 x - 3) = 2 -
2\log_2 x\] When \(-1 < \log_2 x
\leq 3\), we know that \(\log_2 x + 1
> 0\) and \(\log_2 x - 3 \leq
0\), and so \[f(x) = (\log_2 x + 1)
-(\log_2 x - 3) = 4\] When \(\log_2 x
> 3\), we know that \(\log_2 x + 1
\geq 0\) and \(\log_2 x - 3 >
0\), and so \[f(x) = (\log_2 x + 1) +
(\log_2 x - 3) = 2\log_2 x - 2\] We want to find all values of
\(x\) for which \(f(x) = 4\).
When \(\log_2 x \leq -1\), \(f(x) = 2 - 2\log_2 x = 4\) exactly when
\(\log_2 x = -1\).
When \(-1< \log_2 x \leq 3\), \(f(x)\) is always equal to \(4\).
When \(\log_2 x > 3\), \(f(x) = 2\log_2 x - 2 = 4\) exactly when
\(\log_2 x = 3\).
Therefore, \(f(x) = 4\) exactly when
\(-1 \leq \log_2 x \leq 3\), which is
true exactly when \(\frac{1}{2} \leq x \leq
8\).
(It seems surprising that the solution to this equation is actually an
interval of values, rather than a finite number of specific
values.)
If there are 5 or more people seated around a table with 8
chairs, then there are at most 3 empty chairs. But there must be an
empty chair between each pair of people, and this is not possible with 5
people and 3 empty chairs.
Therefore, there are at most 4 people seated.
If there were only 2 people seated, then there would be 6 empty chairs
which would mean that at least one of the two “gaps” around the circular
table had at least 3 empty chairs, and so another person could be
seated, meaning that the table wasn’t full.
Therefore, there are at least 3 people seated.
This means that a full table with 8 chairs has either 3 or 4
people.
If there are 4 people, there are 4 empty chairs, and so there is exactly
1 empty chair between each pair of people.
Thus, people are seated in chairs \(\{1,3,5,7\}\) or in chairs \(\{2,4,6,8\}\).
If there are 3 people, there are 5 empty chairs.
With 3 people, there are 3 gaps totalling 5 chairs, and each gap has at
most 2 chairs in it.
Therefore, the gaps must be 1, 2, 2 in some order. This is the only list
of three positive integers, each equal to 1 or 2, that adds to 5.
The gap of 1 can be between any pair of seats. In other words, the gap
of 1 could be between \(\{1,3\}\),
\(\{2,4\}\), and so on. In each case,
the position of the third person is completely determined because the
remaining two gaps have 2 chairs each.
Thus, with 3 people, they are seated in chairs \[\{1,3,6\}, \{2,4,7\}, \{3,5,8\}, \{4,6,1\},
\{5,7,2\}, \{6,8,3\}, \{7,1,4\}, \{8,2,5\}\] In total, there are
thus 10 ways to seat people at a table with 8 chairs: \[\{1,3,5,7\}, \{2,4,6,8\}, \{1,3,6\}, \{2,4,7\},
\{3,5,8\}, \{4,6,1\}, \{5,7,2\}, \{6,8,3\}, \{7,1,4\},
\{8,2,5\}\]
Suppose that \(k\) is a positive
integer.
Suppose that \(t\) people are seated at
a table with \(6k+5\) chairs so that
the table is full.
When \(t\) people are seated, there are
\(t\) gaps. Each gap consists of either
1 or 2 chairs. (A gap with 3 or more chairs can have an additional
person seated in it, so the table is not full.)
Therefore, there are between \(t\) and
\(2t\) empty chairs.
This means that the total number of chairs is between \(t + t\) and \(t +
2t\).
In other words, \(2t \leq 6k + 5 \leq
3t\).
Since \(2t \leq 6k + 5\), then \(t \leq 3k + \frac{5}{2}\). Since \(k\) and \(t\) are integers, then \(t \leq 3k + 2\).
We note that it is possible to seat \(3k+2\) people around the table in seats
\[\{2, 4, 6, \ldots, 6k+2, 6k+4\}\]
This table is full because \(3k+1\) of
the gaps consist of 1 chair and 1 gap consists of 2 chairs.
Since \(3t \geq 6k + 5\), then \(t \geq 2k + \frac{5}{3}\). Since \(k\) and \(t\) are integers, then \(t \geq 2k + 2\).
We note that it is possible to seat \(2k+2\) people around the table in seats
\[\{3, 6, 9, \ldots, 6k, 6k+3,
6k+5\}\] This table is full because \(2k+1\) of the gaps consist of 2 chairs and
1 gap consists of 1 chair.
We now know that, if there are \(t\)
people seated at a full table with \(6k +
5\) chairs, then \(2k+2 \leq t \leq
3k+2\).
To confirm that every such value of \(t\) is possible, consider a table with
\(t\) people, \(3t - (6k+5)\) gaps of 1 chair, and \((6k+5) - 2t\) gaps of 2 chairs.
From the work above, we know that \(3t \geq
6k+5\) and so \(3t - (6k+5) \geq
0\), and that \(2t \leq 6k+5\)
and so \((6k+5) - 2t \geq 0\).
The total number of gaps is \(3t - (6k+5) +
(6k+5) - 2t = t\), since there are \(t\) people seated.
Finally, the total number of chairs is \[t +
1 \cdot (3t - (6k+5)) + 2 \cdot ((6k+5) - 2t) = t + 3t - 4t - (6k+5) +
2(6k+5) = 6k+5\] as expected.
This shows that every \(t\) with \(2k+2 \leq t \leq 3k+2\) can produce a full
table.
Therefore, the possible values of \(t\)
are those integers that satisfy \(2k + 2 \leq
t \leq 3k + 2\).
There are \((3k + 2) - (2k + 2) + 1 =
k+1\) possible values of \(t\).
Solution 1
For each integer \(n \geq 3\), we
define \(f(n)\) to be the number of
different full tables of size \(n\).
We can check that
\(f(3) = 3\) because the full tables when \(n = 3\) have people in chairs \(\{1\}\), \(\{2\}\), \(\{3\}\),
\(f(4) = 2\) because the full tables when \(n = 4\) have people in chairs \(\{1,3\}\), \(\{2,4\}\), and
\(f(5) = 5\) because the full tables when \(n = 4\) have people in chairs \(\{1,3\}\), \(\{2,4\}\), \(\{3,5\}\), \(\{4,1\}\), \(\{5,2\}\).
In the problem, we are told that \(f(6) =
5\) and in part (a), we determined that \(f(8) = 10\).
This gives us the following table:
| \(\boldsymbol{n}\) | \(\boldsymbol{f(n)}\) |
|---|---|
| 3 | 3 |
| 4 | 2 |
| 5 | 5 |
| 6 | 5 |
| 7 | ? |
| 8 | 10 |
Based on this information, we make the guess that for every integer
\(n \geq 6\), we have \(f(n) = f(n-2) + f(n-3)\).
For example, this would mean that \(f(7) =
f(5) + f(4) = 5 + 2 = 7\) which we can verify is true.
Based on this recurrence relation (which we have yet to prove), we
deduce the values of \(f(n)\) up to and
including \(n = 19\):
| \(\boldsymbol{n}\) | \(\boldsymbol{f(n)}\) |
|---|---|
| 3 | 3 |
| 4 | 2 |
| 5 | 5 |
| 6 | 5 |
| 7 | 7 |
| 8 | 10 |
| 9 | 12 |
| 10 | 17 |
| 11 | 22 |
| 12 | 29 |
| 13 | 39 |
| 14 | 51 |
| 15 | 68 |
| 16 | 90 |
| 17 | 119 |
| 18 | 158 |
| 19 | 209 |
We now need to prove that the equation \(f(n) = f(n-2) + f(n-3)\) is true for all \(n \geq 6\).
We think about each full table as a string of 0s and 1s, with 1
representing a chair that is occupied and 0 representing an empty
chair.
Let \(a(n)\) be the number of full
tables with someone in seat \(1\) (and
thus nobody in seat \(2\)).
Let \(b(n)\) be the number of full
tables with someone in seat \(2\) (and
thus nobody in seat \(1\)).
Let \(c(n)\) be the number of full
tables with nobody in seat 1 or in seat 2.
Since every full table must be in one of these categories, then \(f(n) = a(n) + b(n) + c(n)\).
A full table with \(n\) seats \(n \geq 4\) must correspond to a string that
starts with 10, 01 or 00.
Since there cannot be more than two consecutive 0s, we can further
specify this, namely to say that a full table with \(n\) seats must correspond to a string that
starts with 1010 or 1001 or 0100 or 0101 or 0010. In each case, these
are the first 4 characters of the string and correspond to full (1) and
empty (0) chairs.
Consider the full tables starting with 1010. Note that such strings
end with 0 since the table is circular. Removing the 10 from positions 1
and 2 creates strings of length \(n-2\)
that begin 10. These strings will still correspond to a full table, and
so there are \(a(n-2)\) such strings.
(We note that all possible strings starting 1010 of length \(n\) will lead to all possible strings
starting with 1010 of length \(n-2\).)
Consider the full tables starting with 1001. Note that such a string
ends with 0 since the table is circular. Removing the 100 from positions
1, 2 and 3 creates strings of length \(n-3\) that begin 10. (There must have been
a 0 in position 5 after the 1 in position 4.) These strings will still
correspond to full tables, and so there are \(a(n-3)\) such strings.
Consider the full tables starting with 0100. Removing the 100 from
positions 2, 3 and 4 creates strings of length \(n-3\) that begin 01. (There must have been
a 1 in position 5 after the 0 in position 4.) These strings will still
correspond to full tables, and so there are \(b(n-3)\) such strings.
Consider the full tables starting with 0101. Removing the 01 from
positions 3 and 4 creates strings of length \(n-2\) that begin 01. (The 1 in position 4
must have been followed by one or two 0s and so these strings maintains
the desired properties.) These strings will still correspond to full
tables, and so there are \(b(n-2)\)
such strings.
Consider the full tables starting with 0010. These strings must begin
with either 00100 or 00101.
If strings start 00100, then they start 001001 and so we remove the 001
in positions 4, 5 and 6 and obtain strings of length \(n-3\) that start 001 (and thus start 00).
There are \(c(n-3)\) such
strings.
If strings start 00101, we remove the 01 in positions 4 and 5 and obtain
strings of length \(n-2\) that start
001 (and thus start 00). There are \(c(n-2)\) such strings.
These 6 cases and subcases count all strings counted by \(f(n)\).
Therefore, \[\begin{align*}
f(n) & = a(n-2) + a(n-3) + b(n-3) + b(n-2) + c(n-3) + c(n-2)\\
& = a(n-2) + b(n-2) + c(n-2) + a(n-3) + b(n-3) + c(n-3)\\
& = f(n-2) + f(n-3)\end{align*}\] as required, which means
that the number of different full tables when \(n = 19\) is 209.
Solution 2
Extending our approach from (b), the number of people seated at a
full table with 19 chairs is at least \(\frac{19}{3} = 6\frac{1}{3}\) and at most
\(\frac{19}{2} = 9\frac{1}{2}\).
Since the number of people is an integer, there must be 7, 8 or 9 people
at the table, which means that the number of empty chairs is 12, 11 or
10, respectively.
Suppose that there are 9 people and 9 gaps with a total of 10 empty
chairs.
In this case, there is 1 gap with 2 empty chairs and 8 gaps with 1 empty
chair.
There are 19 pairs of chairs in which we can put 2 people with a gap of
2 in between: \(\{1,4\}\), \(\{2,5\}\), \(\ldots\), \(\{19,3\}\).
Once we choose one of these pairs, the seat choice for the remaining 8
people is completely determined by placing people in every other
chair.
Therefore, there are 19 different full tables with 9 people.
Suppose that there are 8 people and 8 gaps with a total of 11 empty
chairs.
In this case, there are 3 gaps with 2 empty chairs and 5 gaps with 1
empty chair.
There are 7 different circular orderings in which these 8 gaps can be
arranged: \[22211111, 22121111, 22112111,
22111211, 22111121, 21212111, 21211211\] We note that "22211111"
would be the same as, for example, "11222111" since these gaps are
arranged around a circle.
If the three gaps of length 2 are consecutive, there is only one
configuration (22211111).
If there are exactly 2 consecutive gaps of length 2, there are 4
relative places in which the third gap of length 2 can be placed.
If there are no consecutive gaps of length 2, these gaps can either be
separated by 1 gap each (21212111) with 3 gaps on the far side, or can
be separated by 1 gap, 2 gaps, and 2 gaps (21211211). There is only one
configuration for the gaps in this last situation.
There are 7 different circular orderings for these 8 gaps.
Each of these 7 different orderings can be placed around the circle of
19 chairs in 19 different ways, because each can be started in 19
different places. Because 19 is prime, none of these orderings
overlap.
Therefore, there are \(7 \cdot 19 =
133\) different full tables with 8 people.
Suppose that there are 7 people and 7 gaps with a total of 12 empty
chairs.
In this case, there are 2 gaps with 1 empty chair and 5 gaps with 2
empty chairs.
The 2 gaps with 1 empty chair can be separated by 0 gaps with 2 empty
chairs, 1 gap with 2 empty chairs, or 2 gaps with 2 empty chairs.
Because the chairs are around a circle, if there were 3, 4 or 5 gaps
with 2 empty chairs between them, there would be 2, 1 or 0 gaps going
the other way around the circle.
This means that there are 3 different configurations for the gaps.
Each of these configurations can be placed in 19 different ways around
the circle of chairs.
Therefore, there are \(3 \cdot 19 =
57\) full tables with 7 people.
In total, there are \(19 + 133 + 57 = 209\) full tables with 19 chairs.
Solution 3
As in Solution 2, there must be 7, 8 or 9 people in chairs, and so
there are 7, 8 or 9 gaps.
If there are 7 gaps, there are 2 gaps of 1 chair and 5 gaps of 2
chairs.
If there are 8 gaps, there are 5 gaps of 1 chair and 3 gaps of 2
chairs.
If there are 9 gaps, there are 8 gaps of 1 chair and 1 gap of 2
chairs.
We consider three mutually exclusive cases: (i) there is a person in
chair 1 and not in chair 2, (ii) there is a person in chair 2 and not in
chair 1, and (iii) there is nobody in chair 1 or in chair 2. Every full
table fits into exactly one of these three cases.
Case (i): there is a person in chair 1 and not in chair 2
We use the person in chair 1 to “anchor” the arrangement, by starting
at chair 1 and arranging the gaps (and thus the full chairs) clockwise
around the table from chair 1.
If there are 7 gaps, we need to choose 2 of them to be of length 1, and
so there are \(\displaystyle\binom{7}{2}\) ways of
arranging the gaps starting at chair 1.
If there are 8 gaps, we need to choose 3 of them to be of length 2, and
so there are \(\displaystyle\binom{8}{3}\) ways of
arranging the gaps starting at chair 1.
If there are 9 gaps, we need to choose 1 of them to be of length 2, and
so there are \(\displaystyle\binom{9}{1}\) ways of
arranging the gaps starting at chair 1.
In this case, there are a total of \(\displaystyle\binom{7}{2} + \binom{8}{3} +
\binom{9}{1} = 21 + 56 + 9 = 86\) full tables.
Case (ii): there is a person in chair 2 and not in chair 1
We use the same reasoning starting with the person in chair 2 as the
anchor.
Again, there are 86 full tables in this case.
Case (iii): there is nobody in chair 1 or chair 2
Since there is nobody in chair 1 or chair 2, there must be a person
in chair 3 and also in chair 19, which fixes one gap of 2 chairs.
Here, we use the person in chair 3 as the anchor.
If there are 7 gaps, there are 2 gaps of 1 chair and 4 gaps of 2 chairs
left to place. There are \(\displaystyle\binom{6}{2}\) ways of doing
this.
If there are 8 gaps, there are 5 gaps of 1 chair and 2 gaps of 2 chairs
left to place. There are \(\displaystyle\binom{7}{2}\) ways of doing
this.
If there are 9 gaps, there are 8 gaps of 1 chair and 0 gaps of 2 chairs
left to place. There is 1 way to do this.
In this case, there are a total of \(\displaystyle\binom{6}{2} + \binom{7}{2} + 1 = 15
+ 21 + 1 = 37\) full tables.
In total, there are \(86 + 86 + 37 =
209\) full tables with 19 chairs.
Since \(0 < \dfrac{1}{3} < \dfrac{2}{3} < 1\), then \(\left\lfloor\dfrac{1}{3}\right\rfloor = \left\lfloor\dfrac{2}{3}\right\rfloor = 0\).
Since \(1 \leq \dfrac{3}{3} < \dfrac{4}{3} < \dfrac{5}{3} < 2\), then \(\left\lfloor\dfrac{3}{3}\right\rfloor = \left\lfloor\dfrac{4}{3}\right\rfloor = \left\lfloor\dfrac{5}{3}\right\rfloor = 1\).
These fractions can continue to be grouped in groups of 3 with the
last full group of 3 satisfying \(19 \leq
\dfrac{57}{3} < \dfrac{58}{3} < \dfrac{59}{3} < 20\),
which means that \(\left\lfloor\dfrac{57}{3}\right\rfloor =
\left\lfloor\dfrac{58}{3}\right\rfloor =
\left\lfloor\dfrac{59}{3}\right\rfloor = 19\).
The last term is \(\left\lfloor\dfrac{60}{3}\right\rfloor = \lfloor
20 \rfloor = 20\).
If the given sum is \(S\), we obtain \[\begin{align*} S & = 2 \cdot 0 + 3 \cdot 1 + 3 \cdot 2 + \cdots + 3 \cdot 19 + 1 \cdot 20 \\ & = 0 + 3(1 + 2 + \cdot + 19) + 20 \\ & = 3 \cdot \tfrac{1}{2} \cdot 19 \cdot 20 + 20 \\ & = 570 + 20 \\ & = 590\end{align*}\]
For every positive integer \(m > 4\), let \[q(m) = \left\lfloor{\dfrac{1}{3}}\right\rfloor+ \left\lfloor{\dfrac{2}{3}}\right\rfloor+ \left\lfloor{\dfrac{3}{3}}\right\rfloor+\ldots+ \left\lfloor{\dfrac{m-2}{3}}\right\rfloor + \left\lfloor{\dfrac{m-1}{3}}\right\rfloor\] Extending our work from (a), we know that \(k-1 \leq \dfrac{3k-3}{3} < \dfrac{3k-2}{3} < \dfrac{3k-1}{3} < k\) for each positive integer \(k\), and so \(\left\lfloor\dfrac{3k-3}{3}\right\rfloor = \left\lfloor\dfrac{3k-2}{3}\right\rfloor = \left\lfloor\dfrac{3k-1}{3}\right\rfloor = k-1\).
Every positive integer \(m>4\)
can be written as \(m = 3s\) or \(m = 3s+1\) or \(m
= 3s+2\), for some positive integer \(s\), depending on its remainder when
divided by 3.
We can thus write \[\begin{align*}
q(3s) & = \left\lfloor{\dfrac{1}{3}}\right\rfloor+
\left\lfloor{\dfrac{2}{3}}\right\rfloor+
\left\lfloor{\dfrac{3}{3}}\right\rfloor+\ldots+
\left\lfloor{\dfrac{3s-2}{3}}\right\rfloor +
\left\lfloor{\dfrac{3s-1}{3}}\right\rfloor \\
& = 2\cdot 0 + 3(1 + 2 + 3 + \cdots + (s-1)) \\
& = 3 \cdot \dfrac{1}{2} \cdot (s-1) s \\
& = \dfrac{3s(s-1)}{2} \\
& = \dfrac{3s(3s-3)}{6}\\
& \\
q(3s+1) & = \left\lfloor{\dfrac{1}{3}}\right\rfloor+
\left\lfloor{\dfrac{2}{3}}\right\rfloor+
\left\lfloor{\dfrac{3}{3}}\right\rfloor+\ldots+
\left\lfloor{\dfrac{3s-2}{3}}\right\rfloor +
\left\lfloor{\dfrac{3s-1}{3}}\right\rfloor +
\left\lfloor{\dfrac{3s}{3}}\right\rfloor \\
& = q(3s) + s \\
& = \dfrac{3s(3s-3)}{6} + \dfrac{3s\cdot 2}{6} \\
& = \dfrac{3s(3s-1)}{6}\\
& \\
q(3s+2) & = q(3s+1) + \left\lfloor{\dfrac{3s+1}{3}}\right\rfloor \\
& = \dfrac{3s(3s-1)}{6} + s \\
& = \dfrac{3s(3s-1)}{6} + \dfrac{3s \cdot 2}{6} \\
& = \dfrac{3s(3s+1)}{6}\end{align*}\] We want to find a
polynomial \(p(x)\) for which \(q(m) = \lfloor p(m) \rfloor\) for every
positive integer \(m > 4\).
In other words, we want to find a polynomial \(p(x)\) for which \[\lfloor p(3s) \rfloor = \dfrac{3s(3s-3)}{6}
\qquad \lfloor p(3s+1) \rfloor = \dfrac{3s(3s-1)}{6} \qquad \lfloor
p(3s+2) \rfloor = \dfrac{3s(3s+1)}{6}\] for every positive
integer \(s\).
We will show that the polynomial \(p(x) =
\dfrac{(x-1)(x-2)}{6}\) satisfies the desired conditions.
If \(x = 3s+1\) for some positive
integer \(s\), then \[\dfrac{(x-1)(x-2)}{6} =
\dfrac{(3s+1-1)(3s+1-2)}{6} = \dfrac{3s(3s-1)}{6}\] We note that
\(3s\) is a multiple of 3. Since \(3s\) and \(3s-1\) are consecutive integers, then one
of these is a multiple of 2. Thus, \(3s(3s-1)\) is a multiple of 6 and so \(\dfrac{3s(3s-1)}{6}\) is an integer.
This means that \(\left\lfloor
\dfrac{3s(3s-1)}{6} \right\rfloor = \dfrac{3s(3s-1)}{6}\).
Therefore, \(q(3s+1) = \dfrac{3s(3s-1)}{6} = \left\lfloor \dfrac{3s(3s-1)}{6} \right\rfloor = \lfloor p(3s+1) \rfloor\).
If \(x = 3s+2\) for some positive
integer \(s\), then \[\dfrac{(x-1)(x-2)}{6} =
\dfrac{(3s+2-1)(3s+2-2)}{6} = \dfrac{3s(3s+1)}{6}\] We note that
\(3s\) is a multiple of 3. Since \(3s\) and \(3s+1\) are consecutive integers, then one
of these is a multiple of 2. Thus, \(3s(3s+1)\) is a multiple of 6 and so \(\dfrac{3s(3s+1)}{6}\) is an integer.
This means that \(\left\lfloor
\dfrac{3s(3s+1)}{6} \right\rfloor = \dfrac{3s(3s+1)}{6}\).
Therefore, \(q(3s+2) = \dfrac{3s(3s+1)}{6} = \left\lfloor \dfrac{3s(3s+1)}{6} \right\rfloor = \lfloor p(3s+2) \rfloor\).
If \(x = 3s\) for some positive integer \(s\), then \[\dfrac{(x-1)(x-2)}{6} = \dfrac{(3s-1)(3s-2)}{6} = \dfrac{9s^2 - 9s + 2}{6}\] Now, \(\dfrac{9s^2 - 9s}{6} = \dfrac{9s(s-1)}{6}\) is an integer because \(9s\) is a multiple of 3 and one of \(s\) and \(s-1\) is even.
Since \(\dfrac{9s^2 - 9s + 2}{6} = \dfrac{9s^2 - 9s}{6} + \dfrac{1}{3}\), then \(\dfrac{9s^2 - 9s + 2}{6}\) is \(\dfrac{1}{3}\) more than an integer which means that \(\left\lfloor \dfrac{9s^2 - 9s + 2}{6} \right\rfloor = \dfrac{9s^2 - 9s}{6} = \dfrac{3s(3s-3)}{6} = q(3s)\).
Therefore, \(q(3s) = \dfrac{3s(3s-3)}{6} = \left\lfloor \dfrac{(3s-1)(3s-2)}{6} \right\rfloor = \lfloor p(3s) \rfloor\).
This means that the polynomial \(p(x) = \dfrac{(x-1)(x-2)}{6}\) satisfies the required conditions.
Before working on the specific question we have been asked, we
simplify the given expression for \(f(n)\) by noting that if \(k \geq n\), then \(kn \leq k^2 < k^2+1\).
This means that if \(k \geq n\), we
have \(0 < \dfrac{kn}{n^2 + 1} <
1\) and so \(\left\lfloor
\dfrac{kn}{k^2+1} \right\rfloor = 0\).
This means that, for a fixed positive integer \(n\), the apparently infinite sum that
represents \(f(n)\) can be stopped when
\(k = n-1\) because every subsequent
term equals 0.
Thus, \[f(n) = \left\lfloor \frac{n}{1^2+1}
\right\rfloor
+ \left\lfloor \frac{2n}{2^2+1} \right\rfloor
+ \left\lfloor \frac{3n}{3^2+1} \right\rfloor + \cdots
+ \left\lfloor \frac{(n-2)n}{(n-2)^2+1} \right\rfloor
+ \left\lfloor \frac{(n-1)n}{(n-1)^2+1} \right\rfloor\] We note
that \[\begin{align*}
f(1) & = 0 ~~\text{(since no terms are non-zero)} \\
f(2) & = \left\lfloor \frac{1 \cdot 2}{1^2+1} \right\rfloor = 1 \\
f(3) & = \left\lfloor \frac{1 \cdot 3}{1^2+1} \right\rfloor +
\left\lfloor \frac{2 \cdot 3}{2^2+1} \right\rfloor = \left\lfloor
\frac{3}{2} \right\rfloor + \left\lfloor \frac{6}{5} \right\rfloor = 1 +
1 = 2 \\
f(4) & = \left\lfloor \frac{1 \cdot 4}{1^2+1} \right\rfloor +
\left\lfloor \frac{2 \cdot 4}{2^2+1} \right\rfloor + \left\lfloor
\frac{3 \cdot 4}{3^2+1} \right\rfloor = \left\lfloor \frac{4}{2}
\right\rfloor + \left\lfloor \frac{8}{5} \right\rfloor + \left\lfloor
\frac{12}{10} \right\rfloor = 2 + 1 + 1 = 4\end{align*}\]
Suppose that \(t\) is an odd positive
integer for which \(f(t+1) - f(t) =
2\).
We will assume that \(t\) is not a
prime number, and show that \(f(t+1) - f(t)
\neq 2\). This will show us that if \(f(t+1) - f(t) = 2\), it must be the case
that \(t\) is prime. Since \(t\) is odd and not prime, then \(t = 1\) or \(t\) is composite.
We note that when \(t = 1\), we obtain
\(f(2) - f(1) = 1 - 0 = 1 \neq
2\).
Next, suppose that \(t\) is odd and
composite.
Since \(t\) is odd and composite, then
\(t\) can be written as \(t = rs\) for some odd positive integers
\(r \geq s > 1\). (\(t\) can be written in this form in at least
one way, so we take one of these possibilities.)
In this case, consider \(f(t+1) -
f(t)\).
We can write this as \[\begin{align*}
f(t+1) - f(t) & = \phantom{-}\left\lfloor \dfrac{t+1}{1^2+1}
\right\rfloor
+ \left\lfloor \dfrac{2(t+1)}{2^2+1} \right\rfloor + \cdots +
\left\lfloor \dfrac{(t-1)(t+1)}{(t-1)^2+1} \right\rfloor
+ \left\lfloor \dfrac{t(t+1)}{t^2+1} \right\rfloor \\
& ~~~~~ - \left\lfloor \dfrac{t}{1^2+1} \right\rfloor
- \left\lfloor \dfrac{2t}{2^2+1} \right\rfloor - \cdots
- \left\lfloor \dfrac{(t-1)t}{(t-1)^2+1}
\right\rfloor\end{align*}\] We re-write this as \[\begin{align*}
f(t+1) - f(t) & =
\left(\left\lfloor\dfrac{t+1}{1^2+1}\right\rfloor -
\left\lfloor\dfrac{t}{1^2+1}\right\rfloor\right)
+ \left(\left\lfloor \dfrac{2(t+1)}{2^2+1} \right\rfloor - \left\lfloor
\dfrac{2t}{2^2+1} \right\rfloor \right)
+ \cdots \\
& ~~~~~ + \left(\left\lfloor
\dfrac{(t-1)(t+1)}{(t-1)^2+1}\right\rfloor - \left\lfloor
\dfrac{(t-1)t}{(t-1)^2+1} \right\rfloor\right) + \left\lfloor
\dfrac{t(t+1)}{t^2+1} \right\rfloor\end{align*}\] In the \(t-1\) sets of parentheses, we have terms of
the form \(\left\lfloor \dfrac{k(t+1)}{k^2+1}
\right\rfloor - \left\lfloor \dfrac{kt}{k^2+1} \right\rfloor\)
for each integer \(k\) from \(1\) to \(t-1\).
We know that \(\dfrac{k(t+1)}{k^2+1} > \dfrac{kt}{k^2+1}\) because both \(k\) and \(t\) are positive, the denominators are equal and \(k(t+1) > kt\).
Thus, \(\left\lfloor \dfrac{k(t+1)}{k^2+1}
\right\rfloor \geq \left\lfloor
\dfrac{kt}{k^2+1} \right\rfloor\). (The greatest integer less
than or equal to the first fraction must be at least as large as the
greatest integer less than or equal to the second fraction.)
This means that the \(t-1\) differences
in parentheses, each of which is an integer, is at least 0.
To show that \(f(t+1) - f(t) \neq 2\),
we show that there are at least 2 places where the difference is at
least 1, and that the final term is at least 1. This will tell us that
\(f(t+1) - f(t) \geq 3\) and so \(f(t+1) - f(t) \neq 2\), which will tell us
that \(t\) cannot be composite, and so
\(t\) must be prime, as required.
Consider \(\left\lfloor
\dfrac{t(t+1)}{t^2+1} \right\rfloor\).
Since \(t(t+1) = t^2 + t \geq t^2 +
1\), then \(\dfrac{t(t+1)}{t^2 + 1}
\geq 1\), which means that \(\left\lfloor \dfrac{t(t+1)}{t^2+1} \right\rfloor
\geq 1\).
Consider \(\left\lfloor\dfrac{t+1}{1^2+1}\right\rfloor - \left\lfloor\dfrac{t}{1^2+1}\right\rfloor = \left\lfloor\dfrac{t+1}{2}\right\rfloor - \left\lfloor\dfrac{t}{2}\right\rfloor\).
Since \(t\) is odd, then we write \(t = 2u + 1\) for some positive integer \(u\), which gives \[\left\lfloor\dfrac{t+1}{2}\right\rfloor - \left\lfloor\dfrac{t}{2}\right\rfloor = \left\lfloor\dfrac{2u+2}{2}\right\rfloor - \left\lfloor\dfrac{2u+1}{2}\right\rfloor = \lfloor u+1 \rfloor - \left\lfloor u + \dfrac{1}{2}\right\rfloor = (u+1) - u = 1\] Recall that \(t = rs\) with \(r \geq s > 1\).
Consider the term \(\left\lfloor\dfrac{r(t+1)}{r^2+1}\right\rfloor - \left\lfloor\dfrac{rt}{r^2+1}\right\rfloor\).
We have \[\left\lfloor\dfrac{r(t+1)}{r^2+1}\right\rfloor - \left\lfloor\dfrac{rt}{r^2+1}\right\rfloor = \left\lfloor\dfrac{r(rs+1)}{r^2 + 1}\right\rfloor - \left\lfloor\dfrac{r\cdot rs}{r^2+1}\right\rfloor = \left\lfloor\dfrac{r^2s+r}{r^2 + 1}\right\rfloor - \left\lfloor\dfrac{r^2s}{r^2+1}\right\rfloor\] We note that \(\dfrac{r^2s+r}{r^2 + 1} \geq \dfrac{r^2s+s}{r^2 + 1} = s\) and \(\dfrac{r^2s}{r^2+1} < \dfrac{r^2s+s}{r^2+1} = s\).
Thus, \(\left\lfloor\dfrac{r^2s+r}{r^2 + 1}\right\rfloor \geq s\).
Also, \(\left\lfloor\dfrac{r^2s}{r^2+1}\right\rfloor < s\) which means \(\left\lfloor\dfrac{r^2s}{r^2+1}\right\rfloor \leq s - 1\) and so \(\left\lfloor\dfrac{r(t+1)}{r^2+1}\right\rfloor - \left\lfloor\dfrac{rt}{r^2+1}\right\rfloor \geq 1\).
Therefore, if \(t\) is odd and not prime, then \(f(t+1) - f(t) \neq 2\) because we have found three terms that are equal to at least 1 meaning that \(f(t+1) - f(t) \geq 3\), and so if \(f(t+1) - f(t)\), then \(t\) must be prime.
Here is an alternative approach so show that \(f(t+1) - f(t) \geq 3\) when \(t\) is odd and composite.
As above, we look for at least 3 integers \(k\) for which \(\left\lfloor \dfrac{k(t+1)}{k^2+1} \right\rfloor -
\left\lfloor \dfrac{kt}{k^2+1} \right\rfloor \geq 1\). Here, we
allow for the possibility that \(k =
t\) knowing that the second term in this difference will be 0 in
this case.
The positive integer \(k\) has the
property that \(\left\lfloor
\dfrac{k(t+1)}{k^2+1} \right\rfloor - \left\lfloor
\dfrac{kt}{k^2+1} \right\rfloor \geq 1\) exactly when there is
an integer \(N\) for which \(\dfrac{k(t+1)}{k^2+1} \geq N >
\dfrac{kt}{k^2+1}\).
This pair of inequalities is equivalent to the pair of inequalities
\(t+1 \geq N \cdot \dfrac{k^2+1}{k} >
t\) which is in turn equivalent to \(t+1 \geq Nk + \dfrac{N}{k} > t\).
The following three pairs \((N,k)\) of
integers satisfy this equation:
\(k = 1\) and \(N = \dfrac{t+1}{2}\) (noting that \(t\) is odd), which give \(Nk + \dfrac{N}{k} = t+1\);
\(k = r\) and \(N = s\), which give \(Nk + \dfrac{N}{k} = rs + \dfrac{s}{r}\) (noting that \(\dfrac{s}{r} < 1\));
\(k = t\) and \(N = 1\), which give \(Nk + \dfrac{N}{k} = t + \dfrac{1}{t}\).
This shows that \(f(t+1) - f(t) \geq 3\) when \(t\) is odd and composite, as required.