9
$\begingroup$

Given a set $M$ of $1985$ distinct positive integers, none of which has a prime divisor greater than $26$, prove that $M$ contains at least one subset of four distinct elements, whose product is the fourth power of an integer.

I couldn't even start.

$\endgroup$
  • $\begingroup$ Shooting in dark: I would start from counting prime numbers less than $26$ and considering their possible configurations among $1985$ members of $M$. $\endgroup$ – CiaPan Jul 15 '15 at 13:20
  • $\begingroup$ Please feel free to ask any questions. $\endgroup$ – Jorge Fernández Hidalgo Jul 15 '15 at 13:26
  • $\begingroup$ The solution is widely available on the web. However, I like the answer given by dREaM, though it is on similar lines, but more intuitively explained. See cs.cornell.edu/~asdas/imo/imo/isoln/isoln854.html $\endgroup$ – Shailesh Jul 15 '15 at 13:31
5
$\begingroup$

It could be interesting to show the more general case, that is, if we know the prime divisors of all elements in $M$ are amongst $p_{1}, p_{2}, ..., p_{n}$, and $M$ has at least $2^{n} \cdot 3 + 1$ elements, then it contains at least one subset of four distinct elements whose product is a fourth power.

The trick is to assign each element $m$ in $M$ with an $n$-tuple $(x_{1}, x_{2}, ..., x_{n})$, where $x_{i}$ is an indicator variable equal to $0$ if the exponent of $p_{i}$ in $m$'s prime factorization is even, and $1$ otherwise.

As my teacher explained this problem, these tuples become our objects with which to consider the pigeonhole principle, and our boxes are the possible choices of $0$'s and $1$'s for each indicator. Then by the pigeonhole principle, we have that every subset of our $2^{n}+1$ elements of $M$ contains two (distinct) elements with the same object, or $n$-tuple, and consequently the product of these two elements is a square.

Our process consists of repeatedly removing these pairs, and replacing them with two of our remaining possible numbers. Since $M$ has at least $2^{n}\cdot 3 + 1$ elements, we can select at least $2^{n}+1$ pairs.

Now we must consider the $2^{n}+1$ numbers that are products of the two elements of each pair. We can repeat the same argument as above once again, to have four elements $a,b,c,d$ in $M$ where $\sqrt{ab}\sqrt{cd}$ is a perfect square. Then $abcd$ is a fourth power, and our result has been shown.

In your case, we have that $n=9$, as $1985 > 3 \cdot 2^{9} + 1 = 1537$.

$\endgroup$
  • $\begingroup$ I can't get something: Once you've found the first pair, say $(a,b)$, isn't it enough to remove that pair and find another one $(c,d)$? the product $abcd$ is a fourth power, isn't it? $\endgroup$ – Daniel Jul 15 '15 at 13:35
  • 1
    $\begingroup$ the product of two arbitrary squares is not a fourth power. For example $4\cdot9$ is not a fourth power. $\endgroup$ – Jorge Fernández Hidalgo Jul 15 '15 at 13:36
  • 1
    $\begingroup$ Got it! No, what I've argued is not true. $\endgroup$ – Daniel Jul 15 '15 at 13:36
5
$\begingroup$

There are $9$ primes less than $26$.

You can look at each integer $n$ as a binary $9$-tuple that gives you the value of each $\alpha_i$ $\bmod 2$ when writing $n$ as $2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}7^{\alpha_4}11^{\alpha_5}13^{\alpha_6}17^{\alpha_7}19^{\alpha_8}23^{\alpha_9}$.

Hence we have $1985$ such lists. We shall prove there are two of these lists so that when we add them all nine terms are multiples of $2$. This is clear, since $1985>512=2^9$ which is the total number of possible lists ther must be two that are equal. So we take those two equal lists, they represent numbers $a$ and $b$. We delete numbers $a$ and $b$ from the list and we place their product $ab$ in a separate list. We continue to do this until we have $511$ numbers in the first list.

When we finish doing this the new list will have $(1985-511)/2=737$ numbers. So we will have in the new list $737$ squares. All these numbers are of the $2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}7^{\alpha_4}11^{\alpha_5}13^{\alpha_6}17^{\alpha_7}19^{\alpha_8}23^{\alpha_9}$. And each $\alpha_i$ is even. Convert each of these numbers into a binary $9$-tuple where term $i$ is the congruence $\bmod 4$ of $\alpha_i$.

Since $737>512=2^9$ there are two numbers that give the same list. The product of these two numbers is therefore a fourth power This proof works for as little as $1537$ numbers, but the problem statement say $1985$ because this is problem $4$ (second easiest) of the imo $1985$

$\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.