Solutions and Comments

---

43.

Two players play a game: the first player thinks of $n$ integers $x_1$, $x_2$, $\dots$, $x_n$, each with one digit, and the second player selects some numbers $a_1$, $a_2$, $\dots$, $a_n$ and asks what is the value of the sum $a_1{x}_1+a_2{x}_2+\dots +a_n{x}_n$. What is the minimum number of questions used by the second player to find the integers $x_1$, $x_2$, $\dots$, $x_n$?

Solution. We are going to prove that the second player needs only one question to find the integers $x_1$, $x_2$, $\dots$, $x_n$. Indeed, let him choose $a_1=100$, $a_2={100}^2$, $\dots$, $a_n={100}^n$ and ask for the value of the sum

$S_n=100x_1+{100}^2{x}_2+\dots +{100}^n{x}_n\hspace{1em}\hspace{1em}.$
Note that

$\begin{array}{cc}|\hfill & \frac{100x_1+{100}^2{x}_2+\dots +{100}^{n-1}{x}_{n-1}}{{100}^n}|\hfill \\ \multicolumn{0}{c}{}& \le \frac{100\Vert x_1\Vert +{100}^2\Vert x_2\Vert +\dots +{100}^{n-1}\Vert x_{n-1}\Vert }{{100}^n}\hfill \\ \multicolumn{0}{c}{}& \le \frac{9(100+{100}^2+\dots +{100}^{n-1})}{{100}^n}\hfill \\ \multicolumn{0}{c}{}& <\frac{{10}^{2n-1}}{{10}^{2n}}=\frac{1}{10}\hspace{1em}.\hfill \end{array}$
Hence

$|\frac{S_n}{{100}^n}-x_n|=\frac{100x_1+{100}^2{x}_2+\dots +{100}^{n-1}{x}_{n-1}}{{100}^n}<\frac{1}{10}\hspace{1em},$
and $x_n$ can be obtained. Now, we can find the sum

$S_{n-1}=S_n-{100}^n{x}_n=100x_1+{100}^2{x}_2+\dots +{100}^{n-1}{x}_{n-1}$
and similarly obtain $x_{n-1}$. The procedure continues until all the numbers are found.

---

44.

Find the permutation $\{a_1,a_2,\dots ,a_n\}$ of the set $\{1,2,\dots ,n\}$ for which the sum

Solution. Let $a=(a_1,a_2,\dots ,a_n)$ be a permutation of $\{1,2,\dots ,n\}$ and define

$f(a)=\sum _{k=1}^{n-1}\Vert a_{k+1}-a_k\Vert +\Vert a_n-a_1\Vert \hspace{1em}.$
With $a_{n+1}=a_1$ and ${\epsilon }_0={\epsilon }_n$, we find that

$f(a)=\sum _{k=1}^n{\epsilon }_k(a_{k+1}-a_k)=\sum _{k=1}^n({\epsilon }_{k-1}-{\epsilon }_k)a_k$
where ${\epsilon }_1$, ${\epsilon }_2$, $\dots$, ${\epsilon }_n$ are all equal to $1$ or $-1$. Thus

$f(a)=\sum _{k=1}^n{\beta }_{k}k\hspace{1em}.$
where each ${\beta }_k$ is one of $-2$, 0, 2, and $\sum _{k=1}^n{\beta }_k=0$ (there are the same number of positive and negative numbers among the ${\beta }_k$).

Therefore

$f(a)=2(x_1+x_2+\dots +x_m)-2(y_1+y_2+\dots +y_m)$
where $x_1,\dots ,x_m,y_1,\dots ,y_m\in \{1,2,\dots ,n\}$ and are distinct from each other. Hence $f(a)$ is maximum when $\{x_1,x_2,\dots ,x_m\}=\{n,n-1,\dots ,n-m+1\}$, $\{y_1,y_2,\dots ,y_m\}=\{1,2,\dots ,m\}$ with $m=\lfloor n/2\rfloor$, i.e., $m$ is as large as possible. The maximum value is

$2\lfloor \frac{n}{2}\rfloor (n-\lfloor \frac{n}{2}\rfloor )\hspace{1em}.$
This value is attained by taking

$a=(s+1,1,s+2,2,\dots ,2s,s)\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{when}\hspace{1em}\hspace{1em}n=2s$
and

$a=(s+2,1,s+3,2,\dots ,2s+1,s,s+1)\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{when}\hspace{1em}n=2s+1\hspace{1em}.$
Since $\Vert a_n-a_1\Vert =1$ for these permutations, the maximum value of the given expression is

$2\lfloor \frac{n}{2}\rfloor (n-\lfloor \frac{n}{2}\rfloor )-1\hspace{1em}.$
This is equal to $2s^2-1$ when $n=2s$, and to $2s(s+1)-1$ when $n=2s+1$.

---

45.

Prove that there is no nonconstant polynomial $p(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\dots +a_0$ with integer coefficients $a_i$ for which $p(m)$ is a prime number for every integer $m$.

Solution. Let $a$ be an integer, for which $p(a)\ne -1,0,1$. (If there is no such $a$, then $p$ cannot take all prime values.) Suppose that $b$ is a prime divisor of $p(a)$. Now, for any integer $k$,

$p(a+\mathrm{kb})-p(a)=a_n[(a+\mathrm{kb}){}^n-a^n]+a_{n-1}[(a+\mathrm{kb}){}^{n-1}-a_{n-1}]+\dots +a_1[(a+\mathrm{kb})-a]\hspace{1em}.$
It can be seen that $b$ is a divisor of $p(a+\mathrm{kb})-p(a)$ and hence of $p(a+\mathrm{kb})$ for every integer $k$. Both of the equations $p(x)=b$ and $p(x)=-b$ have at most finitely many roots. So some of the values of $p(a+\mathrm{kb})$ must be composite, and the result follows.

Comment. It should have been stated in the problem that the polynomial was nonconstant, or had positive degree.

---

46.

Let $a_1=2$, $a_{n+1}=\frac{a_n+2}{1-2a_n}$ for $n=1,2,\dots$. Prove that

(a) $a_n\ne 0$ for each positive integer $n$;

(b) there is no integer $p\ge 1$ for which $a_{n+p}=a_n$ for every integer $n\ge 1$ (i.e., the sequence is not periodic).

Solution. (a) We prove that $a_n=\tan n\alpha$ where $\alpha =\arctan 2$ by mathematical induction. This is true for $n=1$. Assume that it holds for $n=k$. Then

$a_{k+1}=\frac{2+a_n}{1-2a_n}=\frac{\tan \alpha +\tan n\alpha }{1-\tan \alpha \tan n\alpha }=\tan (n+1)\alpha \hspace{1em},$
as desired.

Suppose that $a_n=0$ with $n=2m+1$. Then $a_{2m}=-2$. However,

$a_{2m}=\tan 2m\alpha =\frac{2\tan m\alpha }{1-\tan {}^{2}m\alpha }=\frac{2a_m}{1-a_m^2}\hspace{1em},$
whence

$\frac{2a_m}{1-a_m^2}=-2\&lrArr;a_m=\frac{1\pm \sqrt{5}}{2}\hspace{1em},$
which is not possible, since $a_m$ has to be rational.

Suppose that $a_n=0$ with $n=2^k(2m+1)$ for some positive integer $k$. Then

$0=a_n=\tan 2·2^{k-1}(2m+1)\alpha =\frac{2\tan 2^{k-1}(2m+1)}{1-\tan {}^2{2}^{k-1}(2m+1)}=\frac{2a_{n/2}}{1-a_{n/2}^2}\hspace{1em},$
so that $a_{n/2}=0$. Continuing step by step backward, we finally come to $a_{2m+1}=0$, which has already been shown as impossible.

(b) Assume, if possible, that the sequence is periodic, i.e., there is a positive integer $p$ such that $a_{n+p}=a_n$ for every positive integer $n$. Thus

$\tan (n+p)\alpha -\tan n\alpha =\frac{\sin p\alpha }{\cos (n+p)\alpha \cos n\alpha }=0\hspace{1em}.$
Therefore $\sin p\alpha =0$ and so $a_p=\tan p\alpha =0$, which, as we have shown, is impossible. The desired result follows.

---

47.

Let $a_1,a_2,\dots ,a_n$ be positive real numbers such that $a_1{a}_2\dots a_n=1$. Prove that

Solution. First, we recall that Chebyshev's Inequalities:

(1) if the vectors $(a_1,a_2,\dots ,a_n)$ and $(b_1,b_2,\dots ,b_n)$ are similarly sorted (that is, both rising or both falling), then

$\frac{a_1{b}_1+\dots +a_n{b}_n}{n}\ge \frac{a_1+\dots +a_n}{n}·\frac{b_1+\dots +b_n}{n}\hspace{1em};$
(2) if the vectors $(a_1,a_2,\dots ,a_n)$ and $(b_1,b_2,\dots ,b_n)$ are oppositely sorted (that is, one rising and the other falling), then

$\frac{a_1{b}_1+\dots +a_n{b}_n}{n}\le \frac{a_1+\dots +a_n}{n}·\frac{b_1+\dots +b_n}{n}\hspace{1em}.$

If $x_1,x_2,\dots ,x_n$ are positive real numbers with $x_1\le x_1\le \dots \le x_n$, then $x_1^n\le x_2^n\le \dots \le x_n^n$. From Chebyshev's Inequality (1), we have, for each $k=1,2,\dots ,n$, that

$\sum _{i=1,i\ne k}^n{x}_i^n=\sum _{i=1,i\ne k}^n{x}_i^{n-1}{x}_i\ge \frac{1}{n-1}(\sum _{i=1,i\ne k}^n{x}_i)(\sum _{i=1,i\ne k}^n{x}_i^{n-1})\hspace{1em}.$
The Arithmetic-Geometric Means Inequality yields

$\sum _{i=1,i\ne k}^n{x}_i^{n-1}\ge (n-1)x_1\dots x_{k-1}{x}_{k+1}\dots x_n\hspace{1em},$
for $k=1,\dots ,n$. Therefore,

$\sum _{i=1,i\ne k}^n{x}_i^n\ge (x_1\dots x_{k-1}{x}_{k+1}\dots x_n)\sum _{i=1,i\ne k}^n{x}_i\hspace{1em}.$
for each $k$®.This inequality can also be written

$x_1^n+\dots +x_{k-1}^n+x_{k+1}^n+\dots x_n^n+x_1{x}_2\dots x_n\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}\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}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\ge x_1\dots x_{k-1}{x}_{k+1}\dots x_n(x_1+x_2+\dots +x_n)\hspace{1em},$
or

$\frac{1}{x_1{x}_2\dots x_n+x_1^n+\dots +x_{k-1}^n+x_{k+1}^n+\dots +x_n^n}\le \frac{1}{x_1+x_2+\dots +x_n}·\frac{1}{x_1\dots x_{k-1}{x}_{k+1}\dots x_n}\hspace{1em}.$
Adding up these inequalities, for $1\le k\le n$, we get

$\sum _{k=1}^n\frac{1}{x_1{x}_2\dots x_n+x_1^n+\dots +x_{k-1}^n+x_{k+1}^n+\dots x_n^n}\le \frac{1}{x_1{x}_2\dots x_n}\hspace{1em}.$
Now, let the $x_k^n$ be equal to the $a_k$ in increasing order to obtain the desired result.

---

48.

Let $A_1{A}_2\dots A_n$ be a regular $n-$gon and $d$ an arbitrary line. The parallels through $A_i$ to $d$ intersect its circumcircle respectively at $B_i$ ( $i=1,2,\dots ,n$. Prove that the sum

Solution. Select a system of coordinates so that $O$ is the centre of the circumcircle and the $x-$axis (or real axis) is orthogonal to $d$. Without loss of generality, we may assume that the radius of the circumcircle is of length 1. Let $a_k$ the the affix (complex number representative) of $A_k$ ( $1\le k\le n)$. Then the $a_k$ are solutions of the equation $z^n=\lambda$, where $\lambda$ is a complex number with $\Vert \lambda \Vert =1$. Since $A_k$ and $B_k$ are symmetrical with respect to the real axis, the affix of $B_k$ is $\stackrel{\&OverLine;}{a_k}$, the complex conjugate of $a_k$, for $1\le k\le n$, Thus

$A_k{B}_k^2=\Vert a_k-\stackrel{\&OverLine;}{a_k}\Vert {}^2=(a_k-\stackrel{\&OverLine;}{a_k})(\stackrel{\&OverLine;}{a_k}-a_k)=2a_k\stackrel{\&OverLine;}{a_k}-a_k^2-\stackrel{\&OverLine;}{a_k}{}^2=2-a_k-\stackrel{\&OverLine;}{a_k}{}^2\hspace{1em}.$
Summing these inequalities yields that

$\sum _{k=1}^n{A}_k{B}_k^2=2n-\sum _{k=1}^n{a}_k^2-\sum _{k=1}^n\stackrel{\&OverLine;}{a_k}{}^2\hspace{1em}.$
Since $\{a_k:1\le k\le n\}$ is a complete set of solutions of the equation $z^n=\lambda$, their sum and the sum of their pairwise products vanishes. Hence

$0=\sum _{k=1}^n{a}_k^2=\sum _{k=1}^n\stackrel{\&OverLine;}{a_k}{}^2\hspace{1em}.$
Hence $\sum _{k=1}^n{A}_k{B}_k^2=2n\hspace{1em}.$