2020 Hypatia Contest
Solutions
(Grade 11)

Wednesday, April 15, 2020 (in North America and South America)

Thursday, April 16, 2020 (outside of North American and South America)

©2020 University of Waterloo

1. 1. The cost of 12 bags of avocados is $\mathrm{\$}5.00\times 12=\mathrm{\$}60.00$.

      Thus, the chef spent $\mathrm{\$}135.00-\mathrm{\$}60.00=\mathrm{\$}75.00$ on mangoes. The cost of each box of mangoes is $\mathrm{\$}12.50$, and so the chef purchased ${\displaystyle \frac{\mathrm{\$}75.00}{\mathrm{\$}12.50}}=6$ boxes of mangoes.

   2. Solution 1

      A bag of avocados sells for $5.00, and so a 10% discount represents a savings of $\frac{10}{100}\times \mathrm{\$}5.00$ or $0.10\times \mathrm{\$}5.00$ which equals $\mathrm{\$}0.50$.

      Thus, the discounted price for a bag of avocados is $\mathrm{\$}5.00-\mathrm{\$}0.50=\mathrm{\$}4.50$.

      A box of mangoes sells for $12.50, and so a 20% discount represents a savings of $\frac{20}{100}\times \mathrm{\$}12.50$ or $0.20\times \mathrm{\$}12.50$ which equals $\mathrm{\$}2.50$.

      Thus, the discounted price for a box of mangoes is $\mathrm{\$}12.50-\mathrm{\$}2.50=\mathrm{\$}10.00$. On Saturdays, the total cost for 8 bags of avocados and 4 boxes of mangoes is $$\mathrm{\$}4.50\times 8+\mathrm{\$}10.00\times 4=\mathrm{\$}36.00+\mathrm{\$}40.00=\mathrm{\$}76.00$$

      Solution 2

      A bag of avocados sells for $5.00, and so a 10% discount is equivalent to paying $100\mathrm{\%}-10\mathrm{\%}=90\mathrm{\%}$ of the regular price.

      Thus, the discounted price for a bag of avocados is $\frac{90}{100}\times \mathrm{\$}5.00=0.90\times \mathrm{\$}5.00=\mathrm{\$}4.50$.

      A box of mangoes sells for $12.50, and so a 20% discount is equivalent to paying $100\mathrm{\%}-20\mathrm{\%}=80\mathrm{\%}$ of the regular price.

      Thus, the discounted price for a box mangoes is $\frac{80}{100}\times \mathrm{\$}12.50=0.80\times \mathrm{\$}12.50=\mathrm{\$}10.00$. On Saturdays, the total cost for 8 bags of avocados and 4 boxes of mangoes is $$\mathrm{\$}4.50\times 8+\mathrm{\$}10.00\times 4=\mathrm{\$}36.00+\mathrm{\$}40.00=\mathrm{\$}76.00$$

   3. Avocados are sold in bags of 6 and the chef needs 100 avocados.

      Since $6\times 16=96$ and $6\times 17=102$, the chef will need to purchase 17 bags of avocados (16 bags is not enough).

      Mangoes are sold in boxes of 15 and the chef needs 70 mangoes.

      Since $15\times 4=60$ and $15\times 5=75$, the chef will need to purchase 5 boxes of mangoes. The total cost of the purchase was $\mathrm{\$}5.00\times 17+\mathrm{\$}12.50\times 5=\mathrm{\$}85.00+\mathrm{\$}62.50=\mathrm{\$}147.50$.

   4. Avocados are sold for $5.00 per bag, and so the cost to purchase any number of bags is a whole number.

      Mangoes are sold for $12.50 per box, and so the cost to purchase mangoes is a whole number only when an even number of boxes are bought (1 box costs $12.50, 2 boxes cost $25.00, 3 boxes cost $37.50, and so on).

      Since the chef spends exactly $75.00 (a whole number), then the chef must purchase an even number of boxes of mangoes.

      If the chef purchases 2 boxes of mangoes, the cost is $25.00, which leaves $\mathrm{\$}75.00-\mathrm{\$}25.00=\mathrm{\$}50.00$ to be used to purchase $\mathrm{\$}50.00÷\mathrm{\$}5.00=10$ bags of avocados.

      In this case, the chef has $10\times 6=60$ avocados and $2\times 15=30$ mangoes.

      Each tart requires 1 avocado and 2 mangoes and so the chef can make $30÷2=15$ tarts (he has more than 15 avocados but only 30 mangoes).

      If the chef purchases 4 boxes of mangoes, the cost is $4\times \mathrm{\$}12.50=\mathrm{\$}50.00$, which leaves $\mathrm{\$}75.00-\mathrm{\$}50.00=\mathrm{\$}25.00$ to be used to purchase $\mathrm{\$}25.00÷\mathrm{\$}5.00=5$ bags of avocados.

      In this case, the chef has $5\times 6=30$ avocados and $4\times 15=60$ mangoes.

      Each tart requires 1 avocado and 2 mangoes and so the chef can make 30 tarts.

      If the chef purchases 6 boxes of mangoes, the cost is $6\times \mathrm{\$}12.50=\mathrm{\$}75.00$, which leaves no money to purchase avocados.

      Purchasing more than 6 boxes of mangoes will cost the chef more than $75.00. Therefore, if the chef purchases 30 avocados (5 bags) and 60 mangoes (4 boxes), she will have spent exactly $75.00, have twice as many mangoes as avocados, and be able to make the greatest number of tarts, 30.

2. 1. The parabola $y=\frac{1}{4}{x}^2$ and the parabolic rectangle are each symmetrical about the $y$-axis, and thus a second vertex of the rectangle lies on the parabola and has coordinates $(-6,9)$.

      A third vertex of the parabolic rectangle lies on the $x$-axis vertically below $(6,9)$, and thus has coordinates $(6,0)$. Similarly, the fourth vertex also lies on the $x$-axis vertically below $(-6,9)$, and thus has coordinates $(-6,0)$.

   2. If one vertex of a parabolic rectangle is $(-3,0)$, then a second vertex has coordinates $(3,0)$, and so the rectangle has length 6.

      The vertex that lies vertically above $(3,0)$ has $x$-coordinate 3.

      This vertex lies on the parabola $y=\frac{1}{4}{x}^2$ and thus has $y$-coordinate equal to $\frac{1}{4}(3{)}^2=\frac{9}{4}$.

      The width of the rectangle is equal to this $y$-coordinate $\frac{9}{4}$, and so the area of the parabolic rectangle having one vertex at $(-3,0)$ is $6\times \frac{9}{4}=\frac{54}{4}=\frac{27}{2}$.

   3. Let a vertex of the parabolic rectangle be the point $(p,0)$, with $p>0$.

      A second vertex (also on the $x$-axis) is thus $(-p,0)$, and so the rectangle has length $2p$.

      The width of this rectangle is given by the $y$-coordinate of the point that lies on the parabola vertically above $(p,0)$, and so the width is $\frac{1}{4}{p}^2$.

      The area of a parabolic rectangle having length $2p$ and width $\frac{1}{4}{p}^2$ is $2p\times \frac{1}{4}{p}^2=\frac{1}{2}{p}^3$.

      If such a parabolic rectangle has length 36, then $2p=36$, and so $p=18$.

      The area of this rectangle is $\frac{1}{2}(18{)}^3=2916$.

      If such a parabolic rectangle has width 36, then $\frac{1}{4}{p}^2=36$ or $p^2=144$, and so $p=12$ (since $p>0$).

      The area of this rectangle is $\frac{1}{2}(12{)}^3=864$. The areas of the two parabolic rectangles that have side length 36 are 2916 and 864.

   4. Let a vertex of the parabolic rectangle be the point $(m,0)$, with $m>0$.

      A second vertex (also on the $x$-axis) is thus $(-m,0)$, and so the rectangle has length $2m$.

      The width of this rectangle is given by the $y$-coordinate of the point that lies on the parabola vertically above $(m,0)$, and so the width is $\frac{1}{4}{m}^2$.

      The area of a parabolic rectangle having length $2m$ and width $\frac{1}{4}{m}^2$ is $2m\times \frac{1}{4}{m}^2=\frac{1}{2}{m}^3$.

      If the length and width of such a parabolic rectangle are equal, then $$\begin{array}{rl}\frac{1}{4}{m}^2& =2m\\ m^2& =8m\\ m^2-8m& =0\\ m(m-8)& =0\end{array}$$ Thus $m=8$ (since $m>0$), and so the area of the parabolic rectangle whose length and width are equal is $\frac{1}{2}(8{)}^3=256$.

3. 1. For $n\ge 3$ and $k\ge 0$, the value of $T(n,k)$ is constant for all possible locations of the $k$ interior points and all possible triangulations. Thus, we may use the triangulation shown to determine that $T(3,2)=5$.

   

   2. We begin by drawing triangulations to determine the values of $T(4,k)$ for $k=0,1,2,3$.

      
      Hide/Reveal Descriptions of Triangulations

      A series of four diagrams, where each diagram is built from the previous diagram in the series.

      1. The first diagram illustrates that $T(4,0)=2$. It is a square with one diagonal drawn dividing the interior into two triangular regions.
      2. The second diagram illustrates that $T(4,1)=4$. One interior point has been added to one of the two triangular regions of the first diagram, and this point is connected to each of the three vertices of that region. The interior of the square is now divided into 4 triangular regions.
      3. The third diagram illustrates that $T(4,2)=6$. An interior point has been added to the other triangular region of the first diagram, and this point is connected to each of the three vertices of that region. The interior of the square is now divided into 6 triangular regions.
      4. The fourth diagram illustrates that $T(4,3)=8$. An interior point has been added to one of the 6 triangular regions of the third diagram, and this point is connected to each of the three vertices of that region. The interior of the square is now divided into 8 triangular regions.

      ---

      Although we would obtain these same four answers by positioning the interior points in different locations, or by completing the triangulations in different ways, the diagrams above were created to help visualize a pattern.

      From the answers shown, we see that $T(4,k+1)=T(4,k)+2$, for $k=0,1,2$.

      We must justify why this observation is true for all $k\ge 0$ so that we may use the result to determine the value of $T(4,100)$.

      Notice that each triangulation (after the first) was created by placing a new interior point inside the previous triangulation.

      Further, each square is divided into triangles, and so each new interior point is placed inside a triangle of the previous triangulation (since no 3 points may lie on the same line).

      For example, in the following diagrams, we observe that $P$ lies in triangle $t$ of the previous triangulation.

      

      Also, each of the triangles outside of $t$ is untouched by the addition of $P$, and thus they continue to contribute the same number of triangles (5) to the value of $T(4,3)$ as they did to the value of $T(4,2)$.

      Triangle $t$ contributes 1 to the value of $T(4,2)$.

      To triangulate the region defined by triangle $t$, $P$ must be joined to each of the 3 vertices of triangle $t$ (no other triangulation of this region is possible).

      Thus, the placement of $P$ divides triangle $t$ into 3 triangles for every possible location of $P$ inside triangle $t$.

      That is, $t$ contributes 1 to the value of $T(4,2)$, but the region defined by $t$ contributes 3 to the value of $T(4,3)$ after the placement of $P$. To summarize, the value of $T(4,k+1)$ is 2 more than the value of $T(4,k)$ for all $k\ge 0$ since:

      • the $(k+1{)}^{st}$ interior point may be placed anywhere inside the triangulation for $T(4,k)$ (provided it is not on an edge)

      • specifically, the $(k+1{)}^{st}$ interior point lies inside a triangle of the triangulation which gives $T(4,k)$

      • this triangle contributed 1 to the value of $T(4,k)$

      • after the $(k+1{)}^{st}$ interior point is placed inside this triangle and joined to each of the 3 vertices of the triangle, this area contributes 3 to the value of $T(4,k+1)$

      • this is a net increase of 2 triangles, and thus $T(4,k+1)=T(4,k)+2$, for all $k\ge 0$.

      $T(4,0)=2$ and each additional interior point increases the number of triangles by 2.

      Thus, $k$ additional interior points increases the number of triangles by $2k$, and so $T(4,k)=T(4,0)+2k=2+2k$ for all $k\ge 0$. Using this formula, we get $T(4,100)=2+2(100)=202$.

   3. In the triangulation of a regular $n$-gon with no interior points, we may choose any one of the $n$ vertices and join this vertex to each of the remaining $n-3$ non-adjacent vertices.

      All such triangulations of a regular $n$-gon with no interior points creates $n-2$ triangles, and so $T(n,0)=n-2$ for all $n\ge 3$ (since $T(n,0)$ is constant).

      The reasoning used in part (b) extends to any regular polygon having $n\ge 3$ vertices.

      That is, each additional interior point that is added to the triangulation for $n\ge 3$ vertices and $k\ge 0$ interior points gives a net increase of 2 triangles.

      Thus, $T(n,k+1)=T(n,k)+2$ for all regular polygons having $n\ge 3$ vertices and $k\ge 0$ interior points.

      So then $k$ additional interior points increases the number of triangles by $2k$, and so $T(n,k)=T(n,0)+2k=(n-2)+2k$ for all $k\ge 0$. Using this formula $T(n,k)=(n-2)+2k$, we get $T(n,n)=(n-2)+2n=3n-2$ and $3n-2=2020$ when $n=\frac{2022}{3}=674$.

4. 1. Solution 1

      If $x_0$ is even, then $x_0^2$ is even, and so $x_1=x_0^2+1$ is odd.

      If $x_1$ is odd, then $x_1^2$ is odd, and so $x_2=x_1^2+1$ is even.

      Thus if $x_0$ is even, then $x_2$ is even and so $x_2-x_0$ is even.

      If $x_0$ is odd, then $x_0^2$ is odd, and so $x_1=x_0^2+1$ is even.

      If $x_1$ is even, then $x_1^2$ is even, and so $x_2=x_1^2+1$ is odd.

      Thus if $x_0$ is odd, then $x_2$ is odd and so $x_2-x_0$ is even.

      Therefore, for all possible values of $x_0$, $x_2-x_0$ is even.

      Solution 2

      Using the definition twice and simplifying, we get $$\begin{array}{rl}{x}_2& =(x_1{)}^2+1\\ x_2& =((x_0{)}^2+1{)}^2+1\\ x_2& =(x_0{)}^4+2(x_0{)}^2+2\\ x_2& =(x_0{)}^4+2((x_0{)}^2+1)\\ x_2-x_0& =(x_0{)}^4+2((x_0{)}^2+1)-x_0\end{array}$$ To show that $x_2-x_0$ is even, we may show that $(x_0{)}^4+2((x_0{)}^2+1)-x_0$ is even (since the expressions are equal).

      Since $2((x_0{)}^2+1)$ is the product of some integer and 2, this term is even for all possible values of $x_0$.

      If $x_0$ is even, then $(x_0{)}^4$ is even, and so $(x_0{)}^4+2((x_0{)}^2+1)-x_0$ is the sum and difference of three even terms and thus is even.

      If $x_0$ is odd, then $(x_0{)}^4$ is odd, $(x_0{)}^4-x_0$ is even, and so $(x_0{)}^4+2((x_0{)}^2+1)-x_0$ is even.

      Thus, $x_2-x_0$ is even for all possible values of $x_0$.

      Solution 3

      Using the definition twice and simplifying, we get $$\begin{array}{rl}{x}_2& =(x_1{)}^2+1\\ x_2& =((x_0{)}^2+1{)}^2+1\\ x_2& =(x_0{)}^4+2(x_0{)}^2+2\\ x_2-x_0& =(x_0{)}^4+2(x_0{)}^2-x_0+2\\ x_2-x_0& =(x_0{)}^4+(x_0{)}^2+(x_0{)}^2-x_0+2\\ x_2-x_0& =(x_0{)}^2((x_0{)}^2+1)+x_0(x_0-1)+2\end{array}$$ To show that $x_2-x_0$ is even, we may show that $(x_0{)}^2((x_0{)}^2+1)+x_0(x_0-1)+2$ is even (since they are equal).

      Since $x_0-1$ is one less than $x_0$, then $x_0$ and $x_0-1$ are consecutive integers and so one of them is even.

      Thus, the product $x_0(x_0-1)$ is even.

      Similarly, $(x_0{)}^2$ is one less than $(x_0{)}^2+1$, and thus these are consecutive integers and so one of them is even.

      Therefore, the product $(x_0{)}^2((x_0{)}^2+1)$ is even.

      Since $(x_0{)}^2((x_0{)}^2+1)+x_0(x_0-1)+2$ is the sum of three even integers, $x_2-x_0$ is even for all possible values of $x_0$.

   2. An integer is divisible by 10 exactly when its units (ones) digit is 0.

      The difference $x_{2026}-x_{2020}$ has units digit 0 exactly when $x_{2026}$ and $x_{2020}$ have equal units digits.

      Thus, we will show that for all possible values of $x_0$, the units digit of $x_{2026}$ is equal to the units digit of $x_{2020}$, and so $x_{2026}-x_{2020}$ is divisible by 10.

      When a non-negative integer is divided by 10, the remainder is one of the integers from 0 through 9, inclusive.

      Thus for every possible choice for $x_0$, there exists some non-negative integer $k$, so that $x_0$ can be expressed in exactly one of the following ways: $10k$, $10k+1$, $10k+2$, $\dots$, $10k+8$, $10k+9$.

      If for example $x_0$ has units digit 4, then $x_0=10k+4$ for some non-negative integer $k$, and so $x_1=(10k+4{)}^2+1=100k^2+80k+17=10(10k^2+8k+1)+7$, and thus has units digit 7.

      Since $x_1$ is determined by $x_0$ only ($x_1=(x_0{)}^2+1$), the units digit of $x_1$ is uniquely determined by the units digit of $x_0$.

      For example, if the units digit of $x_0$ is 4, then the units digit of $x_1$ is equal to the units digit of $(4{)}^2+1$, which equals 7.

      More generally, if the units digit of $x_i$ (for a non-negative integer $i$) is equal to $u$, then the units digit of $x_{i+1}$ is equal to the units digit of $u^2+1$.

      (Can you explain why this is true?)

      For example, if we know that $x_{15}=29$, then the units digit of $x_{16}$ is equal to the units digit of $9^2+1=82$, which is 2.

      Given that we know all possible units digits of $x_0$, this provides an efficient method for determining the units digits of $x_1$, $x_2$, $x_3$, and so on. In the table below, we list the units digits for the terms $x_1$ through $x_7$ for each of the 10 possible units digits of $x_0$, 0 through 9 inclusive.

      $x_0$	0	1	2	3	4	5	6	7	8	9
      $x_1$	1	2	5	0	7	6	7	0	5	2
      $x_2$	2	5	6	1	0	7	0	1	6	5
      $x_3$	5	6	7	2	1	0	1	2	7	6
      $x_4$	6	7	0	5	2	1	2	5	0	7
      $x_5$	7	0	1	6	5	2	5	6	1	0
      $x_6$	0	1	2	7	6	5	6	7	2	1
      $x_7$	1	2	5	0	7	6	7	0	5	2

      Looking at the table, we see that for each of the possible units digits for $x_0$, the units digit of $x_1$ is equal to the units digit of $x_7$.

      Thus beginning at $x_1$, each column in the table will repeat every 6 terms, and so independent of the starting value $x_0$, $x_{i+6}$ and $x_i$ have equal units digits for all integers $i\ge 1$. Since $2026-2020=6$, then $x_{2026}$ and $x_{2020}$ have equal units digits, and so $x_{2026}-x_{2020}$ has units digit 0, and thus is divisible by 10.

   3. Since $x_{115}-110=(x_{115}-5)-105$, then $x_{115}-110$ is divisible by 105 exactly when $x_{115}-5$ is divisible by 105.

      Further, $105=3\times 5\times 7$ and each of $3,5,7$ is a prime number, and so $x_{115}-5$ is divisible by 105 exactly when it is divisible by 3, 5 and 7.

      Every $x_i$ is a multiple of 3, 1 more than a multiple of 3, or 2 more than a multiple of 3.

      Suppose that $x_i$ is a multiple of 3. Then $x_i=3k$ for some non-negative integer $k$, and so $$x_{i+1}=(x_i{)}^2+1=(3k{)}^2+1=3(3k^2)+1$$ which is 1 more than a multiple of 3.

      If $x_i$ is 1 more than a multiple of 3, then $x_i=3k+1$ for some non-negative integer $k$, and so $$x_{i+1}=(x_i{)}^2+1=(3k+1{)}^2+1=9k^2+6k+2=3(3k^2+2k)+2$$ which is 2 more than a multiple of 3.

      If $x_i$ is 2 more than a multiple of 3, then $x_i=3k+2$ for some non-negative integer $k$, and so $$x_{i+1}=(x_i{)}^2+1=(3k+2{)}^2+1=9k^2+12k+5=3(3k^2+4k+1)+2$$ which is 2 more than a multiple of 3.

      Each possible choice of $x_0$ is a multiple of 3, 1 more than a multiple of 3, or 2 more than a multiple of 3.

      If $x_0$ is a multiple of 3, then $x_1$ is 1 more than a multiple of 3 and $x_2,x_3,x_4,\dots$ and so on are each 2 more than a multiple of 3.

      If $x_0$ is 1 or 2 more than a multiple of 3, then $x_1,x_2,x_3,x_4,\dots$ and so on are each 2 more than a multiple of 3.

      Therefore, $x_2,x_3,x_4,\dots$ and so on are all 2 more than a multiple of 3 (independent of $x_0$), and so for all $i\ge 2$, $x_i$ is a number of the form $3k+2$ for some non-negative integer $k$.

      Therefore, $x_{115}-5=3k+2-5=3(k-1)$ is divisible by 3 for all possible choices of $x_0=n$.

      Thus, we need to only determine when $x_{115}-5$ is divisible by 5 and 7.

      For which of the possible values of $x_0$ is $x_{115}-5$ divisible by 5?

      $x_{115}-5$ is divisible by 5 exactly when $x_{115}$ is divisible by 5.

      Every $x_i$ is either a multiple of 5, 1 more than a multiple of 5, 2 more than a multiple of 5, 3 more than a multiple of 5, or 4 more than a multiple of 5. With respect to division by 5, the table below gives the remainders of $x_{i+1}$ given each of the 5 possible remainders of $x_i$, 0 through 4 inclusive.

      $x_i$	$x_{i+1}=(x_i{)}^2+1$
      $5k$	$25k^2+1=5(5k^2)+1$
      $5k+1$	$25k^2+10k+2=5(5k^2+2k)+2$
      $5k+2$	$25k^2+20k+5=5(5k^2+4k+1)$
      $5k+3$	$25k^2+30k+10=5(5k^2+6k+2)$
      $5k+4$	$25k^2+40k+17=5(5k^2+8k+3)+2$

      From this table, we make the following observations:

      • if $x_i$ is a multiple of 5, then $x_{i+1}$ is 1 more than a multiple of 5

      • if $x_i$ is 1 more than a multiple of 5, then $x_{i+1}$ is 2 more than a multiple of 5

      • if $x_i$ is 2 more than a multiple of 5, then $x_{i+1}$ is a multiple of 5

      • if $x_i$ is 3 more than a multiple of 5, then $x_{i+1}$ is a multiple of 5

      • if $x_i$ is 4 more than a multiple of 5, then $x_{i+1}$ is 2 more than a multiple of 5

      Using these observations, we summarize the remainders of $x_1,x_2,x_3,x_4$ when dividing by 5 for each of the possible remainders for $x_0$.

      $x_0$	0	1	2	3	4
      $x_1$	1	2	0	0	2
      $x_2$	2	0	1	1	0
      $x_3$	0	1	2	2	1
      $x_4$	1	2	0	0	2

      With respect to division by 5, we see in the table above that for each of the possible remainders for $x_0$, the remainder for $x_1$ is equal to that of $x_4$.

      Thus beginning at $x_1$, each column in the table repeats every 3 terms, and so independent of the starting value $x_0$, $x_{i+3}$ and $x_i$ have equal remainders after division by 5 for all integers $i\ge 1$.

      Since $115=3(37)+4$, then $x_{115}$ and $x_4$ have the same remainders after division by 5, and so $x_{115}$ is divisible by 5 for all choices of $x_0=n$ which are either 2 more than a multiple of 5 or 3 more than a multiple of 5.

      Finally, we want to determine for which of the possible values of $x_0$ is $x_{115}-5$ divisible by 7.

      $x_{115}-5$ divisible by 7 exactly when $x_{115}$ is 5 more than a multiple of 7.

      Every $x_i$ is exactly one of: a multiple of 7, 1 more than a multiple of 7, 2 more than a multiple of 7, and so on up to 6 more than a multiple of 7. With respect to division by 7, the table below gives the remainders of $x_{i+1}$ given each of the 7 possible remainders of $x_i$, 0 through 6 inclusive.

      $x_i$	$x_{i+1}=(x_i{)}^2+1$
      $7k$	$49k^2+1=7(7k^2)+1$
      $7k+1$	$49k^2+14k+2=7(7k^2+2k)+2$
      $7k+2$	$49k^2+28k+5=7(7k^2+4k)+5$
      $7k+3$	$49k^2+42k+10=7(7k^2+6k+1)+3$
      $7k+4$	$49k^2+56k+17=7(7k^2+8k+2)+3$
      $7k+5$	$49k^2+70k+26=7(7k^2+10k+3)+5$
      $7k+6$	$49k^2+84k+37=7(7k^2+12k+5)+2$

      From this table, we make the following observations:

      • if $x_i$ is a multiple of 7, then $x_{i+1}$ is 1 more than a multiple of 7

      • if $x_i$ is 1 more than a multiple of 7, then $x_{i+1}$ is 2 more than a multiple of 7

      • if $x_i$ is 2 more than a multiple of 7, then $x_{i+1}$ is 5 more than a multiple of 7

      • if $x_i$ is 3 more than a multiple of 7, then $x_{i+1}$ is 3 more than a multiple of 7

      • if $x_i$ is 4 more than a multiple of 7, then $x_{i+1}$ is 3 more than a multiple of 7

      • if $x_i$ is 5 more than a multiple of 7, then $x_{i+1}$ is 5 more than a multiple of 7

      • if $x_i$ is 6 more than a multiple of 7, then $x_{i+1}$ is 2 more than a multiple of 7

      Using these observations, we summarize the remainders of $x_1,x_2,x_3,x_4$ when dividing by 7 for each of the possible remainders for $x_0$.

      $x_0$	0	1	2	3	4	5	6
      $x_1$	1	2	5	3	3	5	2
      $x_2$	2	5	5	3	3	5	5
      $x_3$	5	5	5	3	3	5	5
      $x_4$	5	5	5	3	3	5	5

      Looking at the table, we see that if $x_0$ is $0,1,2,5,$ or 6 more than a multiple of 7, then $x_i$ is 5 more than a multiple of 7 for all $i\ge 3$.

      Also, if $x_0$ is 3 or 4 more than a multiple of 7, then $x_i$ is 3 more than a multiple of 7 for all $i\ge 1$ (and thus never 5 more than a multiple of 7).

      Therefore, $x_{115}-5$ is a multiple of 7 exactly when $x_0$ is not 3 or 4 more than a multiple of 7.

      Summary: $x_{115}-110$ is divisible by 105 exactly when

      • $x_0$ is 2 or 3 more than a multiple of 5, and

      • $x_0$ is a multiple of 7 or $1,2,5,$ or 6 more than a multiple of 7.

      The values of $x_0$ in the range $1\le x_0\le 35$ satisfying these properties are: $$2,7,8,12,13,22,23,27,28,33$$ The values of $x_0$ in the range $36\le x_0\le 100$ satisfying these properties must each be a mutiple of $5\times 7=35$ greater than one the numbers in the above list.

      Thus, there are 10 possible values for $x_0$ in the original list, 10 more from $2+35=37$ to $33+35=68$, and 9 more from $2+2(35)=72$ to $28+2(35)=98$, so 29 in total (note that $33+2(35)>100$). If Parsa chooses an integer $n$ with $1\le n\le 100$ at random and sets $x_0=n$, the probability that $x_{115}-110$ is divisible by 105 is $\frac{29}{100}$.