2017 Hypatia Contest
Solutions
(Grade 11)

Wednesday, April 12, 2017 (in North America and South America)

Thursday, April 13, 2017 (outside of North American and South America)

1. Since $ABCD$ is a cyclic quadrilateral, $\angle DCB +\angle DAB= 180\degree$ or $(2u)\degree+88\degree=180\degree$ or $2u=92$ and so $u=46$.
2. Since $STQR$ is a cyclic quadrilateral, $\angle SRQ +\angle STQ= 180\degree$ or $x\degree+58\degree=180\degree$ and so $x=122$. Since $PQRS$ is a cyclic quadrilateral, $\angle SPQ +\angle SRQ= 180\degree$ or $y\degree+x\degree=180\degree$ or $y+122=180$ and so $y=58$.
3. In $\triangle JKL$, $KJ=KL$ and so $\angle KLJ=\angle KJL=35\degree$ ($\triangle JKL$ is isosceles).
  
  In $\triangle JKL$, $\angle JKL=180\degree-2(35\degree)=110\degree$.
  
  Since $JKLM$ is a cyclic quadrilateral, $\angle JML +\angle JKL= 180\degree$ or $\angle JML+110\degree=180\degree$, and so $\angle JML=70\degree$.
  
  In $\triangle JLM$, $LJ=LM$ and so $\angle MJL=\angle JML=70\degree$ ($\triangle JLM$ is isosceles). In $\triangle JLM$, $\angle JLM=180\degree-2(70\degree)=40\degree$, and so $w=40$.
4. Solution 1
  
  Since $DEFG$ is a cyclic quadrilateral, $\angle DGF +\angle DEF= 180\degree$ or $\angle DGF+z\degree=180\degree$ and so $\angle DGF=180\degree-z\degree$.
  
  Since $FGH$ is a straight angle, then $\angle DGF+\angle DGH=180\degree$ or $(180\degree-z\degree)+\angle DGH=180\degree$ or $\angle {DGH}=180\degree-180\degree+z\degree=z\degree$.
  
  Solution 2
  
  Since $DEFG$ is a cyclic quadrilateral, $\angle DGF +\angle DEF= 180\degree$.
  
  Since $FGH$ is a straight angle, then $\angle DGF+\angle DGH=180\degree$. Therefore, $\angle DGF+\angle DGH=\angle DGF+\angle DEF$, and so $\angle DGH=\angle DEF=z\degree$.
1. We complete Row 5 of the table, as shown.
  - Row 1: 1
  - Row 2: 1, 2, 3
  - Row 3: 1, 2, 3, 4, 5
  - Row 4: 1, 2, 3, 4, 5, 6, 7
  - Row 5: 1, 2, 3, 4, 5, 6, 7, 8, 9
  - $\vdots$
  After having completed $n$ rows, $n^2$ integers have been written.
  
  Therefore, after having completed 5 rows, $5^2=25$ integers have been written.
  
  The 25$^{th}$ integer written in the table is the last integer in Row 5, which is 9.
2. After having completed 10 rows, $10^2=100$ integers have been written in the table.
  
  Therefore, the 100$^{th}$ integer written in the table is the last integer in Row 10.
  
  Row $n$ ends at the $n^{th}$ odd integer.
  
  Beginning at 1, the first odd integer is $1=2(1)-1$, the second odd integer is $3=2(2)-1$, the third odd integer is $5=2(3)-1$.
  
  Beginning at 1, the $n^{th}$ odd integer is $2n-1$ (1 less than the $n^{th}$ even integer $2n$).
  
  Row 10 ends at the $10^{th}$ odd integer, which is $2(10)-1=19$. Therefore, the 100$^{th}$ integer written in the table is 19.
3. After completing 44 rows, $44^2=1936$ integers have been written in the table.
  
  After completing 45 rows, $45^2=2025$ integers have been written in the table.
  
  Therefore, the 2017$^{th}$ integer written in the table is in Row 45.
  
  The final integer written in Row 45 is the 45$^{th}$ odd integer, which is $2(45)-1=89$. The 2025$^{th}$ integer written in the table is 89, and so the 2017$^{th}$ integer written in the table is $2025-2017=8$ less than 89, or $89-8=81$.
4. Each row, after the first, contains all of the integers that were written in the previous row, followed by the next two consecutive integers.
  
  For example, Row 3 contains all integers that were written in Row 2 (that is, $1,2,3$), followed by the next two consecutive integers, 4 and 5.
  
  Therefore, the first time an integer is written in the table, it appears as the last integer in a row, or as the second last integer in a row.
  
  Since each row ends at the $n^{th}$ odd integer, then the last integer in each row is odd, and the second last integer in each row is even.
  
  The first time the integer 96 appears in the table, it is the second last integer written in a row (since 96 is even), and 97 is the last integer written in that same row.
  
  Since Row $n$ ends with the $n^{th}$ odd integer, $2n-1$, then when $2n-1=97$, we get $2n=98$ and so $n=49$.
  
  That is, Row 49 ends with the integer 97 and so the second last integer written in Row 49 is 96.
  
  Since 96 first appears in Row 49 of the table, then 96 appears in every row following Row 49 and does not appear in any row before Row 49. Therefore, the integer 96 appears in $200-48=152$ of the first 200 rows of the table.
1. When the line $y=-15$ intersects the parabola with equation $y=-x^2+2x$, the $x$-coordinates of the two points of intersection satisfy the equation $-15=-x^2+2x$.
  
  Solving this equation, we get $x^2-2x-15=0$ or $(x+3)(x-5)=0$, and so $x=-3$ or $x=5$. Since both points of intersection lie on the line $y=-15$, then the coordinates of the two points of intersection are $(-3,-15)$ and $(5,-15)$.
2. The point with $x$-coordinate 4, on the parabola with equation $y=-x^2-3x$, has $y$-coordinate $-4^2-3(4)=-28$.
  
  Therefore, the line intersects the parabola at the point $(4,-28)$.
  
  The line passes through the point $(0,8)$, and so the line has slope $\dfrac{-28-8}{4-0}=\dfrac{-36}{4}=-9$.
  
  The line has slope $-9$ and $y$-intercept 8, and so the equation of the line is $y=-9x+8$.
  
  When the line $y=-9x+8$ intersects the parabola with equation $y=-x^2-3x$, the $x$-coordinates of the two points of intersection satisfy the equation $-9x+8=-x^2-3x$.
  
  Solving this equation, we get $x^2-6x+8=0$ or $(x-2)(x-4)=0$, and so $x=2$ or $x=4$. Therefore, the line intersects the parabola at $x=4$ and at $x=2$, and so $a=2$.
3. The point with $x$-coordinate $p$, on the parabola with equation $y=-x^2+kx$, has $y$-coordinate $-p^2+kp$.
  
  Therefore, the line intersects the parabola at the point $(p,-p^2+kp)$.
  
  Similarly, the line also intersects the parabola at the point $(q,-q^2+kq)$. The slope of the line passing through the points $(p,-p^2+kp)$ and $(q,-q^2+kq)$ is $\dfrac{(-p^2+kp)-(-q^2+kq)}{p-q}$, where $p\neq q$ and so $p-q\neq0$.
  
  Simplifying this slope, we get \[\begin{align*} \dfrac{(-p^2+kp)-(-q^2+kq)}{p-q}&=\dfrac{q^2-p^2+kp-kq}{p-q}\\ &=\dfrac{(q-p)(q+p)+k(p-q)}{p-q}\\ &=\dfrac{(q-p)(q+p)}{p-q}+\dfrac{k(p-q)}{p-q}\\ &=\dfrac{-(p-q)(q+p)}{p-q}+\dfrac{k(p-q)}{p-q}\\ &=-(q+p)+k\\ &=k-q-p\end{align*}\]
  
  The line has slope $k-q-p$ and passes through the point $(p,-p^2+kp)$.
  
  Therefore, the equation of the line is $y-(-p^2+kp)=(k-q-p)(x-p)$.
  
  (The equation of a line having slope $m$ and passing through the point $(x_1,y_1)$ is $y-y_1=m(x-x_1)$. This is called the point-slope form of a line.) Finally, we determine the $y$-intercept of the line by substituting $x=0$ into the equation of the line $y-(-p^2+kp)=(k-q-p)(x-p)$ and solving for $y$.
  
  \[\begin{align*} y-(-p^2+kp)&=(k-q-p)(x-p)\\ y-(-p^2+kp)&=(k-q-p)(0-p)\\ y+p^2-kp&=-kp+pq+p^2\\ y&=-p^2+kp-kp+pq+p^2\\ y&=pq\end{align*}\]
  
  The $y$-intercept of the line that intersects the parabola with equation $y=-x^2+kx$ at $x=p$ and at $x=q$ with $p\neq q$, is $pq$.
4. When the curve $x=\dfrac{1}{k^3}y^2+\dfrac{1}{k}y$ intersects the parabola with equation $y=-x^2+kx$, the $x$-coordinates of the two points of intersection ($(0,0)$ and $T$) satisfy the equation $x=\dfrac{1}{k^3}(-x^2+kx)^2+\dfrac{1}{k}(-x^2+kx)$, where $k\neq0$.
  
  Simplifying this equation, we get \[\begin{align*} x&=\dfrac{1}{k^3}(-x^2+kx)^2+\dfrac{1}{k}(-x^2+kx)\\ k^3x&=(-x^2+kx)^2+k^2(-x^2+kx)\\ k^3x&=x^4-2kx^3+k^2x^2-k^2x^2+k^3x\\ 0&=x^4-2kx^3\\ 0&=x^3(x-2k)\end{align*}\]
  
  Since $x^3(x-2k)=0$, then the $x$-coordinates of the points of intersection of the curve and the parabola are $x=0$ and $x=2k$.
  
  Therefore, the $x$-coordinate of point $T$ is $x=2k$, and the $y$-coordinate of $T$ is $-(2k)^2+k(2k)=-4k^2+2k^2=-2k^2$.
  
  Since the $y$-coordinate of point $T$ does not contain a linear term in the variable $k$ and does not contain a constant term, then the equation of the parabola on which all such points $T$ lie, contains a quadratic term only.
  
  That is, all points $T(2k,-2k^2)$ lie on a parabola with an equation of the form $y=ax^2$.
  
  Substituting, we get $-2k^2=a(2k)^2$ or $-2k^2=4ak^2$ or $-2=4a$ (since $k\neq0$), and so $a=-\dfrac12$.
  
  (We may verify that $x=2k$ and $y=-2k^2$ satisfies $y=ax^2+bx+c$ only if $a=-\dfrac12$ and $b=c=0$.) Therefore, the equation of the required parabola is $y=-\dfrac{1}{2}x^2$.

Let $N=abcdefghi$ be the largest 9-digit zigzag number.

We will determine $N$ by assigning each of the digits $1,2,3,4,5,6,7,8,$ and 9 to $a,b,c,d,e,f,g,h,$ and $i$.

We begin by trying to construct a zigzag number with $a=9$, since any other choice will give us a smaller zigzag number.

It cannot be that $b=8$ since any of the remaining possible choices for $c$ gives $a>b>c$.

That is, the middle of the first three adjacent digits would be less than the first digit and greater than the third digit.

In our attempt to find the maximum possible zigzag number, we choose $b$ to equal the next largest possible number, $7$.

Since $a>b$, then it must be that $b<c$, which means that $c=8$ (since 9 has already been assigned).

At this point, we have \[N=978defghi.\] If the largest 9-digit zigzag number starts with 9, then it must begin with 978.

We continue to assign values to digits, ensuring that for each group of three adjacent digits, either the middle digit is greater than each of the other two digits or the middle digit is less than each of the other two digits.

Since $b<c$, then $c>d$.

This tells us that $d<e$ and since $N$ is as large as possible, we choose $d=5$ and $e=6$ to give \[N=97856fghi.\] Since $d<e$, then $e>f$ and thus $f<g$.

Of the remaining digits, we choose $f=3$ and $g=4$ to make $N$ as large as possible.

Finally, since $f<g$, then $g>h$ and thus $h<i$ so we choose $h=1$ and $i=2$. Therefore, the largest 9-digit zigzag number is $N=978563412$.
We proceed by proving several facts.

Fact 1: $G(6,2)=L(6,5)$

Consider a 6-digit zigzag number counted by $G(6,2)$, say $n=251634$.

We form a new 6-digit number by subtracting each of the digits of $n$ from 7 to obtain $N = 526143$. Note that $N$ is a 6-digit zigzag number and one that is counted by $L(6,5)$.

Consider now an arbitrary 6-digit zigzag number counted by $G(6,2)$, say $n=2bcdef$, where $b,c,d,e,f$ are the digits $1,3,4,5,6$ in some order so that $2<b$, $b>c$, $c<d$, $d>e$, and $e<f$.

We form a new 6-digit number by subtracting each of the digits of $n$ from 7 to obtain $N=5(7-b)(7-c)(7-d)(7-e)(7-f)$.

Since $b,c,d,e,f$ are the digits $1,3,4,5,6$ in some order, then $7-b,7-c,7-d,7-e,7-f$ are the digits $6,4,3,2,1$ in some order.

Since $2<b$, then $-2>-b$ and so $7-2>7-b$ or $5>7-b$.

Since $b>c$, then $-b<-c$ and so $7-b<7-c$.

Similarly, $7-c>7-d$ and $7-d<7-e$ and $7-e>7-f$.

Therefore, $N$ is a 6-digit zigzag number and one that is counted by $L(6,5)$.

Also, if $2bcdef$ and $2BCDEF$ are two different zigzag numbers counted by $G(6,2)$, then one of the following must be true: $b \neq B$ or $c \neq C$ or $d \neq D$ or $e \neq E$ or $f \neq F$.

This means that $5(7-b)(7-c)(7-d)(7-e)(7-f)$ and $5(7-B)(7-C)(7-D)(7-E)(7-F)$ will be different numbers counted by $G(6,2)$ as at least one pair of corresponding digits will be unequal.

In other words, each zigzag number counted by $G(6,2)$ corresponds to a different zigzag number counted by $L(6,5)$, and so $G(6,2) \leq L(6,5)$. (There could be zigzag numbers counted by $L(6,5)$ that are not achieved by using this process.)

However, we can apply the same process to an arbitrary zigzag number counted by $L(6,5)$ to obtain one counted by $G(6,2)$, and thus show that $L(6,5) \leq G(6,2)$.

In other words, $G(6,5)=L(6,2)$.

Fact 2: $G(6,a)=L(6,7-a)$ for $a=1,2,3,4,5,6$

Using a similar argument to that in Fact #1, we can show that $G(6,a)=L(6,7-a)$ for each of $a=1,2,3,4,5,6$.

We can now prove the statement from (ii): \[\begin{align*} & \hspace{0.5cm} G(6,1)+G(6,2)+G(6,3)+G(6,4)+G(6,5)+G(6,6) \\ & = L(6,6)+L(6,5)+L(6,4)+L(6,3)+L(6,2)+L(6,1) \\ & = L(6,1)+L(6,2)+L(6,3)+L(6,4)+L(6,5)+L(6,6)\end{align*}\] as required.

We note further that we can generalize Fact 2 in a way that will be useful in (c).

Fact 3: $G(n,a)=L(n,n+1-a)$ for each pair of integers $a$ and $n$ with $1 \leq a \leq n \leq 9$

To see this, we use a similar argument to that from Fact 1, instead subtracting each digit of a zigzag number counted by $G(n,a)$ from $n+1$ to obtain a corresponding zigzag number counted by $L(n,(n+1)-a)$.

We now prove that $G(6,3)=L(5,3)+L(5,4)+L(5,5)$.

Fact 4: The number of zigzag numbers of the form $35cdef$ equals $L(5,4)$

We use $G(6,35)$ to represent the number of zigzag numbers of the form $35cdef$. (We will use analogous notation later as well.)

Consider a 6-digit zigzag number counted by $G(6,35)$, say $n=351624$.

We form a 5-digit number by deleting the first digit of $n$ to obtain $51624$ and then replacing the 4, 5 and 6 with 3, 4 and 5, respectively, to obtain $N=41523$.

Note that $N$ is a 5-digit zigzag number and one that is counted by $L(5,4)$.

Consider now an arbitrary 6-digit zigzag number counted by $G(6,35)$, say $n=35cdef$, where $c,d,e,f$ are the digits $1,2,4,6$ in some order so that $3<5$, $5>c$, $c<d$, $d>e$, and $e<f$.

We form a new 6-digit number by deleting the first digit of $n$ to obtain $5cdef$ (whose digits are $1,2,4,5,6$ in some order).

Note that we have $5>c$ and $c<d$ and $d>e$ and $e<f$.

We then replace the digits $4,5,6$ with $3,4,5$ respectively to obtain $4c'd'e'f'$.

Since the digits of the $5cdef$ are $1,2,4,5,6$ and the digits of $4c'd'e'f'$ are $1,2,3,4,5$ (arranged in the same order), then we have not changed the relative ordering of the digits of the number, so we will still have $5>c'$ and $c'<d'$ and $d'>e'$ and $e'<f'$.

Therefore, $N$ is a 5-digit zigzag number and one that is counted by $L(5,4)$.

Also, if $35cdef$ and $35CDEF$ are two different zigzag numbers counted by $G(6,3)$, then one of the following must be true: $b \neq B$ or $c \neq C$ or $d \neq D$ or $e \neq E$ or $f \neq F$.

This means that $4c'd'e'f'$ and $4C'D'E'F'$ will be different numbers counted by $L(5,4)$. (For example, if $c'=C'$, then we must have had $c=C$.)

In other words, each zigzag number counted by $G(6,35)$ corresponds to a different zigzag number counted by $L(5,4)$, and so $G(6,35) \leq L(5,4)$.

However, we can apply the reverse process to an arbitrary zigzag number counted by $L(5,4)$ (change $3,4,5$ to $4,5,6$ and put a 3 on the front) to obtain one counted by $G(6,35)$, and thus show that $L(5,4) \leq G(6,35)$.

In other words, $G(6,35)=L(5,4)$.

Fact 5: $G(6,3a)=L(5,a-1)$ for each of $a=4,5,6$

Using a similar argument to that in Fact #4, we can show that $G(6,3a)=L(5,a-1)$ for each of $a=4,5,6$.

We can now prove the statement from (i), noting that the second digit of a zigzag number counted by $G(6,3)$ must be 4, 5 or 6 and so each zigzag number counted by $G(6,3)$ must be of the form $34cdef$ or $35cdef$ or $36cdef$: \[G(6,3) = G(6,34)+G(6,35)+G(6,36) = L(5,3)+L(5,4)+L(5,5)\] as required.

Before concluding (b), we note the following generalization of Fact 5 that will be useful in (c):

Fact 6: $G(n,ab)=L(n-1,b-1)$ for all integers $n,a,b$ with $1 \leq a < b \leq n \leq 9$ To see this, we use a similar argument to that from Fact 5, again removing the first digit $a$ and reducing all digits from $a+1$ to $n$, inclusive, by 1 to obtain digits $a$ to $n-1$.

Let $T$ be the total number of 8-digit zigzag numbers. An 8-digit zigzag number starts with one of $1,2,3,4,5,6,7,8$ and its second digit is either less than or greater than its first digit.

Therefore, $T$ equals the sum of \[\ell = L(8,1)+L(8,2)+L(8,3)+L(8,4)+L(8,5)+L(8,6)+L(8,7)+L(8,8)\] and \[g= G(8,1)+G(8,2)+G(8,3)+G(8,4)+G(8,5)+G(8,6)+G(8,7)+G(8,8)\] From Fact 3, $L(8,1)=G(8,8)$ and $L(8,2)=G(8,7)$ and $L(8,3)=G(8,6)$ and so on.

Therefore, \[\ell = G(8,8)+G(8,7)+G(8,6)+G(8,5)+G(8,4)+G(8,3)+G(8,2)+G(8,1) = g\] and so $T = 2(G(8,1)+G(8,2)+G(8,3)+G(8,4)+G(8,5)+G(8,6)+G(8,7)+G(8,8))$.

We calculate the value of each of the terms on the right side by building a table of values of $G(n,k)$ for $3 \leq n \leq 8$ and $1 \leq k \leq 8$.

Note that if $k \geq n$, then $G(n,k)=0$ as no $n$-digit zigzag number can begin with $k>n$ and if $k = n$, an $n$-digit zigzag number starting with $n=k$ cannot have its second digit greater than its first.

Also, the only 3-digit zigzag numbers are 132, 231, 213 and 312 because the two other ways of arranging the digits 1, 2 and 3 (123 and 321) do not satisfy the zigzag property.

Thus $G(3,1)=1$, $G(3,2)=1$ and $G(3,3)=0$. This gives us the following start to the table:

	$\boldsymbol{k=1}$	$\boldsymbol{k=2}$	$\boldsymbol{k=3}$	$\boldsymbol{k=4}$	$\boldsymbol{k=5}$	$\boldsymbol{k=6}$	$\boldsymbol{k=7}$	$\boldsymbol{k=8}$
$\boldsymbol{n=3}$	1	1	0	0	0	0	0	0
$\boldsymbol{n=4}$				0	0	0	0	0
$\boldsymbol{n=5}$					0	0	0	0
$\boldsymbol{n=6}$						0	0	0
$\boldsymbol{n=7}$							0	0
$\boldsymbol{n=8}$								0

To complete the table, we build a relationship between the values of $G$ in one row and the values of $G$ in the previous row.

For a positive digit $n$ with $4 \leq n \leq 8$ and a positive digit $k < n$, we have: \[\begin{align*} G(n,k) & = G(n,k(k+1)) + G(n,k(k+2)) + \cdots + G(n,k(n-1)) + G(n,kn) \\ & \hspace{2cm}\mbox{(since the second digit must be larger than $k$)} \\ & = L(n-1,k) + L(n-1,k+1) + \cdots + L(n-1,n-2) + L(n-1,n-1) \quad\mbox{(by Fact 6)} \\ & = G(n-1,n-k) + G(n-1,n-k-1) + \cdots + G(n-1,2) + G(n-1,1) \quad \mbox{(by Fact 3)}\end{align*}\] Using this formula, \[\begin{align*} G(4,1) & = G(3,3)+G(3,2)+G(3,1)=2 \\ G(4,2) & = G(3,2)+G(3,1) = 2 \\ G(4,3) & = G(3,1) = 1 \\ G(5,1) & = G(4,4)+G(4,3)+G(4,2)+G(4,1)=5 \\ G(5,2) & = G(4,3)+G(4,2)+G(4,1)=5 \\ G(5,3) & = G(4,2)+G(4,1)=4 \\ \vdots &\end{align*}\]

Proceeding in this way, we complete the table row by row and obtain:

	$\boldsymbol{k=1}$	$\boldsymbol{k=2}$	$\boldsymbol{k=3}$	$\boldsymbol{k=4}$	$\boldsymbol{k=5}$	$\boldsymbol{k=6}$	$\boldsymbol{k=7}$	$\boldsymbol{k=8}$
$\boldsymbol{n=3}$	1	1	0	0	0	0	0	0
$\boldsymbol{n=4}$	2	2	1	0	0	0	0	0
$\boldsymbol{n=5}$	5	5	4	2	0	0	0	0
$\boldsymbol{n=6}$	16	16	14	10	5	0	0	0
$\boldsymbol{n=7}$	61	61	56	46	32	16	0	0
$\boldsymbol{n=8}$	272	272	256	223	178	122	61	0

Finally, $T = 2(272+272+256+224+178+122+61)=2770$, and so the number of 8-digit zigzag numbers is 2770.

	\(\boldsymbol{k=1}\)	\(\boldsymbol{k=2}\)	\(\boldsymbol{k=3}\)	\(\boldsymbol{k=4}\)	\(\boldsymbol{k=5}\)	\(\boldsymbol{k=6}\)	\(\boldsymbol{k=7}\)	\(\boldsymbol{k=8}\)
\(\boldsymbol{n=3}\)	1	1	0	0	0	0	0	0
\(\boldsymbol{n=4}\)				0	0	0	0	0
\(\boldsymbol{n=5}\)					0	0	0	0
\(\boldsymbol{n=6}\)						0	0	0
\(\boldsymbol{n=7}\)							0	0
\(\boldsymbol{n=8}\)								0

2017 Hypatia Contest Solutions (Grade 11)

2017 Hypatia Contest
Solutions
(Grade 11)