Problem of the Month 2022-2023

Problem 0: September 2022

Problem

1. Consider the integers $392$, $487$, $638$, and $791$. For each of these integers, do the following.

   1. Determine whether the integer is a multiple of $7$.

   2. With the hundreds digit equal to $A$, the tens digit equal to $B$, and the units digit equal to $C$, compute $2A+3B+C$.

   What do you notice?

2. Suppose $n=ABC$ is a three-digit integer ($A$ is the hundreds digit, $B$ is the tens digit, and $C$ is the units digit). Show that if $ABC$ is a multiple of $7$, then $2A+3B+C$ is a multiple of $7$.

3. Show that if $2A+3B+C$ is a multiple of $7$, then the three-digit integer $n=ABC$ is a multiple of $7$.

4. Suppose $ABCDEF$ is a six-digit integer that has each of its digits different from $0$. Show that $ABCDEF$ is a multiple of $7$ if and only if $BCDEFA$ is a multiple of $7$.

5. Think of ways to generalize the fact in part (d).

Hint

1. No hint given.

2. What are the remainders when $100$ and $10$ are divided by $7$?

3. No hint given.

4. Try to find a condition on six-digit integers that detects divisibility by $7$. There is a well-known general test for divisibility by $7$, but it will be useful to find another one that is specific to six-digit integers and similar to the condition for three-digit integers implied by (b) and (c).

Solution

1. In the table below, the first column contains the four integers given in the problem, the middle column says whether that integer is a multiple of $7$, and the third column contains the value of $2A+3B+C$.

   $\mathit{A}\mathit{B}\mathit{C}$	Multiple of 7?	$\mathbf{2}\mathit{A}\mathbf{+}\mathbf{3}\mathit{B}\mathbf{+}\mathit{C}$
   $392$	yes ($7\times 56$)	$35$
   $487$	no	$39$
   $638$	no	$29$
   $791$	yes ($7\times 113$)	$42$

   The two integers that are multiples of $7$ have the property that $2A+3B+C$ is also a multiple of $7$, and the two integers that are not multiples of $7$ have the property that $2A+3B+C$ is not a multiple of $7$.

2. The integer $ABC$ is equal to $100A+10B+C$. Observe that $100=7\times 14+2$ and $10=7+3$, so we have that $$\begin{array}{rl}ABC& =100A+10B+C\\ & =[7(14)+2]A+(7+3)B+C\\ & =7(14A+B)+(2A+3B+C)\end{array}$$ which can then be rearranged to get $ABC-7(14A+B)=2A+3B+C$.

   We are assuming that $ABC$ is a multiple of $7$, so the expression $2A+3B+C$ is equal to the difference of two multiples of $7$, and so it must be a multiple of $7$.

3. Using the calculation from part (b), $ABC=7(14A+B)+2A+3B+C$ for any three-digit positive integer $ABC$. If $2A+3B+C$ is a multiple of $7$, then $ABC$ is the sum of two multiples of $7$ and so must be a multiple of $7$.

4. The combined result of parts (b) and (c) is that a three-digit integer $ABC$ is a multiple of $7$ if and only if the integer $2A+3B+C$ is a multiple of $7$. To answer the question in this part, we will first establish a similar fact about six-digit integers.

   To do this, we first divide each of $10$, ${10}^2$, ${10}^3$, ${10}^4$, and ${10}^5$ by $7$ to find the quotient and remainder. $$\begin{array}{rl}10& =7+3\\ {10}^2& =7(14)+2\\ {10}^3& =7(142)+6\\ {10}^4& =7(1428)+4\\ {10}^5& =7(14285)+5\end{array}$$

   Since $ABCDEF=A\times {10}^5+B\times {10}^4+C\times {10}^3+D\times {10}^2+E\times 10+F$, we can substitute the equations above and rearrange to get that $$ABCDEF=7(14285A+1428B+142C+14D+E)+(5A+4B+6C+2D+3E+F)$$ and since $7(14285A+1428B+142C+14D+E)$ is a multiple of $7$, a similar argument to those used in parts (b) and (c) imply that the integer $ABCDEF$ is a multiple of $7$ if and only if the quantity $5A+4B+6C+2D+3E+F$ is a multiple of $7$.

   We will now prove that $ABCDEF$ is a multiple of $7$ if and only if $BCDEFA$ is a multiple of $7$. First, assume that $ABCDEF$ is a multiple of $7$. By the fact established above, the integer $5A+4B+6C+2D+3E+F$ is a multiple of $7$. Though it may seem like a strange observation, this implies that $3(5A+4B+6C+2D+3E+F)$ must be a multiple of $7$. Expanding and grouping some terms, we have $$\begin{array}{rl}3(5A+4B+6C+2D+3E+F)& =15A+12B+18C+6D+9E+3F\\ & =(14A+7B+14C+7E)\\ & +(A+5B+4C+6D+2E+3F)\\ & =7(2A+B+2C+E)\\ & +(5B+4C+6D+2E+3F+A)\end{array}$$ and so $7(2A+B+2C+E)+(5B+4C+6D+2E+3F+A)$ is a multiple of $7$. This implies that $5B+4C+6D+2E+3F+A$ is a multiple of $7$, and by the fact established above, the six-digit integer $BCDEFA$ is a multiple of $7$.

   We now suppose that $BCDEFA$ is a multiple of $7$. We have already shown above that if the digits are "cycled" to the left, then the integer obtained is also a multiple of $7$. Applying this several times, we have that $CDEFAB$ is a multiple of $7$, as are $DEFABC$, $EFABCD$, $FABCDE$, and finally $ABCDEF$.

   As an example, you can verify for yourself that $314517$ is a multiple of $7$, and so are each of $145173$, $451731$, $517314$, $173145$, and $731451$. Similarly, the integer $215739$ is not a multiple of $7$, and neither are any of $157392$, $573921$, $739215$, $392157$, and $921573$.

   Note: The assumption that none of the digits of $ABCDEF$ are zero implies that each of the integers obtained by cycling the digits is a six-digit integer. If we were to allow digits equal to $0$, the claim remains true, but in practice we may need to include "leading zeros". For example, cycling the digits of the integer $300412$ in this way would lead to $004123$ (which is really a four-digit integer), then $041230$, $412300$, $123004$, and so on.

5. While we will not include proofs here, we will list a few ways that the result in (d) can be generalized.

   • If the number of digits in an integer is any positive multiple of $6$, then the result of part (d) still holds. That is, if $n$ has $6k$ digits for some $k\ge 1$, then $n$ is a multiple of $7$ if and only if the integer obtained by cycling its digits is a multiple of $7$.

   • For any prime number $p$, other than $2$ and $5$, if an integer has $p-1$ digits, then it is a multiple of $p$ if and only if the integer obtained by cycling its digits is a multiple of $p$. For example, a $16$-digit integer is a multiple of $17$ if and only if the integer obtained by cycling its digits is a multiple of $17$. The reason this fails for $p=2$ and $p=5$ is related to the fact that $2$ and $5$ are the prime factors of $10$, which is the base of our number system.

   • Suppose $k$ is an integer. The Euler Totient Function of $k$, denoted by $\phi (k)$, is defined to be the number of integers $m$ with $1\le m\le k$ such that $gcd(m,k)=1$. For example, $\phi (6)=2$ since $1$ and $5$ are the only integers between $1$ and $6$ inclusive that have a $gcd$ of $1$ with $6$. $\phi (21)=12$ since there are exactly $12$ integers $m$ from $1$ to $21$ inclusive with the property that $gcd(m,21)=1$. They are $1,2,4,5,8,10,11,13,16,17,19,20$.

     If $k$ is an integer that is neither a multiple of $2$ nor a multiple of $5$, then any $\phi (k)$-digit integer is a multiple of $k$ if and only if the integer obtained by rotating its digits is a multiple of $k$. For example, the $12$-digit integer $439874621235$ is a multiple of $21$, and so are $398746212354$, $987462123543$, and so on.

     One of the key observations for proving something like this is a result due to Euler that says that when $a$ and $k$ are nonzero integers with $gcd(a,k)=1$, the remainder when dividing $a^{\phi (k)}$ by $k$ is $1$.

Problem 1: October 2022

Problem

In any triangle, there is a unique circle called its incircle that can be drawn in such a way that it is tangent to all three sides of the triangle. For a given triangle, the radius of its incircle is known as its inradius and is denoted by $r$.

For each side of the triangle (which is tangent to the incircle), another tangent to the incircle can be drawn in such a way that it is parallel to that side. The three sides as well as these three new tangents give a total of six tangents to the incircle. They uniquely determine a hexagon that we will call the Seraj hexagon of the triangle.

Finally, for a given triangle, we will denote by $s$ its semiperimeter, which is defined to be half of its perimeter.

The diagram below is of a triangle showing its incircle and Seraj hexagon.

1. Sketch the $3$–$4$–$5$ triangle with its incircle and Seraj hexagon. Compute its inradius, semiperimeter, and the area of its Seraj hexagon.

2. Find a general expression for the area of a triangle in terms only of its inradius and semiperimeter.

3. Find a general expression for the area of the Seraj hexagon of a triangle in terms of its three side lengths, its semiperimeter, and its inradius.

4. What is the largest possible value that can be obtained by dividing the area of a triangle’s Seraj hexagon by the total area of the triangle?

Hint

1. There are several ways to compute the area of the Seraj hexagon. One is to subtract the areas of three smaller triangles from that of the full triangle.

2. From the centre of the incircle, draw a radius to each point of tangency the circle has with the triangle.

3. • If $\mathrm{△}ABC$ is similar to $\mathrm{△}DEF$, then ${\displaystyle \frac{AB}{DE}}={\displaystyle \frac{BC}{EF}}={\displaystyle \frac{AC}{DF}}$. It is a useful general fact that if we denote this common ratio by $k$, then any two corresponding altitudes of these two triangles also have a ratio of $k$. Can you compute the ratio of the areas of $\mathrm{△}ABC$ and $\mathrm{△}DEF$ in terms of $k$?

   • One possible expression is $$rs[1-{(1-{\displaystyle \frac{a}{s}})}^2-{(1-{\displaystyle \frac{b}{s}})}^2-{(1-{\displaystyle \frac{c}{s}})}^2]$$

4. Try to prove that $3(x^2+y^2+z^2)\ge (x+y+z{)}^2$ is true for all real numbers $x$, $y$, and $z$ and determine a condition on $x$, $y$, and $z$ that implies $3(x^2+y^2+z^2)=(x+y+z{)}^2$.

Solution

Note: In this solution, we will denote by $|\mathrm{△}ABC|$ the area of $\mathrm{△}ABC$. We will also use the following facts about circles.

Fact 1: Suppose a circle has centre $O$ and $P$ is a point on its circumference. The tangent to the circle at point $P$ is perpendicular to the radius from $O$ to $P$.

Fact 2: For any point $Q$ outside of a circle, there are exactly two tangents to the circle that pass through $Q$. If the points of tangency are $A$ and $B$, then $AQ=BQ$.

1. Below is a picture of the triangle. Its vertices are labelled by $A$, $B$, and $C$ with the right angle at $C$, $AC=3$, $BC=4$, and $AB=5$. The centre of the incircle is labelled by $I$, and $AB$, $BC$, and $AC$ are tangent to the incircle at $D$, $E$, and $F$, respectively.

   

   Since the perimeter is $3+4+5=12$, the semiperimeter is $s={\displaystyle \frac{12}{2}}=6$.

   To compute $r$, we first use Fact 1 to get that $\mathrm{\angle }IFC=\mathrm{\angle }IEC=90\mathrm{°}$. We are assuming that $\mathrm{\angle }FCE=90\mathrm{°}$ as well, and since the sum of the angles of a quadrilateral is always $360\mathrm{°}$, $\mathrm{\angle }FIE=90\mathrm{°}.$ Therefore, $CFIE$ is a rectangle. Since $IF$ and $IE$ are radii of the incircle, $IF=IE=r$. Since $CFIE$ is a rectangle, $CF=CE=r$.

   Using that $CF=CE=r$, we get $BE=BC-CE=4-r$ and $AF=AC-CF=3-r$. By Fact 2, $BD=BE$ and $AD=AF$, and since $AB=5$, $$\begin{array}{rl}5& =AB\\ & =AD+BD\\ & =AF+BE\\ & =(3-r)+(4-r)\\ & =7-2r\end{array}$$ This gives $5=7-2r$, which can be solved for $r$ to get $r=1$.

   In the diagram below, the Seraj hexagon has been added. The side of the Seraj hexagon that is parallel to $AB$ (and tangent to the incircle) intersects $BC$ at $L$ and $AC$ at $M$. The side of the Seraj hexagon that is parallel to $BC$ intersects $AC$ at $G$ and $AB$ at $H$. The side of the Seraj hexagon that is parallel to $AC$ intersects $AB$ at $J$ and $BC$ at $K$. The point of tangency of $JK$ with the circle is labelled by $N$.

   

   To compute the area of the Seraj hexagon, we will compute the areas of $\mathrm{△}MLC$, $\mathrm{△}AHG$, and $\mathrm{△}JBK$ and subtract their combined area from the area of $\mathrm{△}ABC$.

   To compute the area of $\mathrm{△}MLC$, we first set $CM=x$ and $CL=y$. Since $LM$ is parallel to $AB$, we have that $\mathrm{\angle }CML=\mathrm{\angle }CAB$ and $\mathrm{\angle }CLM=\mathrm{\angle }CBA$. Since the two share a right angle at $C$, $\mathrm{△}MLC$ is similar to $\mathrm{△}ABC$. Therefore, ${\displaystyle \frac{y}{x}}={\displaystyle \frac{CL}{CM}}={\displaystyle \frac{BC}{AC}}={\displaystyle \frac{4}{3}}$, or $y={\displaystyle \frac{4}{3}}x$.

   From earlier, we have that $CF=CE=1$, which means $FM=1-x$ and $EL=1-y$. By Fact 2, $LM=EL+FM=2-x-y$. By the Pythagorean theorem applied to $\mathrm{△}CML$ and using that $y={\displaystyle \frac{4}{3}}x$, we have $$\begin{array}{rl}C{M}^2+C{L}^2& =L{M}^2\\ x^2+y^2& =(2-x-y{)}^2\\ x^2+{\left(\frac{4}{3}x\right)}^2& ={(2-\frac{7}{3}x)}^2\\ x^2+\frac{16}{9}{x}^2& =4-\frac{28}{3}x+\frac{49}{9}{x}^2\\ 0& =\frac{8}{3}{x}^2-\frac{28}{3}x+4\\ 0& =2x^2-7x+3& \text{(multiply by }\frac{3}{4}\text{)}\\ 0& =(x-3)(2x-1)\end{array}$$ If $x-3=0$, then $M$ is at $A$, but $AB$ and $LM$ are distinct parallel lines, so they have no points in common. Therefore, $2x-1=0$ or $x={\displaystyle \frac{1}{2}}$, so $y={\displaystyle \frac{4}{3}}\times {\displaystyle \frac{1}{2}}={\displaystyle \frac{2}{3}}$. We can now compute $$|\mathrm{△}CML|={\displaystyle \frac{1}{2}}xy={\displaystyle \frac{1}{2}}\times {\displaystyle \frac{1}{2}}\times {\displaystyle \frac{2}{3}}={\displaystyle \frac{1}{6}}$$

   We now compute the area of $\mathrm{△}JBK$. By Fact 1, $\mathrm{\angle }IEK=\mathrm{\angle }INK=90\mathrm{°}$, and since $JK$ is parallel to $AC$, $\mathrm{\angle }EKN=90\mathrm{°}$ as well. By reasoning similar to earlier, we conclude that $INKE$ is a square of side-length $r$, which means $EK=r$. We also have that $CE=r$, so this means $BK=BC-CE-EK=4-1-1=2$.

   Since $JK$ is parallel to $AC$, $\mathrm{△}JBK$ is similar to $\mathrm{△}ABC$ by reasoning similar to that which was used to show that $\mathrm{△}MLC$ was similar to $\mathrm{△}ABC$. This means ${\displaystyle \frac{JK}{AC}}={\displaystyle \frac{BK}{BC}}$ or $JK={\displaystyle \frac{AC\times BK}{BC}}$. Substituting $AC=3$, $BK=2$, and $BC=4$ into this equation, we get $JK={\displaystyle \frac{3}{2}}$. Therefore, $$|\mathrm{△}JBK|={\displaystyle \frac{1}{2}}\times BK\times JK={\displaystyle \frac{1}{2}}\times 2\times {\displaystyle \frac{3}{2}}={\displaystyle \frac{3}{2}}$$

   Using very similar reasoning, one can show that $|\mathrm{△}AHG|={\displaystyle \frac{2}{3}}$. Therefore, the area of the Seraj hexagon is $$|\mathrm{△}ABC|-|\mathrm{△}MLC|-|\mathrm{△}JBK|-|\mathrm{△}AHG|=\frac{1}{2}\times 4\times 3-\frac{1}{6}-\frac{3}{2}-\frac{2}{3}=\frac{11}{3}$$

2. In the diagram below, a triangle has its incircle drawn. Radii are drawn from the centre of the incircle, $I$, to the points of tangency of $AB$, $BC$, and $AC$, which are labelled $D$, $E$, and $F$, respectively. As well, $I$ is connected by line segments to each vertex of the triangle.

   

   Set $AB=c$, $BC=a$, and $AC=b$. With this notation, the semiperiemter of $\mathrm{△}ABC$ is $s={\displaystyle \frac{a+b+c}{2}}$. Since $ID$, $IE$, and $IF$ are radii to points of tangency, they are perpendicular to $AB$, $BC$, and $AC$, respectively. Therefore, they are altitudes of $\mathrm{△}ABI$, $\mathrm{△}BCI$, and $\mathrm{△}CAI$, respectively. These three triangles compose the entirety of $\mathrm{△}ABC$ with no overlap, so the area of $\mathrm{△}ABC$ is equal to the sum of their areas. Therefore, $$\begin{array}{rl}|\mathrm{△}ABC|& ={\displaystyle \frac{1}{2}}\times AB\times ID+{\displaystyle \frac{1}{2}}\times BC\times IE+{\displaystyle \frac{1}{2}}\times AC\times IF\\ & ={\displaystyle \frac{1}{2}}cr+{\displaystyle \frac{1}{2}}ar+{\displaystyle \frac{1}{2}}br\\ & =r\times {\displaystyle \frac{a+b+c}{2}}\\ & =rs\end{array}$$

   As an example demonstrating this formula, consider $\mathrm{△}ABC$ from part (a). Using the usual area formula, $|\mathrm{△}ABC|={\displaystyle \frac{1}{2}}\times 3\times 4=6$. From part (a), its semiperimeter is ${\displaystyle \frac{3+4+5}{2}}=6$ and inradius is $r=1$, so $rs=1\times 6=6$, which is the correct area.

3. In the diagram below, $\mathrm{△}ABC$ has its incircle and Seraj hexagon drawn. The side of the Seraj hexagon that is parallel to $BC$ intersects $AB$ at $D$ and $AC$ at $E$. The side parallel to $AB$ intersects $AC$ at $F$ and $BC$ at $G$. The side parallel to $AC$ intersects $BC$ at $H$ and $AB$ at $J$. The altitude of $\mathrm{△}ABC$ from $A$ is also drawn and its points of intersection with $BC$ and $DE$ are labelled by $K$ and $L$, respectively¹.

   

   By construction, $DE$ is parallel to $BC$. By reasoning similar to that which was used in earlier parts, this means $\mathrm{△}ABC$ is similar to $\mathrm{△}ADE$ and $\mathrm{△}ABK$ is similar to $\mathrm{△}ADL$. These two pairs of similar triangles imply that ${\displaystyle \frac{DE}{BC}}={\displaystyle \frac{AD}{AB}}$ and ${\displaystyle \frac{AD}{AB}}={\displaystyle \frac{AL}{AK}}$. We will call this common ratio $k$. The area of $\mathrm{△}ADE$ can be computed in terms of $k$ and the area of $\mathrm{△}ABC$ as follows $$\begin{array}{rl}|\mathrm{△}ADE|& ={\displaystyle \frac{1}{2}}(DE)(AL)\\ & ={\displaystyle \frac{1}{2}}(k(BC))(k(AK))\\ & =k^2({\displaystyle \frac{1}{2}}\times BC\times AK)\\ & =k^2|\mathrm{△}ABC|\end{array}$$

   We next examine the quantity $k$. Since $DE$ and $BC$ are different parallel tangents to the incircle and $KL$ is perpendicular to both lines, the length of $KL$ must be equal to the diameter of the incircle (you may want to think about why this is true). The diameter of the incircle is $2r$, so $KL=2r$, which means $AL=AK-2r$.

   Therefore, we have $k={\displaystyle \frac{AL}{AK}}={\displaystyle \frac{AK-2r}{AK}}=1-{\displaystyle \frac{2r}{AK}}$. From part (b), $|\mathrm{△}ABC|=rs$, but from the usual formula for the area of a triangle we also have $|\mathrm{△}ABC|={\displaystyle \frac{1}{2}}(BC)(AK)$. This implies $2rs=(BC)(AK)$ or $AK={\displaystyle \frac{2rs}{BC}}$. Substituting into the formula for $k$ above, we have that $$k=1-{\displaystyle \frac{2r}{AK}}=1-{\displaystyle \frac{2r(BC)}{2rs}}=1-{\displaystyle \frac{BC}{s}}$$ If we set $AB=c$, $BC=a$, and $AC=b$, then we get $k=1-{\displaystyle \frac{a}{s}}$. Earlier, we showed that $|\mathrm{△}ADE|=k^2|\mathrm{△}ABC|$, so $$|\mathrm{△}ADE|={(1-{\displaystyle \frac{a}{s}})}^2|\mathrm{△}ABC|$$ By similar reasoning, we also have $$\begin{array}{rl}|\mathrm{△}JBH|& ={(1-{\displaystyle \frac{b}{s}})}^2|\mathrm{△}ABC|\\ |\mathrm{△}FGC|& ={(1-{\displaystyle \frac{c}{s}})}^2|\mathrm{△}ABC|\end{array}$$ The area of the Seraj hexagon is equal to the area of $\mathrm{△}ABC$ minus the combined area of these three triangles, so using the formulas just above as well as $|\mathrm{△}ABC|=rs$, we have $$\begin{array}{rl}|DEFGHJ|& =|\mathrm{△}ABC|-|\mathrm{△}ADE|-|\mathrm{△}JBH|-|\mathrm{△}FGC|\\ & =|\mathrm{△}ABC|[1-{(1-{\displaystyle \frac{a}{s}})}^2-{(1-{\displaystyle \frac{b}{s}})}^2-{(1-{\displaystyle \frac{c}{s}})}^2]\\ & =rs[1-{(1-{\displaystyle \frac{a}{s}})}^2-{(1-{\displaystyle \frac{b}{s}})}^2-{(1-{\displaystyle \frac{c}{s}})}^2]\end{array}$$

4. As suggested in the hint, we will show that $3(x^2+y^2+z^2)\ge (x+y+z{)}^2$ for all real numbers $x$, $y$, and $z$. To see this, note that the inequality is equivalent to the inequality $$3(x^2+y^2+z^2)-(x+y+z{)}^2\ge 0$$ which, after expanding and rearranging the left side, is the same as $$2(x^2+y^2+z^2)-2(xy+yz+zx)\ge 0$$ After further manipulation, this is equivalent to $$(x-y{)}^2+(y-z{)}^2+(z-x{)}^2\ge 0$$ Therefore, the given inequality is true exactly when $(x-y{)}^2+(y-z{)}^2+(z-x{)}^2\ge 0$. The sum of three squares is always non-negative, so this inequality is always true. Therefore, the given inequality is true for all real numbers $x$, $y$, and $z$, as claimed. Moreover, the only way that the quantity $(x-y{)}^2+(y-z{)}^2+(z-x{)}^2$ can be equal to $0$ is when $x=y=z$, and hence, the only way that $3(x^2+y^2+z^2)=(x+y+z{)}^2$ is when $x=y=z$.

   Dividing the expression for the area of the Seraj hexagon from part (c) by $rs$, we get that the ratio of the area of the Seraj hexagon to that of the triangle is $$1-{(1-{\displaystyle \frac{a}{s}})}^2-{(1-{\displaystyle \frac{b}{s}})}^2-{(1-{\displaystyle \frac{c}{s}})}^2$$ Using the inequality established above, we can multiply by $-{\displaystyle \frac{1}{3}}$ to get that for any real numbers $x$, $y$, and $z$, $-x^2-y^2-z^2\le -{\displaystyle \frac{1}{3}}(x+y+z{)}^2$. Applying this with $x=1-{\displaystyle \frac{a}{s}}$, $y=1-{\displaystyle \frac{b}{s}}$, and $z=1-{\displaystyle \frac{c}{s}}$, we get that $$\begin{array}{rl}1-{(1-{\displaystyle \frac{a}{s}})}^2-{(1-{\displaystyle \frac{b}{s}})}^2-{(1-{\displaystyle \frac{c}{s}})}^2& =1-x^2-y^2-z^2\\ & \le 1-{\displaystyle \frac{1}{3}}(x+y+z{)}^2\\ & =1-{\displaystyle \frac{1}{3}}{(1-{\displaystyle \frac{a}{s}}+1-{\displaystyle \frac{b}{s}}+1-{\displaystyle \frac{c}{s}})}^2\\ & =1-{\displaystyle \frac{1}{3}}{(3-{\displaystyle \frac{a+b+c}{s}})}^2\\ & =1-{\displaystyle \frac{1}{3}}{(3-{\displaystyle \frac{2s}{s}})}^2\\ & =1-{\displaystyle \frac{1}{3}}\\ & ={\displaystyle \frac{2}{3}}\end{array}$$ Therefore, the ratio is at most ${\displaystyle \frac{2}{3}}$ in every triangle. By the remark at the end of the proof of the inequality, the ratio equals ${\displaystyle \frac{2}{3}}$ exactly when $1-{\displaystyle \frac{a}{s}}=1-{\displaystyle \frac{b}{s}}=1-{\displaystyle \frac{c}{s}}$. Since $s$ is always nonzero, this is equivalent to $a=b=c$. Therefore, the ratio is maximized when the triangle is equilateral. It is not difficult to explicitly show that the area of the Seraj hexagon in an equilateral triangle is equal to two thirds of the area of the triangle.

1. If $\mathrm{\angle }ABC$ or $\mathrm{\angle }ACB$ is obtuse, then $AK$ intersects some extensions $DE$ and $BC$ and not the line segments themselves. We leave it to the reader to verify that the argument that follows works even if $AK$ does not pass through $DE$ and $BC$.↩︎

Problem 2: November 2022

Problem

Let $\varphi ={\displaystyle \frac{1+\sqrt{5}}{2}}\approx 1.61803$. For integers $d_k,d_{k-1},\dots ,d_1,d_0,d_{-1},\dots ,d_{-r}$, each equal to $0$ or $1$, the expression $$(d_k{d}_{k-1}\cdots d_2{d}_1{d}_0.d_{-1}{d}_{-2}\cdots d_{-r}{)}_{\varphi }$$ is called a base $\varphi$ expansion and represents the real number $$d_k{\varphi }^k+d_{k-1}{\varphi }^{k-1}+\cdots +d_1\varphi +d_0+d_{-1}{\varphi }^{-1}+d_{-2}{\varphi }^{-2}+\cdots +d_{-r}{\varphi }^{-r}$$ The integers $d_k$ through $d_{-r}$ are called the digits of the expansion. For example, the base $\varphi$ expansion ${1101.011}_{\varphi }$ represents the real number $$(1\times {\varphi }^3)+(1\times {\varphi }^2)+(0\times \varphi )+1+(0\times {\varphi }^{-1})+(1\times {\varphi }^{-2})+(1\times {\varphi }^{-3})$$ which can be simplified to get $$\begin{array}{rl}{\varphi }^3+{\varphi }^2+1+\frac{1}{{\varphi }^2}+\frac{1}{{\varphi }^3}& ={\left(\frac{1+\sqrt{5}}{2}\right)}^3+{\left(\frac{1+\sqrt{5}}{2}\right)}^2+1+{\left(\frac{2}{1+\sqrt{5}}\right)}^2+{\left(\frac{2}{1+\sqrt{5}}\right)}^3\\ & =\frac{16+8\sqrt{5}}{8}+\frac{6+2\sqrt{5}}{4}+1+\frac{4}{6+2\sqrt{5}}+\frac{8}{16+8\sqrt{5}}\\ & =(2+\sqrt{5})+(\frac{3}{2}+\frac{1}{2}\sqrt{5})+1+(\frac{3}{2}-\frac{1}{2}\sqrt{5})-(2-\sqrt{5})\\ & =4+2\sqrt{5}\end{array}$$ and so ${1101.011}_{\varphi }=4+2\sqrt{5}$.

1. What are the real numbers represented by ${1011}_{\varphi }$ and ${10000}_{\varphi }$?

2. Find a base $\varphi$ expansion of the real number $4+3\sqrt{5}$.

3. Show that ${\varphi }^2=\varphi +1$ and use this to deduce that ${\varphi }^{n+1}={\varphi }^n+{\varphi }^{n-1}$ for all integers $n$.

4. Show that every positive integer has a base $\varphi$ expansion and find a base $\varphi$ expansion for each positive integer from $1$ through $10$. One approach is to prove and use the following two facts.

   • If a real number $n$ has a base $\varphi$ expansion, then it has a base $\varphi$ expansion that does not have two consecutive digits equal to $1$.

   • If a real number $n$ has a base $\varphi$ expansion, then it has a base $\varphi$ expansion that has its units digit, $d_0$, equal to $0$.

Hint

1. No hint given.

2. What is $\varphi +{\displaystyle \frac{1}{\varphi }}$?

3. No hint given.

4. One way to prove the first fact is to show that if there are two consecutive digits equal to $1$, then there is a base $\varphi$ expansion with fewer non-zero digits. To prove the second fact, use the same idea as in the proof of the first fact, but in reverse.

Solution

1. Expanding and simplifying, we have $$\begin{array}{rl}{1011}_{\varphi }={\varphi }^3+\varphi +1& ={\left(\frac{1+\sqrt{5}}{2}\right)}^3+\frac{1+\sqrt{5}}{2}+1\\ & =\frac{16+8\sqrt{5}}{8}+\frac{1+\sqrt{5}}{2}+1\\ & =\frac{4+2\sqrt{5}}{2}+\frac{1+\sqrt{5}}{2}+\frac{2}{2}\\ & =\frac{7+3\sqrt{5}}{2}\end{array}$$

   $$\begin{array}{rl}{10000}_{\varphi }={\varphi }^4& ={\left(\frac{1+\sqrt{5}}{2}\right)}^4\\ & ={\left(\frac{1+\sqrt{5}}{2}\right)}^2{\left(\frac{1+\sqrt{5}}{2}\right)}^2\\ & =\left(\frac{6+2\sqrt{5}}{4}\right)\left(\frac{6+2\sqrt{5}}{4}\right)\\ & =\frac{56+24\sqrt{5}}{16}\\ & =\frac{7+3\sqrt{5}}{2}\end{array}$$ and so we see that ${1011}_{\varphi }={10000}_{\varphi }$

2. There are several ways to approach this problem and we will demonstrate two of them. First, from the example given in the problem statement, we have that $$4+2\sqrt{5}={\varphi }^3+{\varphi }^2+1+\frac{1}{{\varphi }^2}+\frac{1}{{\varphi }^3}$$ and using the hint, we have that $$\varphi +\frac{1}{\varphi }=\frac{1+\sqrt{5}}{2}+\frac{2}{1+\sqrt{5}}=\frac{1+\sqrt{5}}{2}+\frac{2(\sqrt{5}-1)}{4}=\sqrt{5}$$ and so $$\begin{array}{rl}4+3\sqrt{5}& =(4+2\sqrt{5})+\sqrt{5}\\ & =({\varphi }^3+{\varphi }^2+1+\frac{1}{{\varphi }^2}+\frac{1}{{\varphi }^3})+(\varphi +\frac{1}{\varphi })\\ & =1111.111\end{array}$$

   Another approach is to use what might be called a "greedy algorithm". We first note that $4+3\sqrt{5}\approx 10.708204$ and then consider powers of $\varphi$ and find the first one that does not exceed it. As it turns out, ${\varphi }^4\approx 6.854102$ and ${\varphi }^5\approx 11.090170$. It can be checked that ${\varphi }^4={\displaystyle \frac{7+3\sqrt{5}}{2}}$, so if we let $\alpha =4+3\sqrt{5}$, then $$\alpha -{\varphi }^4={\displaystyle \frac{8+6\sqrt{5}}{2}}-{\displaystyle \frac{7+3\sqrt{5}}{2}}={\displaystyle \frac{1+3\sqrt{5}}{2}}$$ The approximate value of $\alpha -{\varphi }^4$ is $3.854102$. Now we check that ${\varphi }^2\approx 2.618034$ and ${\varphi }^3\approx 4.236068$, so the largest power of $\varphi$ that does not exceed $\alpha -{\varphi }^4$ is ${\varphi }^2$, and it can be checked that $$\alpha -{\varphi }^4-{\varphi }^2=-1+\sqrt{5}\approx 1.236068$$ Since ${\varphi }^0=1$ and ${\varphi }^1=\varphi \approx 1.618034$, the largest power of $\varphi$ that does not exceed $\alpha -{\varphi }^4-{\varphi }^2$ is ${\varphi }^0=1$, and so we now consider the quantity $$\alpha -{\varphi }^4-{\varphi }^2-1=-2+\sqrt{5}\approx 0.236068$$ Considering $\varphi$ taken to negative integer exponents, we find that ${\varphi }^{-3}\approx 0.236068$, so we suspect that $-2+\sqrt{5}$ is exactly equal to ${\varphi }^{-3}$. Indeed, $${\left({\displaystyle \frac{2}{1+\sqrt{5}}}\right)}^3={\displaystyle \frac{8}{16+8\sqrt{5}}}={\displaystyle \frac{1}{2+\sqrt{5}}}=-2+\sqrt{5}$$ Therefore, $\alpha -{\varphi }^4-{\varphi }^2-1={\displaystyle \frac{1}{{\varphi }^3}}$ which can be rearranged to get $\alpha ={\varphi }^4+{\varphi }^2+{\varphi }^0+{\varphi }^{-3}$, which means $4+3\sqrt{5}=10101.001$. Notice that these two base $\varphi$ expansions are different and both correct. A way to see that the expansions are equal is explained throughout the rest of the solution.

3. Expanding ${\varphi }^2$ and simplifying, we have $$\begin{array}{rl}{\varphi }^2& ={\left(\frac{1+\sqrt{5}}{2}\right)}^2\\ & =\frac{6+2\sqrt{5}}{4}\\ & =\frac{3+\sqrt{5}}{2}\\ & =\frac{1+\sqrt{5}}{2}+\frac{2}{2}\\ & =\varphi +1\end{array}$$ Multiplying this equation by ${\varphi }^{n-1}$ gives ${\varphi }^{n-1}+{\varphi }^n={\varphi }^{n+1}$. It will be useful in part (d) to note that this means that ${011}_{\varphi }={100}_{\varphi }$ and more generally, if $011$ ever occurs in a base $\varphi$ expansion, it can be replaced by $100$, or vice versa, without changing the actual value of the number being expressed.

4. As suggested in the problem, we will use the facts in the bullet points. Specifically, we will use Fact 1 and Fact 2 below:

   Fact 1: If a real number $n$ has a base $\varphi$ expansion, then it has a base $\varphi$ expansion that does not have two consecutive digits equal to $1$.

   Fact 2: If a real number $n$ has a base $\varphi$ expansion, then it has a base $\varphi$ expansion that has its units digit $d_0$ equal to $0$.

   Proof of Fact 1. Let $n=d_k{d}_{k-1}\cdots d_2{d}_1{d}_0.d_{-1}{d}_{-2}\cdots d_{-r}$ be a base $\varphi$ expansion of $n$. We will call the digit $d_m$ bad if $d_m=1$ and at least one of $d_{m+1}$ and $d_{m-1}$ is equal to $1$. We want to show that $n$ has a base $\varphi$ expansion that has no bad digits.

   Observe that if $n$ has an expansion with every digit equal to $0$, then $n$ must itself be the real number $0$. This is because every power of $\varphi$ is positive.

   Suppose the given expansion of $n$ has at least one bad digit. Then we let $m$ be the largest integer such that $d_m$ is bad. By definition, $d_m=1$ and either $d_{m+1}=1$ or $d_{m-1}=1$. However, it is not possible for $d_{m+1}=1$ since this would imply that $d_{m+1}$ is bad, but $m$ is the largest integer such that $d_m$ is bad.

   Thus, we must have $d_{m+1}=0$, $d_m=1$, and $d_{m-1}=1$, and so the given expansion is $$n=d_k{d}_{k-1}\cdots d_{m+2}011d_{m-2}\cdots d_1{d}_0.d_{-1}{d}_{-2}\cdots d_{-r}$$ By the remark at the end of part (c), we can replace the $011$ by $100$ to get that $$n=d_k{d}_{k-1}\cdots d_{m+2}100d_{m-2}{d}_{m-2}\cdots d_1{d}_0.d_{-1}{d}_{-2}\cdots d_{-r}$$

   Notice that we have found a base $\varphi$ expansion of $n$ with fewer non-zero digits, under the assumption that the expansion had at least one bad digit. In other words, if a base $\varphi$ expansion of $n$ has at least one bad digit, then there is a base $\varphi$ expansion of $n$ that has fewer non-zero digits. Thus, as long as there is a bad digit, we can decrease the number of non-zero digits.

   By the above remark, unless $n=0$, the number of nonzero digits cannot decrease indefinitely since there were finitely many digits to begin with. Thus, we must eventually lose the ability to decrease the number of nonzero digits, and by the previous paragraph, this means we must eventually reach a base $\varphi$ expansion that has no bad digits. ◻

   Below is an example of the procedure explained in the proof of Fact 1. It is used to find a base $\varphi$ expansion of $n={1010101110011.1101}_{\varphi }$ that has no bad digits. There is a step where a leading $11$ is replaced by $100$. The digits are aligned in the equations to indicate where this happened. In every line except the last, the the digits that are changed in the subsequent line are highlighted. $$\begin{array}{rl}n& =10101\mathbf{011}{10011.1101}_{\varphi }\\ & =101\mathbf{011}{0010011.1101}_{\varphi }\\ & =1\mathbf{011}{000010011.1101}_{\varphi }\\ & =\mathbf{11}{00000010011.1101}_{\varphi }\\ & =10000000010\mathbf{011}{.1101}_{\varphi }\\ & =1000000001010\mathbf{0.11}{01}_{\varphi }\\ & ={10000000010101.0001}_{\varphi }\end{array}$$

   Proof of Fact 2. This can be shown by an argument rather similar to the proof of Fact 1. This time, we will introduce bad digits in order to remove a potential $1$ from the units digit. Suppose $n$ has a base $\varphi$ expansion. By Fact 1, we can assume that the expansion $n={d_k{d}_{k-1}\cdots d_2{d}_1{d}_0{d}_{-1}\cdots d_{-r}}_{\varphi }$ is a expansion without any bad digits. If $d_0=0$, then there is nothing to do, so we assume that $d_0=1$. We will now artificially add two "trailing" $0$’s as digits. That is, we also have that $$n=d_k{d}_{k-1}\cdots d_2{d}_1{d}_0{d}_{-1}\cdots d_{-r}{d}_{-r-1}{d}_{-r-2}$$ where $d_{-r-1}=d_{-r-2}=0$. Let $m$ be the largest integer with $0>m$ and $d_m=d_{m-1}=0$. Since we have added two trailing zeros, we know this must happen somewhere, so it is possible to choose $m$ this way.

   By the choice of $m$, we must have that $d_{m+1}=1$, and since the expansion has no bad digits, $d_{m+2}=0$. By the choice of $m$, it then follows that $d_{m+3}=1$, then since there are no bad digits, we get $d_{m+4}=0$, and so on. Since $d_0=1$, this alternating pattern must eventually reach $d_0=1$. In other words, the expansion takes the form $$n=d_k{d}_{k-1}\cdots d_3{d}_2{d}_{1}1.010101\cdots 010100d_{m-2}{d}_{m-3}\cdots d_{-r}{d}_{-r-1}{d}_{-r-2}$$ By part (c), we can change $d_m$ and $d_{m-1}$ to $1$’s and compensate by changing $d_{m+1}$ to $0$. The new expansion is $$n=d_k{d}_{k-1}\cdots d_3{d}_2{d}_{1}1.010101\cdots 010011d_{m-2}{d}_{m-3}\cdots d_{-r}{d}_{-r-1}{d}_{-r-2}$$ Repeating this process, we now change $d_{m+1}$ and $d_{m+2}$ to $1$’s and change $d_{m+3}$ to a $0$. This process terminates in the expansion $$n=d_k{d}_{k-1}\cdots d_3{d}_2{d}_{1}0.111111\cdots 111d_{m-2}{d}_{m-3}\cdots d_{-r}$$ which indeed has $d_0=0$. ◻

   The procedure in the proof of Fact 2 is used below to find a base $\varphi$ expansion of the number represented as $n={100101001.01010101001010010001}_{\varphi }$ that has $d_0=0$. As was done earlier, in each line but the last, the three digits highlighted are the ones that change in the subsequent line. $$\begin{array}{rl}n& =100101001.0101010\mathbf{100}{1010010001}_{\varphi }\\ n& =100101001.01010\mathbf{100}{111010010001}_{\varphi }\\ n& =100101001.010\mathbf{100}{11111010010001}_{\varphi }\\ n& =100101001.0\mathbf{100}{1111111010010001}_{\varphi }\\ n& =10010100\mathbf{1.00}{111111111010010001}_{\varphi }\\ n& ={100101000.11111111111010010001}_{\varphi }\end{array}$$

   Now we will apply the facts to derive base $\varphi$ expansions for the first ten positive integers.

   To start, we have that $1=1_{\varphi }$ since $1={\varphi }^0$. This means the integer $1$ has a base $\varphi$ expansion. Following the procedure outlined in the proof of Fact 2, $1={0.11}_{\varphi }$. It is easy to add $1$ to a base $\varphi$ expansion that has $d_0=0$ because we can simply change $d_0=1$. Thus, we have that $2={1.11}_{\varphi }$, and using the procedure from the proof of Fact 1 again, we get $2={10.01}_{\varphi }$.

   Continuing in this way, if we have a base $\varphi$ expansion of the integer $n$, then we can use the technique in the proof of Fact 1 to find a base $\varphi$ expansion that does not have any bad digits. Then, if necessary, we can use the technique in the proof of Fact 2 to find a base $\varphi$ expansion of $n$ that has $d_0=0$. From this, we can find a base $\varphi$ expansion of $n+1$ by taking the base $\varphi$ expansion of $n$ and switching $d_0$ from $0$ to $1$, which has the effect of adding $1$. This process can be repeated to find a base $\varphi$ expansion of $n+2$, then $n+3$, and so on. Starting with $n=1$, this is demonstrated up to $n=10$ below.

   $$\begin{array}{rl}1& =1_{\varphi }\\ & ={1.00}_{\varphi }\\ & ={0.11}_{\varphi }\\ \\ 2& ={1.11}_{\varphi }\\ & ={10.01}_{\varphi }\\ \\ 3& ={11.01}_{\varphi }\\ & ={100.01}_{\varphi }\\ \\ 4& ={101.01}_{\varphi }\\ & ={101.0100}_{\varphi }\\ & ={101.0011}_{\varphi }\\ & ={100.1111}_{\varphi }\\ \\ 5& ={101.1111}_{\varphi }\\ & ={110.0111}_{\varphi }\\ \\ 6& ={111.0111}_{\varphi }\\ & ={1001.1001}_{\varphi }\\ & ={1010.0001}_{\varphi }\\ \\ 7& ={1011.0001}_{\varphi }\\ & ={1100.0001}_{\varphi }\\ \\ 8& ={1101.0001}_{\varphi }\\ & ={10000.1101}_{\varphi }\\ \\ 9& ={10001.1101}_{\varphi }\\ & ={10010.0101}_{\varphi }\\ \\ 10& ={10011.0101}_{\varphi }\\ & ={10100.0101}_{\varphi }\end{array}$$