Solutions for June, 2002 problems

151.

Prove that, for any natural number
$n$, the
equation
$x(x+1)(x+2)\dots (x+2n1)+(x+2n+1)(x+2n+2)\dots (x+4n)=0$
does not have real solutions.
Solution 1. With
$y=x+2n$, the given equation can
be rewritten as
$(y1)(y2)\dots (y2n)+(y+1)(y+2)\dots (y+2n)=0\hspace{1em}.$
When the left side is expanded, the coefficients of the odd
powers of
$y$ cancel out, and we get a sum involving only
even powers of
$y$ with positive coefficients. Hence the
left side must be positive for all real values of
$y$, and
so there is not real solution for the equation (and for the
given equation in
$x$).
Solution 2. [Y. Yang] Let
$A=x(x+1)\dots (x+2n1)$
and
$B=(x+2n+1)(x+2n+2)\dots (x+4n)$. It is clear that
none of the numbers
$0,1,\dots ,2n1,2n+1,\dots ,4n$
is a solution. Since
$A$ and
$B$ cannot simultaneously vanish
for any value of
$x$,
$A+B=0$ can occur only if one is
positive and the other negative.
Suppose that
$A<0$. Then there must be an odd number of
negative factors in
$A$, so that
$2k1<x<2k$ for some
integer
$k\in [0,n1]$. In this situation, the factors
$x$,
$x+1$,
$\dots $,
$x+2k$ are negative and all the other
factors involved in
$A$ and those in
$B$ are positive, so that
$B>0$. We show that the absolute
value of
$A$ must be less than the absolute value of
$B$
by comparing pairs of factors.
For the positive factors of
$A$, we have
$x+2k+1<x+2n+1$,
$x+2k+2<x+2n+2$,
$\dots $,
$x+2n1=x+2k+(2n2k1)<x+4n2k1=x+2n+(2n2k1)$. For the negative factors A, we have that
$\Vert x\Vert <2k+1=4k2k+1\le 4n42k+1<4n(2k+1)<4n+x=x+4n$
$\Vert x+1\Vert <2k<4n1+x=x+4n1$
$\dots \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\Vert x+2k1\Vert <x+4n2k\hspace{1em}.$
(Draw a diagram of the real line.) Multiplying all the inequalities
yields that
$\Vert A\Vert <\Vert B\Vert =B$, so that
$A+B$ cannot vanish.
Suppose that
$B<0$. Then there are an odd number of negative
factors in
$B$, so that, for some positive
$k$ not
exceeding
$n$,
$2n2k<x<2n2k+1$. Since
$A$ has all negative factors, we have that
$A>0$.
As in the earlier case, it can be proved that
$\Vert A\Vert >\Vert B\Vert $, so that
$A+B$ cannot vanish. The desired result
follows.

152.

Andrew and Brenda are playing the following game.
Taking turns, they write in a sequence, from left to right,
the numbers 0 or 1 until each of them has written 2002 numbers
(to produce a 4004digit number). Brenda is the winner if the
sequence of zeros and ones, considered as a binary number
(i.e., written to base 2), cannot be written as the sum of
two integer squares. Otherwise, the winner is Andrew. Prove that
the second player, Brenda, can always win the game, and explain her
winning strategy (i.e., how she must play to ensure winning
every game).
Solution. First it will be established that
if the binary representation of a number
$n$ has two
consecutive ones
and an even number of zeros in its rightmost positions, the number
cannot be written as the sum of two perfect squares. For, all
such numbers
$n$ must have the form
${4}^{k}(4s+3)$. Suppose, if
possible, that such a number can be written as the sum of two
squares:
$n={x}^{2}+{y}^{2}$. Using the fact that squares, modulo 4,
are congruent to 0 or 1, we see that when
$n$ is odd the representation
is impossible, while if
$n$ is even, both
$x$ and
$y$ must be even
as well and
$(n/4)=(x/2){}^{2}+(y/2){}^{2}$. We can apply the same
argument to
$(n/4)$ and continue dividing by 4 until we get a
representation of
$4s+3$. But this yields a contradiction.
We show that the second player, Brenda, has a winning strategy:
she should always play so that the resulting 4004 digit number has
the form described in the foregoing paragraph.
Case 1: Suppose the first player, Andrew, writes only 0.
Then Brenda writes 1 on the first three turns and then keeps
writing 0. This will result in the base 2 number
$010101000\dots 000=21\xb7{4}^{1999}$, which by the argument
above cannot be written as the sum of two squares.
Case 2: Suppose on the other hand, at some point, Andrew inserts
a 1. Brenda then writes 1 on her next term, and copies what Andrew
writes thereafter. The result number will have the form of
$n$ in
the first paragraph and so cannot be written as the sum of two squares.
Brenda triumphs again.
Comment. As you will have noticed, the problem solved here
differs from the one originally posed which said that Brenda was
the winner if the final number could be written as the sum of
two integer squares. This was our mistake, and, when discovered, was
too late to correct. This changed the original problem to a much
more difficult one. Nevertheless, some comments on the new problem
will be provided as a good example of how advantage can be taken
even from mistakes.
There is a simple and clear condition that some numbers cannot be
written as a sum of two squares: it is enough to show that they
are congruent to 3, modulo 4. The difficulty of the problem arises
from the fact that if the number is not congruent to 3, it does
not necessarily mean that it can be written as the sum of two squares.
A theorem in number theory states that a positive integer can
be written as the sum of two squares if and only if no prime congruent
to 3, modulo 4, divides the number to an odd exponent.
For the problem solved above, it is enough to use the weaker condition
and have Brenda ignore all numbers other than those congruent to
3 modulo 4 that are winning numbers for her. To solve the problem
actually posed, it is not enough to consider only such numbers. It
becomes a problem to connect the binary representation of a number to
the number of its prime factors congruent to 3, modulo 4.
Two students, who sent their work on the problem posed, deserve
recognition for their excellent ideas and results. Andrew Critch tried
to come up with a strategy that eliminates the losing situations for
Brenda. He succeeds in eliminating
${2}^{4003}$ such situations, out of
all the
${2}^{4004}$ possible endgame scenarios. Leonid Chindelevitch
goes further in exploring the problem, using a different approach.
He realizes that the number 2002 in the problem is not sufficient for
the algorithm of the game. By experimentation, he concludes that there
is a winning strategy for Brenda in the case that every player writes
1, 2 or 4 numbers. (The first two cases simply require Brenda to
write a zero every time, while the third one is a bit more
complicated.) However, there is no such strategy for Brenda when
each player writes three numbers. On the contrary, in this case,
there is a winning strategy for Andrew. He starts with 1, and follows
with 1 on each of his other two turns if Brenda write 0 on her
first move. Otherwise, he follows with 1 on his second move if
Brenda's first move is 1, and then imitates Brenda's second move
on his third move. This yields one of the results: 101010,
101011, 101110, 101111, 111000, 111110, 111111 (in decimal:
42, 43, 46, 47, 56, 57, 62, 63), none of which is the sum of
two integer squares.
In order to investigate the problem further, Leonid has designed an
algorithm to verify the existence of a winning strategy with respect
to the number
$n$ of moves for each player. Computer simulations
reveal that, for the
$1\le n\le 15$, Brenda has a winning
strategy only for
$n=1,2,4$. Since the algorithm used is
exponential, the time becomes quite large under increase of
$n$;
for
$n=15$, more than six hours are required. Leonid also tries
to determine the probability for Brenda to lead the game for
ending at a winning number, and comes up with the conclusion that
the probability is less than
$0.31$ for large numbers such as 2002.
Accordingly, he concludes that it is not likely that there is a
winning strategy for such a game with a large number of moves.
Isn't it great!
Bonus points will be given to students with reasonable ideas on
this problem. For the others, the problem will not be taken into
account in compiling their scores.

153.

(a) Prove that, among any 39 consecutive natural
numbers, there is one the sum of whose digits (in base 10) is
divisible by 11.


(b) Present some generalizations of this problem.
Solution. (a) Consider 20 consecutive numbers such that the
smallest of them has units digit 0, and tens digit other than 9.
Then, if
$S$ equals the sum of the digits of the smallest number,
then the sums of the digitis of the 20 numbers are, in turn,
$S$,
$S+1$,
$\dots $,
$S+9$,
$S+1$,
$\dots $,
$S+10$. These
include 11 consecutive numbers, one of which must be divisible by 11.
Among any 39 consecutive integers, we can always find 20 such numbers.
All that is required is that at least 20 of the 39 numbers must have
the same hundreds digit. If all 39 have the same hundreds digit,
then this is so. Otherwise, there are two hundred digits involved,
and, by the pigeonhole principle, there must be twenty with
the same hundreds digit.
Comment. It is not easy to formulate new problems. This is
why those solving part (a) were given a full score, and bonus points
assigned to anyone providing a reasonable suggestion for (b). Here
are some generalizations:
(1) Prove that, among any
$20n+39$ consecutive natural numbers,
there is one, the sum of whose digits is divisible by
$11+n$.
[H. Li]
(2) Prove that, among any
$20k1$ consecutive natural numbers, there
is one, the sum of whose digits is divisible by
$k+9$ for
$1\le k\le 10$. (This is the same as (1) for
$n=2,3,4,5$.)
(3) Prove that, among any
$200k1$ consecutive natural numbers, there
is one the sum of whose digits is divisible by
$k+18$
(
$1\le k\le 5$).
We are open to further suggestions. Send them along to
Ms. Valeria Pandelieva, 641 Kirkwood Avenue, Ottawa, ON K1Z 5X5.

154.

(a) Give as neat a proof as you can that, for any
natural number
$n$, the sum of the squares of the numbers
$1,2,\dots ,n$ is equal to
$n(n+1)(2n+1)/6$.


(b) Find the least natural number
$n$ exceeding 1 for which
$({1}^{2}+{2}^{2}+\dots +{n}^{2})/n$ is the square of a natural number.
(a)
Solution. There are many ways of proving the formula.
Two standard ways are to use induction and to make use of the
identity
$(j+1){}^{3}={j}^{3}+3{j}^{2}+3j+1$ summed for
$1\le j\le n$. Y.Yang gives a geometric argument. Place
unit cubical blocks in a pyramidic array with
${n}^{2}$ blocks at
the bottom level,
$(n1){}^{2}$ blocks at the next level, and so
on, until there is a single block at the top. Inscribe this
in a squarebased right pyramid, whose slant edges pass through
the upper outer corner of each level of cubes. This pyramid
has a base with side length
$n+1$ and a height
$n+1$.
The sum of the first
$n$ squares
is equal to the volume of the cubes, which in turn is equal to
the volume of the circumscribed pyramid less the volume of the
space within the pyramid not occupied by the cubes.
The volume of the circumscribing pyramid is
$\frac{1}{3}(n+1){}^{2}(n+1)=\frac{1}{3}(n+1){}^{3}$. Now look at the leftover part.
It consists of a small pyramid at the top, and at each level,
4 square corner pyramids and 4 triangular prisms. Calling the
top level the zeroth, we find that at the
$k$th level down,
the volume of the leftover part is equal to
$4\xb7\frac{1}{3}\xb7(1/2){}^{2}+4\xb7\frac{1}{2}(1/2)k=(1/3)+k$. Summing this for
$0\le k\le n$ yields
$(1/3)(n+1)+(1/2)n(n+1)$, so that the total volume of
all the cubes is
$\frac{1}{3}(n+1){}^{3}\frac{1}{3}(n+1)\frac{1}{2}n(n+1)=\frac{1}{6}(n+1)[2(n+1){}^{2}23n]=\frac{1}{6}(n+1)(2{n}^{2}+n)=\frac{1}{6}n(n+1)(2n+1)\hspace{1em}.$
(b) Solution 1. The condition to be satisfied is
$(n+1)(2n+1)=6{m}^{2}$ for some integer
$m$. Since the right side
is even,
$n$ be an odd number, say,
$2k1$. The equation reduces
to
$k(4k1)=3{m}^{2}$. Suppose, to begin with,
$k$ is a multiple
of 3:
$k=3s$. Then
$s(12s1)={m}^{2}$. Since
$s$ and
$12s1$
are coprime, both must be squares, i.e.,
$s={p}^{2}$ and
$12s1={q}^{2}$ for some natural numbers
$p$ and
$q$. But
$12s1\equiv 3$ (mod 4) cannot be the square of a natural
number. Thus, there is no solution in this case.
The other possibility is that
$4k1$ is a multiple of 3;
equivalently,
$k1$ is a multiple of 3 (why?), so that
$k=3s+1$. Thus,
$(3s+1)(4s+1)={m}^{2}$. Since
$3s+1$ and
$4s+1$ are coprime (why?),
$3s+1={p}^{2}$ and
$4s+1={q}^{2}$ for some natural numbers
$p$ and
$q$.
We now check in turn all the odd squares of the form
$4s+1$
until we come to one for which
$3s+1$ is square. This leads us
to
$4s+1={15}^{2}$ and
$3s+1={13}^{2}$, so that
$s=56$,
$k=169$,
$n=337$.
Solution 2. It is required to find the smallest natural
number
$n$ for which
$(n+1)(2n+1)=6{m}^{2}$, for some positive
integer
$m$. We manipulate the equation to make use of the
technique of completion of the square. The equation is equivalent to
$16{n}^{2}+24n+8=48{m}^{2}$ or
$(4n+3){}^{2}1=3(4m){}^{2}$. Setting
$x=4n+3$ and
$y=4m$, we see that we need to find solutions
of the equation
${x}^{2}3{y}^{2}=1$ where
$x\equiv 3$ and
$y\equiv 0$
(modulo 4).
Noting that
${x}^{2}3{y}^{2}=(x+\sqrt{3})(x\sqrt{3})$, and that
${2}^{2}3\xb7{1}^{2}=1$, we can deduce that the equation
${x}^{2}3{y}^{2}=1$ is satisfied by
$(x,y)=({x}_{n},{y}_{n})$ where
${x}_{n}+\sqrt{3}{y}_{n}=(2+\sqrt{3}){}^{n}$ for each nonnegative integer
$n$. These solutions can be given through the recursion
${x}_{1}=2\hspace{1em},\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{y}_{1}=1$
${x}_{n+1}=2{x}_{n}+3{y}_{n}\hspace{1em},\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{y}_{n+1}={x}_{n}+2{y}_{n}\hspace{1em}.$
The smallest solutions of this equation are
$(x,y)=(1,0),(2,1),(7,4),(26,15),(97,56),(362,209),(1351,780)$. Of these, only
$(7,4)$ and
$(1351,780)$ have
the desired properties, and these correspond to
$(n,m)=(1,1)$ and
$(337,195)$. The first gives the trivial case,
and the second gives the minimum value
$337$ of
$n$.

155.

Find all real numbers
$x$ that satisfy the equation
${3}^{[(1/2)+\mathrm{log}{}_{3}(\mathrm{cos}x+\mathrm{sin}x)]}{2}^{\mathrm{log}{}_{2}(\mathrm{cos}x\mathrm{sin}x)}=\sqrt{2}\hspace{1em}.$
[The logarithms are taken to bases 3 and 2 respectively.]
Solution. By the definition and properties of the logarithmic
function, it follows that (1) the domain of the equation is the set of
all
$x$ for which
$\mathrm{cos}x+\mathrm{sin}x>0$ and
$\mathrm{cos}x\mathrm{sin}x>0$,
and that (2)
${3}^{\mathrm{log}{}_{3}M}=M$ when
$M>0$.
The given equation is equivalent to
$\sqrt{3}(\mathrm{cos}x+\mathrm{sin}x)(\mathrm{cos}x\mathrm{sin}x)=\sqrt{2}$
$\&lrArr;(\sqrt{3}1)\mathrm{cos}x+(\sqrt{3}+1)\mathrm{sin}x=\sqrt{2}$
$\&lrArr;\frac{\sqrt{6}\sqrt{2}}{4}\mathrm{cos}x+\frac{\sqrt{6}+\sqrt{2}}{4}\mathrm{sin}x=\frac{1}{2}\hspace{1em}.$
Noting that
$(\sqrt{6}\sqrt{2})/4=\mathrm{sin}{15}^{\u02c6}$ and
$(\sqrt{6}+\sqrt{2})/4=\mathrm{cos}{15}^{\u02c6}$, we see that the
equation is equivalent to
$\mathrm{sin}(x+{15}^{\u02c6})=\frac{1}{2}$,
whose solutions are
$x={15}^{\u02c6}+k{360}^{\u02c6}$ and
$x={165}^{\u02c6}+k{360}^{\u02c6}$ for integers
$k$, The latter
family are extraneous, so only the former family constitute
the solutions to the given problem.
Comment. Most participants attempted this problem and dealt
well with the trigonometric transformations. However, it is
important to check all purported solutions against the given equation,
because the derived equation becomes equivalent to the equation solved in
the solution only in the presence of the restrictions on the domain.
Many students neglected this.

156.

In the triangle
$\mathrm{ABC}$, the point
$M$ is from the
inside of the angle
$\mathrm{BAC}$ such that
$\angle \mathrm{MAB}=\angle \mathrm{MCA}$
and
$\angle \mathrm{MAC}=\angle \mathrm{MBA}$. Similarly, the point
$N$
is from the inside of the angle
$\mathrm{ABC}$ such that
$\angle \mathrm{NBA}=\angle \mathrm{NCB}$ and
$\angle \mathrm{NBC}=\angle \mathrm{NAB}$. Also, the point
$P$ is from the inside of the angle
$\mathrm{ACB}$ such that
$\angle \mathrm{PCA}=\angle \mathrm{PBC}$ and
$\angle \mathrm{PCB}=\angle \mathrm{PAC}$.
(The points
$M$,
$N$ and
$P$ each could be inside or outside of
the triangle.) Prove that the lines
$\mathrm{AM}$,
$\mathrm{BN}$ and
$\mathrm{CP}$ are concurrent
and that their intersection point belongs to the circumcircle of the
triangle
$\mathrm{MNP}$.
Solution. First, note that the point
$M$ is inside the triangle
$\mathrm{ABC}$ when
$\angle A$ is acute and outside the triangle when
$\angle A$ is obtuse. Indeed,
$\angle A=\angle \mathrm{MAB}+\angle \mathrm{MAC}=\angle \mathrm{MCA}+\angle \mathrm{MBA}<{90}^{\u02c6}$ implies that in the
quadrilateral
$\mathrm{AMBC}$,
$\angle \mathrm{BMC}>{180}^{\u02c6}$, which means that
the point
$M$ is inside the triangle. Similarly,
$\angle A>{90}^{\u02c6}$
implies that, in the quadrilateral
$\mathrm{ABMC}$,
$\angle \mathrm{BMC}<{180}^{\u02c6}$;
thus, the point
$M$ is outside the triangle. The same reasoning can
be applied to determine whether the points
$N$ and
$P$ are inside or
outside of the triangle
$\mathrm{ABC}$. It is straightforward to verify that
when one of the angles is right, the respective point is on the side
of the triangle opposite to the right angle.
Wolog, consider
$\angle C$. Case 1:
$\angle C<{90}^{\u02c6}$.
Let
$\mathrm{CP}$ instersect the segment
$\mathrm{AB}$ at
$C\text{'}$. Since
$\mathrm{PC}\text{'}$ is the
angle bisector of
$\angle \mathrm{APB}$ (
$\angle \mathrm{APC}\text{'}=\angle \mathrm{BPC}\text{'}=\angle \mathrm{ACB}$), it follows that
$\mathrm{AC}\text{'}:C\text{'}B=\mathrm{AP}:\mathrm{BP}$. The triangles
$\mathrm{APC}$ and
$\mathrm{BPC}$ are similar, so that
$\mathrm{AP}:\mathrm{CP}=\mathrm{AC}:\mathrm{BC}$ and
$\mathrm{BP}:\mathrm{CP}=\mathrm{BC}:\mathrm{AC}\Rightarrow \mathrm{AP}:\mathrm{BP}={\mathrm{AC}}^{2}:{\mathrm{CB}}^{2}\Rightarrow \mathrm{AC}\text{'}:C\text{'}B={\mathrm{AC}}^{2}:{\mathrm{CB}}^{2}$. Similarly, if
$\mathrm{AM}$ intersects
$\mathrm{BC}$ at
$M\text{'}$ and
$\mathrm{BN}$ instersects
$\mathrm{AC}$ at
$N"$, then
$\mathrm{BA}\text{'}:A\text{'}C={\mathrm{BA}}^{2}:{\mathrm{AC}}^{2}$
and
$\mathrm{CB}\text{'}:B\text{'}A={\mathrm{CB}}^{2}:{\mathrm{BA}}^{2}$. Apply Ceva's
Theorem to the lines
$\mathrm{AM}$,
$\mathrm{BN}$,
$\mathrm{CP}$ to deduce from
$\frac{\mathrm{AC}\text{'}}{C\text{'}B}\xb7\frac{\mathrm{BA}\text{'}}{A\text{'}C}\xb7\frac{\mathrm{CB}\text{'}}{B\text{'}A}=\frac{{\mathrm{AC}}^{2}}{{\mathrm{CB}}^{2}}\xb7\frac{{\mathrm{BA}}^{2}}{{\mathrm{AC}}^{2}}\xb7\frac{{\mathrm{CB}}^{2}}{{\mathrm{BA}}^{2}}=1$
that the lines
$\mathrm{AM}$,
$\mathrm{BN}$ and
$\mathrm{CP}$ are concurrent. Denote by
$K$
the intersection point of these lines and by
$O$ the circumcentre of
the triangle
$\mathrm{ABC}$.
Since
$\angle \mathrm{APB}=2\angle C=\angle \mathrm{AOB}$, the quadrilateral
$\mathrm{APOB}$ is concyclic. Also, if the line
$\mathrm{PC}\text{'}$ intersects the circumcircle
of
$\mathrm{APOB}$ at the point
$C"$, then this point
$C"$ is the midpoint of
that arc
$\mathrm{AB}$ not containing
$O$ (as
$\mathrm{PC}\text{'}$ is the angle bisector
of
$\angle \mathrm{APB}$), and
$O$ is the midpoint of the other arc
$\mathrm{AB}$.
Thus,
$\mathrm{OC}"$ is the diameter of this circle and
$\angle \mathrm{OPC}"=\angle \mathrm{OPC}={90}^{\u02c6}$. Since the point
$K$ is on the line
$\mathrm{PC}$,
$\angle \mathrm{OPK}={90}^{\u02c6}$, too; thus
$P$ is a point on the
circle whose diamter is
$\mathrm{OK}$. Similarly, the points
$M$ and
$N$
are on the same circle. This circle contains all the points
$M$,
$N$,
$P$,
$K$,
$O$, so that the intersection point of
$\mathrm{AM}$,
$\mathrm{BN}$ and
$\mathrm{CP}$ is on the circumcircle of
$\mathrm{MNP}$.
Case 2:
$\angle C={90}^{\u02c6}$. In this case, the point
$P$ is on the hypotenuse
$\mathrm{AB}$ (thus, it coincides with the point
$C\text{'}$ of Case 1), and is also the point where the altitude from
$C$ to
$\mathrm{AB}$ intersects
$\mathrm{AB}$. By the similarity of the triangles
$\mathrm{ABC}$ and
$\mathrm{APC}$,
$\mathrm{AP}:\mathrm{AC}=\mathrm{AC}:\mathrm{AB}$, while, by the similarity of the
triangles,
$\mathrm{BPC}$ and
$\mathrm{ABC}$, it follows that
$\mathrm{PC}:\mathrm{BC}=\mathrm{BC}:\mathrm{AB}$. Then
$\mathrm{AP}:\mathrm{PC}={\mathrm{AC}}^{2}:{\mathrm{BC}}^{2}$, which replaces the equation
$\mathrm{AC}\text{'}:C\text{'}B={\mathrm{AC}}^{2}:{\mathrm{BA}}^{2}$ of Case 1.The other two angles are acute, so that the
remaining parts of the solution can be pursued as in Case 1.
Case 3:
$\angle C>{90}^{\u02c6}$ Now the point
$C$ is outside of
the triangle
$\mathrm{ABC}$, as well as the circumcentre
$O$. The proof is
similar to that of Case 1, and follows the same steps.
Sources: Problem 151 is from the Bulgarian magazine
Matematika Plus, 2001. Problems 152, 154, 155, 156 are from the
contest papers of the 2001 Winter and Spring National Mathematics
Contests for High School students in Bulgaria.