Find all integers

Question

How can I solve this problem of Chinese Girls math 2019?

Find integers $a_1,a_2,\cdots,a_{18}$, s.t. $a_1=1,a_2=2,a_{18}=2019$, and for all $3\le k\le 18$, there exists $1\le i<j<k$ with $a_k=a_i+a_j$.

Original Problem

Any brilliant ideas? I know the numbers are 1.2.3.5.8.13.21.34.55.89.144.233.267.500.508. 1008.1011.2019

Answer 1

Just for fun; There will be $$\prod_{i=4}^{17} (f_{k+1}-2)$$ number of possible $18$-tuples of integer satisfying above condition. where $f_{i}$ is $(i)th$ fibonacci number.

---

If you want to calculate:

Given : $a_1=1$ and $a_2=2$ So by the construction $a_k=a_i+a_j$ for $1 \leq i < j < k$

• The possibility for $a_3$ is 1 i.e., $a_3=a_1+a_2=2+1=3$

• Now we'll try to construct $a_4$ in all possible ways:

  $a_4=a_1+a_2=3$ or $a_4=a_1+a_3=4$ or $a_4=a_2+a_3=5$

  S0 possibility for $a_4$ are $3,4,5$

• Now let us try for $a_5$

  $a_5$ by above construction $a_5$ can have all numbers that $a_4$ have and in addition to it $a_5$ will also have $6,7,8$

• Similarly, $a_6$ :

  clearly $a_6$ will have all elements of $a_5$ and in addition to it, it will also have

  $z_6=\{a_5 -a_3\}+(greatest/last \;element \;of \;a_4)$

  so possibility for $a_6$ is $\{3,4,5,6,7,8,9,10,11,12,13\}$

Let's do one more for better understanding i.e. $a_7$

• $a_7$ will have all the elements of $a_6$ and in addition to it, it will also have

  $z_7=\{a_6 - a_4\}+(greatest/last \;element \;of \;a_5)$

---

Note at every step say $ith$ we are adding $f_{i-1}$ additional consecutive numbers to the set, where $f_{i-1}$ is $(i-1)th$ fibonacci number.

i.e., if we are to calculate the possibility set for $a_k$ then it will have numbers

$\{a_{k-1} \}$ $\cup$ {$f_{k-1}$ consecutive numbers after last element of $a_{k-1}$}

Let's see what we got:

$|a_4|=3=f_2+f_3$

$|a_5|=|a_4|+f_4=f_2+f_3+f_4$

.

.

$|a_k|=\sum_{i=2}^{k-1}f_{i}$

And we know that,

$$\sum_{i=1}^{n}f_{i}=f_{n+2}-1$$

So, $$\sum_{i=2}^{k-1}f_{i}=f_{k+1}-2$$ as $f_1=1$

Now if we seek to find to the total number of possible integers which satisfy the above condition.

$a_1,a_2,a_3,a_{18}$ are fixed and have only one possibility so we will focus on $4 \leq i \leq 17$

Now by simple combination rule, we will have

Total number of possible $18$-tuples $$= \prod_{i=1}^{18} |a_i|$$

Which is actually $$= \prod_{i=4}^{17} (f_{k+1}-2)$$