Solutions and Comments

Write your solutions to be read. You may have to rework and re-edit your solution to make the argument clear, close gaps in the reasoning, define symbols used and present ideas in logical order. Always check your work. It is too easy to miscopy or misrepresent a symbol and to make a computational mistake. In a competition, your goal is to maximize the number of points you receive. In the following solutions, $[A\dots Z]$ represents the area of the figure $A\dots Z$, dist $(A,\mathrm{BC})$ is the perpendicular distance from point $A$ to line $\mathrm{BC}$, and dist $(a,b)$ is the perpendicular distance between parallel lines $a$ and $b$.

---

13.

Suppose that $x_1,x_2,\dots ,x_n$ are nonnegative real numbers for which $x_1+x_2+\dots +x_n<\frac{1}{2}$. Prove that

Comments. Some of you tried a ``moving variables'' argument, or an ``extreme case'' argument, i.e., if we make $x_i$ as large as possible, we reduce the product, so that if it works for $(x_1,x_2,\dots ,x_n)=(\frac{1}{2},0,0,\dots ,0)$, then we are in business. Some felt that if it works for the extreme case with each $x_i=1/2n$, then we are ok. Unless you back this up with solid argument and detailed analysis that relates the general case to the extreme case, then it is worthless. ``Moving variable'' arguments are always risky and best avoided. Both approaches often muddy the situation rather than clarify it.

Solution 1. If $0<u,v<1$, then

$(1-u)(1-v)=1-(u+v)+\mathrm{uv}>1-(u+v)\hspace{1em}.$
It can be shown by induction that

$(1-x_1)(1-x_2)\dots (1-x_k)>1-(x_1+x_2+\dots +x_k)$
for $2\le k\le n$, whence

$(1-x_1)\dots (1-x_n)>1-(x_1+\dots +x_n)>\frac{1}{2}\hspace{1em}.$

Comments. You should carry out the necessary induction argument. Note that the problem asks for $>$ rather than $\ge$.

Solution 2. [R. Barrington Leigh] Let

$t_k=\sum \{x_{i_1}{x}_{1_2}\dots x_{i_k}:1\le i_1<i_2<\dots <i_k\le n\}$
for $1\le k\le n$. Then

$(1-x_1)(1-x_2)\dots (1-x_n)=1-t_1+t_2-t_3+t_4-\dots +(-1){}^n{t}_n\hspace{1em}.$
For $1\le k\le n-1$, we have that

$\begin{array}{cc}{t}_k\hfill & =\sum \{x_{i_1}{x}_{i_2}\dots x_{i_k}:1\le i_1<i_2<\dots <i_k\le n\}\hfill \\ \multicolumn{0}{c}{}& >\sum \{x_{i_1}{x}_{i_2}\dots x_{i_k}(x_{i_k+1}+x_{i_k+2}+\dots +x_n):1\le i_1<i_2<\dots <i_k\le n\}=t_{k+1}\hfill \end{array}$
so that

$(1-x_1)(1-x_2)\dots (1-x_n)=(1-t_1)+(t_2-t_3)+\dots >(1-t_1)=1-(x_1+\dots +x_n)>\frac{1}{2}\hspace{1em}.$

---

14.

Given a convex quadrilateral, is it always possible to determine a point in its interior such that the four line segments joining the point to the midpoints of the sides divide the quadrilateral into four regions of equal area? If such a point exists, is it unique?

Note. Let $\mathrm{ABCD}$ be the quadrilateral and let $P,Q,R,S$ be the respective midpoints of $\mathrm{AB}$, $\mathrm{BC}$, $\mathrm{CD}$, $\mathrm{DA}$. Recall that $\mathrm{PS}\mathrm{QR}$ and $\mathrm{PQ}\mathrm{SR}$ (prove it!).

Solution 1. Observe that $[\mathrm{APS}]=\frac{1}{4}[\mathrm{ABD}]$ and $[\mathrm{CRQ}]=\frac{1}{4}[\mathrm{CDB}]$, so that $[\mathrm{APS}]+[\mathrm{CRQ}]=\frac{1}{4}[\mathrm{ABCD}]$ (why?). Since

$[\mathrm{ABCD}]=\frac{1}{2}\mathrm{BD}·(\mathrm{dist}\hspace{1em}(A,\mathrm{BD})+\mathrm{dist}\hspace{1em}(C,\mathrm{BD}))$

$[\mathrm{APS}]=\frac{1}{4}\mathrm{BD}·\mathrm{dist}\hspace{1em}(A,\mathrm{PS})$

$[\mathrm{CRQ}]=\frac{1}{4}\mathrm{BD}·\mathrm{dist}\hspace{1em}(C,\mathrm{QR})$
we have that

$\begin{array}{cc}\mathrm{dist}\hspace{1em}(A,\mathrm{PS})\hfill & +\mathrm{dist}\hspace{1em}(C,\mathrm{QR})=\frac{1}{2}[\hspace{1em}\mathrm{dist}\hspace{1em}(A,\mathrm{BD})+\hspace{1em}\mathrm{dist}\hspace{1em}(C,\mathrm{BD})\hfill \\ \multicolumn{0}{c}{}& =\mathrm{dist}(\mathrm{PS},\mathrm{QR})\hspace{1em}.\hfill \end{array}$
Hence it is possible to draw a line $m$ parallel to and between $\mathrm{PS}$ and $\mathrm{QR}$ for which dist $(m,\mathrm{QR})$ = dist $(A,\mathrm{PS})$ and dist $(m,\mathrm{PS})$ = dist $(C,\mathrm{QR})$. For any point $M$ on $m$, we have that $[\mathrm{MQR}]=[\mathrm{APS}]$ and $[\mathrm{MSP}]=[\mathrm{CRQ}]$, so that $[\mathrm{MQCR}]=[\mathrm{APMS}]=\frac{1}{4}[\mathrm{ABCD}]$.

In a similar way, we can draw a line $n$ parallel to and between $\mathrm{PQ}$ and $\mathrm{SR}$ for which dist $(n,\mathrm{PQ})$ = dist $(D,\mathrm{SR})$ and dist $(n,\mathrm{SR})$ = dist $(B,\mathrm{PQ})$, so that, for any point $N$ on $n$, $[\mathrm{NPQ}]=[\mathrm{DSR}]$, $[\mathrm{NRS}]=[\mathrm{BRP}]$ and $[\mathrm{NPBQ}]=[\mathrm{DSNR}]=\frac{1}{4}[\mathrm{ABCD}]$.

The lines $m$ and $n$ are not parallel, and, so, intersect in a unique point $O$ for which

$[\mathrm{OQCR}]=[\mathrm{APOS}]=[\mathrm{OPBQ}]=[\mathrm{DSOR}]=\frac{1}{4}[\mathrm{ABCD}]\hspace{1em}.$
Note that $m$ and $n$ intersect inside $\mathrm{PQRS}$ and so inside $\mathrm{ABCD}$.

We show that $O$ is the only point with this property. Let $L$ be another point inside $\mathrm{ABCD}$. Then $L$ lies in one of the four partitioning quadrilaterals, say $[\mathrm{OQCR}]$, so that $[\mathrm{LQCR}]<[\mathrm{OQCR}]=\frac{1}{4}[\mathrm{ABCD}]$. Hence, $L$ will satisfy the conditions of the problem.

Comments. A careful solution will contain the observation that $m$ and $n$ are not parallel, and will intersect within the quadrilateral. The fact that $m$ and $n$ have a unique point of intersection does not, in and of itself, establish that the requisite point cannot be found in some other way. Therefore, uniqueness needs to be explicitly handled, either by showing that the required point must lie on $m$ and $n$ or by some other argument.

Solution 2. Analysis. Suppose such a point $O$ exists. Then $[\mathrm{OPBQ}]=[\mathrm{OCQR}]=\frac{1}{4}[\mathrm{ABCD}]$, so that

$[\mathrm{AOB}]=2[\mathrm{POB}]=2([\mathrm{OPBQ}]-[\mathrm{OBQ}])=2([\mathrm{OQCR}]-[\mathrm{OQC}])=2[\mathrm{ROC}]=[\mathrm{DOC}]\hspace{1em}.$
Since $[\mathrm{AOB}]=\frac{1}{2}\mathrm{AB}·\mathrm{dist}\hspace{1em}(O,\mathrm{AB})$ and $[\mathrm{DOC}]=\frac{1}{2}\mathrm{CD}·\mathrm{dist}\hspace{1em}(O,\mathrm{CD})$, we must have that

$\frac{\mathrm{dist}\hspace{1em}(O,\mathrm{AB})}{\mathrm{dist}\hspace{1em}(O,\mathrm{CD})}=\frac{\mathrm{CD}}{\mathrm{AB}}\hspace{1em}.$
The locus of points $O$ with this property is a line $h$ through the intersection of $\mathrm{AB}$ and $\mathrm{CD}$ (or parallel to them if they do not intersect) which lies between them (prove this!). Similarly, $O$ must lie on a line $k$ defined by

$\frac{\mathrm{dist}\hspace{1em}(O,\mathrm{BC})}{\mathrm{dist}\hspace{1em}(O,\mathrm{AD})}=\frac{\mathrm{AD}}{\mathrm{BC}}$
through the intersection of $\mathrm{BC}$ and $\mathrm{AD}$ (if they intersect) that lies between them. These lines are not parallel and intersect within $\mathrm{ABCD}$ (why?). If $O$ exists, it must lie on the intersection of $h$ and $k$.

Synthesis. Construct lines $h$ and $k$ to satisfy the foregoing conditions. They must intersect in a unique point $O$ within $\mathrm{ABCD}$. Now

$[\mathrm{AOB}]=\frac{1}{2}\mathrm{AB}·\mathrm{dist}\hspace{1em}(O,\mathrm{AB})=\frac{1}{2}\mathrm{CD}·\mathrm{dist}\hspace{1em}(O,\mathrm{CD})=[\mathrm{DOC}]\hspace{1em}.$
Hence $[\mathrm{AOP}]=[\mathrm{POB}]=[\mathrm{COR}]=[\mathrm{DOR}]$. Let $\alpha$ be the common value. Similarly, $[\mathrm{BOQ}]=[\mathrm{COQ}]=[\mathrm{AOS}]=[\mathrm{DOS}]=\beta$, say. Then each of $[\mathrm{APOS}]$, $[\mathrm{BQOP}]$, $[\mathrm{CROQ}]$ and $[\mathrm{DSOR}]$ has the value $\alpha +\beta$ and $O$ is the desired point.

---

15.

Determine all triples $(x,y,z)$ of real numbers for which

Comments. In solving a system of equations, one begins by assuming a solution and determining what properties it must have. Since this may involve one-way reasoning, such properties may not necessarily yield a solution and extraneous solutions may arise. Thus, when you have solved the equations, for a complete solution, you should check that the solution is valid.

If, in your manipulations, you divide by a certain quantity or find a quantity in the denominator of a fraction, you should explore the possibility that the quantity could vanish, Remember that you cannot divide by zero. When you write up your final solution, it is often a good idea to deal with this possibility ahead of time and get it out of the way.

Solution 1. Suppose one of the variable, say $x$, is 0. Then $z(x+1)=0$, so $z=0$, and $y(z+1)=0$ so $y=0$. Suppose one of the variables, say $x$ is $-1$. The $x(y+1)=0$, so $y=-1$ and $y(z+1)=0$, so $z=-1$. Hence, if any variable assumes either of the values $-1$ and $0$, then all are equal. Henceforth, we assume that none of them have either value.

>From the equations, we find that

$\frac{y(z+1)}{y+1}=x=\frac{\mathrm{yz}+y-z}{z}$
whence

$\mathrm{yz}(z+1)=(y+1)\mathrm{yz}+(y+1)(y-z)$
or

$\mathrm{yz}(z-y)=(y+1)(y-z)\hspace{1em}.$
Hence, either $y=z$ or $\mathrm{yz}+y+1=0$.

If $y=z$, then $z+1=x+1$. so that $z=x$ and $x=y=z$. Conversely, the system is satisfied when $x=y=z$.

Suppose that $\mathrm{yz}+y+1=0$. Then $x(y+1)=z(x+1)=y(z+1)=-1$, and so $\mathrm{xy}+x+1=\mathrm{xz}+z+1=0$. Suppose $z=t$, Then $x=-(t+1)/t$ and $y=-1/(t+1)$. Conversely, it is straightforward to check that the system is satisfied by

$(x,y,z)=(-\frac{t+1}{t},-\frac{1}{1+t},t)$
where $t\ne 0,-1$. Thus, we have obtained exactly the complete set of solutions.

Comment. The solution with $x,y,z$ unequal may look non-symmetrical. Verify that, if $x=s=-(t+1)/t$, then $y=-1/(1+t)=-(s+1)/s$ and $z=t=-1/(1+s)$. Check that $x$ and $z$ can similarly be expressed in terms of $y=r$.

Solution 2. From the equations, we find that

$x(y-z)=z-x\hspace{1em},\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}y(z-x)=x-y\hspace{1em},\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{and}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}z(x-y)=y-z\hspace{1em}.$
Multiplying these equations yields

$\mathrm{xyz}(y-z)(z-x)(x-y)=(z-x)(x-y)(y-z)\hspace{1em}.$
Hence, either two variables (and so all) are equal or $\mathrm{xyz}=1$. The system is satisfied when all variables are equal.

Suppose that $\mathrm{xyz}=1$. Then

$\mathrm{xy}+x+1=\mathrm{xy}+x+\mathrm{xyz}=x(\mathrm{yz}+y+1)$
and

$\mathrm{yz}+y+1=\mathrm{yz}+y+\mathrm{xyz}=y(\mathrm{zx}+z+1)\hspace{1em}.$
Since $\mathrm{xy}+x=\mathrm{yz}+y=\mathrm{zx}+z$, either $x=y=z=1$ or $\mathrm{xy}+x+1=\mathrm{yz}+y+1=\mathrm{zx}+z+1=0$. We need to check that there are solutions of this type. Select arbitrary $x\ne 0,-1$, then $y$ to satisfy $\mathrm{xy}+x+1=0$ and $z$ to satisfy $\mathrm{xyz}=1$. Then

$\mathrm{zx}+z+1=\mathrm{zx}+z+\mathrm{xyz}=z(\mathrm{xy}+x+1)=0$
and

$\mathrm{yz}+y+1=\mathrm{yz}+y+\mathrm{xyz}=y(\mathrm{zx}+z+1)=0$
so that $x(y+1)=y(x+1)=z(x+1)=-1$ as desired.

Solution 3. As before, we can check that $(x,y,z)=(0,0,0)$ is the only solution in which any variable vanishes. Henceforth, suppose that $\mathrm{xyz}\ne 0$. Let $z=\mathrm{vx}$. Then $y+1=v(x+1)$, whence $y=\mathrm{vx}+v-1$. Therefore

$x(\mathrm{vx}+v)=x(y+1)=y(z+1)=(\mathrm{vx}+v-1)(\mathrm{vx}+1)$
so that

$v(v-1)x^2+v(v-1)x+(v-1)=0\hspace{1em}.$
Either $v=1$ and we are led to $x=y=z$, which works, or

${\mathrm{vx}}^2+\mathrm{vx}+1=0\hspace{1em}.$
Hence

$(x,y,z)=(\frac{-v\pm \sqrt{v^2-4v}}{2v},\frac{(v-2)\pm \sqrt{v^2-4v}}{2},\frac{-v\pm \sqrt{v^2-4v}}{2})\hspace{1em}.$
where $v<0$ or $v\ge 4$. It can be checked that these values satisfy the equations. (Exercise: Check that this colution is consistent with the other solutions.)

Solution 4. As in the foregoing solutions, we can check that $(x,y,z)=(0,0,0),(-1,-1,-1)$ are the only solutions in which any variable assumes either of the values 0 or $-1$. Henceforth, suppose $x,y,z$ all differ from 0 and $-1$.

Let $x(y+1)=y(z+1)=z(x+1)=k$. Then $z=k/(x+1)$ and $y=(k/x)-1=(k-x)/x$. Therefore,

$\begin{array}{cc}k\hfill & =y(z+1)=(\frac{k-x}{x})(\frac{k+x+1}{x+1})\hfill \\ \multicolumn{0}{c}{}& \Rightarrow k(x^2+x)=k^2-x^2+k-x=k(k+1)-(x^2+x)\hfill \\ \multicolumn{0}{c}{}& \Rightarrow (k+1)(x^2+x-k)=0\hfill \\ \multicolumn{0}{c}{}& \Rightarrow k=-1\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{or}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{x}^2+x=k\hspace{1em}.\hfill \end{array}$
Suppose that $x^2+x=k$. Then $x(x+1)=z(x+1)$. Since $x\ne -1$, $x=z$, and so $y+1=x+1$. Thus, $x=y=z$. Suppose that $k=-1$. Then $z=-1/(x+1)$ and $y=-(x+1)/x$. It can be checked that this works.

Comment. It is not hard to check independently that the only nonzero solution in which $x$, $y$, $z$ have the same sign is in fact given by $x=y=z$. For in this case, the ratio of any pair is positive, and the system can be rewritten

$\frac{1}{x}-\frac{1}{y}=1-\frac{z}{x}$

$\frac{1}{z}-\frac{1}{x}=1-\frac{y}{z}$

$\frac{1}{y}-\frac{1}{z}=1-\frac{x}{y}$
whence $3=(x/y)+(y/z)+(z/x)$. By the Arithmetic-Geometric Means Inequality (applicable since the three summands are positive), $(x/y)+(y/z)+(z/x)\ge 3$ with equality if and only if $x/y=y/z=z/x$ or $x=y=z$.

---

16.

Suppose that $\mathrm{ABCDEZ}$ is a regular octahedron whose pairs of opposite vertices are $(A,Z)$, $(B,D)$ and $(C,E)$. The points $F,G,H$ are chosen on the segments $\mathrm{AB}$, $\mathrm{AC}$, $\mathrm{AD}$ respectively such that $\mathrm{AF}=\mathrm{AG}=\mathrm{AH}$.

(a) Show that $\mathrm{EF}$ and $\mathrm{DG}$ must intersect in a point $K$, and that $\mathrm{BG}$ and $\mathrm{EH}$ must intersect in a point $L$.

(b) Let $\mathrm{EG}$ meet the plane of $\mathrm{AKL}$ in $M$. Show that $\mathrm{AKML}$ is a square.

Comment. Many students had complicated arguments involving similar triangles. You should try to envisage the situation in terms of transformations, as this gives you a better sense of what is going on. Of course, if a synthetic argument cannot be found, you always have recourse to the ``refuge of the destitute'', coordinate geometry and the hope that the computations will not be too horrendous. In this case, they are not bad at all.

Solution 1. (a) Since $\mathrm{AF}:\mathrm{AB}=\mathrm{AG}:\mathrm{GC}$, it follows that $\mathrm{FG}\mathrm{BC}\mathrm{ED}$, while $\mathrm{FG}<\mathrm{BC}=\mathrm{ED}$. Hence, $\mathrm{FGDE}$ is a coplanar isosceles trapezoid and so $\mathrm{EF}$ and $\mathrm{DG}$ must intersect in a point $K$. A ${90}^{ˆ}$ rotation about the axis $\mathrm{AZ}$ takes $B\to C$, $F\to G$, $C\to D$, $G\to H$, $D\to E$, $E\to B$. Hence $\mathrm{EF}\to \mathrm{BG}$ and $\mathrm{DG}\to \mathrm{EH}$, so that $\mathrm{BG}$ and $\mathrm{EH}$ must intersect in a point $L$, which is the image of $K$ under the rotation.

(b) $\mathrm{KE}$ and $\mathrm{AB}$ intersect in $F$, so that the two lines are coplanar. Also $\mathrm{KF}:\mathrm{KE}=\mathrm{FG}:\mathrm{ED}=\mathrm{FG}:\mathrm{BC}=\mathrm{AF}:\mathrm{FB}$ so that $\Delta \mathrm{KAF}~\Delta \mathrm{EFB}$ and $\mathrm{AK}\mathrm{EB}$. Hence $K$ lies in a plane through $A$ parallel to $\mathrm{BCDE}$. Because the ${90}^{ˆ}$ rotation about the axis $\mathrm{AZ}$ (which is perpendicular to the planes $\mathrm{BCDE}$ and $\mathrm{AKL}$ takes $K\to L$, $\mathrm{AK}=\mathrm{AL}$ and $\angle \mathrm{KAL}={90}^{ˆ}$.

Consider a dilation with centre $E$ and factor $\Vert \mathrm{AB}\Vert /\Vert \mathrm{FB}\Vert$. Let $I$ be on $\mathrm{AE}$ with $\mathrm{AI}=\mathrm{AF}$. The the dilation takes $F\to K$, $H\to L$, $I\to A$ and the plane of $\mathrm{FGHI}$ to the parallel plane $\mathrm{AKL}$. The image of $G$ under this dilation is the intersection of $\mathrm{EG}$ and the plane of $\mathrm{AKL}$, namely $M$. Thus the square $\mathrm{FGHI}$ goes to $\mathrm{KMLA}$ which must also be a square.

Solution 2. The dilation-reflection perpendicular to a plane through $\mathrm{FG}$ perpendicular to $\mathrm{BE}$ and $\mathrm{CD}$ with factor $\Vert \mathrm{AF}\Vert /\Vert \mathrm{FB}\Vert$ takes $B\to E$, $C\to D$, and fixes $F$ and $G$. The lines $\mathrm{BF}$ and $\mathrm{CG}$ with intersection $A$ gets carried to lines $\mathrm{EF}$ and $\mathrm{DG}$ which intersect in a point $K$ for which $\mathrm{AK}$ is perpendicular to the plane and so parallel to BE and CD, and the distance from $K$ to the plane is $\Vert \mathrm{AF}\Vert /\Vert \mathrm{FB}\Vert$ times the distance from $A$ to the plane.

Similarly, considering a dilation-reflection to a plane through $\mathrm{GH}$ perpendicular to $\mathrm{BC}$ and $\mathrm{DE}$ with the same factor produces the point $L$ with $\mathrm{AL}$ perpendicular to this plane and so parallel to $\mathrm{BC}$ and $\mathrm{ED}$. Thus $\angle \mathrm{KAL}={90}^{ˆ}$.

The reflection in the plane $\mathrm{AECZ}$ fixes $A,C,E,G$ and interchanges the points in each of the pairs $(B,D)$ and $(F,H)$. Hence the line pairs $(\mathrm{EF},\mathrm{DG})$ and $(\mathrm{EH},\mathrm{BG})$ are interchanged as is the pair $K$ and $L$. Thus $\mathrm{AK}=\mathrm{AL}$ and $\mathrm{KL}$ is perpendicular to $\mathrm{AECZ}$. The triangle $\mathrm{AKL}$ is in a plane through $A$ parallel to $\mathrm{BCDE}$. The proof that $\mathrm{AKML}$ is a square can be completed as in Solution 1.

Solution 3. Assign solid coordinates: $A~(0,0,1)$, $B~(0,-1,0)$, $C~(1,0,0)$, $D~(0,1,0)$, $E~(-1,0,0)$. For some $t$ with $0<t<1$, $F~(0,-(1-t),t)$, $G~(1-t,0,t)$, $H~(0,1-t,t)$. The line $\mathrm{EF}$ consists of points $(-u,-(1-u)(1-t),(1-u)t)$, with real $u$ and the line $\mathrm{DG}$ consists of points $((1-v)(1-t),v,(1-v)t)$ with real $v$. They meet in $K~((1-t)/t,(t-1)/t,1)$. Similarly, $L~((1-t)/t,(1-t)/t,1)$, so $A,K,L$ lie on the plane $z=1$. The line $\mathrm{EG}$ consists of points $(-w+(1-t)(1-w),0,t(1-w))$ with real $w$, and this intersects the plane $z=1$ in the point $(2(1-t)/t,0,1)$. The desired result can now be verified.

---

17.

Suppose that $r$ is a real number. Define the sequence $x_n$ recursively by $x_0=0$, $x_1=1$, $x_{n+2}={\mathrm{rx}}_{n+1}-x_n$ for $n\ge 0$. For which values of $r$ is it true that

Answer. The property holds for all values of $r$.

Solution 1. Define $x_{-1}=-1$; the recurrence still holds with this extension of the index. Note that, for $n\ge 0$,

$\begin{array}{cc}(x_{n+1}^2-x_n^2)\hfill & -(x_n{x}_{n+2}-x_{n-1}{x}_{n+1})=x_{n+1}(x_{n+1}+x_{n-1})-x_n(x_n+x_{n+2})\hfill \\ \multicolumn{0}{c}{}& =x_{n+1}({\mathrm{rx}}_n)-x_n({\mathrm{rx}}_{n+1})=0\hfill \end{array}$
so that $x_{n+1}^2-x_n^2=x_n{x}_{n+2}-x_{n-1}{x}_{n+1}$.

We prove by induction that for each nonnegative integer $m$,

$x_{2m}=x_m(x_{m+1}-x_{m-1})$

$x_{2m+1}=x_{m+1}^2-x_m^2=x_m{x}_{m+2}-x_{m-1}{x}_{m+1}\hspace{1em}.$
These equations check out for $m=0$. Suppose they hold for $m=k$. Then

$\begin{array}{cc}{x}_{2k+2}\hfill & ={\mathrm{rx}}_{2k+1}-x_{2k}=r(x_{k+1}^2-x_k^2)-x_k(x_{k+1}-x_{k-1})\hfill \\ \multicolumn{0}{c}{}& =x_{k+1}({\mathrm{rx}}_{k+1}-x_k)-x_k({\mathrm{rx}}_k-x_{k-1})\hfill \\ \multicolumn{0}{c}{}& =x_{k+1}{x}_{k+2}-x_k{x}_{k+1}=x_{k+1}(x_{k+2}-x_k)\hfill \end{array}$

$\begin{array}{cc}{x}_{2k+3}\hfill & ={\mathrm{rx}}_{2k+2}-x_{2k+1}=r(x_{k+1}{x}_{k+2}-x_{k+1}{x}_k)-(x_{k+1}^2-x_k^2)\hfill \\ \multicolumn{0}{c}{}& =x_{k+1}({\mathrm{rx}}_{k+2}-x_{k+1})-x_k({\mathrm{rx}}_{k+1}-x_k)\hfill \\ \multicolumn{0}{c}{}& =x_{k+1}{x}_{k+3}-x_k{x}_{k+2}=x_{k+2}^2-x_{k+1}^2\hfill \end{array}$
so the result holds for $m=k+1$.

Hence

$x_1+x_3+\dots +x_{2m-1}=(x_1^2-x_0^2)+(x_2^2-x_1^2)+\dots +(x_m^2-x_{m-1}^2)=x_m^2$
as desired.

Solution 2. [R. Mong] We prove by induction that, for $m\ge 1$,

$x_1+x_3+\dots +x_{2m-1}=x_m^2$

$x_2+x_4+\dots +x_{2m}=x_m{x}_{m+1}\hspace{1em}.$
These hold for $m=1$. Assume they hold for $1\le k\le m$. Then

$\begin{array}{cc}{x}_1+x_3\hfill & +\dots +x_{2k+1}=1+({\mathrm{rx}}_2-x_1)+({\mathrm{rx}}_4-x_3)+\dots +({\mathrm{rx}}_{2k}-x_{2k-1})\hfill \\ \multicolumn{0}{c}{}& =1+r[x_2+x_4+\dots +x_{2k}]-[1+r(x_2+x_4+\dots +x_{2k-2})-(x_1+x_3+\dots +x_{2k-3})]\hfill \\ \multicolumn{0}{c}{}& =r(x_k{x}_{k+1}-x_{k-1}{x}_k)+x_{k-1}^2={\mathrm{rx}}_k{x}_{k+1}-x_{k-1}({\mathrm{rx}}_k-x_{k-1})\hfill \\ \multicolumn{0}{c}{}& ={\mathrm{rx}}_k{x}_{k+1}-x_{k-1}{x}_{k+1}=x_{k+1}({\mathrm{rx}}_k-x_{k-1})=x_{k+1}^2\hfill \end{array}$

$\begin{array}{cc}{x}_2+x_4\hfill & +\dots +x_{2k+2}=({\mathrm{rx}}_1-x_0)+({\mathrm{rx}}_3-x_2)+\dots +({\mathrm{rx}}_{2k+1}-x_{2k})\hfill \\ \multicolumn{0}{c}{}& ={\mathrm{rx}}_{k+1}^2-x_k{x}_{k+1}=x_{k+1}({\mathrm{rx}}_{k+1}-x_k)=x_{k+1}{x}_{k+2}\hspace{1em}.\hfill \end{array}$
Hence the result holds for all $m$ and the result follows.

Solution 3. The recursion $x_{n+2}={\mathrm{rx}}_{n+1}-x_n$ has characteristic polynomial $t^2-\mathrm{rt}+1$ with discriminant $r^2-4$. Its roots are distinct as long as $r\ne \pm 2$, so we deal with $r=\pm 2$ separately.

The solution for $r=2$ is $x_n=n$ and for $r=-2$ is $x_n=(-1){}^{n-1}n$, and it is straightforward to establish the desired relation in these cases. When $r\ne \pm 2$, the characteristic polynomial has distinct roots $\sigma$ and $1/\sigma$, where $\sigma +1/\sigma =r$, i.e. ${\sigma }^2=r\sigma -1$. Note that $\sigma \ne \pm 1$ since $r\ne \pm 2$. The solution of the recursion is

$x_n=\frac{\sigma }{{\sigma }^2-1}({\sigma }^n-{\sigma }^{-n})\hspace{1em}.$
Then

$\begin{array}{cc}{x}_1+x_3\hfill & +\dots +x_{2m-1}\hfill \\ \multicolumn{0}{c}{}& =\frac{\sigma }{{\sigma }^2-1}(\sigma +{\sigma }^3+\dots +{\sigma }^{2m-1})-\frac{\sigma }{{\sigma }^2-1}({\sigma }^{-1}+{\sigma }^{-3}+\dots +{\sigma }^{-(2m-1)})\hfill \\ \multicolumn{0}{c}{}& =\frac{{\sigma }^2}{{\sigma }^2-1}[\frac{{\sigma }^{2m}-1}{{\sigma }^2-1}]-\frac{1}{{\sigma }^2-1}[\frac{{\sigma }^{-2m}-1}{{\sigma }^{-2}-1}]\hfill \\ \multicolumn{0}{c}{}& =\frac{{\sigma }^2}{({\sigma }^2-1){}^2}[{\sigma }^{2m}-1-1+{\sigma }^{-2m}]=\frac{{\sigma }^2}{({\sigma }^2-1){}^2}({\sigma }^m-{\sigma }^{-m}){}^2=x_m^2\hspace{1em}.\hfill \end{array}$

Comment. Solvers who used the approach of Solution 3 failed to consider the case in which the characteristic polynomial had a double root.

---

18.

Let $a$ and $b$ be integers. How many solutions in real pairs $(x,y)$ does the system

Comments. Several of the solvers got all mixed up with the status of the variables in the problem, and, for example, found infinitely many solutions to the equations. $a$ and $b$ are fixed in advance; they are parameters, and your final answer will be conditioned by the the characteristics of various pairs $(a,b)$. Rather than rush blindly into the problem, it is a good strategy to gain some understanding of the situation by looking at particular cases. For example, if one takes $(a,b)=(0,0)$, it is not too hard to see that $(x,y)=(0,0)$ is the only solution. Similarly, if $(a,b)=(1,1)$, one arrives at the sole solution $(x,y)=(\frac{1}{2},\frac{1}{2})$. However, if $(a,b)=(1,0)$, we find two distinct solutions, $(x,y)=(-\frac{1}{2},1),(0,\frac{1}{2})$. This not only clarifies the situation, but gives you a couple of examples against which you can check your final answer. Get in the habit of using examples to help understanding. It is an excellent exercise to plot, on the same axes, the graphs of the two equations for various values of $a$ and $b$.

Solution 1. Since $2x$ and $2y$ are the difference of two integers, $x$ and $y$ must have the form $m+\frac{u}{2}$ and $n+\frac{v}{2}$ respectively, where $m$ and $n$ are integers and $u$ and $v$ each take one of the values 0 and 1. Plugging these in yields

$m+2n+v=a$

$n+2m+u=b\hspace{1em}.$
Solving for $m$ and $n$ gives

$3m=2b-a+v-2u$

$3n=2a-b+u-2v\hspace{1em}.$
For a viable solution, $u$ and $v$ must be such that the right side of each equation is a multiple of 3 (and this is where the characteristics of the parameters $a$ and $b$ enter in). We consider three cases:

(i) Let $a+b\equiv 0$ (mod 3). Then, for a solution, we must have

$0\equiv 2b-a+v-2u=3b-(a+b)+v-2u\equiv v-2u$
and

$0\equiv 2a-b+u-2v\equiv u-2v$
modulo 3. Since $\{u,v\}\subseteq \{0,1\}$, we must have $u=v=0$, and we obtain the solution

$(x,y)=(\frac{2b-a}{3},\frac{2a-b}{3})\hspace{1em}.$
This checks out.

(ii) Let $a+b\equiv 1$ (mod 3). Then, for a solution, we must have

$0\equiv 2b-a+v-2u\equiv -1+v-2u$
and

$0\equiv 2a-b+u-2v\equiv -1+u-2v$
modulo 3. The only solutions of $u-2v\equiv v-2u\equiv 0$ (mod 3) with $u$ and $v$ equal to 0 or 1 are given by $(u,v)=(1,0),(0,1)$, so, either

$(x,y)=(m+\frac{1}{2},n)\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{with}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}3m=2b-a-2,3n=2a-b+1$
or

$(x,y)=(m,n+\frac{1}{2})\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{with}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}3m=2b-a+1,3n=2a-b-2\hspace{1em}.$
Thus, we get two solutions

$(x,y)=(\frac{4b-2a-1}{6},\frac{2a-b+1}{3}),(\frac{2b-a+1}{3},\frac{4a-2b-1}{6})\hspace{1em}.$
These check out.

(iii) Let $a+b\equiv 2$ (mod 3). Then

$0\equiv 2b-a+v-2u\equiv -2+v-2u$
and

$0\equiv 2a-b+u-2v\equiv -2+u-2v$
modulo 3. For a solution, we must have $v-2u\equiv u-2v\equiv 2$ (mod 3), so that $(u,v)=(1,1)$ and $(x,y)=(m+\frac{1}{2},n+\frac{1}{2})$ with $3m=2b-a-1$ and $3n=2a-b-1$. Hence there is a unique solution

$(x,y)=(\frac{4a-2a+1}{6},\frac{4a-2b+1}{6})\hspace{1em}.$
This checks out.

Hence, when $a+b\equiv 0$ or $a+b\equiv 2$ (mod 3), there is one solution to the system, while when $a+b\equiv 1$ (mod 3), there are two solutions.

Solution 2. Observe that $x$ and $y$ must be half integers. Since

$\lfloor x\rfloor +\lfloor y\rfloor +2x+2y=a+b$
and $x-\frac{1}{2}\le \lfloor x\rfloor \le x$, $y-\frac{1}{2}\le \lfloor y\rfloor \le y$, we must have that

$a+b\le 3(x+y)\le a+b+1\hspace{1em}.$
Hence, $x+y$, being a half integer, must have exactly one of the values

$\frac{a+b}{3},\frac{a+b+\frac{1}{2}}{3},\frac{a+b+1}{3}$
depending on the divisibility of the numerator of the fractions by 3. Consider cases:

(i) Let $a+b\equiv 0$ (mod 3). Then $x+y$ is the integer $(a+b)/3$. If $x$ and $y$ are not themselves integers, then

$\lfloor x\rfloor +\lfloor y\rfloor =(x-\frac{1}{2})+(y-\frac{1}{2})=x+y-1$
so that

$3(x+y)-1\equiv a+b\equiv 0$
modulo 3, a contradiction. Hence, $x$ and $y$ are both integers and

$(x,y)=(\frac{2b-a}{3},\frac{2a-b}{3})\hspace{1em}.$
This checks out.

(ii) Let $a+b\equiv 1$ (mod 3). Then $2(a+b)+1\equiv 0$ (mod 3), and so

$x+y=\frac{a+b+\frac{1}{2}}{3}=\frac{2(a+b)+1}{6}\hspace{1em},$
a half-integer. Hence there are integers $m$ and $n$ for which

$(x,y)=(m+\frac{1}{2},n)\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{or}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}(m+1,n-\frac{1}{2})$
where $m+n=(a+b-1)/3$. We find that

$(x,y)=(\frac{4b-2a-1}{6},\frac{2a-b+1}{3}),(\frac{2b-a+1}{3},\frac{4a-2b-1}{6})\hspace{1em}.$
These check out.

(iii) $a+b\equiv 2$ (mod 3). Then $x+y=(a+b+1)/3$, an integer. In this case, we can check that $x$ and $y$ cannot be integers, so that $x=\lfloor x\rfloor +1/2$ and $y=\lfloor y\rfloor +1/2$, and so

$(x,y)=(\frac{4a-2a+1}{6},\frac{4a-2b+1}{6})\hspace{1em}.$
This checks out.