location:

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$, $\left(2j-1\right)!\left(2j\right)!=\left[\left(2j-1\right)!\right]{}^{2}·2j$. Hence

$S=\underset{j=1}{\overset{50}{\Pi }}\left[\left(2j-1\right)!\right]{}^{2}\left[2j\right]={2}^{50}50!\left[\underset{j=1}{\overset{50}{\Pi }}\left(2j-1\right)!{\right]}^{2} ,$

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-\left(p-1\right)=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 \left(2m-1\right)!$ to an even power and $100!$ to the power with exponent

$⌊100/2⌋+⌊100/4⌋+⌊100/8⌋+⌊100/16⌋+⌊100/32⌋+⌊100/64⌋=50+25+12+6+3+1=97 .$

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=\left(2·4\dots 50\right)\left({2}^{49}·{3}^{49}·{4}^{48}\dots 99\right){}^{2}=50!·{2}^{50}\left(\dots \right){}^{2} ,$

$S/50!$ is a square, and so $S/51!=\left(S/50!\right)÷\left(51\right)$ is not a square. The result follows.
Solution 3. As above, $S/\left(50!\right)$ 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!=\left(S/50!\right)÷\left(k!/50!\right)$ 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!=\left(S/50!\right)×\left(50!/k!\right)$ 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=\left(n+1\right){}^{r}=1+\mathrm{rn}+{\mathrm{Kn}}^{2} .$

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

$\left(n+1\right){}^{r}\ge \left(n+1\right){}^{n}>\left(n+1\right)n\left(n-1\right)\dots 1>n!+1 ,$

a contradiction. The desired result follows.

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

$n!=\left(n+k\right){}^{n}-\left(\genfrac{}{}{0}{}{n}{1}\right)\left(n+k-1\right){}^{n}+\left(\genfrac{}{}{0}{}{n}{2}\right)\left(n+k-2\right){}^{n}-\dots ±\left(\genfrac{}{}{0}{}{n}{n}\right){k}^{n} .$

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\left(i,j,\dots ,k\right)$ 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

$n-\sum _{1\le i\le m}f\left(i\right)+\sum _{1\le i

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 $\left\{1,2,\dots ,n\right\}$ 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$ $\left(1\le i\le n\right)$. The number of selections with property ${P}_{i}$ is the product of $\left(\genfrac{}{}{0}{}{n}{i}\right)$, the number of ways of choosing the $i$ numbers not included and $\left(n+k-i\right){}^{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}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right){i}^{m}=\left\{\begin{array}{cc}\hfill 0\hfill & \hfill \left(0\le m\le n-1\right)\hfill \\ \multicolumn{0}{c}{\left(-1\right){}^{n}n!}& \hfill \left(m=n\right) .\hfill \end{array}$

We use the convention that ${0}^{0}=1$. To prove this, note first that $i\left(i-1\right)\dots \left(i-m\right)={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 $\left(1-1\right){}^{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}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right){i}^{m+1}\hfill & =\sum _{i=1}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right)i\left(i-1\right)\dots \left(i-m\right)-\sum _{k=0}^{m}{b}_{k}\sum _{i=0}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right){i}^{k}\hfill \\ \multicolumn{0}{c}{}& =\sum _{i=m+1}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right)i\left(i-1\right)\dots \left(i-m\right)-0\hfill \\ \multicolumn{0}{c}{}& =\sum _{i=m+1}^{n}\left(-1\right){}^{i}\frac{n!i!}{i!\left(n-i\right)!\left(i-m-1\right)!}=\sum _{j=0}^{n-m-1}\left(-1\right){}^{m+1+j}\frac{n!}{\left(n-m-1-j\right)!j!}\hfill \\ \multicolumn{0}{c}{}& =\sum _{j=0}^{n-m-1}\left(-1\right){}^{m+1}\left(-1\right){}^{j}\frac{n\left(n-1\right)\dots \left(n-m\right)\left[\left(n-m-1\right)!\right]}{\left(n-m-1-j\right)!j!}\hfill \\ \multicolumn{0}{c}{}& =\left(-1\right){}^{m+1}n\left(n-1\right)\dots \left(n-m\right)\sum _{j=0}^{n-m-1}\left(-1\right){}^{j}\left(\genfrac{}{}{0}{}{n-m-1}{j}\right)=0 .\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}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right){i}^{m}=0$ for $0\le m\le n-1$. Now consider the case $m=n$:

$\sum _{i=1}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right){i}^{n}=\sum _{i=1}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right)i\left(i-1\right)\dots \left(i-n+1\right)-\sum _{k=0}^{n-1}{b}_{k}\sum _{i=0}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right){i}^{k} .$

Every term in the first sum vanishes except the $n$th and each term of the second sum vanishes. Hence $\sum _{i=1}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right){i}^{n}=\left(-1\right){}^{n}n!$.
Returning to the problem at hand, we see that the right side of the desired equation is equal to

$\begin{array}{cc}\left(n+k\right){}^{n}\hfill & -\left(\genfrac{}{}{0}{}{n}{1}\right)\left(n+k-1\right){}^{n}+\left(\genfrac{}{}{0}{}{n}{2}\right)\left(n+k-2\right){}^{n}-\dots +\left(-1\right){}^{n}\left(\genfrac{}{}{0}{}{n}{n}\right)\left(n+k-n\right){}^{n}\hfill \\ \multicolumn{0}{c}{}& =\sum _{i=0}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right)\left(n-i+k\right){}^{n}=\sum _{i=0}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right)\sum _{j=0}^{n}\left(\genfrac{}{}{0}{}{n}{j}\right)\left(n-i\right){}^{j}{k}^{n-j}\hfill \\ \multicolumn{0}{c}{}& =\sum _{i=0}^{n}\sum _{j=0}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right)\left(\genfrac{}{}{0}{}{n}{j}\right)\left(n-i\right){}^{j}{k}^{n-j}=\sum _{j=0}^{n}\left(\genfrac{}{}{0}{}{n}{j}\right){k}^{n-j}\sum _{i=0}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right)\left(n-i\right){}^{j}\hfill \\ \multicolumn{0}{c}{}& =\sum _{j=0}^{n}\left(\genfrac{}{}{0}{}{n}{j}\right){k}^{n-j}\sum _{i=0}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{n-i}\right)\left(n-i\right){}^{j}\hfill \\ \multicolumn{0}{c}{}& =\sum _{j=0}^{n}\left(\genfrac{}{}{0}{}{n}{j}\right){k}^{n-j}\sum _{i=0}^{n}\left(-1\right){}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right){i}^{j} .\hfill \end{array}$

When $0\le j\le n-1$, the sum $\sum _{i=0}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{n-i}\right)\left(n-i\right){}^{j}=\sum _{i=0}^{n}\left(-1\right){}^{n-i}\left(\genfrac{}{}{0}{}{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{}{}{0}{}{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{}{}{0}{}{n}{1}\right)\left(m-1\right){}^{n}+\left(\genfrac{}{}{0}{}{n}{2}\right)\left(m-2\right){}^{n}-\dots +\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right)\left(m-i\right){}^{n}+\dots +\left(-1\right){}^{n}\left(\genfrac{}{}{0}{}{n}{n}\right)\left(m-n\right){}^{n}\hfill \\ \multicolumn{0}{c}{}& ={m}^{m}\left[\sum _{j=0}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right)\right]-\left(\genfrac{}{}{0}{}{n}{1}\right){m}^{n-1}\left[\sum _{i=1}^{n}\left(-1\right){}^{i}i\left(\genfrac{}{}{0}{}{n}{i}\right)\right]+\left(\genfrac{}{}{0}{}{n}{2}\right){m}^{n-2}\left[\sum _{i=1}^{n}\left(-1\right){}^{i}{i}^{2}\left(\genfrac{}{}{0}{}{n}{i}\right)\right]+\dots \hfill \\ \multicolumn{0}{c}{}& +\left(-1\right){}^{n}\left(\genfrac{}{}{0}{}{n}{n}\right)\left[\sum _{i=1}^{n}\left(-1\right){}^{i}{i}^{n}\left(\genfrac{}{}{0}{}{n}{i}\right)\right] .\hfill \end{array}$

Let

${f}_{0}\left(x\right)=\left(1-x\right){}^{n}=\sum _{i=0}^{n}\left(-1\right){}^{i}\left(\genfrac{}{}{0}{}{n}{i}\right){x}^{i}$

and let

${f}_{k}\left(x\right)=x{\mathrm{Df}}_{k-1}\left(x\right)$

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

${f}_{k}\left(x\right)=\sum _{i=0}^{n}\left(-1\right){}^{i}{i}^{k}\left(\genfrac{}{}{0}{}{n}{i}\right){x}^{i}$

so that $R=\sum _{k=0}^{n}\left(-1\right){}^{k}\left(\genfrac{}{}{0}{}{n}{k}\right){m}^{n-k}{f}_{k}\left(1\right)$.
By induction, we establish that

${f}_{k}\left(x\right)=\left(-1\right){}^{k}n\left(n-1\right)\dots \left(n-k+1\right){x}^{k}\left(1-x\right){}^{n-k}+\left(1-x\right){}^{n-k+1}{g}_{k}\left(x\right)$

for some polynomial ${g}_{k}\left(x\right)$. This is true for $k=1$ with ${g}_{1}\left(x\right)=0$. Suppose if holds for $k=j$. Then

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

whence

$\begin{array}{cc}{f}_{j+1}\left(x\right)\hfill & =\left(-1\right){}^{j+1}n\left({n}_{1}\right)\dots \left(n-j\right){x}^{j}\left(1-x\right){}^{n-\left(j+1\right)}+\left(1-x\right){}^{n-\left(j+1\right)+1}\left[\left(-1\right){}^{j}n\left(n-1\right)\dots \left(n-j+1\right){x}^{j}\hfill \\ \multicolumn{0}{c}{}& -\left(n-j+1\right){\mathrm{xg}}_{k}\left(x\right)+x\left(1-x\right){g}_{j}\text{'}\left(x\right)\right]\hfill \end{array}$

and we obtain the desired representation by induction. Then for $1\le k\le n-1$, ${f}_{k}\left(1\right)=0$ while ${f}_{n}\left(1\right)=\left(-1\right){}^{n}n!$. Hence $R=\left(-1\right){}^{n}{f}_{n}\left(1\right)=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} ,$

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

$\frac{\mathrm{CE}}{\mathrm{EA}}=\frac{a}{u}=\frac{2a+w}{u+a+v}=\frac{a+w}{a+v} .$

>From these three sets of equations, we deduce that

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

${a}^{2}+\left(w-u\right)a-\mathrm{uv}=0 ,$

${a}^{2}+\left(u-w\right)a-\mathrm{vw}=0 ,$

${a}^{2}+\left(v-u\right)a-\mathrm{uw}=0 ;$

whence

${a}^{3}=\mathrm{uvw} \mathrm{and} 3{a}^{2}=\mathrm{uv}+\mathrm{vw}+\mathrm{uw} .$

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=\left(\mathrm{BD}+\mathrm{MD}+\mathrm{BM}\right)-\left(\mathrm{AE}+\mathrm{ME}+\mathrm{AM}\right)=\left(\mathrm{BD}-\mathrm{AE}\right)+\frac{1}{2}\left(\mathrm{BM}-\mathrm{AM}\right)\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 $\frakR$ be a rotation of ${60}^{ˆ}$ about $T$ that takes the ray $\mathrm{TU}$ to $\mathrm{TV}$. Then, if $\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 $\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}^{ˆ}⇒{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}^{ˆ}⇒{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}⇒\Delta \mathrm{RQZ}$ is equilateral $⇒\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 $\left(u,-\sqrt{3}u\right)$ and $\left(v,\sqrt{3}v\right)$ for some real $u$ and $v$. Let the coordinates of $P$ be $\left(w,0\right)$. Then $\mathrm{PQ}=\mathrm{PR}$ yields that $w=2\left(u+v\right)$. [Exercise: work it out.]

$\begin{array}{cc}‖\mathrm{PQ}‖{}^{2}-‖\mathrm{QR}‖{}^{2}\hfill & =\left(u-w\right){}^{2}+3{u}^{2}-\left(u-v\right){}^{2}-3\left(u+v\right){}^{2}\hfill \\ \multicolumn{0}{c}{}& ={w}^{2}-2\mathrm{uw}-4v\left(u+v\right)={w}^{2}-2\mathrm{uw}-2\mathrm{vw}\hfill \\ \multicolumn{0}{c}{}& ={w}^{2}-2\left(u+v\right)w=0 .\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 $\frakC$ be the circumcircle of $\Delta \mathrm{PQR}$. If $T$ lies strictly inside $\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 $\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 $\frakC$, whence $\angle \mathrm{QPR}=\angle \mathrm{QTR}={60}^{ˆ}$.
Solution 12. [C. Lau] By the Sine Law,

$\frac{\mathrm{sin}\angle \mathrm{TQP}}{‖\mathrm{TP}‖}=\frac{\mathrm{sin}{120}^{ˆ}}{‖\mathrm{PQ}‖}=\frac{\mathrm{sin}{60}^{ˆ}}{‖\mathrm{PR}‖}=\frac{\mathrm{sin}\angle \mathrm{TRP}}{‖\mathrm{TP}‖} ,$

whence $\mathrm{sin}\angle \mathrm{TQP}=\mathrm{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} \mathrm{right} \mathrm{bisects} \mathrm{EF}$

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

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

Let the side length of the square be 1 and the length of $\mathrm{DE}$ be $a$. Then $‖\mathrm{AB}‖=1$. Since $\Delta \mathrm{ADE}~\Delta \mathrm{FBC}$, $\mathrm{AD}:\mathrm{DE}=\mathrm{BF}:\mathrm{BC}$, so that $‖\mathrm{BF}‖=1/a$ and $‖\mathrm{FC}‖=\sqrt{1+{a}^{2}}/a$. Since $\Delta \mathrm{ADE}~\Delta \mathrm{CQE}$, $\mathrm{CQ}:\mathrm{EC}=\mathrm{AD}:\mathrm{EA}$, so that $‖\mathrm{CQ}‖=\left(1-a\right)/\sqrt{1+{a}^{2}}$. Hence

$\frac{‖\mathrm{FQ}‖}{‖\mathrm{CQ}‖}=1+\frac{‖\mathrm{FC}‖}{‖\mathrm{CQ}‖}=1+\frac{1+{a}^{2}}{a\left(1-a\right)}=\frac{1+a}{a\left(1-a\right)} .$

Since $\Delta \mathrm{ECP}$ is right isosceles, $‖\mathrm{CP}‖=\left(1-a\right)/\sqrt{2}$ and $‖\mathrm{PA}‖=\sqrt{2}-‖\mathrm{CP}‖=\left(1+a\right)/\sqrt{2}$. Hence $‖\mathrm{CP}‖/‖\mathrm{PA}‖=\left(1-a\right)/\left(1+a\right)$. 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~\left(0,1\right)$, $B~\left(0,0\right)$, $C~\left(1,0\right)$, $D~\left(1,1\right)$ and $E~\left(1,t\right)$ for some $t$ with $0\le t\le 1$. It is straightforward to verify that $P~\left(1-\frac{t}{2},\frac{t}{2}\right)$.
Since the slope of $\mathrm{AE}$ is $t-1$, the slope of $\mathrm{AQ}$ should be $\left(1-t\right){}^{-1}$. Since the coordinates of $Q$ have the form $\left(1+s,s\left(1-t\right){}^{-1}\right)$ for some $s$, it is straightforward to verify that

$Q~\left(\frac{2-t}{1+\left(1-t\right){}^{2}},\frac{t}{1+\left(1-t\right){}^{2}\right)}\right) .$

It can now be checked that the slope of each of $\mathrm{BQ}$ and $\mathrm{BP}$ is $t\left(2-t\right){}^{-1}$, which yields the result.
(b) The result fails if $A~\left(0,2\right)$, $B~\left(0,0\right)$, $C~\left(1,0\right)$, $D~\left(1,2\right)$. If $E~\left(1,1\right)$, then $P~\left(\frac{3}{5},\frac{4}{5}\right)$ and $Q~\left(\frac{3}{2},\frac{1}{2}\right)$.