Kvant Math Problem 78
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m34s
Source on kvant.digital
Problem
Prove that every nonnegative integer can be represented in the form $$\frac{(x+y)^2+3x+y}{2},$$, where $x$ and $y$ are nonnegative integers, and that this representation is unique.
Exploration
Let
$$N=\frac{(x+y)^2+3x+y}{2}.$$
A natural first step is to introduce
$$s=x+y.$$
Then
$$N=\frac{s^2+3x+y}{2} =\frac{s^2+2x+s}{2} =\frac{s(s+1)}2+x.$$
This is a much simpler expression. Since $x\ge 0$ and $y\ge 0$, we have $0\le x\le s$. Thus every value represented by a fixed $s$ is
$$\frac{s(s+1)}2,, \frac{s(s+1)}2+1,, \dots,, \frac{s(s+1)}2+s.$$
For small values:
$$s=0:\quad 0,$$
$$s=1:\quad 1,2,$$
$$s=2:\quad 3,4,5,$$
$$s=3:\quad 6,7,8,9.$$
The intervals produced by consecutive values of $s$ are
$$\left[\frac{s(s+1)}2,\frac{s(s+1)}2+s\right] = \left[\frac{s(s+1)}2,\frac{(s+1)(s+2)}2-1\right].$$
The next interval begins at
$$\frac{(s+1)(s+2)}2,$$
exactly one more than the preceding interval's endpoint. Hence the intervals are consecutive and nonoverlapping. This suggests both existence and uniqueness.
The step most likely to hide an error is proving that these intervals cover all nonnegative integers without gaps and without overlaps. Once that is established, the result follows immediately.
Problem Understanding
We must prove that every nonnegative integer $N$ can be written in the form
$$N=\frac{(x+y)^2+3x+y}{2}$$
with $x,y\ge0$, and that the pair $(x,y)$ producing $N$ is unique.
This is a Type B problem, since the statement to be proved is given in advance.
The core difficulty is recognizing the correct change of variables. After setting $s=x+y$, the expression becomes
$$N=\frac{s(s+1)}2+x,$$
where $0\le x\le s$. The problem then becomes a partition of the nonnegative integers into consecutive intervals indexed by $s$.
Proof Architecture
The first lemma is that if $s=x+y$, then
$$\frac{(x+y)^2+3x+y}{2} = \frac{s(s+1)}2+x.$$
This follows by substituting $y=s-x$.
The second lemma is that for fixed $s\ge0$, the represented numbers are exactly the integers in the interval
$$\left[\frac{s(s+1)}2,\frac{s(s+1)}2+s\right].$$
This follows from the condition $0\le x\le s$.
The third lemma is that
$$\frac{s(s+1)}2+s = \frac{(s+1)(s+2)}2-1.$$
Hence the interval for $s$ ends exactly one less than the interval for $s+1$ begins.
The hardest direction is proving existence and uniqueness simultaneously by showing that these intervals form a partition of the set of nonnegative integers.
Solution
Set
$$s=x+y.$$
Since $y=s-x$,
$$\frac{(x+y)^2+3x+y}{2} = \frac{s^2+3x+s-x}{2} = \frac{s^2+s+2x}{2} = \frac{s(s+1)}2+x.$$
Thus every represented number has the form
$$N=\frac{s(s+1)}2+x,$$
where $s\ge0$ and
$$0\le x\le s,$$
because $x\ge0$ and $y=s-x\ge0$.
Fix $s$. As $x$ runs through the integers $0,1,\dots,s$, the values of $N$ are
$$\frac{s(s+1)}2, \frac{s(s+1)}2+1, \dots, \frac{s(s+1)}2+s.$$
Hence the numbers corresponding to this $s$ are exactly the integers in the interval
$$I_s= \left[ \frac{s(s+1)}2,, \frac{s(s+1)}2+s \right].$$
Now compute the right endpoint:
$$\frac{s(s+1)}2+s = \frac{s^2+3s}{2} = \frac{(s+1)(s+2)}2-1.$$
Therefore
$$I_s= \left[ \frac{s(s+1)}2,, \frac{(s+1)(s+2)}2-1 \right].$$
The next interval is
$$I_{s+1} = \left[ \frac{(s+1)(s+2)}2,, \frac{(s+2)(s+3)}2-1 \right].$$
Its left endpoint is exactly one greater than the right endpoint of $I_s$. Consequently the intervals $I_0,I_1,I_2,\dots$ are pairwise disjoint and consecutive.
Since
$$I_0=[0,0],$$
and each interval begins immediately after the preceding one ends, the union
$$I_0\cup I_1\cup I_2\cup\cdots$$
is the set of all nonnegative integers.
Hence every nonnegative integer $N$ belongs to exactly one interval $I_s$. For this unique $s$,
$$N=\frac{s(s+1)}2+x$$
with a unique integer
$$x=N-\frac{s(s+1)}2, \qquad 0\le x\le s.$$
Then
$$y=s-x\ge0,$$
and
$$N=\frac{(x+y)^2+3x+y}{2}.$$
Existence follows because every $N$ lies in some interval $I_s$. Uniqueness follows because the intervals are disjoint and, within a fixed interval, the value of $x$ is uniquely determined by
$$x=N-\frac{s(s+1)}2,$$
after which $y=s-x$ is also uniquely determined.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the transformation of the expression. Starting from
$$N=\frac{(x+y)^2+3x+y}{2},$$
putting $s=x+y$ gives
$$N=\frac{s^2+3x+(s-x)}2 =\frac{s^2+s+2x}{2} =\frac{s(s+1)}2+x.$$
A careless computation of $3x+y$ as $3x+s$ would produce an incorrect formula and destroy the argument.
The second delicate step is identifying the endpoint of the interval. One must verify
$$\frac{s(s+1)}2+s = \frac{s^2+3s}{2} = \frac{(s+1)(s+2)}2-1.$$
The subtraction of $1$ is essential. Without it, consecutive intervals would appear to overlap.
The third delicate step is uniqueness. From
$$N\in I_s,$$
the value of $x$ is forced to be
$$x=N-\frac{s(s+1)}2.$$
Since the intervals $I_s$ are disjoint, there is only one possible $s$. After $s$ and $x$ are fixed, the relation $y=s-x$ gives a unique $y$. No additional argument is needed.
Alternative Approaches
One may express the result in terms of triangular numbers. Let
$$T_s=\frac{s(s+1)}2.$$
The representation becomes
$$N=T_s+x, \qquad 0\le x\le s.$$
Every integer between $T_s$ and $T_{s+1}-1$ is obtained exactly once. Since
$$T_{s+1}-T_s=s+1,$$
these blocks have exactly the required lengths and fit together consecutively. This yields the same proof in the language of triangular numbers.
Another approach is to choose $s$ as the unique integer satisfying
$$T_s\le N<T_{s+1},$$
then define $x=N-T_s$ and $y=s-x$. This constructs the representation directly. The interval approach used above is preferable because existence and uniqueness emerge simultaneously from the partition of the nonnegative integers into the intervals $I_s$.