Solutions and comments

---

61.

Let $S=1!2!3!\dots 99!100!$ (the product of the first 100 factorials). Prove that there exists an integer $k$ for which $1\le k\le 100$ and $S/k!$ is a perfect square. Is $k$ unique? (Optional: Is it possible to find such a number $k$ that exceeds 100?)

Solution 1. Note that, for each positive integer $j$, $(2j-1)!(2j)!=[(2j-1)!]{}^2·2j$. Hence

$S=\underset{j=1}{\overset{50}{\Pi }}[(2j-1)!]{}^2[2j]=2^{50}50![\underset{j=1}{\overset{50}{\Pi }}(2j-1)!{]}^2\hspace{1em},$
from which we see that $k=50$ is the required number.

We show that $k=50$ is the only possibility. First, $k$ cannot exceed 100, for otherwise $101!$ would be a factor of $k!$ but not $S$, and so $S/k!$ would not even be an integer. Let $k\le 100$. The prime $47$ does not divide $k!$ for $k\le 46$ and divides $50!$ to the first power. Since $S/50!$ is a square, it evidently divides $S$ to an odd power. So $k\ge 47$ in order to get a quotient divisible by 47 to an even power. The prime $53$ divides each $k!$ for $k\ge 53$ to the first power and divides $S/50!$, and so $S$ to an even power. Hence, $k\le 52$.

The prime $17$ divides $50!$ and $S/50!$, and hence $S$ to an even power, but it divides each of $51!$ and $52!$ to the third power. So we cannot have $k=51$ or 52. Finally, look at the prime 2. Suppose that $2^{2u}$ is the highest power of 2 that divides $S/50!$ and that $2^v$ is the highest power of 2 that divides $50!$; then $2^{2u+v}$ is the highest power of 2 that divides $S$. The highest power of $2$ that divides $48!$ and $49!$ is $2^{v-1}$ and the highest power of 2 that divides $46!$ and $47!$ is $2^{v-5}$. >From this, we deduce that 2 divides $S/k!$ to an odd power when $47\le k\le 49$. The desired uniqueness of $k$ follows.

Solution 2. Let $p$ be a prime exceeding 50. Then $p$ divides each of $m!$ to the first power for $p\le m\le 100$, so that $p$ divides $S$ to the even power $100-(p-1)=101-p$. From this, it follows that if $53\ge k$, $p$ must divide $S/k!$ to an odd power.

On the other hand, the prime 47 divides each $m!$ with $47\le m\le 93$ to the first power, and each $m!$ with $94\le m\le 100$ to the second power, so that it divides $S$ to the power with exponent $54+7=61$. Hence, in order that it divide $S/k!$ to an even power, we must make $k$ one of the numbers $47,\dots ,52$.

By an argument, similar to that used in Solution 1, it can be seen that $2$ divides any product of the form $1!2!\dots (2m-1)!$ to an even power and $100!$ to the power with exponent

$\lfloor 100/2\rfloor +\lfloor 100/4\rfloor +\lfloor 100/8\rfloor +\lfloor 100/16\rfloor +\lfloor 100/32\rfloor +\lfloor 100/64\rfloor =50+25+12+6+3+1=97\hspace{1em}.$
Hence, 2 divides $S$ to an odd power. So we need to divide $S$ by $k!$ which 2 divides to an odd power to get a perfect square quotient. This reduces the possibilities for $k$ to 50 or 51. Since

$S=2^{99}·3^{98}·4^{97}\dots {99}^2·100=(2·4\dots 50)(2^{49}·3^{49}·4^{48}\dots 99){}^2=50!·2^{50}(\dots ){}^2\hspace{1em},$
$S/50!$ is a square, and so $S/51!=(S/50!)÷(51)$ is not a square. The result follows.

Solution 3. As above, $S/(50!)$ is a square. Suppose that $53\le k\le 100$. Then 53 divides $k!/50!$ to the first power, and so $k!/50!$ cannot be square. Hence $S/k!=(S/50!)÷(k!/50!)$ cannot be square. If $k=51$ or 52, then $k!/50!$ is not square, so $S/k!$ cannot be square. Suppose that $k\le 46$. Then 47 divides $50!/k!$ to the first power, so that $50!/k!$ is not square and $S/k!=(S/50!)\times (50!/k!)$ cannot be square. If $k=47,48$ or 49, then $50!/k!$ is not square and so $S/k!$ is not square. Hence $S/k!$ is square if and only if $k=50$ when $k\le 100$.

---

62.

Let $n$ be a positive integer. Show that, with three exceptions, $n!+1$ has at least one prime divisor that exceeds $n+1$.

Solution. Any prime divisor of $n!+1$ must be larger than $n$, since all primes not exceeding $n$ divide $n!$. Suppose, if possible, the result fails. Then, the only prime that can divide $n!+1$ is $n+1$, so that, for some positive integer $r$ and nonnegative integer $K$,

$n!+1=(n+1){}^r=1+\mathrm{rn}+{\mathrm{Kn}}^2\hspace{1em}.$
This happens, for example, when $n=1,2,4$: $1!+1=2$, $2!+1=3$, $4!+1=5^2$. Note, however, that the desired result does hold for $n=3$: $3!+1=7$.

Henceforth, assume that $n$ exceeds 4. If $n$ is prime, then $n+1$ is composite, so by our initial comment, all of its prime divisors exceed $n+1$. If $n$ is composite and square, then $n!$ is divisible by the four distinct integers $1,n,\sqrt{n},2\sqrt{n}$, while is $n$ is composite and nonsquare with a nontrivial divisor $d$. then $n!$ is divisible by the four distinct integers $1,d,n/d,n$. Thus, $n!$ is divisible by $n^2$. Suppose, if possible, the result fails, so that $n!+1=1+\mathrm{rn}+{\mathrm{Kn}}^2$, and $1\equiv 1+\mathrm{rn}$ (mod $n^2$). Thus, $r$ must be divisible by $n$, and, since it is positive, must exceed $n$. Hence

$(n+1){}^r\ge (n+1){}^n>(n+1)n(n-1)\dots 1>n!+1\hspace{1em},$
a contradiction. The desired result follows.

---

63.

Let $n$ be a positive integer and $k$ a nonnegative integer. Prove that

Solution 1. Recall the Principle of Inclusion-Exclusion: Let $S$ be a set of $n$ objects, and let $P_1$, $P_2$, $\dots$, $P_m$ be $m$ properties such that, for each object $x\in S$ and each property $P_i$, either $x$ has the property $P_i$ or $x$ does not have the property $P_i$. Let $f(i,j,\dots ,k)$ denote the number of elements of $S$ each of which has properties $P_i$, $P_j$, $\dots$, $P_k$ (and possibly others as well). Then the number of elements of $S$ each having none of the properties $P_1$, $P_2$, $\dots$, $P_m$ is

We apply this to the problem at hand. Note that an ordered selection of $n$ numbers selected from among $1,2,\dots ,n+k$ is a permutation of $\{1,2,\dots ,n\}$ if and only if it is constrained to contain each of the numbers 1, 2, $\dots$, $n$. Let $S$ be the set of all ordered selections, and we say that a selection has property $P_i$ iff its fails to include at least $i$ of the numbers $1,2,\dots ,n$ $(1\le i\le n)$. The number of selections with property $P_i$ is the product of $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$, the number of ways of choosing the $i$ numbers not included and $(n+k-i){}^n$, the number of ways of choosing entries for the $n$ positions from the remaining $n+k-1$ numbers. The result follows.

Solution 2. We begin with a lemma:

$\sum _{i=0}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)i^m=\{\begin{array}{cc}\hfill 0\hfill & \hfill (0\le m\le n-1)\hfill \\ \multicolumn{0}{c}{(-1){}^{n}n!}& \hfill (m=n)\hspace{1em}.\hfill \end{array}$
We use the convention that $0^0=1$. To prove this, note first that $i(i-1)\dots (i-m)=i^{m+1}+b_m{i}^m+\dots +b_{1}i+b_0$ for some integers $b_i$. We use an induction argument on $m$. The result holds for each positive $n$ and for $m=0$, as the sum is the expansion of $(1-1){}^n$. It also holds for $n=1,2$ and all relevant $m$. Fix $n\ge 3$. Suppose that it holds when $m$ is replaced by $k$ for $0\le k\le m\le n-2$. Then

$\begin{array}{cc}\sum _{i=0}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)i^{m+1}\hfill & =\sum _{i=1}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)i(i-1)\dots (i-m)-\sum _{k=0}^m{b}_k\sum _{i=0}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)i^k\hfill \\ \multicolumn{0}{c}{}& =\sum _{i=m+1}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)i(i-1)\dots (i-m)-0\hfill \\ \multicolumn{0}{c}{}& =\sum _{i=m+1}^n(-1){}^i\frac{n!i!}{i!(n-i)!(i-m-1)!}=\sum _{j=0}^{n-m-1}(-1){}^{m+1+j}\frac{n!}{(n-m-1-j)!j!}\hfill \\ \multicolumn{0}{c}{}& =\sum _{j=0}^{n-m-1}(-1){}^{m+1}(-1){}^j\frac{n(n-1)\dots (n-m)[(n-m-1)!]}{(n-m-1-j)!j!}\hfill \\ \multicolumn{0}{c}{}& =(-1){}^{m+1}n(n-1)\dots (n-m)\sum _{j=0}^{n-m-1}(-1){}^j\left(\genfrac{}{}{0ex}{}{n-m-1}{j}\right)=0\hspace{1em}.\hfill \end{array}$
(Note that the $j=0$ term is 1, which is consistent with the $0^0=1$ convention mentioned earlier.) So $\sum _{i=0}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)i^m=0$ for $0\le m\le n-1$. Now consider the case $m=n$:

$\sum _{i=1}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)i^n=\sum _{i=1}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)i(i-1)\dots (i-n+1)-\sum _{k=0}^{n-1}{b}_k\sum _{i=0}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)i^k\hspace{1em}.$
Every term in the first sum vanishes except the $n$th and each term of the second sum vanishes. Hence $\sum _{i=1}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)i^n=(-1){}^{n}n!$.

Returning to the problem at hand, we see that the right side of the desired equation is equal to

$\begin{array}{cc}(n+k){}^n\hfill & -\left(\genfrac{}{}{0ex}{}{n}{1}\right)(n+k-1){}^n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)(n+k-2){}^n-\dots +(-1){}^n\left(\genfrac{}{}{0ex}{}{n}{n}\right)(n+k-n){}^n\hfill \\ \multicolumn{0}{c}{}& =\sum _{i=0}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)(n-i+k){}^n=\sum _{i=0}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)\sum _{j=0}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)(n-i){}^j{k}^{n-j}\hfill \\ \multicolumn{0}{c}{}& =\sum _{i=0}^n\sum _{j=0}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)\left(\genfrac{}{}{0ex}{}{n}{j}\right)(n-i){}^j{k}^{n-j}=\sum _{j=0}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)k^{n-j}\sum _{i=0}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)(n-i){}^j\hfill \\ \multicolumn{0}{c}{}& =\sum _{j=0}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)k^{n-j}\sum _{i=0}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{n-i}\right)(n-i){}^j\hfill \\ \multicolumn{0}{c}{}& =\sum _{j=0}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)k^{n-j}\sum _{i=0}^n(-1){}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)i^j\hspace{1em}.\hfill \end{array}$
When $0\le j\le n-1$, the sum $\sum _{i=0}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{n-i}\right)(n-i){}^j=\sum _{i=0}^n(-1){}^{n-i}\left(\genfrac{}{}{0ex}{}{n}{i}\right)i^j$ vanishes, while, when $j=n$, it assunes the value $n!$. Thus, the right side of the given equation is equal to $\left(\genfrac{}{}{0ex}{}{n}{n}\right)k^{0}n!=n!$ as desired.

Solution 3. Let $m=n+k$, so that $m\ge n$, and let the right side of the equation be denoted by $R$. Then

$\begin{array}{cc}R\hfill & =m^n-\left(\genfrac{}{}{0ex}{}{n}{1}\right)(m-1){}^n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)(m-2){}^n-\dots +(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)(m-i){}^n+\dots +(-1){}^n\left(\genfrac{}{}{0ex}{}{n}{n}\right)(m-n){}^n\hfill \\ \multicolumn{0}{c}{}& =m^m[\sum _{j=0}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)]-\left(\genfrac{}{}{0ex}{}{n}{1}\right)m^{n-1}[\sum _{i=1}^n(-1){}^{i}i\left(\genfrac{}{}{0ex}{}{n}{i}\right)]+\left(\genfrac{}{}{0ex}{}{n}{2}\right)m^{n-2}[\sum _{i=1}^n(-1){}^i{i}^2\left(\genfrac{}{}{0ex}{}{n}{i}\right)]+\dots \hfill \\ \multicolumn{0}{c}{}& \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+(-1){}^n\left(\genfrac{}{}{0ex}{}{n}{n}\right)[\sum _{i=1}^n(-1){}^i{i}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)]\hspace{1em}.\hfill \end{array}$

Let

$f_0(x)=(1-x){}^n=\sum _{i=0}^n(-1){}^i\left(\genfrac{}{}{0ex}{}{n}{i}\right)x^i$
and let

$f_k(x)=x{\mathrm{Df}}_{k-1}(x)$
for $k\ge 1$, where $\mathrm{Df}$ denotes the derivative of a function $f$. Observe that, from the closed expression for $f_0(x)$, we can establish by induction that

$f_k(x)=\sum _{i=0}^n(-1){}^i{i}^k\left(\genfrac{}{}{0ex}{}{n}{i}\right)x^i$
so that $R=\sum _{k=0}^n(-1){}^k\left(\genfrac{}{}{0ex}{}{n}{k}\right)m^{n-k}{f}_k(1)$.

By induction, we establish that

$f_k(x)=(-1){}^{k}n(n-1)\dots (n-k+1)x^k(1-x){}^{n-k}+(1-x){}^{n-k+1}{g}_k(x)$
for some polynomial $g_k(x)$. This is true for $k=1$ with $g_1(x)=0$. Suppose if holds for $k=j$. Then

$\begin{array}{cc}{f}_j\text{'}(x)\hfill & =(-1){}^{j}n(n-1)\dots (n-j+1)x^{j-1}(1-x){}^{n-j}-(-1){}^{j}n(n-1)\dots (n-j+1)(n-j)x^j(1-x){}^{n-j-1}\hfill \\ \multicolumn{0}{c}{}& \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}-(n-j+1)(1-x){}^{n-j}{g}_j(x)+(1-x){}^{n-j+1}{g}_j\text{'}(x)\hspace{1em},\hfill \end{array}$
whence

$\begin{array}{cc}{f}_{j+1}(x)\hfill & =(-1){}^{j+1}n(n_1)\dots (n-j)x^j(1-x){}^{n-(j+1)}+(1-x){}^{n-(j+1)+1}[(-1){}^{j}n(n-1)\dots (n-j+1)x^j\hfill \\ \multicolumn{0}{c}{}& \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}-(n-j+1){\mathrm{xg}}_k(x)+x(1-x)g_j\text{'}(x)]\hfill \end{array}$
and we obtain the desired representation by induction. Then for $1\le k\le n-1$, $f_k(1)=0$ while $f_n(1)=(-1){}^{n}n!$. Hence $R=(-1){}^n{f}_n(1)=n!$.

---

64.

Let $M$ be a point in the interior of triangle $\mathrm{ABC}$, and suppose that $D$, $E$, $F$ are respective points on the side $\mathrm{BC}$, $\mathrm{CA}$, $\mathrm{AB}$, which all pass through $M$. (In technical terms, they are cevians.) Suppose that the areas and the perimeters of the triangles $\mathrm{BMD}$, $\mathrm{CME}$, $\mathrm{AMF}$ are equal. Prove that triangle $\mathrm{ABC}$ must be equilateral.

Solution. [L. Lessard] Let the common area of the triangles $\mathrm{BMD}$, $\mathrm{CME}$ and $\mathrm{AMF}$ be $a$ and let their common perimeter be $p$. Let the area and perimeter of $\Delta \mathrm{AME}$ be $u$ and $x$ respectively, of $\Delta \mathrm{MFB}$ be $v$ and $y$ respectively, and of $\Delta \mathrm{CMD}$ be $w$ and $z$ respectively.

By considering pairs of triangles with equal heights, we find that

$\frac{\mathrm{AF}}{\mathrm{FB}}=\frac{a}{v}=\frac{2a+u}{v+a+w}=\frac{a+u}{a+w}\hspace{1em},$

$\frac{\mathrm{BD}}{\mathrm{DC}}=\frac{a}{w}=\frac{2a+v}{u+a+w}=\frac{a+v}{a+u}\hspace{1em},$

$\frac{\mathrm{CE}}{\mathrm{EA}}=\frac{a}{u}=\frac{2a+w}{u+a+v}=\frac{a+w}{a+v}\hspace{1em}.$
>From these three sets of equations, we deduce that

$\frac{a^3}{\mathrm{uvw}}=1\hspace{1em};$

$a^2+(w-u)a-\mathrm{uv}=0\hspace{1em},$

$a^2+(u-w)a-\mathrm{vw}=0\hspace{1em},$

$a^2+(v-u)a-\mathrm{uw}=0\hspace{1em};$
whence

$a^3=\mathrm{uvw}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{and}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}3a^2=\mathrm{uv}+\mathrm{vw}+\mathrm{uw}\hspace{1em}.$
This means that $\mathrm{uv},\mathrm{vw},\mathrm{uw}$ are three positive numbers whose geometric and arithmetic means are both equal to $a^2$. Hence $a^2=\mathrm{uv}=\mathrm{vw}=\mathrm{uw}$, so that $u=v=w=a$. It follows that $\mathrm{AF}=\mathrm{FB}$, $\mathrm{BD}=\mathrm{DC}$, $\mathrm{CE}=\mathrm{EA}$, so that $\mathrm{AD}$, $\mathrm{BE}$ and $\mathrm{CF}$ are medians and $M$ is the centroid.

Wolog, suppose that $\mathrm{AB}\ge \mathrm{BC}\ge \mathrm{CA}$. Since $\mathrm{AB}\ge \mathrm{BC}$, $\angle \mathrm{AEB}\ge {90}^{ˆ}$, and so $\mathrm{AM}\ge \mathrm{MC}$. Thus $x\ge p$. Similarly, $y\ge p$ and $p\ge z$.

Consider triangles $\mathrm{BMD}$ and $\mathrm{AME}$. We have $\mathrm{BD}\ge \mathrm{AE}$, $\mathrm{BM}\ge \mathrm{AM}$, $\mathrm{ME}=\frac{1}{2}\mathrm{BM}$ and $\mathrm{MD}=\frac{1}{2}\mathrm{AM}$. Therefore

$p-x=(\mathrm{BD}+\mathrm{MD}+\mathrm{BM})-(\mathrm{AE}+\mathrm{ME}+\mathrm{AM})=(\mathrm{BD}-\mathrm{AE})+\frac{1}{2}(\mathrm{BM}-\mathrm{AM})\ge 0$
and so $p\ge x$. Since also $x\ge p$, we have that $p=x$. But this implies that $\mathrm{AM}=\mathrm{MC}$, so that $\mathrm{ME}\perp \mathrm{AC}$ and $\mathrm{AB}=\mathrm{BC}$. Since $\mathrm{BE}$ is now an axis of a reflection which interchanges $A$ and $C$, as well as $F$ and $D$, it follows that $p=z$ and $p=y$ as well. Thus, $\mathrm{AB}=\mathrm{AC}$ and $\mathrm{AC}=\mathrm{BC}$. Thus, the triangle is equilateral.

---

65.

Suppose that $\mathrm{XTY}$ is a straight line and that $\mathrm{TU}$ and $\mathrm{TV}$ are two rays emanating from $T$ for which $\angle \mathrm{XTU}=\angle \mathrm{UTV}=\angle \mathrm{VTY}={60}^{ˆ}$. Suppose that $P$, $Q$ and $R$ are respective points on the rays $\mathrm{TY}$, $\mathrm{TU}$ and $\mathrm{TV}$ for which $\mathrm{PQ}=\mathrm{PR}$. Prove that $\angle \mathrm{QPR}={60}^{ˆ}$.

Solution 1. Let $\backslash frakR$ be a rotation of ${60}^{ˆ}$ about $T$ that takes the ray $\mathrm{TU}$ to $\mathrm{TV}$. Then, if $\backslash frakR$ transforms $Q\to Q\text{'}$ and $P\to P\text{'}$, then $Q\text{'}$ lies on $\mathrm{TV}$ and the line $Q\text{'}P\text{'}$ makes an angle of ${60}^{ˆ}$ with $\mathrm{QP}$. Because of the rotation, $\angle P\text{'}\mathrm{TP}={60}^{ˆ}$ and $\mathrm{TP}\text{'}=\mathrm{TP}$, whence $\mathrm{TP}\text{'}P$ is an equilateral triangle.

Since $\angle Q\text{'}\mathrm{TP}=\angle \mathrm{TPP}\text{'}={60}^{ˆ}$, $\mathrm{TV}P\text{'}P$. Let $\backslash frakT$ be the translation that takes $P\text{'}$ to $P$. It takes $Q\text{'}$ to a point $Q\text{'}\text{'}$ on the ray $\mathrm{TV}$, and $\mathrm{PQ}\text{'}\text{'}=P\text{'}Q\text{'}=\mathrm{PQ}$. Hence $Q\text{'}\text{'}$ can be none other than the point $R$ [why?], and the result follows.

Solution 2. The reflection in the line $\mathrm{XY}$ takes $P\to P$, $Q\to Q\text{'}$ and $R\to R\text{'}$. Triangles $\mathrm{PQR}\text{'}$ and $\mathrm{PQ}\text{'}R$ are congruent and isosceles, so that $\angle \mathrm{TQP}=\angle \mathrm{TQ}\text{'}P=\angle \mathrm{TRP}$ (since $\mathrm{PQ}\text{'}=\mathrm{PR}$). Hence $\mathrm{TQRP}$ is a concyclic quadrilateral, whence $\angle \mathrm{QPR}=\angle \mathrm{QTR}={60}^{ˆ}$.

Solution 3. [S. Niu] Let $S$ be a point on $\mathrm{TU}$ for which $\mathrm{SR}\mathrm{XY}$; observe that $\Delta \mathrm{RST}$ is equilateral. We first show that $Q$ lies between $S$ and $T$. For, if $S$ were between $Q$ and $T$, then $\angle \mathrm{PSQ}$ would be obtuse and $\mathrm{PQ}>\mathrm{PS}>\mathrm{PR}$ (since $\angle \mathrm{PRS}>{60}^{ˆ}>\angle \mathrm{PSR}$ in $\Delta \mathrm{PRS}$), a contradiction.

The rotation of ${60}^{ˆ}$ with centre $R$ that takes $S$ onto $T$ takes ray $\mathrm{RQ}$ onto a ray through $R$ that intersects $\mathrm{TY}$ in $M$. Consider triangles $\mathrm{RSQ}$ and $\mathrm{RTM}$. Since $\angle \mathrm{RST}=\angle \mathrm{RTM}={60}^{ˆ}$, $\angle \mathrm{SRQ}={60}^{ˆ}-\angle \mathrm{QRT}=\angle \mathrm{TRM}$ and $\mathrm{SR}=\mathrm{TR}$, we have that $\Delta \mathrm{RSQ}\equiv \Delta \mathrm{RTM}$ and $\mathrm{RQ}=\mathrm{RM}$. (ASA) Since $\angle \mathrm{QRM}={60}^{ˆ}$, $\Delta \mathrm{RQM}$ is equilateral and $\mathrm{RM}=\mathrm{RQ}$. Hence $M$ and $P$ are both equidistant from $Q$ and $R$, and so at the intersection of $\mathrm{TY}$ and the right bisector of $\mathrm{QR}$. Thus, $M=P$ and the result follows.

Solution 4. [H. Pan] Let $Q\text{'}$ and $R\text{'}$ be the respective reflections of $Q$ and $R$ with respect to the axis $\mathrm{XY}$. Since $\angle \mathrm{RTR}\text{'}={120}^{ˆ}$ and $\mathrm{TR}=\mathrm{TR}\text{'}$, $\angle \mathrm{QR}\text{'}R=\angle \mathrm{TR}\text{'}R={30}^{ˆ}$. Since $Q,R,Q\text{'},R\text{'},$ lie on a circle with centre $P$, $\angle \mathrm{QPR}=2\angle \mathrm{QR}\text{'}R={60}^{ˆ}$, as desired.

Solution 5. [R. Barrington Leigh] Let $W$ be a point on $\mathrm{TV}$ such that $\angle \mathrm{WPQ}={60}^{ˆ}=\angle \mathrm{WTU}$. [Why does such a point $W$ exist?] Then $\mathrm{WQTP}$ is a concyclic quadrilateral so that $\angle \mathrm{QWP}={180}^{ˆ}-\angle \mathrm{QTP}={60}^{ˆ}$ and $\Delta \mathrm{PWQ}$ is equilateral. Hence $\mathrm{PW}=\mathrm{PQ}=\mathrm{PR}$.

Suppose $W\ne R$. If $R$ is farther away from $T$ than $W$, then $\angle \mathrm{RPT}>\angle \mathrm{WPT}>\angle \mathrm{WPQ}={60}^{ˆ}\Rightarrow {60}^{ˆ}>\angle \mathrm{TRP}=\angle \mathrm{RWP}>{60}^{ˆ}$, a contradiction. If $W$ is farther away from $T$ than $R$, then $\angle \mathrm{WPT}>\angle \mathrm{WPQ}={60}^{ˆ}\Rightarrow {60}^{ˆ}>\angle \mathrm{RWP}=\angle \mathrm{WRP}>{60}^{ˆ}$, again a contradiction. So $R=W$ and the result follows.

Solution 6. [M. Holmes] Let the circle through $T,P,Q$ intersect $\mathrm{TV}$ in $N$. Then $\angle \mathrm{QNP}={180}^{ˆ}-\angle \mathrm{QTP}={60}^{ˆ}$. Since $\angle \mathrm{PQN}=\angle \mathrm{PTN}={60}^{ˆ}$, $\Delta \mathrm{PQN}$ is equilateral so that $\mathrm{PN}=\mathrm{PQ}$. Suppose, if possible, that $R\ne N$. Then $N$ and $R$ are two points on $\mathrm{TV}$ equidistant from $P$. Since $\angle \mathrm{PNT}<\angle \mathrm{PNQ}={60}^{ˆ}$ and $\Delta \mathrm{PNR}$ is isosceles, we have that $\angle \mathrm{PNR}<{90}^{ˆ}$, so $N$ cannot lie between $T$ and $R$, and $\angle \mathrm{PRN}=\angle \mathrm{PNR}=\angle \mathrm{PNT}<{60}^{ˆ}$. Since $\angle \mathrm{PTN}={60}^{ˆ}$, we conclude that $T$ must lie between $R$ and $N$, which transgresses the condition of the problem. Hence $R$ and $N$ must coincide and the result follows.

Solution 7. [P. Cheng] Determine $S$ on $\mathrm{TU}$ and $Z$ on $\mathrm{TY}$ for which $\mathrm{SR}\mathrm{XY}$ and $\angle \mathrm{QRZ}={60}^{ˆ}$. Observe that $\angle \mathrm{TSR}=\angle \mathrm{SRT}={60}^{ˆ}$ and $\mathrm{SR}=\mathrm{RT}$.

Consider triangles $\mathrm{SRQ}$ and $\mathrm{TRZ}$. $\angle \mathrm{SRQ}=\angle \mathrm{SRT}-\angle \mathrm{QRT}=\angle \mathrm{QRZ}-\angle \mathrm{QRT}=\angle \mathrm{TRZ}$; $\angle \mathrm{QSR}={60}^{ˆ}=\angle \mathrm{ZTR}$, so that $\Delta \mathrm{SRQ}=\Delta \mathrm{TRZ}$ (ASA).

Hence $\mathrm{RZ}=\mathrm{RQ}\Rightarrow \Delta \mathrm{RQZ}$ is equilateral $\Rightarrow \mathrm{RZ}=\mathrm{ZQ}$ and $\angle \mathrm{RZQ}={60}^{ˆ}$. Now, both $P$ and $Z$ lie on the intersection of $\mathrm{TY}$ and the right bisector of $\mathrm{QR}$, so they must coincide: $P=Z$. The result follows.

Solution 8. Let the perpendicular, produced, from $Q$ to $\mathrm{XY}$ meet $\mathrm{VT}$, produced, in $S$. Then $\angle \mathrm{XTS}=\angle \mathrm{VTY}={60}^{ˆ}=\angle \mathrm{XTU}$, from which is can be deduced that $\mathrm{TX}$ right bisects $\mathrm{QS}$. Hence $\mathrm{PS}=\mathrm{PQ}=\mathrm{PR}$, so that $Q,R,S$ are all on the same circle with centre $P$.

Since $\angle \mathrm{QTS}={120}^{ˆ}$, we have that $\angle \mathrm{SQT}=\angle \mathrm{QSR}={30}^{ˆ}$, so that $\mathrm{QR}$ must subtend an angle of ${60}^{ˆ}$ at the centre $P$ of the circle. The desired result follows.

Solution 9. [A.Siu] Let the right bisector of $\mathrm{QR}$ meet the circumcircle of $\mathrm{TQR}$ on the same side of $\mathrm{QR}$ at $T$ in $S$. Since $\angle \mathrm{QSR}=\angle \mathrm{QTR}={60}^{ˆ}$ and $\mathrm{QS}=\mathrm{QR}$, $\angle \mathrm{SQR}=\angle \mathrm{SRQ}={60}^{ˆ}$. Hence $\angle \mathrm{STQ}={180}^{ˆ}-\angle \mathrm{SRQ}={120}^{ˆ}$. But $\angle \mathrm{YTQ}={120}^{ˆ}$, so $S$ must lie on $\mathrm{TY}$. It follows that $S=P$.

Solution 10. Assign coordinates with the origin at $T$ and the $x-$axis along $\mathrm{XY}$. The the respective coordinates of $Q$ and $R$ have the form $(u,-\sqrt{3}u)$ and $(v,\sqrt{3}v)$ for some real $u$ and $v$. Let the coordinates of $P$ be $(w,0)$. Then $\mathrm{PQ}=\mathrm{PR}$ yields that $w=2(u+v)$. [Exercise: work it out.]

$\begin{array}{cc}\Vert \mathrm{PQ}\Vert {}^2-\Vert \mathrm{QR}\Vert {}^2\hfill & =(u-w){}^2+3u^2-(u-v){}^2-3(u+v){}^2\hfill \\ \multicolumn{0}{c}{}& =w^2-2\mathrm{uw}-4v(u+v)=w^2-2\mathrm{uw}-2\mathrm{vw}\hfill \\ \multicolumn{0}{c}{}& =w^2-2(u+v)w=0\hspace{1em}.\hfill \end{array}$
Hence $\mathrm{PQ}=\mathrm{QR}=\mathrm{PR}$ and $\Delta \mathrm{PQR}$ is equilateral. Therefore $\angle \mathrm{QPR}={60}^{ˆ}$.

Solution 11. [J.Y. Jin] Let $\backslash frakC$ be the circumcircle of $\Delta \mathrm{PQR}$. If $T$ lies strictly inside $\backslash frakC$, then ${60}^{ˆ}=\angle \mathrm{QTR}>\angle \mathrm{QPR}$ and ${60}^{ˆ}=\angle \mathrm{PTR}>\angle \mathrm{PQR}=\angle \mathrm{PRQ}$. Thus, all three angle of $\Delta \mathrm{PQR}$ would be less than ${60}^{ˆ}$, which is not possible. Similarly, if $T$ lies strictly outside $\backslash frakC$, then ${60}^{ˆ}=\angle \mathrm{QTR}<\angle \mathrm{QPR}$ and ${60}^{ˆ}=\angle \mathrm{PTR}<\angle \mathrm{PQR}=\angle \mathrm{PRQ}$, so that all three angles of $\Delta \mathrm{PQR}$ would exceed ${60}^{ˆ}$, again not possible. Thus $T$ must be on $\backslash frakC$, whence $\angle \mathrm{QPR}=\angle \mathrm{QTR}={60}^{ˆ}$.

Solution 12. [C. Lau] By the Sine Law,

$\frac{\sin \angle \mathrm{TQP}}{\Vert \mathrm{TP}\Vert }=\frac{\sin {120}^{ˆ}}{\Vert \mathrm{PQ}\Vert }=\frac{\sin {60}^{ˆ}}{\Vert \mathrm{PR}\Vert }=\frac{\sin \angle \mathrm{TRP}}{\Vert \mathrm{TP}\Vert }\hspace{1em},$
whence $\sin \angle \mathrm{TQP}=\sin \angle \mathrm{TRP}$. Since $\angle \mathrm{QTP}$, in triangle $\mathrm{QTP}$ is obtuse, $\angle \mathrm{TQP}$ is acute.

Suppose, if possible, that $\angle \mathrm{TRP}$ is obtuse. Then, in triangle $\mathrm{TPR}$, $\mathrm{TP}$ would be the longest side, so $\mathrm{PR}<\mathrm{TP}$. But in triangle $\mathrm{TQP}$, $\mathrm{PQ}$ is the longest side, so $\mathrm{PQ}>\mathrm{TP}$, and so $\mathrm{PQ}\ne \mathrm{PR}$, contrary to hypothesis. Hence $\angle \mathrm{TRP}$ is acute. Therefore, $\angle \mathrm{TQP}=\angle \mathrm{TRP}$. Let $\mathrm{PQ}$ and $\mathrm{RT}$ intersect in $Z$. Then, ${60}^{ˆ}=\angle \mathrm{QTZ}={180}^{ˆ}-\angle \mathrm{TQP}-\angle \mathrm{QZT}={180}^{ˆ}-\angle \mathrm{TRP}-\angle \mathrm{RZP}=\angle \mathrm{QPR}$, as desired.

---

66.

(a) Let $\mathrm{ABCD}$ be a square and let $E$ be an arbitrary point on the side $\mathrm{CD}$. Suppose that $P$ is a point on the diagonal $\mathrm{AC}$ for which $\mathrm{EP}\perp \mathrm{AC}$ and that $Q$ is a point on $\mathrm{AE}$ produced for which $\mathrm{CQ}\perp \mathrm{AE}$. Prove that $B,P,Q$ are collinear.

(b) Does the result hold if the hypothesis is weakened to require only that $\mathrm{ABCD}$ is a rectangle?

Solution 1. Let $\mathrm{ABCD}$ be a rectangle, and let $E$, $P$, $Q$ be determined as in the problem. Suppose that $\angle \mathrm{ACD}=\angle \mathrm{BDC}=\alpha$. Then $\angle \mathrm{PEC}={90}^{ˆ}-\alpha$. Because $\mathrm{EPQC}$ is concyclic, $\angle \mathrm{PQC}=\angle \mathrm{PEC}={90}^{ˆ}-\alpha$. Because $\mathrm{ABCQD}$ is concyclic, $\angle \mathrm{BQC}=\angle \mathrm{BDC}=\alpha$. The points $B$, $P$, $Q$ are collinear $\&lrArr;\angle \mathrm{BQC}=\angle \mathrm{PQC}\&lrArr;\alpha ={90}^{ˆ}-\alpha \&lrArr;\alpha ={45}^{ˆ}\&lrArr;\mathrm{ABCD}$ is a square.

Solution 2. (a) $\mathrm{EPQC}$, with a pair of supplementary opposite angles, is concyclic, so that $\angle \mathrm{CQP}=\angle \mathrm{CEP}={180}^{ˆ}-\angle \mathrm{EPC}-\angle \mathrm{ECP}={45}^{ˆ}$. Since $\mathrm{CBAQ}$ is concyclic, $\angle \mathrm{CQB}=\angle \mathrm{CAB}={45}^{ˆ}$. Thus, $\angle \mathrm{CQP}=\angle \mathrm{CQB}$ so that $Q$, $P$, $B$ are collinear.

(b) Suppose that $\mathrm{ABCD}$ is a nonquare rectangle. Then taking $E=D$ yields a counterexample.

Solution 3. (a) The circle with diameter $\mathrm{AC}$ that passes through the vertices of the square also passes through $Q$. Hence $\angle \mathrm{QBC}=\angle \mathrm{QAC}$. Consider triangles $\mathrm{PBC}$ and $\mathrm{EAC}$. Since triangles $\mathrm{ABC}$ and $\mathrm{EPC}$ are both isosceles right triangles, $\mathrm{BC}:\mathrm{AC}=\mathrm{PC}:\mathrm{EC}$. Also $\angle \mathrm{BCA}=\angle \mathrm{PCE}={45}^{ˆ}$. Hence $\Delta \mathrm{PBC}~\Delta \mathrm{EAC}$ (SAS) so that $\angle \mathrm{PBC}=\angle \mathrm{EAC}=\angle \mathrm{QAC}=\angle \mathrm{QBC}$. It follows that $Q$, $P$, $B$ are collinear.

Solution 4. [S. Niu] Let $\mathrm{ABCD}$ be a rectangle and let $E,P,Q$ be determined as in the problem. Let $\mathrm{EP}$ be produced to meet $\mathrm{BC}$ in $F$. Since $\angle \mathrm{ABF}=\angle \mathrm{APF}$, the quadrilateral $\mathrm{ABPF}$ is concyclic, so that $\angle \mathrm{PBC}=\angle \mathrm{PBF}=\angle \mathrm{PAF}$. Since $\mathrm{ABCQ}$ is concyclic, $\angle \mathrm{QBC}=\angle \mathrm{QAC}=\angle \mathrm{PAE}$. Now $B,P,Q$ are collinear

$\&lrArr;\angle \mathrm{PBC}=\angle \mathrm{QBC}\&lrArr;\angle \mathrm{PAF}=\angle \mathrm{PAE}\&lrArr;\mathrm{AC}\hspace{1em}\hspace{1em}\mathrm{right}\hspace{1em}\hspace{1em}\mathrm{bisects}\hspace{1em}\hspace{1em}\mathrm{EF}$

$\&lrArr;\angle \mathrm{ECA}=\angle \mathrm{ACB}={45}^{ˆ}\&lrArr;\mathrm{ABCD}\hspace{1em}\hspace{1em}\mathrm{is}\hspace{1em}\hspace{1em}a\hspace{1em}\hspace{1em}\mathrm{square}\hspace{1em}.$

Solution 5. [M. Holmes] (a) Suppose that $\mathrm{BQ}$ intersects $\mathrm{AC}$ in $R$. Since $\mathrm{ABCQD}$ is concyclic, $\angle \mathrm{AQR}=\angle \mathrm{AQB}=\angle \mathrm{ACB}={45}^{ˆ}$, so that $\angle \mathrm{BQC}={45}^{ˆ}$. Since $\angle \mathrm{EQR}=\angle \mathrm{AQB}=\angle \mathrm{ECR}={45}^{ˆ}$, $\mathrm{ERCQ}$ is concyclic, so that $\angle \mathrm{ERC}={180}^{ˆ}-\angle \mathrm{EQC}={90}^{ˆ}$. Hence $\mathrm{ER}\perp \mathrm{AC}$, so that $R=P$ and the result follows.

Solution 6. [L. Hong] (a) Let $\mathrm{QC}$ intersect $\mathrm{AB}$ in $F$. We apply Menelaus' Theorem to triangle $\mathrm{AFC}$: $B$, $P$, $Q$ are collinear if and only if

$\frac{\mathrm{AB}}{\mathrm{BF}}·\frac{\mathrm{FQ}}{\mathrm{QC}}·\frac{\mathrm{CP}}{\mathrm{PA}}=-1\hspace{1em}.$
Let the side length of the square be 1 and the length of $\mathrm{DE}$ be $a$. Then $\Vert \mathrm{AB}\Vert =1$. Since $\Delta \mathrm{ADE}~\Delta \mathrm{FBC}$, $\mathrm{AD}:\mathrm{DE}=\mathrm{BF}:\mathrm{BC}$, so that $\Vert \mathrm{BF}\Vert =1/a$ and $\Vert \mathrm{FC}\Vert =\sqrt{1+a^2}/a$. Since $\Delta \mathrm{ADE}~\Delta \mathrm{CQE}$, $\mathrm{CQ}:\mathrm{EC}=\mathrm{AD}:\mathrm{EA}$, so that $\Vert \mathrm{CQ}\Vert =(1-a)/\sqrt{1+a^2}$. Hence

$\frac{\Vert \mathrm{FQ}\Vert }{\Vert \mathrm{CQ}\Vert }=1+\frac{\Vert \mathrm{FC}\Vert }{\Vert \mathrm{CQ}\Vert }=1+\frac{1+a^2}{a(1-a)}=\frac{1+a}{a(1-a)}\hspace{1em}.$
Since $\Delta \mathrm{ECP}$ is right isosceles, $\Vert \mathrm{CP}\Vert =(1-a)/\sqrt{2}$ and $\Vert \mathrm{PA}\Vert =\sqrt{2}-\Vert \mathrm{CP}\Vert =(1+a)/\sqrt{2}$. Hence $\Vert \mathrm{CP}\Vert /\Vert \mathrm{PA}\Vert =(1-a)/(1+a)$. Multiplying the three ratios together and taking account of the directed segments gives the product $-1$ and yields the result.

Solution 7. (a) Select coordinates so that $A~(0,1)$, $B~(0,0)$, $C~(1,0)$, $D~(1,1)$ and $E~(1,t)$ for some $t$ with $0\le t\le 1$. It is straightforward to verify that $P~(1-\frac{t}{2},\frac{t}{2})$.

Since the slope of $\mathrm{AE}$ is $t-1$, the slope of $\mathrm{AQ}$ should be $(1-t){}^{-1}$. Since the coordinates of $Q$ have the form $(1+s,s(1-t){}^{-1})$ for some $s$, it is straightforward to verify that

$Q~(\frac{2-t}{1+(1-t){}^2},\frac{t}{1+(1-t){}^2)})\hspace{1em}.$
It can now be checked that the slope of each of $\mathrm{BQ}$ and $\mathrm{BP}$ is $t(2-t){}^{-1}$, which yields the result.

(b) The result fails if $A~(0,2)$, $B~(0,0)$, $C~(1,0)$, $D~(1,2)$. If $E~(1,1)$, then $P~(\frac{3}{5},\frac{4}{5})$ and $Q~(\frac{3}{2},\frac{1}{2})$.