The original problem of IMO $1985$ was as follows-

Given any $1985$ positive integers all of which contains no prime factor $>23,$ prove that you can find four of them whose multiple is a perfect fourth power.

I solved this problem earlier.There are total $9$ primes $≤23$.Then every given integer is of the form $2^a3^b5^c7^d11^e13^f17^g19^h23^k$. Now consider the ordered $9$-tuple of the powers of the $9$ primes corresponding to every given numbers whose coordinates are either $0$ or $1$ accordingly as the power is even or odd. Then there are total $2^9=512$ such $9$-vectors.So by Pigeon Hole Principle there are two vectors exactly with the same configuration $(1985>512)$. The multiplication of these two numbers is a perfect square.We can have more than $512$ such pairs and among these pairs,e.i.among these perfect squares we can have similarly two numbers with exactly the same pre-defined vector configuration. Then their multiplication is a perfect fourth power.It is easy to check that the number $1985$ can be replaced by $1537$.

Now, this problem can be generalized as below:

Let $N(m,n,p)=$ the smallest positive integer $k$ such that for any given set of $k$ positive integers with no prime factor $> m$ such that there exist $n$ out of them whose multiple is a perfect $p$th power.
In the above problem we just proved that $N(23,4,4)=1537$.We can even prove by similar argument that $N(m,4,4)=(2^p+1)2+2^p-1=3(2^p+1)-2$ where $p=π(m)$ is the number of primes $\leq m$.
Now my questions are what is the explicit/most general formula,can it be calculated? Are there any asymptotic approximations?

  • $\begingroup$ The IMO 1985 question tackled here $\endgroup$
    – Joffan
    Sep 9, 2017 at 21:43

1 Answer 1


$\newcommand{\F}{\mathbb{F}} \newcommand{\Fpn}{\mathbb{F}_p^{n}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\s}{\mathfrak{s}} \newcommand{\rt}{r} $Let $\s$ denote the Erdős-Ginzburg-Ziv constant as defined in Erdős-Ginzburg-Ziv constants by avoiding three-term arithmetic progressions. Then $$N(\rho_n,k,k)\leq\s((\Z/k\Z)^n)$$ where $\rho_n$ is the $n$'th prime. (The inequality is because $\s$ allows multisets whereas $N$ does not.) An upper bound is proved in that paper:

Corollary 1.2 Let $k\geq 2$ be an integer and let $p_1,\dots,p_m$ be its distinct prime factors. Then we have $$\s((\Z/k\Z)^n)< 3k(\rt(\F_{p_1}^{n})+\dots+\rt(\F_{p_m}^{n}))$$ for every positive integer $n$.

Recall that $\rt(\F_2^n)=2^n$. For primes $p\geq 3$ it is known from [10] and [5] that $\rt(\Fpn)\leq (J(p)p)^n$, with $0.8414\leq J(p)\leq 0.9184$

Lower bounds are also discussed.


You must log in to answer this question.

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