Effective methods for this qustion.

Question

In the beginning, the numbers $1, 2, 3, ..., 57$ were written on the board. In each process, the numbers a and b are selected and deleted from the board so that the number $a$ divides the number $b$ completely. The number $\frac{b}{a}$ is written instead of the deleted numbers (For example, in the first operation, the numbers $a = 3$ and $b = 9$ can be deleted and the number $\frac{9}{3} = 3$ can be written on the board again). At least how many numbers can be left on the board after a few actions?

It is clear that the remaining numbers are primes $29,31,37,41,43,47,53$. In each of my attempts, I find $2$ different numbers in addition to these prime. But I am waiting for your answers to see more different points of view.

Answer 1

(Fill in the gaps as needed. If you're stuck, show your work and explain what you've tried.)

Hint: Consider the prime factorization of $ 57! $.
Focus on those whose power is odd.
As you've realized, the primes $> 28$ must always occur. These have power of 1 in the prime factorization.

---

Claim: The product of the numbers that are left can be written in the form $ \frac{ \prod_{a \in A } a } { \prod_{b \not \in A } b } $, where $ A \subset [57]$.

Claim: If $p ^k \mid \mid 57$ and $k$ is odd, then we're always left with a term that is a multiple of $p$.

Corollary: The product of the numbers at the end is

$$ 2 \times 3 \times 5 \times 7 \times 11 \times 17 \times 19 \times 29 \times 31 \times 37 \times 41 \times 43 \times 47 \times 53.$$

Corollary: We must have at least $X$ numbers left behind. Recall that each of these numbers is less than 57.

$X = 11$

Corollary: The minimum left behind is $X$, and we need to find a contraction that yields $X$.

(Disclaimer: I've not done this yet.)

One possible set of numbers to be left is $ 7, 38, 55, 57, 29 , 31 ,37 , 41 , 43 , 47 , 53$. We do not use any of these in the steps, other than possibly 7.
However, thinking through it further, because "b/a is an integer" is a very strong condition, the invariant might be too weak. So, this part is worth thinking about.

Answer 2

You might try an approach like this in EXCEL because you don't have to worry about word-wrap, and you can see the entire string if the cells to the right are empty.

Beginning with $\{1,2,3,\cdots,57\}\\$

\begin{align*} Column_A\quad & Column_B\\ 19,57\rightarrow3\quad &\{1,2,3,3,4,5,6,7\cdots 56\}\\ 8,56\rightarrow7\quad &\{1,2,3,3,4,5,6,7,7\cdots 55\}\\ 11,55\rightarrow5\quad &\{1,2,3,3,4,5,5,6,7,7\cdots 54\}\\ 27,54\rightarrow2\quad &\{1,2,2,3,3,4,5,5,6,7,7,\cdots,26,28\cdots 53\}\\ \end{align*}

Now, perhaps it is time to cleanup such as

\begin{align*} 2,2\rightarrow1\quad &\{1,1,3,3,4,5,5,6,7,7,\cdots,26,28\cdots 53\}\\ 3,3\rightarrow1\quad &\{1,1,1,4,5,5,6,7,7,\cdots,26,28\cdots 53\}\\ 5,5\rightarrow1\quad &\{1,1,1,4,6,7,7,\cdots,26,28\cdots 53\}\\ 7,7\rightarrow1\quad &\{1,1,1,1,4,6,\cdots,26,28\cdots 53\}\\ 1,1\rightarrow1\quad &\{1,1,1,4,6,\cdots,26,28\cdots 53\}\\ 1,1\rightarrow1\quad &\{1,1,4,6,\cdots,26,28\cdots 53\}\\ 1,1\rightarrow1\quad &\{1,4,6,\cdots,26,28\cdots 53\}\\ 13,52\rightarrow4\quad &\{1,4,4,6,\cdots,12,14\cdots,26,28\cdots,51,53\}\\ \end{align*}

Number will be deleted, added, and deleted again from the list. For example, the interactions of $\quad11,55\quad 4,44 \quad 11,33 \quad 2,22\quad 11,11\quad$ will end up deleting $11$ from the list permanently. As an alternative to the above, you can, in one step, drop the numbers $\quad 11,22,33,44,55\quad$ from the list, knowing $11$ and multiples will all go. For other "factors" you will have to test them for having odd or even interactions as we did with $11x$.