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

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .