Let $n$ be a positive integer. Consider sequences $a_0, a_1, ..., a_k$ and $b_0, b_1,,..,b_k$ such that $a_0 = b_0 = 1$ and $a_k = b_k = n$ and such that for all $i$ such that $1 \le i \le k $, we have that $(a_i, b_i)$ is either equal to $(1 + a_{i-1}, b_{i-1})$ or $(a_{i-1}; 1 + b_{i-1})$. Consider for $1 \le i \le k$ the number $c_i = \begin{cases} a_i \,\,\, if \,\,\, a_i = a_{i-1} \\ b_i \,\,\, if \,\,\, b_i = b_{i-1}\end{cases}$ Show that $c_1 + c_2 + ... + c_k = n^2 - 1$.
Problem
Source: Dutch IMO TST 2015 day 1 p3
Tags: algebra, Sequence, Sum
Mathasocean
16.03.2020 18:27
I think there is a mistake in problem should such: c1+c2+...+ck =n^2-1.am I true?
parmenides51
16.03.2020 18:36
Mathasocean wrote: I think there is a mistake in problem should such: c1+c2+...+ck =n^2-1.am I true? yes there was a typo, in the official english translation, just corrected it
Supercali
16.03.2020 18:42
Visualize the dual sequence as a path of lattice points. Realize that $c_1+\cdots+c_k$ is just some fixed area.
cazanova19921
16.05.2020 13:42
By the definition of $(a_i, b_i)_{i=0}^k$, there exists $(e_1, ..., e_k) \in \{0, 1 \}^k$ such that $\begin{cases} a_i = e_i+a_{i-1} &\mbox{ for all } 1 \leq i \leq k \\ b_i = 1-e_i+b_{i-1} &\mbox{ for all } 1 \leq i \leq k \end{cases}$ Let $S_i = \sum_{j=1}^{i}e_j$ for all $1 \leq i \leq k $. Then we have $\begin{cases} a_i = S_i+1 &\mbox{ for all } 1 \leq i \leq k \\ b_i = i+1-S_i &\mbox{ for all } 1 \leq i \leq k \end{cases}$ In paricular, $S_k=a_k-1=n-1$ and $S_k=k+1-b_k=k-(n-1)$. So $k=2(n-1)$. By definition of the sequence $(c_i)_{i=1}^k$, we have $c_i=e_ib_i+(1-e_i)a_i=(i+1)e_i-e_iS_i+1-e_i+S_i-e_iS_i=ie_i+S_i-2e_iS_i+1$ for all $1 \leq i \leq k$. Therefore $\sum_{i=1}^{k}c_i=\sum_{i=1}^{k}ie_i+\sum_{i=1}^{k}S_i-2\sum_{i=1}^{k}e_iS_i+k$. Now, $\sum_{i=1}^{k}ie_i+\sum_{i=1}^{k}S_i=\sum_{i=1}^{k}ie_i+\sum_{i=1}^{k}(k+1-i)e_i=(k+1)S_k$ and $2\sum_{i=1}^{k}e_iS_i=(\sum_{i=1}^ke_i)^2+\sum_{i=1}^{k}e_i=S_k^2+S_k$ So $\sum_{i=1}^{k}c_i=(k+1)S_k-S_k-S_k^2+k=n^2-1$.