Let $ n$ be a natural number, and we consider the sequence $ a_1, a_2 \ldots , a_{2n}$ where $ a_i \in (-1,0,1)$ If we make the sum of consecutive members of the sequence, starting from one with an odd index and finishing in one with and even index, the result is $ \le 2$ and $ \ge -2$ How many sequence are there satisfying this conditions?
Problem
Source: Argentina IMO TST 2006 problem 6
Tags: absolute value, combinatorics unsolved, combinatorics
Albanian Eagle
30.08.2009 07:35
I didn't have time to make all the calculations but here's some thoughts: Since I couldn't find any nice combinatorial argument I thought of a "brute force approach". We see that each pair has a sum in $ S=\{-2,-1,0,1,2\}$ but we have three types of $ 0$, two types of $ \pm 1$ and one type of $ \pm 2$. Let $ F(n)$ be the number of sequences we are looking at. Let $ f(n)$ denote the number of sequences of length $ n$ with entries in $ S'=S/\{0\}$ (taking different types into account) so that all consecutive sums have absolute value $ \le 2$, so that we have \[ F(n)=\sum_{k=0}^n3^{n-k}f(k)\binom{n}{k}\] Now let $ g(n),h(n),g'(n),h'(n)$ be respectively the number of sequences of length $ n$ with entries in $ S'$ so that the absolute value of the sum of consecutive terms doesn't exceed 2 and so that the sums of the first $ r$ terms ($ 1\le r \le n$) lies in $ \{-2,-1,0\},\{0,1,2\},\{-2,-1,0,1\},\{-1,0,1,2\}$ respectively. Then we have \[ f(n)=g(n-1)+h(n-1)+2g'(n-1)+2h'(n-1)\] \[ g(n)=h(n-1)+2g'(n-1),h(n)=g(n-1)+2h'(n-1)\] \[ g'(n)=2g(n-1)+2h'(n-1)+h(n-1),h'(n)=2h(n-1)+2g'(n-1)+g(n-1)\] If we let $ a(n)=g(n)+h(n)$ and $ b(n)=g'(n)+h'(n)$ we have \[ f(n)=a(n-1)+2b(n-1)\] \[ a(n)=a(n-1)+2b(n-1)\qquad ,\qquad b(n)=3a(n-1)+2b(n-1)\] Now everything can be computed recursively and with some algebra we should be able to get the answer.