Minimum number of terms on the board 
Suppose $1$ through $33$ is written on the board. Every move consists of replacing $x$ and $y$ with $\frac{y}{x}$ iff $x|y$. Find the minimum number of terms that can be on the board.

The numbers that can never be removed are primes >16.5 (17,19,23,29,31). I'm relatively new to these kinds of problems so I don't really know where to start. It seems that the only way of getting rid of multiple terms, $a_1,a_2, \cdots a_n$ is only if $\prod_{k=1}^{n-1} a_k=a_n$. Thanks!
 A: All together, the numbers $1$ through $33$ contain $31$ prime factors of $2$, $15$ factors of $3$, $7$ factors of $5$, $4$ factors of $7$, $3$ factors of $11$, $2$ of $13$, and $1$ each of $17,19,23,29$, and $31$.
Now, every time you replace $x$ and $y$ by $\frac{y}{x}$, you are eliminating an even number of instances of one or more prime factors. So, starting with an odd number of prime factors of $2$, for example, this means that we can't get rid of all prime factors $2$, i.e. we will be left with a $2$. 
So, it looks like the best you can do is to be left with a $2$, a $3$, a $5$, a $11$, and one of each of $17,19,23,29$, and $31$ (obviously, you can get rid of any $1$'s that appear).
But can you actually get to those very $9$ numbers when starting with the original numbers $1$ through $33$?  Yes, simply keep applying the process to the biggest pair of $x$ and $y$. That is, start with $33$ and $11$, then do $32$ and $16$, etc. Keep doing this, and you'll get there; this is easily enough verified yourself on a piece of paper.
However, we can do better than that: if we never touch the number $30$, then given that $30$ contains a single $2$, $3$, and $5$ as prime factors, we can actually get rid of all $2$'s, $3$'s, and $5$'s at the end. As such, we'd be left with: $11$, $17$, $19$, $23$, $29$, $30$, and $31$, i.e. $7$ numbers. 
As an alternative, we could have left $10$ (combing a $2$ and a $5$) and $33$, leaving us with $10$, $17$, $19$, $23$, $29$, $30$, and $33$. Another $7$-number solution is $15$, $17$, $19$, $22$, $23$, $29$, and $31$. But it is clear that you can't do better than any of these: $7$ is the minimum.
