Consider an infinite array of integers. Assume that each integer is equal to the sum of the integers immediately above and immediately to the left. Assume that there exists a row $R_0$ such that all the number in the row are positive. Denote by $R_1$ the row below row $R_0$, by $R_2$ the row below row $R_1$, and so on. Show that for each positive integer $n$, row $R_n$ cannot contain more than $n$ zeros.
Problem
Source: MOP 2005 Homework - Blue Group #11
Tags: calculus, derivative, algebra, polynomial, combinatorics unsolved, combinatorics
19.05.2014 21:13
We call a maximal set of positive connected integers in the same row a positive zone. We call a maximal set of negative connected integers in the same row a negative zone. We shall say positive or negative zones are super zones. We call a maximal set of connected zeroes in the same row a zero zone. We shall prove $R_n$ always begins with a super zone via induction. It is clear $R_0$ begins with a super-zone. Now let us assume $R_n$ begins with a super zone. Then the numbers below the first super zone of $R_n$ have at most 1 zero, making $R_{n+1}$ begin with a super zone. The same idea can be used to prove $R_n$ ends in a super zone. The number of super zones $R_n$ has is equal to : (the number of pairs of consecutive integers $a,b$ where $a$ is to the left of $b$ and $a$ has the opposite sign of $b$, plus the number of consecutive pairs 0,b where b is different from 0 and is to the right of $0$) +1 . It is clear that the number above $b$ is not zero, so that number belongs to a superzone. We shall say that pair($a,b$ or $0,b$) is attributed to the superset of $R_{n-1}$ that contains the number above $b$. Therefore, for each superzone $T$ there are 4 options: T has 1 zero below it and 1 pair attributed to it. Call this an $A$ superzone (the number under the last number of the superset cannot be zero) T has no zero below it and 1 pair attributed to it. Call this an $B$ superzone T has 1 zero below it and no pair attributed to it. Call this an $C$ superzone(the number under the last number of the superset must be zero) T has no zero below it and no pair attributed to it. Call this an $D$ superzone Denote by $S_n$ the number of superzones of $R_n$, by $Z_n$, the number of zero zones of $R_n$ and by $O_n$ the number of zeroes in $R_n$ Suppose row $R_{n}$ has $a,b,c,d$ superzone of types $A,B,C,D$ respectively. Then $S_{n+1}=(a+b)+1=S_n-c-d+1$, $Z_{n+1}=a+c$. If $c=0$ then $O_{n+1}=a$, and if $c>0$ then $O_{n+1}\leq a+c+O_n-(Z_n-c)=a+2c+O_n-Z_n$. So when $c=0$ we have: $O_{n+1}-Z_{n+1}+S_{n+1}=(a)-(a)+(S_n-d+1)=S_n-d+1\leq S_n+1\leq (O_{n}-Z_{n})+S_{n}+1$ when $c>o$ we have: $O_{n+1}-Z_{n+1}+S_{n+1}\leq (a+2c+O_n-Z_n)-(a+c)+(S_n-c-d+1)=O_n-Z_n+S_n-d+1\leq O_n-Z_n+S_n+1$. Since we already know that $O_0-Z_0+S_0=1$ then we can know $O_n-Z_n+S_n\leq n+1$ which implies $O_n\leq n+1-(S_n-Z_n)$ but there are clearly more super zones than zero zones. This implies $O_n\leq n$ as desired.
28.06.2014 19:51
Is this connected to the derivative, 2nd derivative, etc. derivative of a polynomial?