i tried doing something with intervals of the form $((9999n + 4999)^2, (9999n + 5000)^2)$ but didnt lead anywhere

@above you can finish with a density argument, because anything in between has to be an odd perfect power and for large $n$ we don't have enough of those

@khina can you prove that?

khina wrote: @above you can finish with a density argument, because anything in between has to be an odd perfect power and for large $n$ we don't have enough of those oh wait i kinda stated that "for large $n$ intervals as described above occur with more frequency than odd perfect powers" how many points?

@above well it depends on how u say it but like honestly that sounds okay to me? like i mean that's the main idea so... and the bounding can just be done with sketchy bigO stuff

Idea: Consider the gap between two consecutive cubes $n^3$ and $(n+1)^3$. The gap is of size $O(n^2)$. There are at most $\log_{2}((n+1)^3) = O(\log n)$ perfect powers with exponent $\ge 4$ in the gap, which divides the gap into more smaller segment. By Pigeonhole Principle, there exists a segment of length $O\left(\frac{n^2}{\log n}\right)$, from which we can find $C$ consecutive squares where $C$ is any fixed constant. Choosing a large enough $C$ works.

yes @above that's it also can someone with permissions add all the 2020 CMO problems to contest collections?

zschess wrote: Idea: Consider the gap between two consecutive cubes $n^3$ and $(n+1)^3$. The gap is of size $O(n^2)$. There are at most $\log_{2}((n+1)^3) = O(\log n)$ perfect powers with exponent $\ge 4$ in the gap, which divides the gap into more smaller segment. By Pigeonhole Principle, there exists a segment of length $O\left(\frac{n^2}{\log n}\right)$, from which we can find $C$ consecutive squares where $C$ is any fixed constant. Choosing a large enough $C$ works. My sol: For $n$ large enough the density of having a perfect $kth$ power in such an interval $\sqrt[k]{((9999n+5000)^2-(9999n+4999)^2-2))}$. As $n$ approaches infinity and $k\ge 3$ this eventually becomes near zero (which I fakeproved in contest). This works because only $\epsilon$ of these intervals have a non-square power.

@above incorrect: you have the idea of a density argument, but you can't frame it like probability because it's... not randomly placed. your solution also just doesn't make sense in a lot of ways. a few other errors, but the probability phrasing is fundamentally wrong so i'm not really sure what to say

Chinese Remainder Theorem

thedragon01 wrote: Chinese Remainder Theorem THIS WILL NOT WORK

KaiDaMagical336 wrote: My sol: For $n$ large enough the density of having a perfect $kth$ power in such an interval $\sqrt[k]{((9999n+5000)^2-(9999n+4999)^2-2))}$. As $n$ approaches infinity and $k\ge 3$ this eventually becomes near zero (which I fakeproved in contest). This works because only $\epsilon$ of these intervals have a non-square power. well apparently THIS ALSO WILL NOT WORK i don't know what you mean by "the density of having a perfect $k$th power" because as far as i'm concerned, that is not correct english, nor a proper phrase or idea.

Well considering number of squares and nonsquare powers in an interval works. Mine is an easy fix but crt is not correct idea.

Here was my solution: Let $\{b_i\}$ be the increasing sequence of all perfect squares. We call two numbers $b_i, b_{i+1}$ $p-blocked$ for some positive integer $p \ge 2$ such that $x < p^e < y$ for an odd positive integer exponent $e \ge 3$. Consider an odd positive integer $m = 2k+1$. First, we begin by noting that any consecutive elements of $S$ of the form $b_n = (k+mt)^2 = r^2 \ , \ b_{n+1} = (k+1+mt)^2 = (r+1)^2$ has a difference divisible by $m$. It remains to show that there are infinitely many such $b_n, b_{n+1}$ that are not $p-blocked$. Consider two such $b_n, b_{n+1}$ that are $p-blocked$. Then we have $$b_n < p^e < b_{n+1}$$$$r^2 < p^e < (r+1)^2$$$$(pr)^2 < p^{e+2} < (p(r+1))^2$$ So the next closest possible $p-blocked$ number is $(pr)^2 \ge (2r)^2$. Thus all of pairs $b_i = (k+mt)^2 \ , \ b_{i+1} = (k+1+mt)^2$ where $(k+mt) \in [r, 2r)$ must be blocked by different values of $p$. There are at least $r/m$ different such pairs in the interval, meaning at least $r/m$ distinct $p$ such that $r^2 \le p^e < (2r)^2$. However, this means that there exists some $p \ge r/m$ such that $$(2r)^2 > p^e \ge p^3 \ge (r/m)^3$$ However, given some $m$, we can choose $r > 4m^3$, so that $(2r)^2 < (r/m)^3$, a contradiction. Thus not all $b_i, b_{i+1}$ in the chosen interval are $p-blocked$. Finally, as we can keep successively choosing values of $r$ such that $r_i > 4m^3$ and $r_{i+1} > 2r_i$, we have infinitely many solutions, as desired.

This shows that the conditions hold for all positive odd integers $m$, not only 9999.

First, we define two sets $A=\{ n^2| n\in \mathbb{N}\}$, $B=\{ n^2| n\in\mathbb{N}, 9999\mid 2n+1\}$, it's trivial to prove that the density of $B$ in $A$ is $\dfrac{1}{9999}$ and the density of $A$ in $S$ is $1$; so the density of $B$ in $S$ is $\dfrac{1}{9999}$. Perfect powers which are not perfect squares have a density of $0$ in $S$, which implies that the set of elements in $B$ with a perfect square as following element in $S$ has a density of $\dfrac{1}{9999}$ in $S$, so the thesis is true.

Observe that if $a_n=k^2$ and $a_{n+1}=(k+1)^2$, and $k \equiv 4999 \pmod{9999}$, then $9999 \mid a_{n+1}-a_n$. It is clear that the number of elements in $S$ that are at most $n$ for some positive integer $n$ is $O(\sqrt{n})$. Also, it is clear that the number of elements in $S$ which are squares $k^2\leq n$ such that $k \equiv 4999 \pmod{9999}$ is $O(\tfrac{\sqrt{n}}{9999})=O(\sqrt{n})$. Finally, it is evident that the number of non-square elements in $S$ that are at most $n$ is $O(\sqrt[3]{n})$. Hence, the number of elements in $S$ which are squares $k^2\leq n$ such that $k\equiv 4999 \pmod{9999}$, and whose "subsequent" element is also a square is $O(\sqrt{n}-\sqrt[3]{n})=O(\sqrt{n})$, since there can be at most $O(\sqrt[3]{n})$ elements $\leq n$ which aren't squares. Since $O(\sqrt{n})$ functions grow arbitrarily large as $n \to \infty$, we're done. $\blacksquare$

What does O mean and how can I learn that density stuff?

??? Replace $9999$ with $2c+1$. For any positive integer $N$, there are $\Omega(\sqrt{N})$ pairs of the form $[k(2c+1)+c]^2,[k(2c+1)+c+1]^2]$, but $O(\sqrt[3]{N})$ perfect powers that aren't perfect squares upper-bounded by $N$. Hence, there are $\Omega(\sqrt{N})$ pairs of consecutive perfect squares less than $N$ that don't contain any other perfect powers inbetween, and differ by a multiple of $2c+1$, proving the desired claim as we can take $N$ to be arbitrarily large.

I claim that there exist infinitely many integers $N$ such that $a_N = k^2$ and $a_{N+1} = (k+1)^2$, where $2k+1$ is a multiple of $9999$. In particular, assume for the sake of contradiction that there exists a $M$ such that no such pairs with $k > M$ exist. In particular, let $M_0$ be the smallest integer greater than $M$ with $9999 \mid 2M_0 + 1$ and $M_i = 9999+M_{i-1}$ for each $i$. Consider the first $\log_2 M + 1$ values of $i$. It follows that there exists a $N_i < \log_2 M$ such that a $N_i$th power, say $a_{N_i}$, appears between $M_i^2$ and $M_{i+1}^2$ for each $i$. In fact, all such $N_i$ must be distinct because the difference between two $M_i^2$'s is at most $19998 \cdot M_i \cdot \log_2 M_i$ while the difference between two consecutive $N_i$th powers is at least $M_i^{2(N_i-1)/N}$. But this is a contradiction by Pigeonhole.