There are $n$ positive integers on the board. We can add only positive integers $c=\frac{a+b}{a-b}$, where $a$ and $b$ are numbers already writted on the board. $a)$ Find minimal value of $n$, such that with adding numbers with described method, we can get any positive integer number written on the board $b)$ For such $n$, find numbers written on the board at the beginning
Problem
Source: Regional Olympiad - Federation of Bosnia and Herzegovina 2009
Tags: board, Minimal, combinatorics
30.09.2018 00:18
We say that a generator of $ \mathbb{N}^* $ is a set that spans $ \mathbb{N}^* $ under the operation defined in the statement. What the first subpoint asks is equivalent with asking what is the cardinal of a minimal generator of $ \mathbb{N}^*. $ Let $ M $ be a minimal generator of $ \mathbb{N}^*. $ Clearly, $ 1\in M. $ Otherwise, it would be generated by another two numbers $ a,b\in\mathbb{N}^*\setminus\{ 1\} , $ i.e, $ 1=\frac{a+b}{a-b} , $ which implies $ b\not\in\mathbb{N}^*\setminus\{ 1\} , $ false. Now, there must be another element besides $ 1 $ in $ M, $ because iterative operations cannot happen (due to division by zero). Let that element be $ 2. $ We prove that $ M=\{ 1,2\} $ is a generator of $ \mathbb{N}^*. $ Let $ k\in\mathbb{N}^*\setminus\{ 1\}. $ If it´s odd, we can see that $ k $ is generated by any $ a=l \cdot\left( \frac{k-1}{2}\right) $ and $ b=l\cdot\left( \frac{k+1}{2}\right) , $ i.e., $ k=\frac{a+b}{a-b} $ (verify!), where $ l\in\mathbb{N}^*. $ So, $ 3 $ is obtained with $ a+1=b=2, $ and $ 5 $ with $ a+1=b=3. $ If $ k $ is even, $ k $ can be generated by any $ a=l\cdot\left( k-1\right) $ and $ =l\cdot\left( k+1\right) . $ So, $ 4 $ is obtained with $ a+2=b=5. $ Continuing this algorithm we span all naturals with $ M $ in the order $ 1,2,3,5,4,7,6,9,8,11,10, $ etc. The answer to a) is $ 2. $ For b), we recall that $ 1 $ must be one of the two initial numbers written (see above for argumentation). This, along with the second initial number, say $ n, $ clearly must create a natural number (otherwise it couldn't produce $ \mathbb{N}^* $). That means $ \mathbb{N^*}\ni\frac{n+1}{n-1}=1+\frac{2}{n-1} , $ which occurs only for $ n\in\{ 2,3\} . $ For $ n=2, $ we already showed that the generator works. For $ n=3, $ the first operation gives $ 2, $ and now continue in the same manner as for $ n=2. $ The final answer is $ 1,2 $ and $ 1,3. $