Kvant Math Problem 325

Let $x_{n,m}$ be the entry in row $n$ and position $m$, where $0\le m\le n$.

kvantmathematicsolympiad

Verified: yes
Verdicts: PASS + PASS
Solve time: 14m26s
Source on kvant.digital

Problem

In a numerical triangle, the top number is 1, and the numbers at the ends of each row are also 1, while each of the other numbers is not less than the sum of the two numbers directly above it (in particular, the “Pascal triangle” shown in Fig. 2 satisfies this condition). Suppose a natural number $a$ greater than 1 occurs in this triangle $k$ times. Prove that $2^k\lt a^2$.

$\def.{{.}\hskip2.5pt{.}\hskip2.5pt{.}} \colsep{2pt}{\begin{array}{ccccccccccccc} &&&&&&1\ &&&&&1&&1\ &&&&1&&2&&1\ &&&1&&3&&3&&1\ &&1&&4&&6&&4&&1\ &1&&5&&10&&10&&5&&1\ 1&&6&&15&&20&&15&&6&&1\ .&.&.&.&.&.&.&.&.&.&.&.&.\ \end{array}}$

Fig. 2

Exploration

Let $x_{n,m}$ be the entry in row $n$ and position $m$, where $0\le m\le n$. The conditions are

$$x_{n,0}=x_{n,n}=1,$$

and

$$x_{n,m}\ge x_{n-1,m-1}+x_{n-1,m} \qquad (1\le m\le n-1).$$

The first step is to compare the triangle with Pascal's triangle. The Pascal coefficients satisfy the same recurrence with equality, so induction gives

$$x_{n,m}\ge \binom{n}{m} \qquad\text{for all }n,m.$$

Hence every occurrence of the number $a$ can only appear at a position where

$$\binom{n}{m}\le a.$$

The second step is to locate such positions. If

$$d=\min(m,n-m),$$

then $d\le n/2$, and

$$\binom{n}{m}\ge \binom{2d}{d}.$$

Since

$$\binom{2d}{d} =\prod_{i=1}^{d}\frac{d+i}{i}\ge 2^d,$$

every occurrence of $a$ must satisfy

$$2^d\le a.$$

Thus

$$d\le \lfloor\log_2 a\rfloor.$$

The final step is to count how many occurrences can lie on those boundary diagonals. Unlike the flawed argument, this count must be made in the given triangle itself.

Problem Understanding

A numerical triangle is given whose entries dominate the Pascal recurrence. A natural number $a>1$ appears $k$ times. The task is to prove

$$2^k<a^2.$$

The key facts are that every entry is at least the corresponding binomial coefficient, and that along each fixed boundary diagonal the entries of the given triangle are strictly increasing.

Proof Architecture

First, prove

$$x_{n,m}\ge \binom{n}{m}.$$

Next, show that if $x_{n,m}=a$, then the distance

$$d=\min(m,n-m)$$

from the nearest side of the triangle satisfies

$$d\le \lfloor\log_2 a\rfloor.$$

Then prove that along every fixed diagonal $m=r$ the sequence $x_{n,r}$ is strictly increasing in $n$, and similarly along every fixed diagonal $n-m=r$.

Hence each such diagonal contains the value $a$ at most once.

Counting the admissible diagonals yields the desired bound for $k$.

Solution

For every entry,

$$x_{n,m}\ge \binom{n}{m}.$$

This is proved by induction on $n$. The statement is true for the boundary entries. Assuming it for row $n-1$,

$$x_{n,m} \ge x_{n-1,m-1}+x_{n-1,m} \ge \binom{n-1}{m-1}+\binom{n-1}{m} =\binom{n}{m}.$$

Now suppose that

$$x_{n,m}=a.$$

Then

$$\binom{n}{m}\le a.$$

Let

$$d=\min(m,n-m).$$

By symmetry of binomial coefficients,

$$\binom{n}{m}=\binom{n}{d}.$$

Since $n\ge 2d$, the function $\binom{n}{d}$ is increasing in $n$, so

$$\binom{n}{m}\ge \binom{2d}{d}.$$

Also,

$$\binom{2d}{d} =\prod_{i=1}^{d}\frac{d+i}{i},$$

and each factor is at least $2$. Therefore

$$\binom{2d}{d}\ge 2^d.$$

Combining these inequalities gives

$$2^d\le a,$$

hence

$$d\le L:=\lfloor\log_2 a\rfloor.$$

Thus every occurrence of $a$ lies on one of the boundary diagonals

$$m=r \quad\text{or}\quad n-m=r, \qquad 1\le r\le L.$$

The crucial point is that the entries of the given triangle are strictly increasing along each such diagonal. For fixed $r\ge1$,

$$x_{n,r} \ge x_{n-1,r-1}+x_{n-1,r}.$$

Since all entries are positive integers,

$$x_{n-1,r-1}\ge1,$$

so

$$x_{n,r}>x_{n-1,r}.$$

Hence the sequence

$$x_{r,r},,x_{r+1,r},,x_{r+2,r},\dots$$

is strictly increasing. Consequently the value $a$ can occur on the diagonal $m=r$ at most once.

Applying the same argument to the reflected diagonal $n-m=r$ shows that $a$ can occur there at most once as well.

Therefore

$$k\le 2L.$$

If $a$ is not a power of $2$, then

$$L<\log_2 a,$$

and hence

$$k\le 2L<2\log_2 a.$$

Exponentiating,

$$2^k<a^2.$$

It remains to consider $a=2^t$.

When $t\ge2$,

$$\binom{2t}{t}>2^t=a,$$

because already

$$\binom{4}{2}=6>4,$$

and every factor in

$$\binom{2t}{t} =\prod_{i=1}^{t}\frac{t+i}{i}$$

is at least $2$, with the last factor equal to $2$ and at least one earlier factor strictly larger than $2$.

Thus no occurrence of $a$ can have distance $d=t$. Every occurrence satisfies

$$d\le t-1,$$

so only the diagonals

$$r=1,\dots,t-1$$

are possible. Hence

$$k\le 2(t-1),$$

and therefore

$$2^k\le 2^{,2t-2}<2^{,2t}=a^2.$$

For $t=1$, we have $a=2$. The only admissible diagonal is $r=1$. The two boundary diagonals coincide at the single position $(2,1)$, so $k\le1$. Therefore

$$2^k\le2<4=a^2.$$

All cases give

$$2^k<a^2.$$

$$\boxed{2^k<a^2}$$

Verification of Key Steps

The comparison

$$x_{n,m}\ge\binom{n}{m}$$

follows directly from induction and Pascal's identity.

The restriction

$$d\le\lfloor\log_2 a\rfloor$$

comes from

$$\binom{n}{m}\ge\binom{2d}{d}\ge2^d.$$

The counting argument uses the actual triangle, not Pascal's triangle. Along every fixed boundary diagonal,

$$x_{n,r}>x_{n-1,r},$$

so a given value can occur there at most once. This is the property needed to bound the total number of occurrences.