# Generalization of an IMO 1985 Problem in Elementary Number Theory and Combinatorics.

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?

• The IMO 1985 question tackled here Sep 9, 2017 at 21:43

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