2
$\begingroup$

I found this interesting problem in a Romanian mathematical magazine while preparing for the USAMO. Let $k$ be a non-zero natural number. Determine $x,y,z \in \Bbb N$ such that $$\binom {z+k}{x+y} - \binom {z}{x} \le k \space and \space 2x+y \le z.$$

$\endgroup$
  • 1
    $\begingroup$ If you consider 0 to be a natural number then (x,y,z) = (0,1,1) seems to be the only solution. I may be wrong! $\endgroup$ – Satish Ramanathan Jul 21 '16 at 13:10
  • $\begingroup$ @satishramanathan Can you repost your answer please? I didn't have enough time to read it carefully and it seemed an elegant solution. $\endgroup$ – I. Stefan Aug 3 '16 at 21:11
2
+50
$\begingroup$

I suspect you are looking for less of a brute force argument than those above.

Firstly, note that $(x,y,z)=(0,0,n)$ is a solution for $n \geq 0$ (for any appropriate convention for $0$ choose $0$), since the LHS of the first inequality is just $0$. Therefore, assume $x+y \geq 1$.

A useful identity is obtained as follows: consider partitioning a set of size $z+k$ into two subsets $A$ and $B$ of sizes $z$ and $k$ respectively. To choose $x+y$ objects from the $z+k$, we can independently choose $n$ objects from $A$ and $m$ objects from $B$ such that $n+m=x+y$, then sum over the possible values of $n$: $$\binom{z+k}{x+y}=\sum_{j=0}^N\binom{k}{j}\binom{z}{x+y-j},$$ where $N = \min\{x+y, k\}\geq 1$. Note that the second given inequality gives $z\geq x+y$ so these are the correct limits. Applying this inequality further, we obtain: $$\binom{z}{x}\leq \binom{z}{x+y}; \text{and}$$ $$\binom{z}{r}\geq \binom{2x+y}{r}.$$ Consequently, $$\binom{z+k}{x+y}-\binom{z}{x}\geq \sum_{j=1}^N\binom{k}{j}\binom{2x+y}{x+j}\geq k.$$ Therefore for the first given inequality to hold, we must have $N=1$ and $$\binom{2x+y}{x+1}=1;$$ that is, $x+1=2x+y$ and so $x+y=1$, which automatically ensures $N=1$ for every $k$.

It is then straightforward to check the two cases:

$x=1$, $y=0 \implies$ $$\binom{z+k}{x+y}-\binom{z}{x}=\binom{z+k}{1}-\binom{z}{1}=k.$$ $x=0$, $y=1 \implies$ $$\binom{z+k}{x+y}-\binom{z}{x}=\binom{z+k}{1}-\binom{z}{0}=z+k-1.$$ In summary the solutions are: $$\color{red}{(0,0,n); (1,0,n+2) \text{ and } (0,1,1) \text{ for } n\geq 0}$$ as seen in the other answers.

$\endgroup$
3
$\begingroup$

Let us separate it into cases :

Case 1 : $x,y,z\ge 1$.

Then, $z\ge 2x+y\ge 2\cdot 1+1=3$.

Now, let us prove by induction on $z$ that if $z\ge 3$, then

$$\binom{z+k}{x+y}-\binom zx\gt k\tag1$$ holds for all $x,y\ge 1$ such that $2x+y\le z$.

If $z=3$, then $(x,y)=(1,1)$, so $$\binom{z+k}{x+y}-\binom{z}{x}-k=\frac{(k+3)(k+2)}{2}-3-k=\frac{k(k+3)}{2}\gt 0$$

Here, assume that $(1)$ holds for $z$.

In the following, we use $$\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$$

For $x\ge 2$ and $2x+y\le z$, $$\begin{align}\binom{(z+1)+k}{x+y}-\binom{z+1}x&=\left(\binom{z+k}{x+y}+\binom{z+k}{x+y-1}\right)-\left(\binom{z}{x}+\binom{z}{x-1}\right)\\&=\left(\binom{z+k}{x+y}-\binom{z}{x}\right)+\left(\binom{z+k}{(x-1)+y}-\binom{z}{x-1}\right)\\&\gt k+k\\&\gt k\end{align}$$ where both $$\binom{z+k}{x+y}-\binom{z}{x}\gt k\quad\text{and}\quad \binom{z+k}{(x-1)+y}-\binom{z}{x-1}\gt k$$ come from the inductive assumption.

For $x=1$ and $2\cdot 1+y\le z$,

$$\begin{align}\binom{(z+1)+k}{x+y}-\binom{z+1}x&=\left(\binom{z+k}{1+y}+\binom{z+k}{y}\right)-\left(\binom z1+1\right)\\&=\left(\binom{z+k}{1+y}-\binom{z}{1}\right)+\left(\binom{z+k}{y}-1\right)\\&\gt k+0\\&= k\end{align}$$ where $$\binom{z+k}{1+y}-\binom{z}{1}\gt k$$ comes from the inductive assumption.

For $x=1$ and $2x+y=z+1$, $$\begin{align}\binom{(z+1)+k}{x+y}-\binom{z+1}x&=\left(\binom{z+k}{y+1}+\binom{z+k}{y}\right)-\left(\binom{z}{1}+1\right)\\&=\left(\binom{z+k}{1+(y-1)}-\binom{z}{1}\right)+\left(\binom{z+k}{y+1}-1\right)\\&\gt k+0\\&=k\end{align}$$ where $$\binom{z+k}{1+(y-1)}-\binom{z}{1}\gt k$$ comes from the inductive assumption.

For $2\le x\le\lfloor\frac{z+1}{2}\rfloor$ and $2x+y=z+1$, $$\begin{align}\binom{(z+1)+k}{x+y}-\binom{z+1}x&=\left(\binom{z+k}{x+y}+\binom{z+k}{x+y-1}\right)-\left(\binom{z}{x}+\binom{z}{x-1}\right)\\&=\left(\binom{z+k}{(x-1)+(y+1)}-\binom{z}{x-1}\right)+\left(\binom{z+k}{x+(y-1)}-\binom{z}{x}\right)\\&\gt k+k\\&\gt k\end{align}$$ where $$\binom{z+k}{x+(y-1)}-\binom{z}{x}\gt k$$ comes from the inductive assumption.

Hence, $$\binom{(z+1)+k}{x+y}-\binom{z+1}x\gt k$$ holds for all $x,y\ge 1$ such that $2x+y\le z+1$. $\quad\blacksquare$

Therefore, there are no solutions if $x,y,z\ge 1$.

Case 2 : $xyz=0$

Case 2-1 : $z=0$ leads that $x=y=0$.

Case 2-2 : $x=0$ $$\binom{z+k}{y}\le k+1$$ Here, let us prove by induction on $z$ that if $z\ge 2$, then $$\binom{z+k}{y}\gt k+1\tag2$$ holds for all $y\ge 2$ where $y\le z$.

For $z=2$, $y=2$, so $$\binom{z+k}{y}-(k+1)=\binom{2+k}{2}-(k+1)=\frac{(k+2)(k+1)}{2}-(k+1)=\frac{(k+1)k}{2}\gt 0$$

Here, assume that $(2)$ holds for $z$.

For $2\le y\le z$, $$\binom{(z+1)+k}{y}=\binom{z+k}{y}+\binom{z+k}{y-1}\gt (k+1)+1\gt k+1$$ where $$\binom{z+k}{y}\gt k+1$$ comes from the inductive assumption.

For $y=z+1$, $$\binom{(z+1)+k}{y}=\binom{z+k}{y}+\binom{z+k}{y-1}\gt 1+(k+1)\gt k+1$$ where $$\binom{z+k}{y-1}\gt k+1$$ comes from the inductive assumption.

Hence, $$\binom{(z+1)+k}{y}\gt k+1$$ holds for all $y\ge 2$ where $y\le z+1$. $\quad\blacksquare$

So, all we need to see is the cases where $0\le y\le 1$ or $0\le z\le 1$.

  • $y=0$ : $z$ can be any value.

  • $y=1$ : $z=0,1$.

  • $z=0$ : $y=0$.

  • $z=1$ : $y=0,1$.

Case 2-3 : $y=0$

$$\binom{z+k}{x}-\binom{z}{x}\le k$$

Here, let us prove by induction on $z$ that if $z\ge 4$, then $$\binom{z+k}{x}-\binom{z}{x}\gt k\tag3$$ holds for all $x\ge 2$ where $2x\le z$.

For $z=4$, $x=2$, so $$\binom{z+k}{x}-\binom{z}{x}-k=\binom{4+k}{2}-\binom{4}{2}-k=\frac{k(k+5)}{2}\gt 0$$

Here, assume that $(3)$ holds for $z$.

For $3\le x\le \frac z2$, $$\begin{align}\binom{(z+1)+k}{x}-\binom{z+1}{x}&=\left(\binom{z+k}{x}+\binom{z+k}{x-1}\right)-\left(\binom{z}{x}+\binom{z}{x-1}\right)\\&=\left(\binom{z+k}{x}-\binom{z}{x}\right)+\left(\binom{z+k}{x-1}-\binom{z}{x-1}\right)\\&\gt k+k\\&\gt k\end{align}$$ where both $$\binom{z+k}{x}-\binom{z}{x}\gt k\quad\text{and}\quad \binom{z+k}{x-1}-\binom{z}{x-1}\gt k$$ come from the inductive assumption.

For $x=2$, $$\begin{align}\binom{(z+1)+k}{x}-\binom{z+1}{x}&=\left(\binom{z+k}{2}+\binom{z+k}{1}\right)-\left(\binom{z}{2}+\binom{z}{1}\right)\\&=\left(\binom{z+k}{2}-\binom{z}{2}\right)+\left(z+k-z\right)\\&\gt k+k\\&\gt k\end{align}$$ where $$\binom{z+k}{2}-\binom{z}{2}\gt k$$ comes from the inductive assumption.

For $x=\lfloor\frac{z+1}{2}\rfloor$, $$\begin{align}\binom{(z+1)+k}{x}-\binom{z+1}{x}&=\left(\binom{z+k}{x}+\binom{z+k}{x-1}\right)-\left(\binom{z}{x}+\binom{z}{x-1}\right)\\&=\left(\binom{z+k}{x}-\binom{z}{x}\right)+\left(\binom{z+k}{x-1}-\binom{z}{x-1}\right)\\&\gt 0+k\\&=k\end{align}$$ where $$\binom{z+k}{x-1}-\binom{z}{x-1}\gt k$$ comes from the inductive assumption.

Hence, $$\binom{(z+1)+k}{x}-\binom{z+1}{x}\gt k$$ holds for all $x\ge 2$ where $2x\le z+1$. $\quad\blacksquare$

So, all we need to see is the cases where $0\le x\le 1$ or $0\le z\le 3$.

  • $x=0$ : $z$ can be any value.

  • $x=1$ : $z$ can be any value.

  • $z=0$ : $x=0$.

  • $z=1$ : $x=0$.

  • $z=2$ : $x=0,1$.

  • $z=3$ : $x=0,1$.

Therefore, the answer is $$\color{red}{\text{$(x,y,z)=(0,0,m),(1,0,n),(0,1,1)\ \ $ where $\ \ m\ge 0,n\ge 2\in\mathbb Z$}}$$

$\endgroup$
  • $\begingroup$ Thanks for you answer! Your solution is too hard for the magazine, I believe that there exists a simple one as the problem it is addressed to 10th graders. $\endgroup$ – I. Stefan Aug 3 '16 at 11:05
  • $\begingroup$ @I.Stefan: You are welcome. Well, yes, there might be a simple solution but I have not been able to find a simple one. By the way, I added some explanations. I hope that helps. $\endgroup$ – mathlove Aug 4 '16 at 6:49
0
$\begingroup$

I would appreciate if someone could poke hole in my argument. It is my humble try

Let $x+y = n$

Then through vandermonde's identity

$$ \sum_{l=0}^{n} {z\choose l}{k\choose(n-l)} - {z\choose{z-n}} \le k$$

If you expand this

$${z\choose0}{k\choose n} + {z\choose1}{k\choose {n-1}} +\cdots {z\choose n}{k\choose 0} - {z\choose n} $$

$${z\choose0}{k\choose n} + {z\choose1}{k\choose {n-1}} +\cdots {z\choose {n-1}}{k\choose 1} $$

But this expression is $\ge k$

For this to be $\le k$ only the last term should be considered which is

$${z\choose {n-1}}{k\choose 1} \le k =>n-1 = 0 and n = 1$$

$ x+y = 1$

Coming back to the original inequality

$${{z+k}\choose {x+y}} - {z\choose x}\le k\tag 1$$

If x = 0 and y = 1, inequality 1 reduces to

$ z+k-1\le k$ implies z = 1

if x = 1 and y = 0, inequality 1 reduces to

$z+k-z \le k$ along with $2x+y\le z$ implies $z \ge2$

Thus the solution is (0,1,1), (1,0,n+2) and ofcourse the trivial solution (0,0,n) for which the inequality is $0 \le k$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.