location:

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}=100{x}_{1}+{100}^{2}{x}_{2}+\dots +{100}^{n}{x}_{n} .$

Note that

$\begin{array}{cc}|\hfill & \frac{100{x}_{1}+{100}^{2}{x}_{2}+\dots +{100}^{n-1}{x}_{n-1}}{{100}^{n}}|\hfill \\ \multicolumn{0}{c}{}& \le \frac{100‖{x}_{1}‖+{100}^{2}‖{x}_{2}‖+\dots +{100}^{n-1}‖{x}_{n-1}‖}{{100}^{n}}\hfill \\ \multicolumn{0}{c}{}& \le \frac{9\left(100+{100}^{2}+\dots +{100}^{n-1}\right)}{{100}^{n}}\hfill \\ \multicolumn{0}{c}{}& <\frac{{10}^{2n-1}}{{10}^{2n}}=\frac{1}{10} .\hfill \end{array}$

Hence

$|\frac{{S}_{n}}{{100}^{n}}-{x}_{n}|=\frac{100{x}_{1}+{100}^{2}{x}_{2}+\dots +{100}^{n-1}{x}_{n-1}}{{100}^{n}}<\frac{1}{10} ,$

and ${x}_{n}$ can be obtained. Now, we can find the sum

${S}_{n-1}={S}_{n}-{100}^{n}{x}_{n}=100{x}_{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 $\left\{{a}_{1},{a}_{2},\dots ,{a}_{n}\right\}$ of the set $\left\{1,2,\dots ,n\right\}$ for which the sum

$S=‖{a}_{2}-{a}_{1}‖+‖{a}_{3}-{a}_{2}‖+\dots +‖{a}_{n}-{a}_{n-1}‖$

has maximum value.
Solution. Let $a=\left({a}_{1},{a}_{2},\dots ,{a}_{n}\right)$ be a permutation of $\left\{1,2,\dots ,n\right\}$ and define

$f\left(a\right)=\sum _{k=1}^{n-1}‖{a}_{k+1}-{a}_{k}‖+‖{a}_{n}-{a}_{1}‖ .$

With ${a}_{n+1}={a}_{1}$ and ${\epsilon }_{0}={\epsilon }_{n}$, we find that

$f\left(a\right)=\sum _{k=1}^{n}{\epsilon }_{k}\left({a}_{k+1}-{a}_{k}\right)=\sum _{k=1}^{n}\left({\epsilon }_{k-1}-{\epsilon }_{k}\right){a}_{k}$

where ${\epsilon }_{1}$, ${\epsilon }_{2}$, $\dots$, ${\epsilon }_{n}$ are all equal to $1$ or $-1$. Thus

$f\left(a\right)=\sum _{k=1}^{n}{\beta }_{k}k .$

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\left(a\right)=2\left({x}_{1}+{x}_{2}+\dots +{x}_{m}\right)-2\left({y}_{1}+{y}_{2}+\dots +{y}_{m}\right)$

where ${x}_{1},\dots ,{x}_{m},{y}_{1},\dots ,{y}_{m}\in \left\{1,2,\dots ,n\right\}$ and are distinct from each other. Hence $f\left(a\right)$ is maximum when $\left\{{x}_{1},{x}_{2},\dots ,{x}_{m}\right\}=\left\{n,n-1,\dots ,n-m+1\right\}$, $\left\{{y}_{1},{y}_{2},\dots ,{y}_{m}\right\}=\left\{1,2,\dots ,m\right\}$ with $m=⌊n/2⌋$, i.e., $m$ is as large as possible. The maximum value is

$2⌊\frac{n}{2}⌋\left(n-⌊\frac{n}{2}⌋\right) .$

This value is attained by taking

$a=\left(s+1,1,s+2,2,\dots ,2s,s\right) \mathrm{when} n=2s$

and

$a=\left(s+2,1,s+3,2,\dots ,2s+1,s,s+1\right) \mathrm{when} n=2s+1 .$

Since $‖{a}_{n}-{a}_{1}‖=1$ for these permutations, the maximum value of the given expression is

$2⌊\frac{n}{2}⌋\left(n-⌊\frac{n}{2}⌋\right)-1 .$

This is equal to $2{s}^{2}-1$ when $n=2s$, and to $2s\left(s+1\right)-1$ when $n=2s+1$.

45.
Prove that there is no nonconstant polynomial $p\left(x\right)={a}_{n}{x}^{n}+{a}_{n-1}{x}^{n-1}+\dots +{a}_{0}$ with integer coefficients ${a}_{i}$ for which $p\left(m\right)$ is a prime number for every integer $m$.
Solution. Let $a$ be an integer, for which $p\left(a\right)\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\left(a\right)$. Now, for any integer $k$,

$p\left(a+\mathrm{kb}\right)-p\left(a\right)={a}_{n}\left[\left(a+\mathrm{kb}\right){}^{n}-{a}^{n}\right]+{a}_{n-1}\left[\left(a+\mathrm{kb}\right){}^{n-1}-{a}_{n-1}\right]+\dots +{a}_{1}\left[\left(a+\mathrm{kb}\right)-a\right] .$

It can be seen that $b$ is a divisor of $p\left(a+\mathrm{kb}\right)-p\left(a\right)$ and hence of $p\left(a+\mathrm{kb}\right)$ for every integer $k$. Both of the equations $p\left(x\right)=b$ and $p\left(x\right)=-b$ have at most finitely many roots. So some of the values of $p\left(a+\mathrm{kb}\right)$ 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-2{a}_{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}=\mathrm{tan}n\alpha$ where $\alpha =\mathrm{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-2{a}_{n}}=\frac{\mathrm{tan}\alpha +\mathrm{tan}n\alpha }{1-\mathrm{tan}\alpha \mathrm{tan}n\alpha }=\mathrm{tan}\left(n+1\right)\alpha ,$

as desired.
Suppose that ${a}_{n}=0$ with $n=2m+1$. Then ${a}_{2m}=-2$. However,

${a}_{2m}=\mathrm{tan}2m\alpha =\frac{2\mathrm{tan}m\alpha }{1-\mathrm{tan}{}^{2}m\alpha }=\frac{2{a}_{m}}{1-{a}_{m}^{2}} ,$

whence

$\frac{2{a}_{m}}{1-{a}_{m}^{2}}=-2&lrArr;{a}_{m}=\frac{1±\sqrt{5}}{2} ,$

which is not possible, since ${a}_{m}$ has to be rational.
Suppose that ${a}_{n}=0$ with $n={2}^{k}\left(2m+1\right)$ for some positive integer $k$. Then

$0={a}_{n}=\mathrm{tan}2·{2}^{k-1}\left(2m+1\right)\alpha =\frac{2\mathrm{tan}{2}^{k-1}\left(2m+1\right)}{1-\mathrm{tan}{}^{2}{2}^{k-1}\left(2m+1\right)}=\frac{2{a}_{n/2}}{1-{a}_{n/2}^{2}} ,$

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

$\mathrm{tan}\left(n+p\right)\alpha -\mathrm{tan}n\alpha =\frac{\mathrm{sin}p\alpha }{\mathrm{cos}\left(n+p\right)\alpha \mathrm{cos}n\alpha }=0 .$

Therefore $\mathrm{sin}p\alpha =0$ and so ${a}_{p}=\mathrm{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

$\sum _{k=1}^{n}\frac{1}{s-{a}_{k}}\le 1$

where $s=1+{a}_{1}+{a}_{2}+\dots +{a}_{n}$.
Solution. First, we recall that Chebyshev's Inequalities:
(1) if the vectors $\left({a}_{1},{a}_{2},\dots ,{a}_{n}\right)$ and $\left({b}_{1},{b}_{2},\dots ,{b}_{n}\right)$ 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} ;$

(2) if the vectors $\left({a}_{1},{a}_{2},\dots ,{a}_{n}\right)$ and $\left({b}_{1},{b}_{2},\dots ,{b}_{n}\right)$ 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} .$

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}\left(\sum _{i=1,i\ne k}^{n}{x}_{i}\right)\left(\sum _{i=1,i\ne k}^{n}{x}_{i}^{n-1}\right) .$

The Arithmetic-Geometric Means Inequality yields

$\sum _{i=1,i\ne k}^{n}{x}_{i}^{n-1}\ge \left(n-1\right){x}_{1}\dots {x}_{k-1}{x}_{k+1}\dots {x}_{n} ,$

for $k=1,\dots ,n$. Therefore,

$\sum _{i=1,i\ne k}^{n}{x}_{i}^{n}\ge \left({x}_{1}\dots {x}_{k-1}{x}_{k+1}\dots {x}_{n}\right)\sum _{i=1,i\ne k}^{n}{x}_{i} .$

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

$\ge {x}_{1}\dots {x}_{k-1}{x}_{k+1}\dots {x}_{n}\left({x}_{1}+{x}_{2}+\dots +{x}_{n}\right) ,$

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

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

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

$S=‖{A}_{1}{B}_{1}‖{}^{2}+\dots +‖{A}_{n}{B}_{n}‖{}^{2}$

is independent of $d$.
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\right)$. Then the ${a}_{k}$ are solutions of the equation ${z}^{n}=\lambda$, where $\lambda$ is a complex number with $‖\lambda ‖=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}=‖{a}_{k}-\stackrel{&OverLine;}{{a}_{k}}‖{}^{2}=\left({a}_{k}-\stackrel{&OverLine;}{{a}_{k}}\right)\left(\stackrel{&OverLine;}{{a}_{k}}-{a}_{k}\right)=2{a}_{k}\stackrel{&OverLine;}{{a}_{k}}-{a}_{k}^{2}-\stackrel{&OverLine;}{{a}_{k}}{}^{2}=2-{a}_{k}-\stackrel{&OverLine;}{{a}_{k}}{}^{2} .$

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

Since $\left\{{a}_{k}:1\le k\le n\right\}$ 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} .$

Hence $\sum _{k=1}^{n}{A}_{k}{B}_{k}^{2}=2n .$