(Iranian Combinatorics Olympiad-2020) Consider the set of $100$ ordered pairs $A = \{(0, 0), (0, 1), \dots, (9, 8), (9, 9)\}$.
Given any subset $S$ of $A$, we have a device to append more elements to $S$. The device takes in two ordered pairs $(a, b)$ and $(c, d)$ from $S$, then appends the ordered pairs $(\min\{a, c\}, \min\{b, d\})$ and $(\max\{a, c\}, \max\{b, d\})$ to $S$.
From some initial $S$, your goal is to obtain $S=A$ using the device. Find the minimum size of $S$ for which this is possible.
I really don't have an idea on how to start. The shortest algorithm I found involved $18$ pairs in which we take pairs of form $(0,x)$ and $(y,0)$ where $x,y=1,2,\dots,9$. We can obtain $(x,y)$ from $(x,0)$ and $(y,0)$. But the answer is $10$ and I can't find a shorter algorithm to this.
We remark that the machine can not produce any new values in either coordinate, all it does is the creation of new pairings. Thus it can't be done with fewer than $10$.
To see that it can be done with $10$, note that it is easy to do it with the $19$ pairs $$\{(0,0), (1,0), \cdots, (9,0), (0,1), \cdots, (0,9)\}$$
so if you can generate that set, you are done. Now consider the $10$ pairs $$\{(0,9), (1,8), (2,7), (3,6), (4,5), (5,4), (6,3), (7,2), (8,1), (9,0)\}$$
We can get the pair $(0,k)$ by applying the machine to $(0,9)$ and $(9-k, k)$. Similarly we can get the pair $(k,0)$.
And we are done.