Canadian Mathematical Society www.cms.math.ca
 location:

Solutions

171.
Let $n$ be a positive integer. In a round-robin match, $n$ teams compete and each pair of teams plays exactly one game. At the end of the match, the $i$th team has ${x}_{i}$ wins and ${y}_{i}$ losses. There are no ties. Prove that

${x}_{1}^{2}+{x}_{2}^{2}+\dots +{x}_{n}^{2}={y}_{1}^{2}+{y}_{2}^{2}+\dots +{y}_{n}^{2} .$

Solution 1. Each game results in both a win and a loss, so the total number of wins is equal to the total number of losses. Thus $\sum {x}_{i}=\sum {y}_{i}$. For each team, the total number of its wins and losses is equal to the number of games it plays. Thus ${x}_{i}+{y}_{i}=n-1$ for each i. Accordingly,

$0=\left(n-1\right)\sum _{i=1}^{n}\left({x}_{i}-{y}_{i}\right)=\sum _{i=1}^{n}\left({x}_{i}+{y}_{i}\right)\left({x}_{i}-{y}_{i}\right)=\sum _{i=1}^{n}\left({x}_{i}^{2}-{y}_{i}^{2}\right)$

from which the desired result follows.
Solution 2. Since ${x}_{i}+{y}_{i}=n-1$ for each $i$ and ${x}_{1}+{x}_{2}+\dots +{x}_{n}={y}_{1}+{y}_{2}+\dots +{y}_{n}=\left(\genfrac{}{}{0}{}{n}{2}\right)$ (the number of games played), we find that

$\begin{array}{cc}\sum _{i=1}^{n}{x}_{i}^{2}\hfill & =\sum _{i=1}^{n}\left[\left(n-1\right)-{y}_{i}\right]{}^{2}\hfill \\ \multicolumn{0}{c}{}& =\sum _{i=1}^{n}{y}_{i}^{2}-2\left(n-1\right)\sum _{i=1}^{n}{y}_{i}+\sum _{i=1}^{n}\left(n-1\right){}^{2}\hfill \\ \multicolumn{0}{c}{}& =\sum _{i=1}^{n}{y}_{i}^{2}-n\left(n-1\right){}^{2}-n\left(n-1\right){}^{2}=\sum _{i=1}^{n}{y}_{i}^{2} .\hfill \end{array}$

172.
Let $a$, $b$, $c$, $d$. $e$, $f$ be different integers. Prove that

$\left(a-b\right){}^{2}+\left(b-c\right){}^{2}+\left(c-d\right){}^{2}+\left(d-e\right){}^{2}+\left(e-f\right){}^{2}+\left(f-a\right){}^{2}\ge 18 .$

Solution 1. Since the sum of the differences is 0, an even number, there must be an even number of odd differences, and therefore an even number of odd squares. If the sum of the squares is less than 18, then this sum must be one of the numbers 6, 8, 10, 12, 14, 16. The only possibilities for expressing any of these numbers as the sum of six nonzero squares is

$6={1}^{2}+{1}^{2}+{1}^{2}+{1}^{2}+{1}^{2}+{1}^{2}$

$12={2}^{2}+{2}^{2}+{1}^{2}+{1}^{2}+{1}^{2}+{1}^{2}$

$14={3}^{3}+{1}^{2}+{1}^{2}+{1}^{2}+{1}^{2}+{1}^{2} .$

Taking note that the sum of the differences is zero, the possible sets of differences (up to order and sign) are $\left\{1,1,1,-1,-1,-1\right\}$, $\left\{3,1,-1,-1,-1,-1\right\}$, $\left\{2,2,-1,-1,-1,-1\right\}$. Since the numbers are distinct, the difference between the largest and smallest is at least 5. This difference must be the sum of differences between adjacent numbers; but checking proves that in each case, an addition of adjacent differences must be less than 5. Hence, it is not possible to achieve a sum of squares less than 18. The sum 18 can be found with the set $\left\{0,1,3,5,4,2\right\}$.
Solution 2. [A. Critch] We prove a more general result. Let $n$ be a positive integer exceeding 1. Let $\left({t}_{1},{t}_{2},\dots ,{t}_{n-1},{t}_{n}\right)$ be an $n-$tple of distinct integers, and suppose that the smallest of these is ${t}_{n}$. Define ${t}_{0}={t}_{n}$, and wolog suppose that ${t}_{0}={t}_{n}=0$. Suppose that, for $1\le i\le n$, ${s}_{i}=‖{t}_{i}-{t}_{i-1}‖$. Let the largest integer be ${t}_{r}$; since the integers are distinct, we must have

$\begin{array}{cc}n-1\hfill & \le {t}_{r}={t}_{r}-{t}_{0}=‖{t}_{r}-{t}_{0}‖\hfill \\ \multicolumn{0}{c}{}& \le ‖{t}_{1}-{t}_{0}‖+\dots +‖{t}_{r}-{t}_{r-1}‖\hfill \\ \multicolumn{0}{c}{}& ={s}_{1}+{s}_{2}+\dots +{s}_{r}\hfill \end{array}$

and

$\begin{array}{cc}n-1\hfill & \le {t}_{r}-{t}_{0}=‖{t}_{n}-{t}_{r}‖\hfill \\ \multicolumn{0}{c}{}& \le ‖{t}_{r+1}-{t}_{r}‖+\dots +‖{t}_{n}-{t}_{n-1}‖={s}_{r+1}+\dots +{s}_{n} .\hfill \end{array}$

Hence.

${s}_{1}+{s}_{2}+\dots +{s}_{n}\ge 2n-2 .$

By the root-mean-square, arithmetic mean (RMS-AM) inequality, we have that

$\left(\frac{{s}_{1}^{2}+{s}_{2}^{2}+\dots +{s}_{n}^{2}}{n}{\right)}^{1/2}\ge \frac{{s}_{1}+{s}_{2}+\dots +{s}_{n}}{n}\ge \frac{2n-2}{n} ,$

so that

${s}_{1}^{2}+{s}_{2}^{2}+\dots +{s}_{n}^{2}\ge \frac{4{n}^{2}-8n+4}{n}=4n-8+\frac{4}{n} .$

Thus,

$\sum _{i=1}^{n}{s}_{i}^{2}\ge 4n-8+⌈4/n⌉ .$

Since the sum of the differences of consecutive ${t}_{i}$ is zero, and so even, the sum of the squares is even. Since $4n-8$ is even and $n\ge 2$, and since the sum exceeds $4n-8$, we see that

$\sum _{i=1}^{n}{s}_{i}^{2}\ge 4n-8+2=4n-6 .$

How can this lower bound be achieved? Since it is equal to ${2}^{2}\left(n-1\right)+{1}^{2}+{1}^{2}$, we can have $n-2$ differences equal to 2 and 2 differences equal to 1. Thus, we can start by going up the odd integers, and then come down via the even integers to 0. In the case of $n=6$, this yields the $6-$tple $\left(1,3,5,4,2,0\right)$.

173.
Suppose that $a$ and $b$ are positive real numbers for which $a+b=1$. Prove that

$\left(a+\frac{1}{a}{\right)}^{2}+\left(b+\frac{1}{b}{\right)}^{2}\ge \frac{25}{2} .$

Determine when equality holds.
Remark. Before starting, we note that when $a+b=1$, $a,b>0$, then $\mathrm{ab}\le \frac{1}{4}$. This is an immediate consequence of the arithmetic-geometric means inequality.
Solution 1. By the root-mean-square, arithmetic mean inequality, we have that

$\begin{array}{cc}\frac{1}{2}\left[\left(a+\frac{1}{a}{\right)}^{2}+\left(b+\frac{1}{b}{\right)}^{2}\right]\hfill & \ge \frac{1}{4}\left[\left(a+\frac{1}{a}\right)+\left(b+\frac{1}{b}\right){\right]}^{2}\hfill \\ \multicolumn{0}{c}{}& =\frac{1}{4}\left(1+\frac{1}{a}+\frac{1}{b}{\right)}^{2}=\frac{1}{4}\left(1+\frac{1}{\mathrm{ab}}{\right)}^{2}\ge \frac{1}{4}·{5}^{2}\hfill \end{array}$

as desired.
Solution 2. By the RMS-AM inequality and the harmonic-arithmetic means inequality, we have that

$\begin{array}{cc}{a}^{2}+{b}^{2}+\left(1/a\right){}^{2}+\left(1/b\right){}^{2}\hfill & \ge \frac{1}{2}\left(a+b\right){}^{2}+\frac{1}{2}\left(\frac{1}{a}+\frac{1}{b}{\right)}^{2}\hfill \\ \multicolumn{0}{c}{}& =\frac{1}{2}+2\left[\frac{\left(1/a\right)+\left(1/b\right)}{2}{\right]}^{2}\hfill \\ \multicolumn{0}{c}{}& \ge \frac{1}{2}+2·\frac{4}{\left(a+b\right){}^{2}}=\frac{17}{2} ,\hfill \end{array}$

from which the result follows.
Solution 3.

$\begin{array}{cc}\left(a+\frac{1}{a}{\right)}^{2}\hfill & +\left(b+\frac{1}{b}{\right)}^{2}\hfill \\ \multicolumn{0}{c}{}& ={a}^{2}+{b}^{2}+\frac{{a}^{2}+{b}^{2}}{{a}^{2}{b}^{2}}+4\hfill \\ \multicolumn{0}{c}{}& =\left(a+b\right){}^{2}-2\mathrm{ab}+\frac{\left(a+b\right){}^{2}-2\mathrm{ab}}{{a}^{2}{b}^{2}}+4\hfill \\ \multicolumn{0}{c}{}& =5-2\mathrm{ab}+\frac{1}{\left(\mathrm{ab}\right){}^{2}}-\frac{2}{\mathrm{ab}}\hfill \\ \multicolumn{0}{c}{}& =4-2\mathrm{ab}+\left(\frac{1}{\mathrm{ab}}-1{\right)}^{2}\ge 4-2\left(\frac{1}{4}\right)+\left(4-1\right){}^{3}=\frac{25}{2} .\hfill \end{array}$

Solution 4. [F. Feng] From the Cauchy-Schwarz and arithmetic-geometric means inequalities, we find that

$\begin{array}{cc}\left[\left(a+\frac{1}{a}{\right)}^{2}\hfill & +\left(b+\frac{1}{b}{\right)}^{2}\right]\left[{1}^{2}+{1}^{2}\right]\hfill \\ \multicolumn{0}{c}{}& =\left[\left(a+\frac{1}{a}{\right)}^{2}+\left(b+\frac{1}{b}{\right)}^{2}\right]\left[\left(a+b\right){}^{2}+\left(a+b\right){}^{2}\right]\hfill \\ \multicolumn{0}{c}{}& \ge \left[\left(a+\frac{1}{a}\right)\left(a+b\right)+\left(b+\frac{1}{b}\right)\left(a+b\right){\right]}^{2}\hfill \\ \multicolumn{0}{c}{}& =\left[\left(a+b\right){}^{2}+2+\left(\frac{a}{b}+\frac{b}{a}\right){\right]}^{2}\hfill \\ \multicolumn{0}{c}{}& \ge \left[1+2+2\right]{}^{2}=25 .\hfill \end{array}$

The desired result follows.

174.
For which real value of $x$ is the function

$\left(1-x\right){}^{5}\left(1+x\right)\left(1+2x\right){}^{2}$

maximum? Determine its maximum value.
Solution 1. The function assumes negative values when $x<-1$ and $x>1$. Accordingly, we need only consider its values on the interval $\left[-1,1\right]$. Suppose, first, that $-1/2\le x\le 1$, in which case all factors of the function are nonnegative. Then we can note, by the arithmetic-geometric means inequality, that

$\left(1-x\right){}^{5}\left(1+x\right)\left(1+2x\right)\le \left[\left(5/8\right)\left(1-x\right)+\left(1/8\right)\left(1+x\right)+\left(2/8\right)\left(1+2x\right)\right]{}^{8}=1$

with equality if and only if $x=0$. Thus, on the interval $\left[-1/2,1\right]$, the function takes its maximum value of 1 when $x=0$.
We adopt the same strategy to consider the situation when $-1\le x\le -1/2$. For convenience, let $u=-x$, so that the want to maximize

$\left(1+u\right){}^{5}\left(1-u\right)\left(2u-1\right){}^{2}$

for $1/2\le u\le 1$. In fact, we are going to maximize

$\left[\alpha \left(1+u\right)\right]{}^{5}\left[\beta \left(1-u\right)\right]\left[\gamma \left(2u-1\right)\right]{}^{2}$

where $\alpha$, $\beta$ and $\gamma$ are positive integers to be chosen to make $5\alpha -\beta +4\gamma =0$ (so that when we calculate the airthmetic mean of the eight factors, the coefficient of $u$ will vanish), and $\alpha \left(1+u\right)=\beta \left(1-u\right)=\gamma \left(2u-1\right)$ (so that we can actually find a case where equality will occur). The latter conditions forces

$\frac{\beta -\alpha }{\beta +\alpha }=\frac{\beta +\gamma }{2\gamma +\beta }$

or $\beta \gamma =3\alpha \gamma +2\alpha \beta$. Plugging $\beta =5\alpha +4\gamma$ into this yields that

$0=2\left(3\alpha \gamma +5{\alpha }^{2}-2{\gamma }^{2}\right)=2\left(5\alpha -2\gamma \right)\left(\alpha +\gamma \right) .$

Thus, let us take $\left(\alpha ,\beta ,\gamma \right)=\left(2,30,5\right)$. Then, by the arithmetic-geometric means inequality, we obtain that

$\begin{array}{cc}\left[2\left(1+u\right)\right]{}^{5/8}\left[30\left(1-u\right)\right]{}^{1/8}\hfill & \left[5\left(2u-1\right)\right]{}^{1/4}\hfill \\ \multicolumn{0}{c}{}& \le \frac{5}{4}\left(1+u\right)+\frac{15}{4}\left(1-u\right)+\frac{5}{4}\left(2u-1\right)=\frac{15}{4} ,\hfill \end{array}$

with equality if and only if $2\left(1+u\right)=30\left(1-u\right)=5\left(2u-1\right)$, i.e., $u=7/8$. Hence,

$\begin{array}{cc}\left(1-x\right){}^{5}\left(1+x\right)\left(1+2x\right){}^{5}\hfill & =\left(1+u\right){}^{5}\left(1-u\right)\left(1-2u\right){}^{2}\hfill \\ \multicolumn{0}{c}{}& \le \left(\frac{15}{8}{\right)}^{8}{2}^{-5/8}{30}^{-1}{5}^{-2}\hfill \\ \multicolumn{0}{c}{}& =\frac{{3}^{7}×{5}^{5}}{{2}^{22}}=\left(\frac{15}{16}{\right)}^{5}\left(\frac{9}{4}\right) ,\hfill \end{array}$

with equality if and only if $x=-7/8$.
It remains to show whether the value of the function when $x=-7/8$ exceeds its value when $x=0$. Recall the Bernoulli inequality: $\left(1+x\right){}^{n}>1+\mathrm{nx}$ for $-1 and positive integer $n$. This can be established by induction (do it!). Using this, we find that

$\left(\frac{15}{16}{\right)}^{5}\left(\frac{9}{4}\right)>\left(1-\frac{5}{16}\right)×2=\frac{22}{16}>1 .$

Thus, the function assumes its maximum value of ${3}^{7}×{5}^{5}×{2}^{-22}$ when $x=-7/8$.
Solution 2. Let $f\left(x\right)=\left(1-x\right){}^{5}\left(1+x\right)\left(1+2x\right){}^{2}$. Then $f\text{'}\left(x\right)=-2\left(1-x\right){}^{4}\left(1+2x\right)x\left(7+8x\right)$. We see that $f\text{'}\left(x\right)>0$ if and only if $x<-7/8$ or $-1/2. Hence $f\left(x\right)$ has relative maxima only when $x=-7/8$ and $x=0$. Checking these two candidates tells us that the absolute maximum of ${3}^{7}×{5}^{5}×{2}^{-22}$ occurs when $x=-7/8$.

175.
$\mathrm{ABC}$ is a triangle such that $\mathrm{AB}<\mathrm{AC}$. The point $D$ is the midpoint of the arc with endpoints $B$ and $C$ of that arc of the circumcircle of $\Delta \mathrm{ABC}$ that contains $A$. The foot of the perpendicular from $D$ to $\mathrm{AC}$ is $E$. Prove that $\mathrm{AB}+\mathrm{AE}=\mathrm{EC}$.
Solution 1. Draw a line through $D$ parallel to $\mathrm{AC}$ that intersects the circumcircle again at $F$. Let $G$ be the foot of the perpendicular from $F$ to $\mathrm{AC}$. Then $\mathrm{DEGF}$ is a rectangle. Since arc $\mathrm{BD}$ is equal to arc $\mathrm{DC}$, and since arc $\mathrm{AD}$ is equal to arc $\mathrm{FC}$ (why?), arc $\mathrm{BA}$ is equal to arc $\mathrm{DF}$. Therefore the chords of these arcs are equal, so that $\mathrm{AB}=\mathrm{DF}=\mathrm{EG}$. Hence $\mathrm{AB}+\mathrm{AE}=\mathrm{EG}+\mathrm{GC}=\mathrm{EC}$.
Solution 2. Note that the length of the shorter arc $\mathrm{AD}$ is less than the length of the shorter arc $\mathrm{DC}$. Locate a point $H$ on the chord $\mathrm{AC}$ so that $\mathrm{AD}=\mathrm{HD}$. Consider triangles $\mathrm{ABD}$ and $\mathrm{HCD}$. We have that $\mathrm{AD}=\mathrm{DH}$, $\mathrm{BD}=\mathrm{CD}$ and $\angle \mathrm{ABD}=\angle \mathrm{HCD}$. This is a case of SSA congruence, the ambiguous case. Since angles $\mathrm{BAD}$ and $\mathrm{DHC}$ are both obtuse (why?), they must be equal rather the supplementary, and the triangles $\mathrm{ABD}$ and $\mathrm{HCD}$ are congruent. (Congruence can also be established using the Law of Sines.) In particular, $\mathrm{AB}=\mathrm{HC}$. Since triangle $\mathrm{ADH}$ is isosceles, $E$ is the midpoint of $\mathrm{AH}$, so that $\mathrm{AB}+\mathrm{AE}=\mathrm{HC}+\mathrm{EH}=\mathrm{EC}$.
Solution 3. Let $\mathrm{DM}$ be a diameter of the circumcircle, so that $M$ is the midpoint of one of the arcs $\mathrm{BC}$. Let $H$ be that point on the chord $\mathrm{AC}$ for which $\mathrm{DA}=\mathrm{DH}$ and let $\mathrm{DH}$ be produced to meet the circle again in $K$. Since $\angle \mathrm{MAD}=\angle \mathrm{DEA}={90}^{ˆ}$, it follows that $\angle \mathrm{MAC}={90}^{ˆ}-\angle \mathrm{EAD}=\angle \mathrm{ADE}$. Since $\mathrm{AM}$ and $\mathrm{DE}$ are both angle bisectors, $\angle \mathrm{BAC}=\angle \mathrm{ADH}$.
Because $\mathrm{ADCK}$ is concyclic, triangles $\mathrm{ADH}$ and $\mathrm{KCH}$ are similar, so that $\mathrm{HC}=\mathrm{CK}$. From the equality of angles $\mathrm{BAC}$ and $\mathrm{ACK}$, we deduce the equality of the arcs $\mathrm{BAC}$ and $\mathrm{ACK}$, and so the equality of the arcs $\mathrm{BA}$ and $\mathrm{CK}$. Hence $\mathrm{AB}=\mathrm{CK}=\mathrm{HC}$. Therefore $\mathrm{AB}+\mathrm{AE}=\mathrm{HC}+\mathrm{EH}=\mathrm{EC}$.
Solution 4. [R. Shapiro] Since $A$ lies on the short arc $\mathrm{BD}$, $\angle \mathrm{BAD}$ is obtuse. Hence the foot of the perpendicular from $D$ to $\mathrm{BA}$ produced is outside of the circumcircle of triangle $\mathrm{ABC}$. In triangles $\mathrm{KBD}$ and $\mathrm{ECD}$, $\angle \mathrm{BKD}=\angle \mathrm{DEC}={90}^{ˆ}$, $\angle \mathrm{KBD}=\angle \mathrm{ABD}=\angle \mathrm{ACD}$ and $\mathrm{BD}=\mathrm{CD}$. Hence the triangles $\mathrm{KBD}$ and $\mathrm{ECD}$ are congruent, so that $\mathrm{DK}=\mathrm{DE}$ and $\mathrm{BK}=\mathrm{EC}$. Since the triangle $\mathrm{ADK}$ and $\mathrm{ADE}$ are right with a common hypotenuse $\mathrm{AD}$ and equal legs $\mathrm{DK}$ and $\mathrm{DE}$, they are congruent and $\mathrm{AK}=\mathrm{AE}$. Hence $\mathrm{EC}=\mathrm{BK}=\mathrm{BA}+\mathrm{AK}=\mathrm{BA}+\mathrm{AE}$, as desired.

176.
Three noncollinear points $A$, $M$ and $N$ are given in the plane. Construct the square such that one of its vertices is the point $A$, and the two sides which do not contain this vertex are on the lines through $M$ and $N$ respectively. [Note: In such a problem, your solution should consist of a description of the construction (with straightedge and compasses) and a proof in correct logical order proceeding from what is given to what is desired that the construction is valid. You should deal with the feasibility of the construction.]
Solution 1. Construction. Draw the circle with diameter $\mathrm{MN}$ and centre $O$. This circle must contain the point $C$, as $\mathrm{MC}$ and $\mathrm{NC}$ are to be perpendicular. Let the right bisector of $\mathrm{MN}$ meet the circle in $K$ and $L$. Join $\mathrm{AK}$ and, if necessary, produce it to meet the circle at $C$. Now draw the circle with diameter $\mathrm{AC}$ and let it meet the right bisector of $\mathrm{AC}$ at $B$ and $D$. Then $\mathrm{ABCD}$ is the required rectangle. There are two options, depending how we label the right bisector $\mathrm{KL}$.
However, the construction does not work if $A$ actually lies on the circle with diameter $\mathrm{MN}$. In this case, $A$ and $C$ would coincide and the situation degenerates. If $A$ lies on the right bisector of $\mathrm{MN}$, then $C$ can be the other point where the right bisector intersects the circle, and $M$ and $N$ can be the other two vertices of the square. If $A$ is not on the right bisector, then there is no square; all of the points $A$, $M$, $C$, $N$ would have to be on the circle, and $\mathrm{AM}$ and $\mathrm{AN}$ would have to subtend angles of ${45}^{ˆ}$ at $C$, which is not possible.
Proof. If $C$ and $O$ are on the same side of $\mathrm{KN}$, then $\angle \mathrm{KCN}=\frac{1}{2}\angle \mathrm{KON}={45}^{ˆ}$, so that $\mathrm{CN}$ makes an angle of ${45}^{ˆ}$ with $\mathrm{AC}$ produced, and so $\mathrm{CN}$ produced contains a side of the square. Similarly, $\mathrm{CM}$ produced contains a side of the square. If $C$ and $O$ are on opposite sides of $\mathrm{KN}$, then $\angle \mathrm{KCN}={135}^{ˆ}$, and $\mathrm{CN}$ still makes an angle of ${45}^{ˆ}$ with $\mathrm{AC}$ produced; the argument can be completed as before.
Solution 2. Construction. Construct circle of diameter $\mathrm{MN}$. Draw $\mathrm{AM}=\mathrm{MR}$ (with the segment $\mathrm{MR}$ intersecting the interior of the circle) and $\mathrm{AM}\perp \mathrm{MR}$. Construct the circle $\mathrm{AMR}$. Let this circle intersect the given circle at $C$. Then construct the square with diagonal $\mathrm{AC}$. If $A$ lies on the circle, then the candidates for $C$ are $A$ and $M$. We cannot take $C=A$, as the situation degererates; if we take $C=M$, then the angle $\mathrm{ACM}$ and segment $\mathrm{CM}$ degenerate. We can complete the analysis as in the first solution.
Proof. Since $\Delta \mathrm{ARM}$ is right isosceles, $\angle \mathrm{ARM}={45}^{ˆ}$. Hence the circle is the locus of points at which $\mathrm{AM}$ subtends an angle equal to ${45}^{ˆ}$ or ${135}^{ˆ}$. Hence the lines $\mathrm{AC}$ and $\mathrm{CM}$ intersect at an angle of ${45}^{ˆ}$. Since $\angle \mathrm{MCN}={90}^{ˆ}$, the lines $\mathrm{AC}$ and $\mathrm{CN}$ also intersect at ${45}^{ˆ}$. It follows that the remaining points on the square with diagonal $\mathrm{AC}$ must lie on the lines $\mathrm{CM}$ and $\mathrm{CN}$.

177.
Let ${a}_{1}$, ${a}_{2}$, $\dots$, ${a}_{n}$ be nonnegative integers such that, whenever $1\le i$, $1\le j$, $i+j\le n$, then

${a}_{i}+{a}_{j}\le {a}_{i+j}\le {a}_{i}+{a}_{j}+1 .$

(a) Give an example of such a sequence which is not an arithmetic progression.
(b) Prove that there exists a real number $x$ such that ${a}_{k}=⌊\mathrm{kx}⌋$ for $1\le k\le n$.
(a) Solution. [R. Marinov] For positive integers $n$, let ${a}_{n}=k-1$ when $n=2k$ and ${a}_{n}=k$ when $n=2k+1$, so that the sequence is $\left\{0,1,1,2,2,3,3,\dots \right\}$. Observe that

${a}_{\left(2p+1\right)+\left(2q+1\right)}={a}_{2\left(p+q+1\right)}=p+q={a}_{2p+1}+{a}_{2q+1}$

${a}_{2p+2q}={a}_{2\left(p+q\right)}=p+q-1=\left(p-1\right)+\left(q-1\right)+1={a}_{2p}+{a}_{2q}+1$

and

${a}_{2p+\left(2q+1\right)}={a}_{2\left(p+q\right)+1}=p+q=\left(p-1\right)+q+1={a}_{2p}+{a}_{2q+1}$

for positive integers $p$ and $q$, whence we see that this sequence satisfies the condition. The corresponding value of $x$ is $1/2$.
Solution. [A. Critch] The assertion to be proved is that all the semi-closed intervals $\left[{a}_{k}/k,{a}_{k+1}/k\right)$ have a point in common. Suppose, if possible, that this fails. Then there must be a pair $\left(p,q\right)$ of necessarily distinct integers for which ${a}_{q}/q\ge \left({a}_{p}+1\right)/p$. This is equivalent to ${\mathrm{pa}}_{q}\ge {\mathrm{qa}}_{p}+q$. Suppose that the sum of these two indices is as small as possible.
Suppose that $p>q$, so that $p=q+r$ for some positive $r$. Then

$\left(q+r\right){a}_{q}\ge {\mathrm{qa}}_{p}+q={\mathrm{qa}}_{q+r}+q\ge {\mathrm{qa}}_{q}+{\mathrm{qa}}_{r}+q$

whence ${\mathrm{ra}}_{q}\ge {\mathrm{qa}}_{r}+q$ and ${a}_{q}/q\ge \left({a}_{r}+1\right)/r$. Thus $p$ and $r$ have the property of $p$ and $q$ and we get a contradiction of the minimality condition.
Suppose that $p, so that $q=p+s$ for some positive $s$. Then

$p+{\mathrm{pa}}_{p}+{\mathrm{pa}}_{s}\ge {\mathrm{pa}}_{p+s}\ge \left(p+s\right){a}_{p}+q={\mathrm{pa}}_{p}+{\mathrm{sa}}_{p}+q$

so that $p+{\mathrm{pa}}_{s}\ge {\mathrm{sa}}_{p}+q>{\mathrm{sa}}_{p}+p+s$, ${\mathrm{pa}}_{s}\ge {\mathrm{sa}}_{p}+s$ and ${a}_{s}/s\ge \left({a}_{p}+1\right)/p$, once again contradicting the minimality condition.

© Canadian Mathematical Society, 2014 : https://cms.math.ca/