1
$\begingroup$

Author's note:I don't want the whole answer,but a guide as to how I should think about this problem.

BdMO 2010

In a set of $131$ natural numbers, no number has a prime factor greater than 42. Prove that it is possible to choose four numbers from this set such that their product is a perfect square.

The above question obviously has "PIGEONHOLE" written all over its face.However,finding the pigeons and holes is the hard part.The first thing to realize is that the number of primes is 13.We can write any number of our list using those primes.Now,since we only care about whether the exponents of the primes are even or odd,there are a total of $2^{13}$ types of integers.I have done a lot more computation but I am unable to see how this is leading us to pigeonholing(okay,I will admit that I should be a little more open-minded but I am certain that this uses pigeonholing).Also,the only way four integers can add up to an even number is if there are an even number of integers of the same parity.In that case,there are a total of $8$ cases for every quadruple of exponents(counting permutations).

A hint will be appreciated.Also,any mention of how you came up with your own solution will be very much appreciated.

EDIT: I have just found this

EDIT: I may have taken a step towards a solution.We can rewrite each of the integers as $x^2m$ where $m$ is squarefree.The number of possible $m$'s is $2^13$ .Now,if we show that there is another integer with the same $x$ part,and argue the same way with another pair of integers,and then multiply them together,our solution will be complete.However,I don't think that the claim is at all true.

$\endgroup$
  • $\begingroup$ I have just found this $\endgroup$ – rah4927 May 16 '14 at 15:56
  • $\begingroup$ @DanielFischer, indeed.Thanks for spotting the mistake. $\endgroup$ – rah4927 May 16 '14 at 15:57
  • $\begingroup$ I have come up with a different strategy(see my next-to-last comment).I am going to express each integer as $m^2x$ where $x$ is squarefree. $\endgroup$ – rah4927 May 16 '14 at 16:05
  • 1
    $\begingroup$ @rah4927 Hm... I first tried to see if I could do something with $\binom{131}{4}$, but that number was too big to be useful. I took my calculator and asked for $\binom{131}{2}$, to see if I could do something with pairs. The result was slightly bigger than our pigeonholes, so it got my interest. Mark Bennet's hint is pointing to exactly this :) $\endgroup$ – chubakueno May 16 '14 at 16:41
  • 1
    $\begingroup$ Actually, I have to fix my argument not to consier quadruplets of the type $xyyz$ . If I make it, I will post it. $\endgroup$ – chubakueno May 16 '14 at 17:06
3
$\begingroup$

There are $\binom{131}{2}=8515>2^{13}$ possible ways to choose a pair $(x,y)$. So we must have at least two different pairs $(x_1,y_1),(x_2,y_2)$ such that their squarefree product is equal. If those pairs do not share an element, we are done. If not, suppose that $x_1=x_2$. So $y_1y_2$ is a perfect square.

Remove $y_1y_2$ from the list. There are $\binom{129}{2}=8256>2^{13}$ possible ways to choose a pair $(w,z)$ now. In the same way, we have two different pairs $(w_1,z_1),(w_2,z_2)$ such that their squarefree product is equal. If those pairs do not share an element, we are done. If not, supposing that $w_1=w_2$, we now have that $z_1z_2$ is a perfect square.

So either $x_1y_1x_2y_2$ or $y_1y_2z_1z_2$ are perfect squares,

$\endgroup$
  • $\begingroup$ Ha!Nice!So we can't replace 131 with 129 after all. $\endgroup$ – rah4927 May 16 '14 at 17:38
  • $\begingroup$ @rah4927 I think so, I had to suck even the last possible unit from $131$:) But who knows, maybe a more sophisticated argument reduces the number of elements. Or we would have to come up with an example of $130$ elements such that no combination of $4$ multiplies to a perfect square... $\endgroup$ – chubakueno May 16 '14 at 17:58
  • $\begingroup$ You can simplify your argument, by simply finding 2 that are a perfect square, and then another 2 that are a perfect square. $\endgroup$ – Calvin Lin May 16 '14 at 22:18
  • $\begingroup$ @calvin But, what if we assign to the $13$ exponents of the $n$th element $n$ expressed as a 13-bit binary string? No product of two will be a square, or, I am missing something? $\endgroup$ – chubakueno May 16 '14 at 23:06
  • $\begingroup$ Ah, I stand corrected. Misunderstood what you were doing. $\endgroup$ – Calvin Lin May 17 '14 at 1:24
1
$\begingroup$

HINT - though I haven't followed through a solution ...

Finding four numbers all at once could be hard. Sometimes divide and conquer goes along with pigeonhole - using pigeonhole to find (disjoint) pairs which give the right parity on some fixed subset of the prime factors, and then using it again to find two pairs which match on the rest - but whether that works depends on whether you can find the right number of pairs for the second stage.

$\endgroup$
  • $\begingroup$ We define addition on binary strings as follows.If A and B are two binary strings of same length,then their sum is the new binary string created by adding the nth element of A to nth element of B i.e. 10011+01001=11010(for our purposes,1+1=0). Then the following statement holds:Given any 131 13-bit binary strings,we can always pick four such that their sum produces the string 0000000000000.How would we proceed to prove this statement?We could realize that this is the exact same problem as above,but it is often hard to reinterpret questions to make them more suitable. $\endgroup$ – rah4927 May 17 '14 at 12:22

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.