A computer program generated $175$ positive integers at random, none of which had a prime divisor grater than $10.$ Prove that there are three numbers among them whose product is the cube of an integer.
Problem
Source:
Tags: pigeonhole principle
02.12.2012 20:35
Basically we have 175 quadruples of nonnegative integers $\mod 3$, for a total of $3^4 = 81$ possibilities. Since $175 > 2\cdot 81$, we must have 3 equal quadruples, which correspond to the integers whose product is a cube.
03.12.2012 07:12
The best bound that can be obtained is 109. We can see that to be able to choose three integers whose sum is multiple of 3 out of given $n$ integers, it suffices to take 5 integers (n=5). Thus it is enough to obtain 5 nos. such that powers of three of the primes are same modulo 3 for all of them. For us to obtain such 5 nos., it is enough to take 3(5-1)+1 = 13 nos with 2 of the powers equal modulo 3. Continuing this argument, we require 3(13-1)+1 = 37 nos with one power equal and thus 3(37-1)+1 =109 nos in general. I think it should be easy to construct a counter example for 108 nos.
03.12.2012 11:19
I think 73 is enough, but I'm not sure that whether 73 is the best bound. We consider the case that there are only two prime divisors first, that is, 2 and 3 are the only prime divisors of all positive integers. We prove that for any 9 of these integers we can find three of them such that the product is a perfect cube. We can suppose that the power of each prime divisor in every integer is 0,1 or 2, so every integer belongs to the set{1,2,3,4,6,9,12,18,36}. If three integers are equal there is nothing to prove, so by the pigeonhole principle we get that at least 5 of there 9 numbers appear. WLOG suppose some integer is equal to 1, then make pairs of the left 8 integers as {2,4} {3,9} {6,36} {12,18}. In every pair, at most one integer can appear. So these integers contain exactly one integer in every pair, then WLOG we can suppose that 2 and 3 are among these integers. For 2*3*36=6^3, we get 6 is in, but 2*6*18=3*6*12=6^3 makes a contradiction! Then we consider the prime divisor 5 and 7, and get that 9*(9-1)+1=73 integers are enough. Maybe find the accuracy bound of this problem is a good job. Computer programms can give us a hand.
03.12.2012 17:43
Guys, see this-http://www.artofproblemsolving.com/Forum/viewtopic.php?f=151&t=509707. Paper leak again???
04.12.2012 05:36
any number must be of the form $2^a3^b5^c7^d$ with $a,b,c,d \ge0$ based on the value of the remainder the power of the primes give ,when divided by 3 , we have atmost 3x3x3x3=81 types of numbers. note that 175>81x2. so , there exists atleast 3 numbers of the same type. their product is trivially a cube.
04.12.2012 13:53
Edit: got it. P.S. cmtappu96 wrote: The best bound that can be obtained is 109. I think it should be easy to construct a counter example for 108 nos. I now think that 109 may not be the best bound.
04.12.2012 19:02
This problem has an equivalence to the card game SET with repeated cards. Three numbers whose product is a cube corresponds exactly to three cards forming a set. The most distinct SET cards you can have without a set is known to be 20. By repeating each number corresponding to those 20 cards twice, that gives a construction of 40 numbers where no perfect cube product can be made. On the other hand a 41 number set would result in a construction of 21 SET cards not forming a set, which is known to be impossible. So 41 is the best bound. Re above: you can suppose 1 is in the set. Multiply all the numbers by the same factor and the problem's conditions do not change. In your example $3 \cdot 6 \cdot 12$ is a cube.
04.12.2012 20:10
MellowMelon wrote: The most distinct SET cards you can have without a set is known to be 20 How?
04.12.2012 21:41
See pages 10-12 of this paper. It's fairly computational and not the kind of question you'd see on an olympiad.
23.11.2015 20:37
Let $N_i=2^{\alpha_i}3^{\beta_i}5^{\gamma_i}7^{\delta_i}$ where i runs from 1 to 175. Now each $\alpha_i, \beta_i, \gamma_i, \delta_i$ leaves a remainder of either 0, 1 or 2 when divided by 3. Now imagine $\alpha_i, \beta_i, \gamma_i, \delta_i$ as 4 spaces to filled by 0, 1, 2. This can be done in $3*3*3*3=81$ ways. So, we can have 81 different combinations of remainders for the powers, when divided by 3. But, we have 175 numbers. By PHP, we can always pick 3 numbers having $\alpha_i, \beta_i, \gamma_i, \delta_i$ leaving the same set of remainders. On multiplying these no.s we get a perfect cube as the powers of the primes in the resultant no. are divisible by 3.
23.11.2015 20:49
MellowMelon wrote: See pages 10-12 of this paper. It's fairly computational and not the kind of question you'd see on an olympiad. The link returns an error
23.11.2015 21:13
You're right. Here's one that works: http://homepages.warwick.ac.uk/staff/D.Maclagan/papers/set.pdf
13.08.2021 07:04
MellowMelon wrote: You're right. Here's one that works: http://homepages.warwick.ac.uk/staff/D.Maclagan/papers/set.pdf This doesn't work either