7
$\begingroup$

At least how many different factors of $20!$ must we choose so that we can always find some subset whose product is a perfect cube? For example, if we choose $\{2,3,5,7,11,13,17,19,22,26,34,38\}$, then no subset has a product that is a perfect cube, so the answer must be more than $12$.

We can write $$20!=2^{18}\times 3^8\times 5^4\times 7^2\times 11\times 13\times 17\times 19$$ The total number of factors is $(18+1)(8+1)(4+1)(2+1)(1+1)^4=41040$, but I don't expect we need to use anything close to that.

$\endgroup$
  • $\begingroup$ Can you please provide an example to make your question more clear? $\endgroup$ – Qwerty Jul 7 '16 at 20:05
  • $\begingroup$ Hope it's clearer. $\endgroup$ – Karo Jul 7 '16 at 20:08
  • $\begingroup$ Find out the total number of primes $<41040$. The answer must be greater than that! $\endgroup$ – Qwerty Jul 7 '16 at 20:12
  • 1
    $\begingroup$ Interesting. One can get a bound of $3^8$, but the truth must be far smaller. $\endgroup$ – André Nicolas Jul 7 '16 at 20:49
  • 1
    $\begingroup$ @Qwerty The OP only considers factors of $20!$ Primes larger than $20$ do not occur. $\endgroup$ – Peter Jul 7 '16 at 22:35
2
$\begingroup$

Seventeen.

There are sixteen factors that are primes or $2^3$ multiplied by a prime, and no non-empty product of these numbers is a perfect cube.

In the other direction, given a sequence of $17$ factors of $20!,$ we can map each factor $x_i=2^{n_{i,1}}3^{n_{i,2}}5^{n_{i,3}}\cdots 19^{n_{i,8}}$ to the tuple $n_i=(n_{i,1},\dots,n_{i,8})$ in the group $G=(\mathbb Z/3\mathbb Z)^8.$ By Olson's theorem (J.E. Olson, "A combinatorial problem on finite abelian groups I–II" J. Number Th. , 1 (1969) pp. 8–10; 195–199) $G$ has Davenport constant 17, which means some non-empty subsequence has total zero. This corresponds to a non-empty product of the factors being a perfect cube.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.