Solutions

171.

Let
$n$ be a positive integer. In a roundrobin
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}\hspace{1em}.$
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}=n1$ for each i.
Accordingly,
$0=(n1)\sum _{i=1}^{n}({x}_{i}{y}_{i})=\sum _{i=1}^{n}({x}_{i}+{y}_{i})({x}_{i}{y}_{i})=\sum _{i=1}^{n}({x}_{i}^{2}{y}_{i}^{2})$
from which the desired result follows.
Solution 2. Since
${x}_{i}+{y}_{i}=n1$ for each
$i$
and
${x}_{1}+{x}_{2}+\dots +{x}_{n}={y}_{1}+{y}_{2}+\dots +{y}_{n}=\left(\genfrac{}{}{0ex}{}{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}[(n1){y}_{i}]{}^{2}\hfill \\ \multicolumn{0}{c}{}& =\sum _{i=1}^{n}{y}_{i}^{2}2(n1)\sum _{i=1}^{n}{y}_{i}+\sum _{i=1}^{n}(n1){}^{2}\hfill \\ \multicolumn{0}{c}{}& =\sum _{i=1}^{n}{y}_{i}^{2}n(n1){}^{2}n(n1){}^{2}=\sum _{i=1}^{n}{y}_{i}^{2}\hspace{1em}.\hfill \end{array}$

172.

Let
$a$,
$b$,
$c$,
$d$.
$e$,
$f$ be different
integers. Prove that
$(ab){}^{2}+(bc){}^{2}+(cd){}^{2}+(de){}^{2}+(ef){}^{2}+(fa){}^{2}\ge 18\hspace{1em}.$
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}\hspace{1em}.$
Taking note that the sum of the differences is zero, the possible
sets of differences (up to order and sign) are
$\{1,1,1,1,1,1\}$,
$\{3,1,1,1,1,1\}$,
$\{2,2,1,1,1,1\}$. 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
$\{0,1,3,5,4,2\}$.
Solution 2. [A. Critch] We prove a more general result.
Let
$n$ be a positive integer exceeding 1.
Let
$({t}_{1},{t}_{2},\dots ,{t}_{n1},{t}_{n})$
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}=\Vert {t}_{i}{t}_{i1}\Vert $.
Let the largest integer be
${t}_{r}$; since the integers are distinct, we must have
$\begin{array}{cc}n1\hfill & \le {t}_{r}={t}_{r}{t}_{0}=\Vert {t}_{r}{t}_{0}\Vert \hfill \\ \multicolumn{0}{c}{}& \le \Vert {t}_{1}{t}_{0}\Vert +\dots +\Vert {t}_{r}{t}_{r1}\Vert \hfill \\ \multicolumn{0}{c}{}& ={s}_{1}+{s}_{2}+\dots +{s}_{r}\hfill \end{array}$
and
$\begin{array}{cc}n1\hfill & \le {t}_{r}{t}_{0}=\Vert {t}_{n}{t}_{r}\Vert \hfill \\ \multicolumn{0}{c}{}& \le \Vert {t}_{r+1}{t}_{r}\Vert +\dots +\Vert {t}_{n}{t}_{n1}\Vert ={s}_{r+1}+\dots +{s}_{n}\hspace{1em}.\hfill \end{array}$
Hence.
${s}_{1}+{s}_{2}+\dots +{s}_{n}\ge 2n2\hspace{1em}.$
By the rootmeansquare, arithmetic mean (RMSAM)
inequality, we have that
$(\frac{{s}_{1}^{2}+{s}_{2}^{2}+\dots +{s}_{n}^{2}}{n}{)}^{1/2}\ge \frac{{s}_{1}+{s}_{2}+\dots +{s}_{n}}{n}\ge \frac{2n2}{n}\hspace{1em},$
so that
${s}_{1}^{2}+{s}_{2}^{2}+\dots +{s}_{n}^{2}\ge \frac{4{n}^{2}8n+4}{n}=4n8+\frac{4}{n}\hspace{1em}.$
Thus,
$\sum _{i=1}^{n}{s}_{i}^{2}\ge 4n8+\lceil 4/n\rceil \hspace{1em}.$
Since the sum of the differences of consecutive
${t}_{i}$ is zero, and
so even, the sum of the squares is even. Since
$4n8$ is even
and
$n\ge 2$, and since the sum exceeds
$4n8$, we see that
$\sum _{i=1}^{n}{s}_{i}^{2}\ge 4n8+2=4n6\hspace{1em}.$
How can this lower bound be achieved? Since it is equal to
${2}^{2}(n1)+{1}^{2}+{1}^{2}$, we can have
$n2$ 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
$(1,3,5,4,2,0)$.

173.

Suppose that
$a$ and
$b$ are positive real numbers
for which
$a+b=1$. Prove that
$(a+\frac{1}{a}{)}^{2}+(b+\frac{1}{b}{)}^{2}\ge \frac{25}{2}\hspace{1em}.$
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 arithmeticgeometric means inequality.
Solution 1. By the rootmeansquare, arithmetic mean inequality,
we have that
$\begin{array}{cc}\frac{1}{2}[(a+\frac{1}{a}{)}^{2}+(b+\frac{1}{b}{)}^{2}]\hfill & \ge \frac{1}{4}[(a+\frac{1}{a})+(b+\frac{1}{b}){]}^{2}\hfill \\ \multicolumn{0}{c}{}& =\frac{1}{4}(1+\frac{1}{a}+\frac{1}{b}{)}^{2}=\frac{1}{4}(1+\frac{1}{\mathrm{ab}}{)}^{2}\ge \frac{1}{4}\xb7{5}^{2}\hfill \end{array}$
as desired.
Solution 2. By the RMSAM inequality and the
harmonicarithmetic means inequality, we have that
$\begin{array}{cc}{a}^{2}+{b}^{2}+(1/a){}^{2}+(1/b){}^{2}\hfill & \ge \frac{1}{2}(a+b){}^{2}+\frac{1}{2}(\frac{1}{a}+\frac{1}{b}{)}^{2}\hfill \\ \multicolumn{0}{c}{}& =\frac{1}{2}+2[\frac{(1/a)+(1/b)}{2}{]}^{2}\hfill \\ \multicolumn{0}{c}{}& \ge \frac{1}{2}+2\xb7\frac{4}{(a+b){}^{2}}=\frac{17}{2}\hspace{1em},\hfill \end{array}$
from which the result follows.
Solution 3.
$\begin{array}{cc}(a+\frac{1}{a}{)}^{2}\hfill & +(b+\frac{1}{b}{)}^{2}\hfill \\ \multicolumn{0}{c}{}& ={a}^{2}+{b}^{2}+\frac{{a}^{2}+{b}^{2}}{{a}^{2}{b}^{2}}+4\hfill \\ \multicolumn{0}{c}{}& =(a+b){}^{2}2\mathrm{ab}+\frac{(a+b){}^{2}2\mathrm{ab}}{{a}^{2}{b}^{2}}+4\hfill \\ \multicolumn{0}{c}{}& =52\mathrm{ab}+\frac{1}{(\mathrm{ab}){}^{2}}\frac{2}{\mathrm{ab}}\hfill \\ \multicolumn{0}{c}{}& =42\mathrm{ab}+(\frac{1}{\mathrm{ab}}1{)}^{2}\ge 42(\frac{1}{4})+(41){}^{3}=\frac{25}{2}\hspace{1em}.\hfill \end{array}$
Solution 4. [F. Feng] From the CauchySchwarz and
arithmeticgeometric means inequalities, we find that
$\begin{array}{cc}[(a+\frac{1}{a}{)}^{2}\hfill & +(b+\frac{1}{b}{)}^{2}][{1}^{2}+{1}^{2}]\hfill \\ \multicolumn{0}{c}{}& =[(a+\frac{1}{a}{)}^{2}+(b+\frac{1}{b}{)}^{2}][(a+b){}^{2}+(a+b){}^{2}]\hfill \\ \multicolumn{0}{c}{}& \ge [(a+\frac{1}{a})(a+b)+(b+\frac{1}{b})(a+b){]}^{2}\hfill \\ \multicolumn{0}{c}{}& =[(a+b){}^{2}+2+(\frac{a}{b}+\frac{b}{a}){]}^{2}\hfill \\ \multicolumn{0}{c}{}& \ge [1+2+2]{}^{2}=25\hspace{1em}.\hfill \end{array}$
The desired result follows.

174.

For which real value of
$x$ is the function
$(1x){}^{5}(1+x)(1+2x){}^{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
$[1,1]$. 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 arithmeticgeometric
means inequality, that
$(1x){}^{5}(1+x)(1+2x)\le [(5/8)(1x)+(1/8)(1+x)+(2/8)(1+2x)]{}^{8}=1$
with equality if and only if
$x=0$. Thus, on the interval
$[1/2,1]$,
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
$(1+u){}^{5}(1u)(2u1){}^{2}$
for
$1/2\le u\le 1$. In fact, we are going to maximize
$[\alpha (1+u)]{}^{5}[\beta (1u)][\gamma (2u1)]{}^{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 (1+u)=\beta (1u)=\gamma (2u1)$ (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(3\alpha \gamma +5{\alpha}^{2}2{\gamma}^{2})=2(5\alpha 2\gamma )(\alpha +\gamma )\hspace{1em}.$
Thus, let us take
$(\alpha ,\beta ,\gamma )=(2,30,5)$.
Then, by the arithmeticgeometric means inequality, we obtain that
$\begin{array}{cc}[2(1+u)]{}^{5/8}[30(1u)]{}^{1/8}\hfill & [5(2u1)]{}^{1/4}\hfill \\ \multicolumn{0}{c}{}& \le \frac{5}{4}(1+u)+\frac{15}{4}(1u)+\frac{5}{4}(2u1)=\frac{15}{4}\hspace{1em},\hfill \end{array}$
with equality if and only if
$2(1+u)=30(1u)=5(2u1)$,
i.e.,
$u=7/8$. Hence,
$\begin{array}{cc}(1x){}^{5}(1+x)(1+2x){}^{5}\hfill & =(1+u){}^{5}(1u)(12u){}^{2}\hfill \\ \multicolumn{0}{c}{}& \le (\frac{15}{8}{)}^{8}{2}^{5/8}{30}^{1}{5}^{2}\hfill \\ \multicolumn{0}{c}{}& =\frac{{3}^{7}\times {5}^{5}}{{2}^{22}}=(\frac{15}{16}{)}^{5}(\frac{9}{4})\hspace{1em},\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:
$(1+x){}^{n}>1+\mathrm{nx}$ for
$1<x,x\ne 0$ and positive integer
$n$. This can be established by induction (do it!). Using this,
we find that
$(\frac{15}{16}{)}^{5}(\frac{9}{4})>(1\frac{5}{16})\times 2=\frac{22}{16}>1\hspace{1em}.$
Thus, the function assumes its maximum value of
${3}^{7}\times {5}^{5}\times {2}^{22}$ when
$x=7/8$.
Solution 2. Let
$f(x)=(1x){}^{5}(1+x)(1+2x){}^{2}$.
Then
$f\text{'}(x)=2(1x){}^{4}(1+2x)x(7+8x)$. We see that
$f\text{'}(x)>0$ if and only if
$x<7/8$ or
$1/2<x<0$.
Hence
$f(x)$ has relative maxima only when
$x=7/8$ and
$x=0$. Checking these two candidates tells us that the
absolute maximum of
${3}^{7}\times {5}^{5}\times {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}^{\u02c6}$,
it follows that
$\angle \mathrm{MAC}={90}^{\u02c6}\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}^{\u02c6}$,
$\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}^{\u02c6}$ 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}^{\u02c6}$, so that
$\mathrm{CN}$ makes an angle of
${45}^{\u02c6}$ 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}^{\u02c6}$, and
$\mathrm{CN}$ still makes an
angle of
${45}^{\u02c6}$ 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}^{\u02c6}$. Hence the circle is the locus of points at which
$\mathrm{AM}$ subtends an angle equal to
${45}^{\u02c6}$ or
${135}^{\u02c6}$.
Hence the lines
$\mathrm{AC}$ and
$\mathrm{CM}$ intersect at an angle of
${45}^{\u02c6}$.
Since
$\angle \mathrm{MCN}={90}^{\u02c6}$, the lines
$\mathrm{AC}$ and
$\mathrm{CN}$ also
intersect at
${45}^{\u02c6}$. 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\hspace{1em}.$


(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}=\lfloor \mathrm{kx}\rfloor $ for
$1\le k\le n$.
(a)
Solution. [R. Marinov] For positive integers
$n$, let
${a}_{n}=k1$ when
$n=2k$ and
${a}_{n}=k$ when
$n=2k+1$, so
that the sequence is
$\{0,1,1,2,2,3,3,\dots \}$.
Observe that
${a}_{(2p+1)+(2q+1)}={a}_{2(p+q+1)}=p+q={a}_{2p+1}+{a}_{2q+1}$
${a}_{2p+2q}={a}_{2(p+q)}=p+q1=(p1)+(q1)+1={a}_{2p}+{a}_{2q}+1$
and
${a}_{2p+(2q+1)}={a}_{2(p+q)+1}=p+q=(p1)+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 semiclosed intervals
$[{a}_{k}/k,{a}_{k+1}/k)$ have a point in
common. Suppose, if possible, that this fails. Then there must
be a pair
$(p,q)$ of necessarily distinct integers for which
${a}_{q}/q\ge ({a}_{p}+1)/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
$(q+r){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 ({a}_{r}+1)/r$. Thus
$p$ and
$r$ have the property of
$p$ and
$q$ and we get a contradiction
of the minimality condition.
Suppose that
$p<q$, so that
$q=p+s$ for some positive
$s$.
Then
$p+{\mathrm{pa}}_{p}+{\mathrm{pa}}_{s}\ge {\mathrm{pa}}_{p+s}\ge (p+s){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 ({a}_{p}+1)/p$, once again contradicting the minimality
condition.