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$ where $p=π(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 '17 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$

Lower bounds are also discussed.

  • $\begingroup$ We can found lower bounds for $N(m,2^k,2^k)$ by elementary methods $\endgroup$ – Shubhrajit Bhattachrya Sep 10 '17 at 4:51

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.