MathDB

4

Part of 2013 Vietnam National Olympiad

Problems(1)

Count the number of number 2013

Source: VMO 2013

1/11/2013
Write down some numbers a1,a2,…,ana_1,a_2,\ldots, a_n from left to right on a line. Step 1, we write a1+a2a_1+a_2 between a1,a2a_1,a_2; a2+a3a_2+a_3 between a2,a3a_2,a_3, …, an−1+ana_{n-1}+a_n between an−1,ana_{n-1},a_n, and then we have new sequence b=(a1,a1+a2,a2,a2+a3,a3,…,an−1,an−1+an,an)b=(a_1, a_1+a_2,a_2,a_2+a_3,a_3, \ldots, a_{n-1}, a_{n-1}+a_n, a_n). Step 2, we do the same thing with sequence b to have the new sequence c again…. And so on. If we do 2013 steps, count the number of the number 2013 appear on the line if a) n=2n=2, a1=1,a2=1000a_1=1, a_2=1000 b) n=1000n=1000, ai=i,i=1,2…,1000a_i=i, i=1,2\ldots, 1000
Sorry for my bad English [color=#008000]Moderator says: alternate phrasing here: https://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=516134
inductioncombinatorics proposedcombinatorics