Given a set $M$ of $1985$ distinct positive integers, none of which has a prime divisor greater than $23$, prove that $M$ contains a subset of $4$ elements whose product is the $4$th power of an integer.
Problem
Source: IMO 1985, Day 2, Problem 4
Tags: modular arithmetic, pigeonhole principle, combinatorics, Extremal combinatorics, number theory, IMO, IMO 1985
20.02.2006 17:06
Given a number with prime factors $\le 23$ of the form $n=2^{a_1}\cdot 3^{a_2}\cdot\ldots\cdot 23^{a_9}$, we can identify it with the vector $v=(a_1\pmod 4,\ldots,a_9\pmod 4)\subset\mathbb Z_4^9$, where $\mathbb Z_4$ is the cyclic group of order $4$. We must thus prove that given any $1985$ elements of $\mathbb Z_4^9$, we can find $4$ which sum up to $0$. In fact, that $1985$ is there only because the contest was held in $1985$ . $2^9\cdot 4-(2^9-1)=1537$ suffices. Consider the following assertion, which we denote by $P_k(n)$, where $n$ is a positive integer $\ge 2$ and $k$ is a positive integer: Given $2^kn-(2^k-1)$ elements of $\mathbb Z_n^k$, we can find $n$ which sum up to $0$. We'll prove that $(*)\ P_k(a),P_k(b)\Rightarrow P_k(ab)$. Then, since $P_k(2)$ is a simple pigeonhole, $P_k(4)$ follows, and since what we want is $P_9(4)$, we're done. Assume that $P_k(a),P_k(b)$ hold, and consider $2^kab-(2^k-1)$ positive natural numbers. Take a group of $2^ka-(2^k-1)$ and select $a$ with sum divisible by $a$. Then, repeat this procedure with the remaining $2^ka-(2^k-1)-a$ numbers, until we have $2^kb-(2^k-1)$ groups of $a$ elements, each one with sum divisible by $a$. Now divide these sums by $a$, and from the collection (multiset) of $2^kb-(2^k-1)$ elements that we get, extract $b$ with sum divisible by $b$. Multiply $a$ back, and take the $ab$ elements which enter these $b$ sums. This is our collection of $ab$ elements with sum divisible by $b$. P.S. $P_1(n)$ is the well-known Erdos-Ginzburg-Ziv Theorem, discussed several times on the forum. Here's one of the older links for example. In that topic, Charlydif wrote that $P_2(n)$ is no longer a conjecture, due to C. Reiher.
17.05.2014 03:51
For a moment let's pretend we are asked for 2 numbers multiplying to a square. We have $9$ primes, so we need $2^9+1$ numbers to find two which's exponents mod 2 are congruent (so they multiply to square). Doing this many times we can find $(1985-(2^9+1))/2 \ge 2^9+1$ pairs of numbers which multiply to squares. So we have $2^9+1$ square numbers, and by the same logic two of them will multiply to a fourth power. We're done.
27.04.2017 17:35
I find this one very nice. As @JuanOrtiz did, notice that $2^9+1$ numbers are enough to find among them 2 nbs which product gives a square. So we start with $2^9+1$ nbs, we know we have a square already. We put the 2 nbs aside, add 2 other nbs and repeat the process. Since each of the 9 exponents is either 0 or 2 mod 4, then there are also $2^9$ choices for a square. This forces us to find $2^9+1$ squares so we need to add 2 $2^9$ times so we need at least $$2^9+1+2 (2^9)=1537.$$We are done.