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)

©2023 University of Waterloo

1. 1. Since the average of the 5 numbers $n$, $2n$, $3n$, $4n$, and $5n$ is 18, we obtain the equation ${\displaystyle \frac{n+2n+3n+4n+5n}{5}}=18$.
      Therefore, ${\displaystyle \frac{15n}{5}}=18$ and so $3n=18$ or $n=6$.

   2. 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 ${\displaystyle \frac{x+y}{2}}={\displaystyle \frac{3x+3y}{6}}={\displaystyle \frac{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 ${\displaystyle \frac{1+3}{2}}=2$.

   3. Since the average of the three numbers $t^2$, $2t$ and $3$ is 9, then ${\displaystyle \frac{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$.

2. 1. Since $Q(5,3)$ is the midpoint of $P(1,p)$ and $R(r,5)$, then ${\displaystyle \frac{1+r}{2}}=5$ and ${\displaystyle \frac{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$.

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

   3. 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)$.

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

   2. 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{array}{rl}(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{array}$$ 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$.

   3. 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{array}{rl}{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{array}$$ 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$$

4. 1. 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}÷\frac{1}{4}=\frac{4}{12}÷\frac{3}{12}=\frac{4}{3}$ of an hour.

      Therefore, Edmundo paints for 80 minutes.

   2. When converted to a fraction, $A\mathrm{\%}$ is equal to ${\displaystyle \frac{A}{100}}$.

      When an amount is increased by $A\mathrm{\%}$, we can find its new value by multiplying by $1+{\displaystyle \frac{A}{100}}$.

      When an amount is decreased by $A\mathrm{\%}$, we can find its new value by multiplying by $1-{\displaystyle \frac{A}{100}}$.

      When $400 is increased by $A\mathrm{\%}$, the amount becomes $\mathrm{\$}400(1+{\displaystyle \frac{A}{100}})$.
      When this value is decreased by $A\mathrm{\%}$, the amount becomes $\mathrm{\$}400(1+{\displaystyle \frac{A}{100}})(1-{\displaystyle \frac{A}{100}})$.
      Therefore, $$\begin{array}{rl}\mathrm{\$}400(1+{\displaystyle \frac{A}{100}})(1-{\displaystyle \frac{A}{100}})& =\mathrm{\$}391\\ (1+{\displaystyle \frac{A}{100}})(1-{\displaystyle \frac{A}{100}})& ={\displaystyle \frac{391}{400}}\\ 1-{\displaystyle \frac{A^2}{{100}^2}}& =1-{\displaystyle \frac{9}{400}}\\ {\displaystyle \frac{A^2}{{100}^2}}& ={\displaystyle \frac{9}{400}}\\ {\displaystyle \frac{A^2}{{100}^2}}& ={\displaystyle \frac{3^2}{{20}^2}}\\ {\displaystyle \frac{A}{100}}& ={\displaystyle \frac{3}{20}}\text{(since }A>0\text{)}\\ A& =100\cdot {\displaystyle \frac{3}{20}}=15\end{array}$$ Therefore, $A=15$.

5. 1. The quadratic function $f(x)=x^2+(2n-1)x+(n^2-22)$ has no real roots exactly when its discriminant, $\mathrm{\Delta }$, is negative.
      The discriminant of this function is $$\begin{array}{rl}\mathrm{\Delta }& =(2n-1{)}^2-4(1)(n^2-22)\\ & =(4n^2-4n+1)-(4n^2-88)\\ & =-4n+89\end{array}$$ We have $\mathrm{\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$.

   2. Using the cosine law in $\mathrm{△}PQR$, $$\begin{array}{rl}P{R}^2& =P{Q}^2+Q{R}^2-2\cdot PQ\cdot QR\cdot \cos (\mathrm{\angle }PQR)\\ {21}^2& =a^2+b^2-2ab\cos ({60}^{\circ })\\ 441& =a^2+b^2-2ab\cdot \frac{1}{2}\\ 441& =a^2+b^2-ab\end{array}$$ Using the sine law in $\mathrm{△}STU$, we obtain ${\displaystyle \frac{ST}{\sin (\mathrm{\angle }TUS)}}={\displaystyle \frac{TU}{\sin (\mathrm{\angle }TSU)}}$ and so ${\displaystyle \frac{a}{4/5}}={\displaystyle \frac{b}{\sin ({30}^{\circ })}}$.
      Therefore, ${\displaystyle \frac{a}{4/5}}={\displaystyle \frac{b}{1/2}}$ and so $a=\frac{4}{5}\cdot 2b=\frac{8}{5}b$.
      Substituting into the previous equation, $$\begin{array}{rl}441& ={\left(\frac{8}{5}b\right)}^2+b^2-\left(\frac{8}{5}b\right)b\\ 441& =\frac{64}{25}{b}^2+b^2-\frac{8}{5}{b}^2\\ 441& =\frac{64}{25}{b}^2+\frac{25}{25}{b}^2-\frac{40}{25}{b}^2\\ 441& =\frac{49}{25}{b}^2\\ 225& =b^2\end{array}$$ Since $b>0$, then $b=15$ and so $a=\frac{8}{5}b=\frac{8}{5}\cdot 15=24$.

6. 1. Solution 1

      We make two copies of the given triangle, labelling them $\mathrm{△}ABC$ and $\mathrm{△}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 $\mathrm{△}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 $\mathrm{△}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 $|\mathrm{△}ABC|$ to represent the area of $\mathrm{△}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}=|\mathrm{△}A{B}_1{C}_1|+|B_2{B}_3{C}_3{C}_2|+|B_4{B}_5{C}_5{C}_4|+|B_6{B}_7{C}_7{C}_6|+|B_8{B}_9{C}_9{C}_8|+|B_{10}BC{C}_{10}|$$ The area of each of these quadrilaterals is equal to the difference of the area of two triangles. For example, $$|B_2{B}_3{C}_3{C}_2|=|\mathrm{△}A{B}_3{C}_3|-|\mathrm{△}A{B}_2{C}_2|=-|\mathrm{△}A{B}_2{C}_2|+|\mathrm{△}A{B}_3{C}_3|$$ Therefore, $$\begin{array}{rl}\mathcal{A}& =|\mathrm{△}A{B}_1{C}_1|-|\mathrm{△}A{B}_2{C}_2|+|\mathrm{△}A{B}_3{C}_3|-|\mathrm{△}A{B}_4{C}_4|+|\mathrm{△}A{B}_5{C}_5|\\ & -|\mathrm{△}A{B}_6{C}_6|+|\mathrm{△}A{B}_7{C}_7|-|\mathrm{△}A{B}_8{C}_8|+|\mathrm{△}A{B}_9{C}_9|-|\mathrm{△}A{B}_{10}{C}_{10}|+|\mathrm{△}ABC|\end{array}$$ Each of $\mathrm{△}A{B}_1{C}_1$, $\mathrm{△}A{B}_2{C}_2$, $\dots$, $\mathrm{△}A{B}_{10}{C}_{10}$ is similar to $\mathrm{△}ABC$ because their two base angles are equal due.
      Suppose that the height of $\mathrm{△}ABC$ from $A$ to $BC$ is $h$.
      Since the height of each of the 11 regions is equal in height, then the height of $\mathrm{△}A{B}_1{C}_1$ is $\frac{1}{11}h$, the height of $\mathrm{△}A{B}_2{C}_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 $\mathrm{△}PQR$ is similar to $\mathrm{△}STU$ and that altitudes are drawn from $P$ and $S$ to $V$ and $W$.

      

      Since $\mathrm{\angle }PQR=\mathrm{\angle }STU$, then $\mathrm{△}PQV$ is similar to $\mathrm{△}STW$ (equal angle; right angle), which means that ${\displaystyle \frac{PQ}{ST}}={\displaystyle \frac{PV}{SW}}$. In other words, the ratio of sides is equal to the ratio of heights.

      Since the height of $\mathrm{△}A{B}_1{C}_1$ is $\frac{1}{11}h$, then $B_1{C}_1=\frac{1}{11}BC$.

      Therefore, $|\mathrm{△}A{B}_1{C}_1|=\frac{1}{2}\cdot B_1{C}_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}|\mathrm{△}ABC|$.

      Similarly, since the height of $\mathrm{△}A{B}_2{C}_2$ is $\frac{2}{11}h$, then $B_2{C}_2=\frac{2}{11}BC$.

      Therefore, $|\mathrm{△}A{B}_2{C}_2|=\frac{1}{2}\cdot B_2{C}_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}|\mathrm{△}ABC|$.

      This result continues for each of the triangles.
      Therefore, $$\begin{array}{rl}\mathcal{A}& =\frac{1^2}{{11}^2}|\mathrm{△}ABC|-\frac{2^2}{{11}^2}|\mathrm{△}ABC|+\frac{3^2}{{11}^2}|\mathrm{△}ABC|-\frac{4^2}{{11}^2}|\mathrm{△}ABC|+\frac{5^2}{{11}^2}|\mathrm{△}ABC|\\ & -\frac{6^2}{{11}^2}|\mathrm{△}ABC|+\frac{7^2}{{11}^2}|\mathrm{△}ABC|-\frac{8^2}{{11}^2}|\mathrm{△}ABC|+\frac{9^2}{{11}^2}|\mathrm{△}ABC|-\frac{{10}^2}{{11}^2}|\mathrm{△}ABC|+\frac{{11}^2}{{11}^2}|\mathrm{△}ABC|\\ & =\frac{1}{{11}^2}|\mathrm{△}ABC|({11}^2-{10}^2+9^2-8^2+7^2-6^2+5^2-4^2+3^2-2^2+1)\\ & =\frac{1}{{11}^2}(770{\text{ cm}}^2)((11+10)(11-10)+(9+8)(9-8)+\cdots +(3+2)(3-2)+1)\\ & =\frac{1}{{11}^2}(770{\text{ cm}}^2)(11+10+9+8+7+6+5+4+3+2+1)\\ & =\frac{1}{11}(70{\text{ cm}}^2)\cdot 66\\ & =420{\text{ cm}}^2\end{array}$$ Therefore, the combined area of the shaded regions of $\mathrm{△}ABC$ is $420{\text{ cm}}^2$.

   2. Solution 1

      We label five additional points in the diagram:

      

      Since $PQ=QR=RS=1$, then $PS=3$ and $PR=2$.
      Since $\mathrm{\angle }PST={90}^{\circ }$, then $PT=\sqrt{P{S}^2+S{T}^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, $\mathrm{△}PDQ$ is right-angled at $D$ and $\mathrm{△}PAR$ is right-angled at $A$.
      Since $\mathrm{△}PDQ$, $\mathrm{△}PAR$ and $\mathrm{△}PST$ are all right-angled and all share an angle at $P$, then these three triangles are similar.

      This tells us that ${\displaystyle \frac{PA}{PS}}={\displaystyle \frac{PR}{PT}}$ and so $PA={\displaystyle \frac{3\cdot 2}{\sqrt{10}}}$. Also, ${\displaystyle \frac{PD}{PS}}={\displaystyle \frac{PQ}{PT}}$ and so $PD={\displaystyle \frac{1\cdot 3}{\sqrt{10}}}$.
      Therefore, $$DA=PA-PD={\displaystyle \frac{6}{\sqrt{10}}}-{\displaystyle \frac{3}{\sqrt{10}}}={\displaystyle \frac{3}{\sqrt{10}}}$$ This means that the area of square $ABCD$ is equal to $D{A}^2={\left({\displaystyle \frac{3}{\sqrt{10}}}\right)}^2={\displaystyle \frac{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 ${\displaystyle \frac{3-2}{0-3}}=-{\displaystyle \frac{1}{3}}$.

      This equation of this line can be written as $y=-{\displaystyle \frac{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=-{\displaystyle \frac{1}{3}}x+3$ and $y=3x$.

      Equating expressions for $y$, we obtain $-{\displaystyle \frac{1}{3}}x+3=3x$ and so ${\displaystyle \frac{10}{3}}x=3$ which gives $x={\displaystyle \frac{9}{10}}$.

      Since $y=3x$, we get $y={\displaystyle \frac{27}{10}}$ and so the coordinates of $D$ are $({\displaystyle \frac{9}{10}},{\displaystyle \frac{27}{10}})$.
      Point $A$ is the intersection point of the lines with equations $y=-{\displaystyle \frac{1}{3}}x+3$ and $y=3x-3$.

      Equating expressions for $y$, we obtain $-{\displaystyle \frac{1}{3}}x+3=3x-3$ and so ${\displaystyle \frac{10}{3}}x=6$ which gives $x={\displaystyle \frac{18}{10}}$.

      Since $y=3x-3$, we get $y={\displaystyle \frac{24}{10}}$ and so the coordinates of $A$ are $({\displaystyle \frac{18}{10}},{\displaystyle \frac{24}{10}})$. (It is easier to not reduce these fractions.)
      Therefore, $$DA=\sqrt{{({\displaystyle \frac{9}{10}}-{\displaystyle \frac{18}{10}})}^2+{({\displaystyle \frac{27}{10}}-{\displaystyle \frac{24}{10}})}^2}=\sqrt{{(-{\displaystyle \frac{9}{10}})}^2+{\left({\displaystyle \frac{3}{10}}\right)}^2}=\sqrt{{\displaystyle \frac{90}{100}}}=\sqrt{{\displaystyle \frac{9}{10}}}$$ This means that the area of square $ABCD$ is equal to $D{A}^2={\left(\sqrt{{\displaystyle \frac{9}{10}}}\right)}^2={\displaystyle \frac{9}{10}}$.

7. 1. 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\underset{―}{}B\underset{―}{}\underset{―}{}\underset{―}{}\underset{―}{}\underset{―}{}\underset{―}{}$$ The 7 blanks must be filled with the remaining 2 R’s and 5 B’s.
      There are ${\displaystyle (\genfrac{}{}{0ex}{}{7}{2})={\displaystyle \frac{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\underset{―}{}B\underset{―}{}\underset{―}{}\underset{―}{}\underset{―}{}BB$$ In these sequences, the 5 blanks must be filled with the remaining 2 R’s and 3 B’s.
      There are ${\displaystyle (\genfrac{}{}{0ex}{}{5}{2})={\displaystyle \frac{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 ${\displaystyle \frac{10}{21}}$.

   2. 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{array}{rl}(a+b)(c+d)& =2023\\ (a+b)+(c+d)& =296\end{array}$$ If we let $s=a+b$ and $t=c+d$, we obtain the equations $$\begin{array}{rl}st& =2023\\ s+t& =296\end{array}$$ 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),\dots ,(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),\dots ,(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),\dots ,(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)$.
      

8. 1. Since $\mathrm{△}ABC$ is right-angled at $B$, then $$\begin{array}{rl}B{C}^2& =A{C}^2-A{B}^2\\ & ={((n+1)(n+4))}^2-{(n(n+1))}^2\\ & =(n+1{)}^2(n+4{)}^2-n^2(n+1{)}^2\\ & =(n+1{)}^2((n+4{)}^2-n^2)\\ & =(n+1{)}^2(n^2+8n+16-n^2)\\ & =(n+1{)}^2(8n+16)\\ & =4(n+1{)}^2(2n+4)\end{array}$$ 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\ge 6$ (since $n\ge 1$) and that $2n+4$ is even.
      Since $n<100000$, then $6\le 2n+4<200004$, 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{200004}\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 ${\displaystyle \frac{446}{2}}-1=222$.

      Thus, there are 222 positive integers $n$ for which the length of $BC$ is an integer.

   2. Let $f(x)=\sqrt{{\log }_{2}x\cdot {\log }_2(4x)+1}+\sqrt{{\log }_{2}x\cdot {\log }_2\left({\displaystyle \frac{x}{64}}\right)+9}$.
      Using logarithm laws, $$\begin{array}{rl}{\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\text{)}\\ & =({\log }_{2}x{)}^2+2\cdot {\log }_{2}x+1\\ & =({\log }_{2}x+1{)}^2\end{array}$$ and $$\begin{array}{rl}{\log }_{2}x\cdot {\log }_2\left({\displaystyle \frac{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\text{)}\\ & =({\log }_{2}x{)}^2-6{\log }_{2}x+9\\ & =({\log }_{2}x-3{)}^2\end{array}$$ Therefore, $$f(x)=\sqrt{{\log }_{2}x\cdot {\log }_2(4x)+1}+\sqrt{{\log }_{2}x\cdot {\log }_2\left({\displaystyle \frac{x}{64}}\right)+9}=\sqrt{({\log }_{2}x+1{)}^2}+\sqrt{({\log }_{2}x-3{)}^2}$$ Before proceeding, we recall that if $a\le 0$, then $\sqrt{a^2}=-a$ and if $a>0$, then $\sqrt{a^2}=a$.
      When ${\log }_{2}x\le -1$, we know that ${\log }_{2}x+1\le 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\le 3$, we know that ${\log }_{2}x+1>0$ and ${\log }_{2}x-3\le 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\ge 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\le -1$, $f(x)=2-2{\log }_{2}x=4$ exactly when ${\log }_{2}x=-1$.
      When $-1<{\log }_{2}x\le 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\le {\log }_{2}x\le 3$, which is true exactly when $\frac{1}{2}\le x\le 8$.
      (It seems surprising that the solution to this equation is actually an interval of values, rather than a finite number of specific values.)

9. 1. 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\}$$

   2. 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\le 6k+5\le 3t$.
      Since $2t\le 6k+5$, then $t\le 3k+\frac{5}{2}$. Since $k$ and $t$ are integers, then $t\le 3k+2$.
      We note that it is possible to seat $3k+2$ people around the table in seats $$\{2,4,6,\dots ,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\ge 6k+5$, then $t\ge 2k+\frac{5}{3}$. Since $k$ and $t$ are integers, then $t\ge 2k+2$.
      We note that it is possible to seat $2k+2$ people around the table in seats $$\{3,6,9,\dots ,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\le t\le 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\ge 6k+5$ and so $3t-(6k+5)\ge 0$, and that $2t\le 6k+5$ and so $(6k+5)-2t\ge 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\le t\le 3k+2$ can produce a full table.
      Therefore, the possible values of $t$ are those integers that satisfy $2k+2\le t\le 3k+2$.
      There are $(3k+2)-(2k+2)+1=k+1$ possible values of $t$.

   3. Solution 1

      For each integer $n\ge 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:

      $\mathit{n}$	$\mathit{f}\mathbf{(}\mathit{n}\mathbf{)}$
      3	3
      4	2
      5	5
      6	5
      7	?
      8	10

      Based on this information, we make the guess that for every integer $n\ge 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$:

      $\mathit{n}$	$\mathit{f}\mathbf{(}\mathit{n}\mathbf{)}$
      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\ge 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\ge 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{array}{rl}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{array}$$ 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\}$, $\dots$, $\{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 (\genfrac{}{}{0ex}{}{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 (\genfrac{}{}{0ex}{}{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 (\genfrac{}{}{0ex}{}{9}{1})}$ ways of arranging the gaps starting at chair 1.
      In this case, there are a total of ${\displaystyle (\genfrac{}{}{0ex}{}{7}{2})+(\genfrac{}{}{0ex}{}{8}{3})+(\genfrac{}{}{0ex}{}{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 (\genfrac{}{}{0ex}{}{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 (\genfrac{}{}{0ex}{}{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 (\genfrac{}{}{0ex}{}{6}{2})+(\genfrac{}{}{0ex}{}{7}{2})+1=15+21+1=37}$ full tables.
      
      In total, there are $86+86+37=209$ full tables with 19 chairs.

10. 1. Since $0<{\displaystyle \frac{1}{3}}<{\displaystyle \frac{2}{3}}<1$, then $\lfloor {\displaystyle \frac{1}{3}}\rfloor =\lfloor {\displaystyle \frac{2}{3}}\rfloor =0$.

       Since $1\le {\displaystyle \frac{3}{3}}<{\displaystyle \frac{4}{3}}<{\displaystyle \frac{5}{3}}<2$, then $\lfloor {\displaystyle \frac{3}{3}}\rfloor =\lfloor {\displaystyle \frac{4}{3}}\rfloor =\lfloor {\displaystyle \frac{5}{3}}\rfloor =1$.

       These fractions can continue to be grouped in groups of 3 with the last full group of 3 satisfying $19\le {\displaystyle \frac{57}{3}}<{\displaystyle \frac{58}{3}}<{\displaystyle \frac{59}{3}}<20$, which means that $\lfloor {\displaystyle \frac{57}{3}}\rfloor =\lfloor {\displaystyle \frac{58}{3}}\rfloor =\lfloor {\displaystyle \frac{59}{3}}\rfloor =19$.
       The last term is $\lfloor {\displaystyle \frac{60}{3}}\rfloor =\lfloor 20\rfloor =20$.

       If the given sum is $S$, we obtain $$\begin{array}{rl}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 \frac{1}{2}\cdot 19\cdot 20+20\\ & =570+20\\ & =590\end{array}$$

    2. For every positive integer $m>4$, let $$q(m)=\lfloor {\displaystyle \frac{1}{3}}\rfloor +\lfloor {\displaystyle \frac{2}{3}}\rfloor +\lfloor {\displaystyle \frac{3}{3}}\rfloor +\dots +\lfloor {\displaystyle \frac{m-2}{3}}\rfloor +\lfloor {\displaystyle \frac{m-1}{3}}\rfloor$$ Extending our work from (a), we know that $k-1\le {\displaystyle \frac{3k-3}{3}}<{\displaystyle \frac{3k-2}{3}}<{\displaystyle \frac{3k-1}{3}}<k$ for each positive integer $k$, and so $\lfloor {\displaystyle \frac{3k-3}{3}}\rfloor =\lfloor {\displaystyle \frac{3k-2}{3}}\rfloor =\lfloor {\displaystyle \frac{3k-1}{3}}\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{array}{rl}q(3s)& =\lfloor {\displaystyle \frac{1}{3}}\rfloor +\lfloor {\displaystyle \frac{2}{3}}\rfloor +\lfloor {\displaystyle \frac{3}{3}}\rfloor +\dots +\lfloor {\displaystyle \frac{3s-2}{3}}\rfloor +\lfloor {\displaystyle \frac{3s-1}{3}}\rfloor \\ & =2\cdot 0+3(1+2+3+\cdots +(s-1))\\ & =3\cdot {\displaystyle \frac{1}{2}}\cdot (s-1)s\\ & ={\displaystyle \frac{3s(s-1)}{2}}\\ & ={\displaystyle \frac{3s(3s-3)}{6}}\\ & \\ q(3s+1)& =\lfloor {\displaystyle \frac{1}{3}}\rfloor +\lfloor {\displaystyle \frac{2}{3}}\rfloor +\lfloor {\displaystyle \frac{3}{3}}\rfloor +\dots +\lfloor {\displaystyle \frac{3s-2}{3}}\rfloor +\lfloor {\displaystyle \frac{3s-1}{3}}\rfloor +\lfloor {\displaystyle \frac{3s}{3}}\rfloor \\ & =q(3s)+s\\ & ={\displaystyle \frac{3s(3s-3)}{6}}+{\displaystyle \frac{3s\cdot 2}{6}}\\ & ={\displaystyle \frac{3s(3s-1)}{6}}\\ & \\ q(3s+2)& =q(3s+1)+\lfloor {\displaystyle \frac{3s+1}{3}}\rfloor \\ & ={\displaystyle \frac{3s(3s-1)}{6}}+s\\ & ={\displaystyle \frac{3s(3s-1)}{6}}+{\displaystyle \frac{3s\cdot 2}{6}}\\ & ={\displaystyle \frac{3s(3s+1)}{6}}\end{array}$$ 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 ={\displaystyle \frac{3s(3s-3)}{6}}\lfloor p(3s+1)\rfloor ={\displaystyle \frac{3s(3s-1)}{6}}\lfloor p(3s+2)\rfloor ={\displaystyle \frac{3s(3s+1)}{6}}$$ for every positive integer $s$.
       We will show that the polynomial $p(x)={\displaystyle \frac{(x-1)(x-2)}{6}}$ satisfies the desired conditions.

       If $x=3s+1$ for some positive integer $s$, then $${\displaystyle \frac{(x-1)(x-2)}{6}}={\displaystyle \frac{(3s+1-1)(3s+1-2)}{6}}={\displaystyle \frac{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 ${\displaystyle \frac{3s(3s-1)}{6}}$ is an integer.
       This means that $\lfloor {\displaystyle \frac{3s(3s-1)}{6}}\rfloor ={\displaystyle \frac{3s(3s-1)}{6}}$.

       Therefore, $q(3s+1)={\displaystyle \frac{3s(3s-1)}{6}}=\lfloor {\displaystyle \frac{3s(3s-1)}{6}}\rfloor =\lfloor p(3s+1)\rfloor$.

       If $x=3s+2$ for some positive integer $s$, then $${\displaystyle \frac{(x-1)(x-2)}{6}}={\displaystyle \frac{(3s+2-1)(3s+2-2)}{6}}={\displaystyle \frac{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 ${\displaystyle \frac{3s(3s+1)}{6}}$ is an integer.
       This means that $\lfloor {\displaystyle \frac{3s(3s+1)}{6}}\rfloor ={\displaystyle \frac{3s(3s+1)}{6}}$.

       Therefore, $q(3s+2)={\displaystyle \frac{3s(3s+1)}{6}}=\lfloor {\displaystyle \frac{3s(3s+1)}{6}}\rfloor =\lfloor p(3s+2)\rfloor$.

       If $x=3s$ for some positive integer $s$, then $${\displaystyle \frac{(x-1)(x-2)}{6}}={\displaystyle \frac{(3s-1)(3s-2)}{6}}={\displaystyle \frac{9s^2-9s+2}{6}}$$ Now, ${\displaystyle \frac{9s^2-9s}{6}}={\displaystyle \frac{9s(s-1)}{6}}$ is an integer because $9s$ is a multiple of 3 and one of $s$ and $s-1$ is even.

       Since ${\displaystyle \frac{9s^2-9s+2}{6}}={\displaystyle \frac{9s^2-9s}{6}}+{\displaystyle \frac{1}{3}}$, then ${\displaystyle \frac{9s^2-9s+2}{6}}$ is ${\displaystyle \frac{1}{3}}$ more than an integer which means that $\lfloor {\displaystyle \frac{9s^2-9s+2}{6}}\rfloor ={\displaystyle \frac{9s^2-9s}{6}}={\displaystyle \frac{3s(3s-3)}{6}}=q(3s)$.

       Therefore, $q(3s)={\displaystyle \frac{3s(3s-3)}{6}}=\lfloor {\displaystyle \frac{(3s-1)(3s-2)}{6}}\rfloor =\lfloor p(3s)\rfloor$.

       This means that the polynomial $p(x)={\displaystyle \frac{(x-1)(x-2)}{6}}$ satisfies the required conditions.

    3. Before working on the specific question we have been asked, we simplify the given expression for $f(n)$ by noting that if $k\ge n$, then $kn\le k^2<k^2+1$.
       This means that if $k\ge n$, we have $0<{\displaystyle \frac{kn}{n^2+1}}<1$ and so $\lfloor {\displaystyle \frac{kn}{k^2+1}}\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)=\lfloor \frac{n}{1^2+1}\rfloor +\lfloor \frac{2n}{2^2+1}\rfloor +\lfloor \frac{3n}{3^2+1}\rfloor +\cdots +\lfloor \frac{(n-2)n}{(n-2{)}^2+1}\rfloor +\lfloor \frac{(n-1)n}{(n-1{)}^2+1}\rfloor$$ We note that $$\begin{array}{rl}f(1)& =0\text{(since no terms are non-zero)}\\ f(2)& =\lfloor \frac{1\cdot 2}{1^2+1}\rfloor =1\\ f(3)& =\lfloor \frac{1\cdot 3}{1^2+1}\rfloor +\lfloor \frac{2\cdot 3}{2^2+1}\rfloor =\lfloor \frac{3}{2}\rfloor +\lfloor \frac{6}{5}\rfloor =1+1=2\\ f(4)& =\lfloor \frac{1\cdot 4}{1^2+1}\rfloor +\lfloor \frac{2\cdot 4}{2^2+1}\rfloor +\lfloor \frac{3\cdot 4}{3^2+1}\rfloor =\lfloor \frac{4}{2}\rfloor +\lfloor \frac{8}{5}\rfloor +\lfloor \frac{12}{10}\rfloor =2+1+1=4\end{array}$$ 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)\ne 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\ne 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\ge 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{array}{rl}f(t+1)-f(t)& =\phantom{-}\lfloor {\displaystyle \frac{t+1}{1^2+1}}\rfloor +\lfloor {\displaystyle \frac{2(t+1)}{2^2+1}}\rfloor +\cdots +\lfloor {\displaystyle \frac{(t-1)(t+1)}{(t-1{)}^2+1}}\rfloor +\lfloor {\displaystyle \frac{t(t+1)}{t^2+1}}\rfloor \\ & -\lfloor {\displaystyle \frac{t}{1^2+1}}\rfloor -\lfloor {\displaystyle \frac{2t}{2^2+1}}\rfloor -\cdots -\lfloor {\displaystyle \frac{(t-1)t}{(t-1{)}^2+1}}\rfloor \end{array}$$ We re-write this as $$\begin{array}{rl}f(t+1)-f(t)& =(\lfloor {\displaystyle \frac{t+1}{1^2+1}}\rfloor -\lfloor {\displaystyle \frac{t}{1^2+1}}\rfloor )+(\lfloor {\displaystyle \frac{2(t+1)}{2^2+1}}\rfloor -\lfloor {\displaystyle \frac{2t}{2^2+1}}\rfloor )+\cdots \\ & +(\lfloor {\displaystyle \frac{(t-1)(t+1)}{(t-1{)}^2+1}}\rfloor -\lfloor {\displaystyle \frac{(t-1)t}{(t-1{)}^2+1}}\rfloor )+\lfloor {\displaystyle \frac{t(t+1)}{t^2+1}}\rfloor \end{array}$$ In the $t-1$ sets of parentheses, we have terms of the form $\lfloor {\displaystyle \frac{k(t+1)}{k^2+1}}\rfloor -\lfloor {\displaystyle \frac{kt}{k^2+1}}\rfloor$ for each integer $k$ from $1$ to $t-1$.

       We know that ${\displaystyle \frac{k(t+1)}{k^2+1}}>{\displaystyle \frac{kt}{k^2+1}}$ because both $k$ and $t$ are positive, the denominators are equal and $k(t+1)>kt$.

       Thus, $\lfloor {\displaystyle \frac{k(t+1)}{k^2+1}}\rfloor \ge \lfloor {\displaystyle \frac{kt}{k^2+1}}\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)\ne 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)\ge 3$ and so $f(t+1)-f(t)\ne 2$, which will tell us that $t$ cannot be composite, and so $t$ must be prime, as required.

       Consider $\lfloor {\displaystyle \frac{t(t+1)}{t^2+1}}\rfloor$.
       Since $t(t+1)=t^2+t\ge t^2+1$, then ${\displaystyle \frac{t(t+1)}{t^2+1}}\ge 1$, which means that $\lfloor {\displaystyle \frac{t(t+1)}{t^2+1}}\rfloor \ge 1$.

       Consider $\lfloor {\displaystyle \frac{t+1}{1^2+1}}\rfloor -\lfloor {\displaystyle \frac{t}{1^2+1}}\rfloor =\lfloor {\displaystyle \frac{t+1}{2}}\rfloor -\lfloor {\displaystyle \frac{t}{2}}\rfloor$.

       Since $t$ is odd, then we write $t=2u+1$ for some positive integer $u$, which gives $$\lfloor {\displaystyle \frac{t+1}{2}}\rfloor -\lfloor {\displaystyle \frac{t}{2}}\rfloor =\lfloor {\displaystyle \frac{2u+2}{2}}\rfloor -\lfloor {\displaystyle \frac{2u+1}{2}}\rfloor =\lfloor u+1\rfloor -\lfloor u+{\displaystyle \frac{1}{2}}\rfloor =(u+1)-u=1$$ Recall that $t=rs$ with $r\ge s>1$.

       Consider the term $\lfloor {\displaystyle \frac{r(t+1)}{r^2+1}}\rfloor -\lfloor {\displaystyle \frac{rt}{r^2+1}}\rfloor$.

       We have $$\lfloor {\displaystyle \frac{r(t+1)}{r^2+1}}\rfloor -\lfloor {\displaystyle \frac{rt}{r^2+1}}\rfloor =\lfloor {\displaystyle \frac{r(rs+1)}{r^2+1}}\rfloor -\lfloor {\displaystyle \frac{r\cdot rs}{r^2+1}}\rfloor =\lfloor {\displaystyle \frac{r^{2}s+r}{r^2+1}}\rfloor -\lfloor {\displaystyle \frac{r^{2}s}{r^2+1}}\rfloor$$ We note that ${\displaystyle \frac{r^{2}s+r}{r^2+1}}\ge {\displaystyle \frac{r^{2}s+s}{r^2+1}}=s$ and ${\displaystyle \frac{r^{2}s}{r^2+1}}<{\displaystyle \frac{r^{2}s+s}{r^2+1}}=s$.

       Thus, $\lfloor {\displaystyle \frac{r^{2}s+r}{r^2+1}}\rfloor \ge s$.

       Also, $\lfloor {\displaystyle \frac{r^{2}s}{r^2+1}}\rfloor <s$ which means $\lfloor {\displaystyle \frac{r^{2}s}{r^2+1}}\rfloor \le s-1$ and so $\lfloor {\displaystyle \frac{r(t+1)}{r^2+1}}\rfloor -\lfloor {\displaystyle \frac{rt}{r^2+1}}\rfloor \ge 1$.

       Therefore, if $t$ is odd and not prime, then $f(t+1)-f(t)\ne 2$ because we have found three terms that are equal to at least 1 meaning that $f(t+1)-f(t)\ge 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)\ge 3$ when $t$ is odd and composite.
       As above, we look for at least 3 integers $k$ for which $\lfloor {\displaystyle \frac{k(t+1)}{k^2+1}}\rfloor -\lfloor {\displaystyle \frac{kt}{k^2+1}}\rfloor \ge 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 $\lfloor {\displaystyle \frac{k(t+1)}{k^2+1}}\rfloor -\lfloor {\displaystyle \frac{kt}{k^2+1}}\rfloor \ge 1$ exactly when there is an integer $N$ for which ${\displaystyle \frac{k(t+1)}{k^2+1}}\ge N>{\displaystyle \frac{kt}{k^2+1}}$.
       This pair of inequalities is equivalent to the pair of inequalities $t+1\ge N\cdot {\displaystyle \frac{k^2+1}{k}}>t$ which is in turn equivalent to $t+1\ge Nk+{\displaystyle \frac{N}{k}}>t$.
       The following three pairs $(N,k)$ of integers satisfy this equation:

       • $k=1$ and $N={\displaystyle \frac{t+1}{2}}$ (noting that $t$ is odd), which give $Nk+{\displaystyle \frac{N}{k}}=t+1$;

       • $k=r$ and $N=s$, which give $Nk+{\displaystyle \frac{N}{k}}=rs+{\displaystyle \frac{s}{r}}$ (noting that ${\displaystyle \frac{s}{r}}<1$);

       • $k=t$ and $N=1$, which give $Nk+{\displaystyle \frac{N}{k}}=t+{\displaystyle \frac{1}{t}}$.

       This shows that $f(t+1)-f(t)\ge 3$ when $t$ is odd and composite, as required.