A maximum number of numbers which can be chosen from the set $\{1, 2, ..., 12\}$

Question

How can I find the maximum amount of numbers which can be chosen from the set $\{ 1, 2, ..., 12 \}$ so that the product of any three numbers is not equal to a cube of a natural number?

Answer 1

If we compute integer decomposition of numbers $\{1,\dots,12\}$: $$\{12 = 2 \times 2 \times 3,11,10 = 2 \times 5,9 = 3 \times 3,8 = 2 \times 2 \times 2,7,6 = 2 \times 3,5,4 = 2 \times 2,3,2,1\}$$ Numbers whose decomposition has at least one number which does not appears three times or more in all decompositions, can be directly added. Those numbers are 11,10,7 and 5, which can be added without "risk". Numbers which remain are:

$\{12 = 2 \times 2 \times 3,9 = 3 \times 3,8 = 2 \times 2 \times 2,6 = 2 \times 3,4 = 2 \times 2,3,2,1\}$

If we take three of these numbers, there are only six combinations which lead to cubic numbers. Those combinations are $\{1,2,4\}, \{4,6,9\}, \{2,4,8\},\{3,6,12\},\{3,8,9\}$ and $\{1,3,9\}$. You can easily check that removing 3 and 4 this combinations can not be built. So, you can conclude that the maximum number that you can take is 10, being $\{1,2,5,6,7,8,9,10,11,12\}$

Edit: 1 should not be taken in the first round, because it appears in all decompositions.

Answer 2

Bit of brute force: Observe we can easily add $1,8$ and all the primes to get $\{1,2,3,5,7,8,11\}$. Further by inspection we may add $6,10, 12$ too. So we have a set with $10$ elements possible.

Combinations of the primes $2,3$ are troublesome, note we cannot have all three among $1,2,4$ or $1,3,9$ or $4,6,9$ or $2, 9,12$ so at least $2$ numbers have to be always set aside, so $10$ is maximal.