location:

55.
A textbook problem has the following form: A man is standing in a line in front of a movie theatre. The fraction $x$ of the line is in front of him, and the fraction $y$ of the line is behind him, where $x$ and $y$ are rational numbers written in lowest terms. How many people are there in the line? Prove that, if the problem has an answer, then that answer must be the least common multiple of the denominators of $x$ and $y$.
Solution. Let $p$ and $q$ be the denominators of $x$ and $y$, when written in their lowest terms; each denominator has no positive divisor save $1$ in common with the corresponding numerator. Let $n$ be the number of people in line. Since $\mathrm{xn}$ and $\mathrm{yn}$ are integers, $p$ and $q$ must both divide $n$, so that $n$ is a multiple of $m$, the least common multiple of $p$ and $q$.
$1-x-y$ can be written as a fraction of the form $u/m$. Since $\left(u/m\right)n=u\left(n/m\right)=1$, we must have that $u=n/m=1$, so that in particular $m=n$.
Comment. This is quite a difficult question to write up, because you have to put your finger quite precisely on the main issues involved. Many solvers relied on statements that were equally if not more difficult to see than the result of the problem. The point of a solution is to show how a result can be obtained from simpler or more wellknown propositions.

56.
Let $n$ be a positive integer and let ${x}_{1},{x}_{2},\dots ,{x}_{n}$ be integers for which

${x}_{1}^{2}+{x}_{2}^{2}+\dots +{x}_{n}^{2}+{n}^{3}\le \left(2n-1\right)\left({x}_{1}+{x}_{2}+\dots +{x}_{n}\right)+{n}^{2} .$

Show that
(a) ${x}_{1},{x}_{2},\dots ,{x}_{n}$ are all nonnegative;
(b) ${x}_{1}+{x}_{2}+\dots +{x}_{n}+n+1$ is not a perfect square.
Solution 1. The inequality can be rewritten as

$\sum _{i=1}^{n}\left({x}_{i}-n\right)\left({x}_{i}-\stackrel{}{n-1}\right)\le 0 .$

(The line over $n-1$ is a form of bracket.) Since each summand is positive for integers other than $n$ and $n-1$, the inequality can hold only if each ${x}_{i}$ is equal to either $n$ or $n-1$. Therefore,

${n}^{2}+1=n\left(n-1\right)+n+1\le {x}_{1}+{x}_{2}+\dots +{x}_{n}+n+1\le {n}^{2}+n+1<\left(n+1\right){}^{2} .$

Parts (a) and (b) follow easily from this.
Solution 2. [R. Furmaniak] Taking the difference between the right and left sides leads to the equivalent inequality

$\sum _{k=1}^{n}\left[2{x}_{k}-\left(2n-1\right)\right]{}^{2}\le n .$

Since each term in the sum is odd, it can only be 1. Therefore $2{x}_{k}-\left(2n-1\right)=±1$, whence ${x}_{k}$ is equal to $n$ or $n-1$ for each $k$. The solution can be concluded as before.
Solution 3. [O. Bormashenko, M. Holmes] The given inequality is equivalent to

$\sum _{i=1}^{n}{x}_{i}\left({x}_{i}-\stackrel{}{2n-1}\right)\le {n}^{2}-{n}^{3} .$

Observe that, for each $i$,

${x}_{i}\left(\stackrel{}{2n-1}-{x}_{i}\right)\le \left[\frac{1}{2}\left(2n-1\right)\right]{}^{2}={n}^{2}-n+\frac{1}{4} .$

This is a consequence of the arithmetic-geometric means inequality when the left side is positive, and obvious when the left side is negative. Since ${x}_{i}$ is supposed to be an integer, we must have

${x}_{i}\left(\stackrel{}{2n-1}-{x}_{i}\right)\le {n}^{2}-n$

and equality occurs if and only if ${x}_{i}=n$ or ${x}_{i}=n-1$. (One way to see this is to note that the left side is a quadratic and can take each of its values no more than twice.) Multiplying by $-1$ yields that

${x}_{i}\left({x}_{i}-\stackrel{}{2n-1}\right)\ge n-{n}^{2}$

whence

$\sum _{i=1}^{n}{x}_{i}\left({x}_{i}-\stackrel{}{2n-1}\right)\ge {n}^{2}-{n}^{3} ,.$

with equality if and only if each ${x}_{i}$ is equal to $n$ or $n-1$. But because of the given inequality, equality does occur. The solution can now be completed as before.
Solution 4. The given inequality is equivalent to

$\sum _{i=1}^{n}\left(n-{x}_{i}\right){}^{2}\le \sum _{i=1}^{n}\left(n-{x}_{i}\right) .\text{ }\left(1\right)$

However, since ${x}_{i}$ is an integer for each $i$, $\left(n-{x}_{i}\right){}^{2}\ge \left(n-{x}_{i}\right)$ with equality if and only if $n-{x}_{i}$ is equal to 0 or 1. Thus

$\sum _{i=1}^{n}\left(n-{x}_{i}\right){}^{2}\ge \sum _{i=1}^{n}\left(n-{x}_{i}\right)\text{ }\left(2\right)$

with equality if and only if $n-{x}_{i}=0$ or 1 for each $i$. But (1) and (2) together imply that equality does occur for each $i$, whence ${x}_{i}$ is equal to either $n$ or $n-1$. The solution is completed as before.

57.
Let $\mathrm{ABCD}$ be a rectangle and let $E$ be a point in the diagonal $\mathrm{BD}$ with $\angle \mathrm{DAE}={15}^{ˆ}$. Let $F$ be a point in $\mathrm{AB}$ with $\mathrm{EF}\perp \mathrm{AB}$. It is known that $\mathrm{EF}=\frac{1}{2}\mathrm{AB}$ and $\mathrm{AD}=a$. Find the measure of the angle $\angle \mathrm{EAC}$ and the length of the segment $\mathrm{EC}$.
Solution. We begin with the observation that $\mathrm{tan}{15}^{ˆ}=2-\sqrt{3}$. (Exercise: Use either $\mathrm{tan}\theta =\left(\mathrm{sin}2\theta \right)/\left(1+\mathrm{cos}2\theta \right){}^{-1}$ or $\mathrm{tan}\theta =\mathrm{tan}\left(3\theta -2\theta \right)$ with $\theta ={15}^{ˆ}$.) Let $a$ and $b$ be the respective lengths of $\mathrm{AD}$ and $\mathrm{FE}$, so that $‖\mathrm{AF}‖=\left(2-\sqrt{3}\right)b$, $‖\mathrm{AB}‖=2b$ and $‖\mathrm{FB}‖=\sqrt{3}b$. Then $\mathrm{tan}\angle \mathrm{FEB}=\sqrt{3}$, so that $\angle \mathrm{FEB}=\angle \mathrm{ADB}={60}^{ˆ}$. Hence $‖\mathrm{BE}‖=2b$, $‖\mathrm{BD}‖=2a$ and $‖\mathrm{ED}‖=2\left(a-b\right)$. Since $a/2b=\mathrm{cot}\angle \mathrm{ADB}=1/\sqrt{3}$, $3{a}^{2}=4{b}^{2}$.
Since $\angle \mathrm{DAC}=\angle \mathrm{ADB}={60}^{ˆ}$ and $\angle \mathrm{DAE}={15}^{ˆ}$, it follows that $\angle \mathrm{EAC}={45}^{ˆ}$.
We can determine $‖\mathrm{EC}‖$ using the law of cosines in $\Delta \mathrm{DEC}$. Thus,

$\begin{array}{cc}‖\mathrm{EC}‖{}^{2}\hfill & =4{b}^{2}+4\left(a-b\right){}^{2}-8\left(a-b\right)b\sqrt{3}/2\hfill \\ \multicolumn{0}{c}{}& =8{b}^{2}-8\mathrm{ab}+4{a}^{2}-4\mathrm{ab}\sqrt{3}+4{b}^{2}\sqrt{3}\hfill \\ \multicolumn{0}{c}{}& =4{b}^{2}\left(2+\sqrt{3}\right)-4\mathrm{ab}\left(2+\sqrt{3}\right)+4{a}^{2}\hfill \\ \multicolumn{0}{c}{}& =3{a}^{2}\left(2+\sqrt{3}\right)-2{a}^{2}\sqrt{3}\left(2+\sqrt{3}\right)+4{a}^{2}\hfill \\ \multicolumn{0}{c}{}& ={a}^{2}\left(4-\sqrt{3}\right) ,\hfill \end{array}$

whence $‖\mathrm{EC}‖=a\sqrt{4-\sqrt{3}}$.
Comment. The length of $\mathrm{EC}$ can be found more straightforwardly by introducing an additional point. Produce the line $\mathrm{FE}$ to meet $\mathrm{CD}$ at $G$. Then $\mathrm{EGC}$ is a right triangle for which $‖\mathrm{EG}‖=a-b$ and $‖\mathrm{GC}‖=\sqrt{3}b$. Applying pythagoras theorem yields

$‖\mathrm{EC}‖{}^{2}={a}^{2}-2\mathrm{ab}+4{b}^{2}={a}^{2}-\sqrt{3}{a}^{2}+3{a}^{2}=\left(4-\sqrt{3}\right){a}^{2} .$

58.
Find integers $a$, $b$, $c$ such that $a\ne 0$ and the quadratic function $f\left(x\right)={\mathrm{ax}}^{2}+\mathrm{bx}+c$ satisfies

$f\left(f\left(1\right)\right)=f\left(f\left(2\right)\right)=f\left(f\left(3\right)\right) .$

Solution 1. Suppose that $f\left(p\right)=f\left(q\right)$ with $p\ne q$. Then $a\left({p}^{2}-{q}^{2}\right)+b\left(p-q\right)=0$, from which $p+q=-b/a$. It follows from this (Explain!) that $f\left(x\right)$ can take the same value at at most two distinct points. In particular, it is not possible that $f\left(1\right)=f\left(2\right)=f\left(3\right)$. Nor can $f\left(1\right)$, $f\left(2\right)$, $f\left(3\right)$ take three different values. Therefore, two of these take one value and the third a second value.
We make another preliminary observation. Suppose $f\left(p\right)=f\left(q\right)=u$, $f\left(r\right)=v$ and $f\left(u\right)=f\left(v\right)$, where $p$, $q$, $r$ are different, and also $u$ and $v$ are different. Then, from the first paragraph, we have that $p+q=u+v=-b/a$.
Suppose, now, that $\left(p,q,r\right)=\left(1,2,3\right)$ and that $f\left(1\right)=u$. Then

$\begin{array}{cc}a+b+c\hfill & =u\hfill \\ \multicolumn{0}{c}{4a+2b+c}& =u\hfill \\ \multicolumn{0}{c}{9a+3b+c}& =3-u\hfill \end{array}$

so that $2\left(5a+2b+c\right)=f\left(1\right)+f\left(3\right)=3$, which is not possible, since $a$, $b$ and $c$ are integers.
Suppose that $\left(p,q,r\right)=\left(2,3,1\right)$. Then we are led to $2\left(5a+2b+c\right)=5$, again an impossibility.
Suppose that $\left(p,q,r\right)=\left(1,3,2\right)$ and that $f\left(1\right)=u$. Then

$\begin{array}{cc}a+b+c\hfill & =u\hfill \\ \multicolumn{0}{c}{9a+3b+c}& =u\hfill \\ \multicolumn{0}{c}{4a+2b+c}& =4-u\hfill \end{array}$

so that $4a+b=0$ and $5a+b=2u-4$. This leads to the assignment

$\left(a,b,c\right)=\left(2u-4,-8u+16,7u-12\right)$

so that

$\begin{array}{cc}f\left(x\right)\hfill & =\left(2u-4\right)\left({x}^{2}-4x\right)+\left(7u-12\right)\hfill \\ \multicolumn{0}{c}{}& =\left(2u-4\right)\left(x-2\right){}^{2}-\left(u-4\right)\hfill \\ \multicolumn{0}{c}{}& =\left(2u-4\right)\left(x-1\right)\left(x-3\right)+u .\hfill \end{array}$

It can be checked that $f\left(u\right)$ and $f\left(4-u\right)$ are equal to $2{u}^{3}-12{u}^{2}+23u-12$.
We can get a particular example by taking $u=0$ to obtain the polynomial $f\left(x\right)=-4\left(x-1\right)\left(x-3\right)$, in which case $f\left(1\right)=f\left(3\right)=0$, $f\left(2\right)=4$ and $f\left(0\right)=f\left(4\right)=-12$.
Solution 2. Let $f\left(x\right)={\mathrm{ax}}^{2}+\mathrm{bx}+c$. Then $f\left(1\right)=a+b+c$, $f\left(2\right)=4a+2b+c$ and $f\left(3\right)=9a+3b+c$. Then

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

$\begin{array}{cc}f\left(f\left(3\right)\right)-f\left(f\left(1\right)\right)\hfill & =a\left[\left(9a+3b+c\right){}^{2}-\left(a+b+c\right){}^{2}\right]+b\left[\left(9a+3b+c\right)-\left(a+b+c\right)\right]\hfill \\ \multicolumn{0}{c}{}& =\left(8a+2b\right)\left[a\left(10a+4b+2c\right)+b\right]\hfill \\ \multicolumn{0}{c}{}& =2\left(4a+b\right)\left(10{a}^{2}+4\mathrm{ab}+2\mathrm{ac}+b\right)\hfill \end{array}$

Suppose that $f\left(f\left(1\right)\right)=f\left(f\left(2\right)\right)=f\left(f\left(3\right)\right)$. If $b=-3a$, then we must have $0=10{a}^{2}+4\mathrm{ab}+2\mathrm{ac}+b=10{a}^{2}-12{a}^{2}+2\mathrm{ac}-3a$, whence $c=a+\left(3/2\right)$. In this case, $a$ and $c$ cannot both be integers. However, if $b=-4a$, then $0=5{a}^{2}+3\mathrm{ab}+2\mathrm{ac}+b=5{a}^{2}-12{a}^{2}+2\mathrm{ac}-4a$, whence $c=\left(7a/2\right)+2$. So we can get integer coefficients by taking $\left(a,b,c\right)=\left(2t,-8t,7t+2\right)$ for some integer $t$.
Comment. To get a single solution quickly, just try to make $f\left(1\right)=f\left(3\right)=1$ and $f\left(2\right)=3$. This leads immediately to $f\left(x\right)=-\left(x-2\right){}^{2}+3=-2{x}^{2}+8x-5$.

59.
Let $\mathrm{ABCD}$ be a concyclic quadrilateral. Prove that

$‖\mathrm{AC}-\mathrm{BD}‖\le ‖\mathrm{AB}-\mathrm{CD}‖ .$

Solution 1. [O. Bormashenko, P. Cheng] Let the diagonals intersect in $M$ and assign the lengths: $\mathrm{AB}=a$, $\mathrm{BC}=b$, $\mathrm{CD}=c$, $\mathrm{DA}=d$, $\mathrm{AM}=r$. $\mathrm{BM}=p$, $\mathrm{CM}=s$, $\mathrm{DM}=q$. Since $\angle \mathrm{ABD}=\angle \mathrm{ACD}$ and $\angle \mathrm{BAC}=\angle \mathrm{BDC}$, triangles $\mathrm{MDC}$ and $\mathrm{MAB}$ are similar, so that, for some $k$, $q=\mathrm{kr}$, $s=\mathrm{kp}$, $c=\mathrm{ka}$. Wolog, we may assume that $k\ge 1$. Note that in triangle $\mathrm{MAB}$, we have that $p and $r, whence $-a or $‖p-r‖.

$\begin{array}{cc}‖\mathrm{AC}-\mathrm{BD}‖\hfill & =‖\left(r+s\right)-\left(p+q\right)‖=\left(k-1\right)‖p-r‖\hfill \\ \multicolumn{0}{c}{}& \le \left(k-1\right)a=‖c-a‖=‖\mathrm{AB}-\mathrm{CD}‖ .\hfill \end{array}$

Solution 2. Let the diagonals intersect in $M$ and assign the lengths: $\mathrm{AB}=a$, $\mathrm{BC}=b$, $\mathrm{CD}=c$, $\mathrm{DA}=d$, $\mathrm{AM}=r$. $\mathrm{BM}=p$, $\mathrm{CM}=s$, $\mathrm{DM}=q$. Let $\angle \mathrm{BAC}=\angle \mathrm{BDC}=\beta$, $\angle \mathrm{ABD}=\angle \mathrm{ACD}=\delta$ and $\angle \mathrm{AMB}=\angle \mathrm{DMC}=\phi$.
Applying the Law of Sines, we find that

$p=\frac{a\mathrm{sin}\beta }{\mathrm{sin}\phi } q=\frac{c\mathrm{sin}\delta }{\mathrm{sin}\phi }$

$r=\frac{a\mathrm{sin}\delta }{\mathrm{sin}\phi } s=\frac{c\mathrm{sin}\beta }{\mathrm{sin}\phi } .$

Hence

$p-r=\frac{a\left(\mathrm{sin}\beta -\mathrm{sin}\delta \right)}{\mathrm{sin}\phi } q-s=\frac{c\left(\mathrm{sin}\delta -\mathrm{sin}\beta \right)}{\mathrm{sin}\phi }$

whence

$\begin{array}{cc}\left(p+q\right)-\left(r+s\right)\hfill & =\frac{\left(a-c\right)\left(\mathrm{sin}\beta -\mathrm{sin}\delta \right)}{\mathrm{sin}\phi }\hfill \\ \multicolumn{0}{c}{}& =\frac{\left(a-c\right)2\mathrm{cos}\left(\left(\beta +\delta \right)/2\right)\mathrm{sin}\left(\left(\beta -\delta \right)/2\right)}{\mathrm{sin}\left(\beta +\delta \right)}\hfill \\ \multicolumn{0}{c}{}& =\frac{\left(a-c\right)\mathrm{sin}\left(\left(\beta -\delta \right)/2\right)}{\mathrm{sin}\left(\left(\beta +\delta \right)/2\right)} .\hfill \end{array}$

Since $\left(\beta +\delta \right)/2\le {90}^{ˆ}$, the absolute value of the sine in the numerator is less than the sine in the denominator, and so we find that

$‖\left(p+q\right)-\left(r+s\right)‖\le ‖a-c‖ ,$

as desired.
Solution 3. [R. Furmaniak] Let $O$ be the circumcentre of $\mathrm{ABCD}$ with $R$ the circumradius. Let $\angle \mathrm{AOB}=\alpha$, $\angle \mathrm{BOC}=\beta$, $\angle \mathrm{COD}=\gamma$ and $\angle \mathrm{DOA}=\delta$. Wolog, we can let $\delta$ be the largest of these angles.
We have that

$\mathrm{AB}=2R\mathrm{sin}\frac{\alpha }{2} \mathrm{CD}=2R\mathrm{sin}\frac{\gamma }{2}$

$\mathrm{AC}=2R\mathrm{sin}\frac{\alpha +\beta }{2} \mathrm{BD}=2R\mathrm{sin}\frac{\beta +\gamma }{2} .$

Thus

$\begin{array}{cc}\mathrm{AB}-\mathrm{CD}\hfill & =2R\left(\mathrm{sin}\frac{\alpha }{2}-\mathrm{sin}\frac{\gamma }{2}\right)\hfill \\ \multicolumn{0}{c}{}& =4R\mathrm{sin}\frac{\alpha -\gamma }{4}\mathrm{cos}\frac{\alpha +\gamma }{4}\hfill \end{array}$

and

$\mathrm{AC}-\mathrm{BD}=4R\mathrm{sin}\frac{\alpha -\gamma }{4}\mathrm{cos}\frac{\alpha +\gamma +2\beta }{4} .$

Since $\left(\alpha +2\beta +\gamma \right)/4$ and $\left(\alpha +\gamma \right)/4$ both do not exceed $\left(\alpha +\beta +\gamma +\delta \right)/4={90}^{ˆ}$, we have that

$\mathrm{cos}\frac{\alpha +\gamma +2\beta }{4}\le \mathrm{cos}\frac{\alpha +\gamma }{4} ,$

and this yields the desired result.

60.
Let $n\ge 2$ be an integer and $M=\left\{1,2,\dots ,n\right\}$. For every integer $k$ with $1\le k\le n$, let

${x}_{k}=\sum \left\{\mathrm{min} A+\mathrm{max} A:A\subseteq M,A \mathrm{has} k \mathrm{elements}\right\}$

where min $A$ is the smallest and max $A$ is the largest number in $A$. Determine $\sum _{k=1}^{n}\left(-1\right){}^{k-1}{x}_{k}$.
Solution 1. For any set $S=\left\{{a}_{1},{a}_{2},\dots ,{a}_{k}\right\}$ we define the related set $S\text{'}=\left\{\left(n+1\right)-{a}_{k},\left(n+1\right)-{a}_{k-1},\dots ,\left(n+1\right)-{a}_{1}\right\}$. As $S$ runs through all the subsets of $\left\{1,2,\dots ,n\right\}$ with $k$ elements, $S\text{'}$ also runs through the same class of subsets; the mapping $S\to S\text{'}$ is one-one. If, say, ${a}_{1}$ is the minimum element and ${a}_{k}$ the maximum element of $S$, then $\left(n+1\right)-{a}_{1}$ is the maximum and $\left(n+1\right)-{a}_{k}$ the minimum element of $S\text{'}$. Hence the sum of the minima and maxima of the two sets is

$\left({a}_{1}+{a}_{k}\right)+2\left(n+1\right)-{a}_{1}-{a}_{k}=2\left(n+1\right) .$

The sum of the maxima and minima of all the sets $S\cup S\text{'}$ is equal to $2{x}_{k}=2\left(n+1\right)\left(\genfrac{}{}{0}{}{n}{k}\right)$, so that ${x}_{k}=\left(n+1\right)\left(\genfrac{}{}{0}{}{n}{k}\right)$. Hence

$\sum _{k=1}^{n}\left(-1\right){}^{k-1}{x}_{k}=-\left(n+1\right)\sum _{k=1}^{n}\left(-1\right){}^{k}\left(\genfrac{}{}{0}{}{n}{k}\right)=-\left(n+1\right)\left[\left(1-1\right){}^{n}-1\right]=n+1 .$

Solution 2. [R. Furmaniak] For a given $k$ and $m$ with $1\le k,m\le n$, the number of $k-$subsets of $M$ with $m$ as the smallest element is $\left(\genfrac{}{}{0}{}{n-m}{k-1}\right)$, and the number of $k-$subsets of $M$ with $m$ as the largest element is $\left(\genfrac{}{}{0}{}{m-1}{k-1}\right)$, We use the convention that $\left(\genfrac{}{}{0}{}{0}{0}\right)=1$ and $\left(\genfrac{}{}{0}{}{x}{y}\right)=0$ when $x. >From this, we see that

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

Hence

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

Now, when $n-m\ge 1$,

$\sum _{k=1}^{n}\left(-1\right){}^{k-1}\left(\genfrac{}{}{0}{}{n-m}{k-1}\right)=\left(1-1\right){}^{n-m}=0$

and, when $m\ge 2$,

$\sum _{k=1}^{n}\left(-1\right){}^{k-1}\left(\genfrac{}{}{0}{}{m-1}{k-1}\right)=\left(1-1\right){}^{m-1}=0 .$

It follows that the required sum is equal to $n+1$.
Solution 3. [O. Bormashenko] Denote by $\sigma$ the quantity $\sum _{k=1}^{n}\left(-1\right){}^{k-1}{x}_{k}$. Let $m$ be a number between 1 and $n-1$, inclusive. $m$ is the minimum of a $k-$set for exactly $\left(\genfrac{}{}{0}{}{n-m}{k-1}\right)$ sets. For a particular $k$, $m$ as minimum contributes $n\left(\genfrac{}{}{0}{}{n-m}{k-1}\right)$ to the sum for ${x}_{k}$. Fixing $m$, $m$ as minimum contributes to $\sigma$ the value

$m\sum _{k=1}^{n}\left(-1\right){}^{k-1}\left(\genfrac{}{}{0}{}{n-m}{k-1}\right)=0 ,$

where $\left(\genfrac{}{}{0}{}{i}{j}\right)=0$ when $j>i$. The only other possible minimum is $n$, and this is a minimum only for the singelton $\left\{n\right\}$, so that $n$ as minimum contributes $n$ to the sum $\sigma$.
By a similar argument, for any number $m=2,3,\dots ,n$, $m$ as maximum contributes 0 to the sum $\sigma$. 1 is maximum only for the singleton $\left\{1\right\}$ and contributes the value 1 to the sum $\sigma$. Hence $\sigma =n+1$.
 top of page | contact us | privacy | site map |