6
$\begingroup$

The set $M$ consists of 2001 distinct positive integers, none of which is divisible by any prime $p > 23$. Prove that there are distinct $x, y, z, t \in M$ such that $xyzt = u^4$ for some integer $u$.

I guess some kinda Pigeonhole Principle argument should be useful, but I can't figure it out.

$\endgroup$
7
  • 1
    $\begingroup$ Have you at least counted the primes below $23$? How many are available as factors of the numbers in $M$? Then what you want are the exponents of those primes $\bmod 4$ $\endgroup$ May 25, 2017 at 20:27
  • $\begingroup$ Yup. Done that. 9 primes. So, we are given 2001 $9$-tuples with elements from $\mathbb{Z}_4$. Don't know how to proceed. $\endgroup$
    – MathManiac
    May 25, 2017 at 20:32
  • $\begingroup$ If $u^4=29^4$ then I don't see any way that it can be product of $xyzt$, none of which has 29 as a divisor. $\endgroup$
    – Χpẘ
    May 25, 2017 at 20:36
  • $\begingroup$ @Χpẘ For some $u$. $u$ doesn't have to be $29$. $\endgroup$ May 25, 2017 at 20:36
  • $\begingroup$ I thought it meant for a given $u$, but it should be $\exists u$? $\endgroup$
    – Χpẘ
    May 25, 2017 at 20:39

2 Answers 2

5
+50
$\begingroup$

Just think of even/odd.

There are 512 classes of integers, depending on the parities of the nine exponents. So two must belong to the same class. Pair them off, you have 1999 numbers left.
Another two belong to the same class as each other because 1999>512. And so on until only 511 numbers are left.

You now have $(2001-511)/2$ pairs of numbers, the product of each pair is a square.

Now, how to show that two of the pairs have a product which is a fourth power...

$\endgroup$
2
  • 2
    $\begingroup$ We can mimic the argument here onwards. We have 745 pairs where product of each pair is a square, and so the exponent of any prime modulo 4 is either 0 or 2 for the product. Again, we have 512 classes in which each product pair can lie, and so, 2 lie in the same. Does this sound good? $\endgroup$
    – MathManiac
    Jun 12, 2017 at 7:49
  • 1
    $\begingroup$ This is actually IMO 1985/4. We only need 1537 numbers. $\endgroup$
    – Calvin Lin
    Jun 15, 2017 at 23:55
0
$\begingroup$

Not an answer, but an approach that I believe will work. As you say in the comments, each of the numbers in $M$ corresponds to a nine position vector with each position being the powers of $2,3,5,\ldots 23$ in the factorization of the number reduced $\bmod 4$. We are looking for four vectors that sum to the zero vector when each entry is reduced $\bmod 4$.

Let us concentrate on the first position in the vector. There are $2001 \choose 4$ ways to choose a four element subset of $M$. If the numbers in $M$ are distributed among the four residues, the sums will be (almost) equidistributed among $0,1,2,3$, so $\frac 14$ of the sums will be zero. Looking at all the entries in the vector we expect ${2001 \choose 4}\frac 1{4^9} \gt 2\ 500\ 000$ sums to be zero in all entries.

To avoid the equidistribution we can have all the elements of $M$ in two classes. If half have entry $0$ and half have entry $1$ in a position, the only way to get a sum of zero is to select all four with the same entry. This is only $\frac 18$ of the sets of four but you still get ${2001 \choose 4}\frac 1{8^9}\approx 4962$ sums to the zero vector.

To make this solid, let there be $a$ numbers with first entry $0, b$ with first entry $1, c$ with first entry $2,$ and $d$ with first entry $3$. You have $a+b+c+d=2001$. To get a sum of $0$ you can select four of the same, giving ${a \choose 4}+{b \choose 4}+{c \choose 4}+{d \choose 4}$ sets, or two with residue $1$ and two with residue $3$ giving ${b \choose 2}{d \choose 2}$ sets, or a number of other possibilities. You need to show that at least $\frac 1{20}$ of the sets sum to zero because $20^9 \lt {2001 \choose 4}$

$\endgroup$

You must log in to answer this question.

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