The most obvious way in which we could force two in the same pile to sum to a perfect square would be to find $3$ numbers, any two of which sum to a perfect square. We can reverse-engineer this: let the $3$ numbers be $a<b<c$, and let their pairwise sums be $(2m-1)^2,(2m)^2,(2m+1)^2$ (Rationale: we want $a,b,c$ to be similar in size, so we should pick squares close to each other; the middle square needs to be even so we end up with integers). Solving simulatenously, we get $a = \frac{(2m-1)^2+(2m)^2-(2m+1)^2}2 = 2m(m-2)$, and similarly, $b=2m^2+1,c=2m(m+2)$. It suffices to find positive integer $m$ such that $n \le 2m(m-2) \le 2m(m+2) \le 2n$. The range of possible $n$ for a given $m$ is thus $m^2+2m \le n \le 2m^2+4m+1$; note that $n=100$ lies in the range for $m=9$. Now, note that $2m^2+4m+1 \ge (m+1)^2 + 2(m+1)$ for all $m\ge 9$, each interval intersects with the next, so all $n\ge100$ lie in such an interval for some $m\ge9$. Remark: Consider a graph where $n+1, ...., 2n$ correspond to the vertices and $x$ and $y$ are connected iff $x+y$ is a perfect square. Then all we need to prove is that this graph is not bipartite. As we know this is equivalent to saying that there is an odd cycle in this graph. Thus, to solve the problem you must explain why there is an odd cycle. And well, presenting a triangle turns out to be the easiest thing to do....

The most interesting thing about this problem is actually how sharp $n \ge 100$ is. I think the following harder formulation would have been much more entertaining than the one actually used (but not as P1, of course): Quote: Find the largest integer $N$ for which one may split $\{N, N+1, \dots, 2N\}$ into two sets, such that in each set, no two elements sum to a perfect square.

As it stands, I find it rather underwhelming that one shows a certain graph is not bipartite by observing it has a triangle, the end.

Nice problem but it stands a bit weird in the number theory category (it would stand weird in C as well. I guess they said "oh it has perfect squares so it must be N"). Slightly underwhelming how easy it is to get the "construction" but anyways here's a solution pretty similar to #1.

A bit silly, but not awful. Also this is definitely algebra. Consider a triple of numbers of the form $(a,b,c)=(2m^2-4m,2m^2+1,2m^2+4m)$ for a positive integer $m$—observe that $a+b,b+c,c+a$ are squares, and $a,b,c$ are always pairwise disjoint. I claim that we can always find such a triple within $\{n,n+1,\ldots,2n\}$ for $n \geq 100$. This is equivalent to saying that there exists an integer $m$ with $$n\leq 2m^2-4m\text{ and } 2n \geq 2m^2+4m \implies m^2+2m \leq n \leq 2m^2-4m.$$For $n \in [100,121)$, we can manually verify that $m=9$ works. Henceforth suppose $n \geq 121$. I claim that choosing $\lfloor \sqrt{n}\rfloor -1$ works in this case. Observe that $$m^2+2m=m(m+2)=\lfloor \sqrt{n}\rfloor^2-1\leq n$$by difference of squares, and (using the inequality $\lfloor x\rfloor\geq x-1$): $$2m^2-4m=2m(m-2)=2(\lfloor \sqrt{n}\rfloor -1)(\lfloor \sqrt{n}\rfloor -3)\geq 2(\sqrt{n} -2)(\sqrt{n}-4)=2n-12\sqrt{n}+16.$$Since we want to show $2m^2-4m\geq n$, it suffices to prove that $$2n-12\sqrt{n}+16\geq n \implies n-12\sqrt{n}+16\geq 0.$$Viewing this inequality as a quadratic inequality in $\sqrt{n}$ and using the quadratic formula yields $$\sqrt{n}\geq 6+2\sqrt{5}.$$We can verify that $6+2\sqrt{5}<11$ by subtracting $6$ from both sides and squaring, so $\sqrt{n}\geq 6+2\sqrt{5}$ indeed holds when $n\geq 121$, proving the claim. Therefore, for $n \geq 100$, there always exists $m$ with $2m^2-4m,2m^2+1,2m^2+4m \in \{n,n+1,\ldots,2n\}$. To finish, observe that by Pigeonhole at least two of these must be in the same pile, so we're done. $\blacksquare$

popcorn1 wrote: Let $n \geqslant 100$ be an integer. Ivan writes the numbers $n, n+1, \ldots, 2 n$ each on different cards. He then shuffles these $n+1$ cards, and divides them into two piles. Prove that at least one of the piles contains two cards such that the sum of their numbers is a perfect square. This is a very good problem. But how in the world is NT. Considering this as NT it is a very bad choice even though it is a great problem. I'm sure also the proposer would agree to this that this isn't NT.

The idea is to show there exist 3 numbers that pairwise sum to a perfect square, since by PHP at least one of those pairs will be in one of the two piles. For $n < 108$, just consider $(126, 163,198)$. For $n\geq 108$, I claim there exists $x$ such that the triple $(2x^2-4x, 2x^2+1, 2x^2+4x)$ works. In order to have these threee numbers to fit in the given range, we need \[n\leq 2x^2-4x \iff \frac{1}{2}n+1\leq (x-1)^2\]\[2x^2+4x\leq 2n \iff n+1\geq (x+1)^2\]so essentially, there must be at least $3$ perfect squares in between $\frac{1}{2}n+1$ and $n+1$, inclusive. Simply consider $x=\left\lfloor \sqrt{n+1}\right \rfloor-1$: clearly $n+1\geq (x+1)^2$. To show the other side, consider the bound \[(x-1)^2=\left(\left\lfloor \sqrt{n+1}\right\rfloor-2\right)^2 \geq \left(\sqrt{n+1}-3\right)^2\]Comparing this to $\frac{1}{2}n+1$ and rearranging yields $ n^2-108n+180\geq 0$, which is clearly positive for $n\geq 108$ as $n^2-108n$ is then non-negative. Since we've covered all of $n\geq 100$, we are done. And yes I could have solved the quadratic to "improve" this to $n\geq 107$ but I'm lazy.

For each integer $k\geq 9$, consider the triple of cards $$(2k^2-4k, 2k^2+1, 2k^2+4k).$$Observe that any two sum to a perfect square, so it kills the problem whenever $$k^2+2k \leq n \leq 2k^2-4k.$$Define the interval $S_k = [k^2+2k, 2k^2-4k+1]$. We claim that: Claim: The intervals $S_{9}, S_{10}, S_{11}, \hdots$ cover $[99, \infty)$. Proof: It suffices to check that there is no integer between $S_k$ and $S_{k+1}$, or that $2k^2-4k \leq (k+1)^2 + 2(k+1) + 1$, which can be easily checked to hold whenever $k\geq 9$. $\blacksquare$ The problem immediately follows from the claim.

The above solutions are quite nice but I guess I will post my solution from the contest. My solution is very greedy and gives an explicit construction for $n \leq 161$ (notice that only two constructions are necessary) Firstly, notice that if there are $n \leq a < b < c \leq 2n$ such that $a+b$, $b+c$, $c+a$ are all perfect squares, we are done by PHP as one of the piles will have to contain one of the pairs $\{a,b\}, \{b,c\}, \{c,a\}$. If $n \in \{100,101,...,126\}$ take $\{126,163,198\}$ and if $n \in \{127,..,160\}$, take $\{160,201,240\}$. Assume from now on that $n \geq 161$ and define $f(n)$ to be the number of squares between $2n$ and $4n$. $\textbf{Lemma:}$ $f(n+k)+1 \geq f(n)$ for all $k,n \in \mathbb{N}$ $\textbf{Proof)}$ We shall prove that whenever $f$ decreases it will increase back up by at least $1$ before ever decreasing again. Notice that $f$ can only decrease if $2n=x^2$ or $2n+1 = x^2$. $\textbf{Case 1)}$ $2n=x^2$ We shall prove that $f$ will increase between $2n=x^2$ and $2k = (x+1)^2-1$ as there are no perfect squares between the two above values. Then we have to prove that there is a square between $4n = 2x^2$ and $4k = 2x^2+4x$ which clearly holds as the difference between two consecutive squares does not exceed $4n$ until between $(2n)^2$ and $(2n+1)^2$. $\textbf{Case 2)}$ $2n+1 = x^2$ We shall once again prove that $f$ will increase between $2n+2 = x^2+1$ and $2k = (x+1)^2$ which is equivalent to proving that there is a square between $2x^2+2$ and $2x^2+4x+2$ which we can once again conclude by the previous reasoning. $\blacksquare$ Now, as $f(161) = 8$, by the $\textbf{Lemma}$, $f(161+k) +1 \geq f(161) = 8$ meaning that for all $n \geq 161$, $f(n) \geq 7$. $\textbf{Case 1)}$ The smallest square greater than or equal to $2n$ is odd Now, denote this square by $(x-2)^2$ and let $a = x^2-2x-3, b= x^2+2x+3, c = x^2+6x+5$, then $$2n \leq (x-2)^2 < a = x^2-2x-3 < x^2+2x+3 = b < x^2+6x+5 = c < (x+3)^2 \leq 4n $$Notice that $a,b,c$ are all even meaning that $\frac{a}{2}, \frac{b}{2}, \frac{c}{2}$ are all integers that are part of $\{n,...,2n\}$ and clearly sum to perfect squares and we're done by the initial PHP argument. $\square$ $\textbf{Case 2)}$ The smallest square greater than or equal to $2n$ is even Now, let the second smallest square greater than $2n$ be denoted by $(x-2)^2$ and repeat the identical argument above once again keeping in mind that $f(n) \geq 7$. $\square$ As we have dealt with both of the above cases we are done. $\blacksquare$

First construction: Let $(a,b,c)=(2x^2-4x,2x^2+1,2x^2+4x)$ for some $x$. We can check that $a+b=(2x-1)^2$, $b+c=(2x+1)^2$, and $a+c=(2x)^2$. We claim that for all $n$, there exists $x$ such that $\{a,b,c\}\subset\{n,n+1,\ldots,2n\}$. Since $2x^2-4x<2x^2+1<2x^2+4x$ for all $x\ge100$, it suffices to find $x$ such that $x^2+2x\le n\le2x^2-4x$. Second construction: We will set $x=\lfloor\sqrt n\rfloor-1$. Proof of left inequality: $x^2+2x\le n$ The inequality $x^2+2x\le\left(\sqrt n-1\right)^2+2\left(\sqrt n-1\right)=n$ is true since $\lfloor s\rfloor\le s$. Proof of right inequality: $n\le2x^2-4x$ We have $x\ge\lfloor\sqrt{100}\rfloor-1=9$. Note that $2t^2-4t=2(t-1)^2-2$ is strictly increasing for all $t>1$. Incidentally, we have $2x^2-4x\ge2(\sqrt n-2)^2-4(\sqrt n-2)$, which we want to prove is at least $n$. As a quadratic in $\sqrt n$, this is $n-12\sqrt n+16\ge0$, true for $n\ge110$. For $n\in[100,110]$, we have $x=9$, so $n\le2x^2-4x$ iff $n\le126$. $\square$

Take $k$ such that $k^2\leq n < (k+1)^2$. Then, let \[a=2k^2-8k+6 < 2k^2 \leq 2n\]\[b=2k^2-4k+3 < 2k^2\leq 2n\]\[c=2k^2-2 <2k^2 \leq 2n\]As for the lower bound, note $(k+1)^2 > n \geq 100$, so $k\geq 10$ \[2k^2-8k+6 = k(k-10) + 5 + k^2+2k+1 > (k+1)^2 > n\]thus, all $a,b,c\in [n,2n]$. Now, note that \[a+b=4k^2-12k+9 = (2k-3)^2\]\[a+c = 4k^2-8k+4 = (2k-2)^2\]\[b+c=4k^2-4k+1 = (2k-1)^2\]So, by pigeonhole at least one of the piles contains two values from $a,b,c$, which will add to a perfect square so we are done. $\blacksquare$.

Leartia wrote: Nice problem but it stands a bit weird in the number theory category (it would stand weird in C as well. I guess they said "oh it has perfect squares so it must be N"). Slightly underwhelming how easy it is to get the "construction" but anyways here's a solution pretty similar to #1.

Sigh for the part where they put it in N...

It will suffice to find cards \(a\), \(b\), \(c\) such that \(a+b\), \(b+c\), \(c+a\) are perfect squares. Indeed the cards \[2k^2-4k<2k^2+1<2k^2+4k\]should work, so long as the three numbers are in the range \([n,2n]\). We will show we may select \(k\) such that they are in the range, whenever \(n\ge100\). Let \(k=\lfloor\sqrt n\rfloor-1\), so that \(2k^2+4k<2(k+1)^2\le2n\), and moreover since \(n\le k^2+4k+3\) we have \[n\le k^2+4k+3\le2k^2-4k\]since \(k\ge9\).

Cute problem . Pretty much the same as all the solution above -- if we could find three cards $a,b,c$ such that $a + b, b + c, c + a$ are all squares, we are done: and by solving $\{ a + b, b + c, c + a \} = \{ (2k - 1)^2, (2k)^2, (2k + 1)^2 \}$, then we have $\{ a,b, c \} = \{ 2k^2 - 4k, 2k^2 + 1, 2k^2 + 4k \}$. Now, it suffices to prove that for any $n \ge 100$, there exists $k$ such that $a,b,c \in [n,2n]$. Note that obviously $k > 0$, and therefore $a,b,c$ must be all distinct. Take the smallest $k \in \mathbb{N}$ such that $n \le 2k^2 - 4k$. Since $n \ge 100$, we have $2k^2 - 4k \ge 100$, which implies $k \ge 9$. We'll now prove that $2k^2 + 4k \le 2n$. This is immediate when $k = 9$, because we have $n \ge 100 > 9 \cdot 11$. Suppose that $k \ge 10$, and FTSOC, $n < k^2 + 2k$, then \[ n < k^2 + 2k \le 2(k - 1)^2 - 4(k - 1). \]because $k \ge 10$, and therefore our choice of $k$ is not minimal, we have a contradiction. Therefore, $k^2 + 2k \le n$, and we are done.

We argue that for such $n$, there exists an integer $k\ge 1$ such that $n\leq 2k(k-2)<2k^2+1<2k(k+2)\leq 2n$. This is enough, as any two of the terms have a square sum. Let $k= \lceil \frac{\sqrt{2n+4}}{2}\rceil+1$. Then $n\le 2k(k-2)$ as by construction we have $2n+4\le (2k-2)^2$. It remains to demonstrate that $2k(k+2)\le 2n$. Equivalently, we can demonstrate $k(k+2)\le n$, or $(k+1)^2\le n+1$. We have \[(k+1)^2 = \left(\left\lceil \frac{\sqrt{2n+4}}{2}\right\rceil+2\right)^2 \le \left(\left\lfloor \frac{\sqrt{2n+4}}{2}\right\rfloor+3\right)^2 \le \frac{2n+4}{4}+6\left\lfloor \frac{\sqrt{2n+4}}{2}\right\rfloor+9.\]Thus it is enough to demonstrate \[6\left\lfloor \frac{\sqrt{2n+4}}{2}\right\rfloor\le n+1-n/2-1-9 = n/2-9.\]Equivalently, it is enough to demonstrate \[18n+36=36\cdot\frac{2n+4}{4}\le n^2/4-9n+81\iff (n/2-27)^2 - 684 = n^2/4-27n+45\ge 0.\]So we are thus done for $n/2\ge 54$, that is, $n\ge 108$. Then, remark that $k=9$ works for $100\le n\le 108$, so we are done.

Solved with Isaac Zhu, Jeffery Chen, Kevin Wu, Albert Wang, Nacho Cho. Claim: There are 5 consecutive squares $(x-2)^2, \cdots , (x+2)^2$ in the interval $[2n+4, 4n+4]$ such that $x$ is even. Proof: If $100 \le n \le 126$ we can take $16^2, \cdots , 20^2$. Otherwise if $n \ge 127$ we have $\sqrt{4n+4}-\sqrt{2n+4} > 6$ and so there exist 6 consecutive squares in the interval, implying what we want. Now consider the integers $a,b,c$ satisfying $$\begin{cases} a+b = (x-1)^2\\ b+c = x^2\\ c+a = (x+1)^2 \end{cases}.$$which clearly has integer solutions due to $x$ being even. Since $$n \le \frac{x^2+(x-1)^2-(x+1)^2}{2} = \text{min}(a,b,c) \le \text{max}(a,b,c) = \frac{x^2+(x+1)^2-(x-1)^2}{2} \le 2n$$due to the bounds we placed on $x$, we have $a,b,c \in [n, 2n]$. Now by pigeonhole two of $a,b,c$ are in the same pile, and we're done.

Consider $k$ the greatest integer such that $(k+1)^2\leq n+1$. Then $(k+2)^2> n+1$. Claim: $n< 2k^2-4k< 2k^2+1< 2k^2+4k\leq 2n.$ Proof: Of course, $(k+1)^2\leq n+1\Rightarrow 2k^2+4k\leq 2n.$ The condition $n\geq 100$ can be used as following: $$n\geq 100\Rightarrow (k+2)^2> 100+1\Rightarrow k\geq 9.$$Since $k\geq 9$, the inequalities $2k^2-4k< 2k^2+1< 2k^2+4k$ are obvious true. Now we are left to prove that $2k^2-4k>n$. But it is enough to prove that $$2k^2-4k\geq (k+2)^2-1=k^2+4k+3\Leftrightarrow k^2\geq 8k+3\Leftrightarrow (k-4)^2\geq 19$$which is true since $k\geq 9$. $\blacksquare$ Denote $x=2k^2-4k, y=2k^2+1$ and $z=2k^2+4k$. Hence $$\begin{cases} x+y = (2k-1)^2\\ x+z = (2k)^2\\ y+z = (2k+1)^2 \end{cases}$$Using the previous claim, we can find a subset $\{x, y, z\}$ of the set $\{n, n+1, \ldots , 2n\}$ so that the sum of any 2 of them is a perfect square. Now, by pigeonhole principle, there will be 2 numbers from the subset $\{x, y, z\}$ in the same pile, and the problem is finished.

Let $a+b=(2x-1)^2$, $b+c=(2x)^2$, $c+a=(2x+1)^2$. Clearly, if $n\le a,b,c\le 2n$, then one of the piles must contain at least $2$ of $a$, $b$, and $c$, making a perfect square. When $x=9$, we get that $a=163$, $b=126$, and $c=198$. This means that for $100\le n\le 126$, one of the piles must contain $2$ cards whose sum is a perfect square. We want to show that there must exist some $x$ such that $n\le a,b,c\le 2n$. We solve the equations to get that $a=2x^2+1$, $b=2x^2-4x$, and $c=2x^2+4x$. We want to show that $n\le b<a<c\le 2n$. We solve $b=2x^2-4x\ge n$ to get that $x\ge 1+\sqrt{1+\frac{n}{2}}$. We solve $c=2x^2+4x\le 2n$ to get $x\le \sqrt{n+1}-1$. Let $x=\lfloor \sqrt{n+1}\rfloor-1$. Then we want to show that $x=\lfloor \sqrt{n+1}\rfloor-1\ge \sqrt{n+1}-2\ge 1+\sqrt{1+\frac{n}{2}}$. We can simplify this to get that $n^2-108n+180\ge0$ so $n\ge 54+\sqrt{54^2-180}$. This means that for $n\ge 54+\sqrt{54^2-180}$, one of the piles must contain $2$ cards whose sum is a perfect square. Since $54+\sqrt{54^2-180}\le 108$, and we've already shown there must be a pile with $2$ cards whose sum is a perfect square for $100\le n\le 126$, there must be a pile with $2$ cards whose sum is a perfect square for $100\le n$.

Let $a=2x^2-4x$, $b=2x^2+1$, and $c=2x^2+4x$. If $n \le a,b,c \le 2n$, then note that one of the piles contains at least $2$ of $a$, $b$, and $c$, and since $a+b$, $b+c$, and $c+a$ are all perfect squares this would give a sum that is a perfect square. For $n \le 107$, take $x=9$ so that $a=126$, $b=163$, and $c=198$. For $n \ge 108$, we want to find a $x$ so that $n \le 2x^2-4x$ and $2x^2+4x \le 2n \equiv (x+1)^2 \le n+1$. We claim that $x= \lfloor \sqrt{n+1} \rfloor -1 \ge \sqrt{n+1}-2$ works. This obviously satisfies $2x^2+4x \le 2n$ so we have to check it satisfies the other condition. Note that $$2x^2-4x \ge 2(\sqrt{n+1}-2)^2-4(\sqrt{n+1}-2) = 2(n+1)-12\sqrt{n+1}+16 = 2n + 18 - 12\sqrt{n+1}.$$For this to be greater than or equal to $n$, we would need to prove $$n \ge 12\sqrt{n+1}-18 \iff (n+18)^2 \ge 144(n+1) \iff n^2-108n+180 \ge 0.$$However since $n \ge 108$ this is obvious so we are done.

Note that if we can find three cards $a,b,c$ such that $n\le a,b,c\le2n$ and $a+b,a+c,b+c$ are all distinct squares. We claim that this is possible with the three squares being $(2k-1)^2,(2k)^2,(2k+1)^2$, respectively, for some $k$ based on the $n$. Specifically, we will show that for all $n\ge100$ are covered by at least one $k$. We will first solve for $a,b,c$. With some simple algebra, we get that $a=2k^2-4k,b=2k^2+1,c=2k^2+4k$. Therefore, a $k$ would cover an $n$ if and only if $k^2+2k<=n<=2k^2-4k$. Therefore, as long as the minimum bound for the next $n$, namely $(k+1)(k+3)$, is less than or equal to the maximum bound for the current $n$, namely $2k^2-4k$, our claim works. Simplifying $k^2+4k+3\le 2k^2-4k$ gives $k\ge9$ when $k$ is a positive integer. We can see that the lower bound covered by $k=9$ is $99$, which is indeed below our required $n=100$. QED.

wth is this problem ;-; Consider a graph with the numbers as nodes and edges drawn between nodes when two nodes sum to a perfect square. It suffices to show that the graph cannot be bipartite through constructing a triangle. Since for $n \geq 100$ we have (by increasing functions) $$\sqrt{2n+2n-1}-\sqrt{n+n+1} > \sqrt{399}-\sqrt{201} > 19-15=4,$$it is pmm,ossible to choose three consecutive squares $(2k-1)^2,(2k)^2,(2k+1)^2.$ Now, let $a+b=(2k-1)^2,b+c=(2k)^2,a+c=(2k+1)^2.$ Solving, $$a=2k^2+1,b=2k^2-4k,c=2k^2+4k.$$We wish to show that a positive integer $k$ exists such that all three of these expressions for $a,b,c$ fall within the range $[n,2n].$ Clearly, none of these can be equal, $2k^2-4k$ is the minimum, and $2k^2+4k$ is the maximum. Thus, we want to prove $2k^2-4k \geq n$ and $2k^2+4k \leq 2n,$ which can be combined into $$k^2+2k\leq n \leq 2k^2-4k.$$Note that for $n=100,$ the construction $k=9$ works. By induction, it suffices to prove that $2k^2-4k \geq (k+1)^2+2(k+1)$ for $k \geq 9,$ which works.

nice solution

Claim. Inequality $n\leq 2k^2-4k\leq 2k^2+1\leq 2k^2+4k\leq 2n$ holds for some positive integer $k$. Proof. It's suffice to show, that all segments $[t^2+2t;2t^2-4t]$ for $t\in \mathbb{Z},t\geq 9$ cover $[100;\infty )$. Indeed, $100\in [99;124]$ and $(t+1)^2+2(t+1)-t^2-2t=2t+2\leq t^2-6t=2t^2-4t-t^2-2t$ for every $t\geq 9$. Now we see, that there are cards with numbers $2k^2-4k,2k^2+1,2k^2+4k$ and by Pingeonhole principle two of them lie in one pile. Straightforward check shows, that these are exactly required cards.

We claim there are at least $3$ squares between $2n+1$ and $3n$ inclusive for $n \geq 100$. Proof. Let $k^2$ ($k \in \mathbb N$) be the largest square smaller than $2n+1$. This implies $k < \sqrt{2n+1}$. Then \[ (k+3)^2 = k^2 + 6k + 9 < 2n+1 + 6\sqrt{2n+1} + 9. \]We can show \[ 1 + 6\sqrt{2n+1} + 9 < n \]by induction. Thus \[ (k+3)^2 < 2n+1 + 6\sqrt{2n+1} + 9 < 3n, \]so $2n+1 \leq (k+1)^2,(k+2)^2,(k+3)^2 \leq 3n$ as desired. Let the two piles be $A$ and $B$. WLOG suppose $A$ is the larger pile, then $A$ has at least $\frac{n+1}{2}$ numbers. Let them be $a_1 < a_2 < \ldots < a_{m}$, where $m \geq \frac{n+1}{2}$. Observe that the sums \[ a_1+a_2,a_1+a_3,a_1+a_4, \ldots, a_1+a_m, a_2+a_m, a_3+a_m, \ldots, a_{m-1} + a_m \]are distinct. The above takes on $2m-3 \geq n+1 - 3 = n-2$ distinct numbers between $2n+1$ and $3n$. Since there are $n$ numbers and at least $3$ perfect squares in that range, at least one of the $n-2$ numbers must be a perfect square by pigeonhole principle.

We just need to show there exists an integral value of $k > 0$ such that $2k^2-4k, 2k^2+1, 2k^2+4k$ belong to the interval $[n, 2n]$. This is mere algebra, and the knowledge that $n \geq 100$. The bound on $100$ is very gentle.

Claim: for each $n$, there exists an integer $X$ such that $2X^2-4X$ and $2X^2 + 4X$ are both numbers written on some card. Proof: In algebra, we claim that there exists an $X$ such that $n \leq 2X^2 - 4X$ and $2X^2 + 4X \leq 2n$. Rewriting this in the quadratic formula, we just need to find an integer between $1 + \sqrt{1 + \frac{n}{2}}$ and $-1 + \sqrt{1+n}$. We can manually verify a bunch of $n$ close to $100$ to see that this is always possible, and for larger $n$ the sizes don't compare. So, for some integer $X$, Ivan writes down $2X^2 + 4X$, $2x^2 - 4X$ and $2X^2 + 1$. Pairs of these numbers sum to $(2X-1)^2$, $(2X)^2$ and $(2X+1)^2$; two of these three numbers must clearly be in the same group, so we have a perfect square.

Observe that if we had a symmetric system of equations \begin{align*} a + b &= p^2 \\ b + c &= q^2 \\ c + a &= r^2 \\ \end{align*}with solutions $a, b, c$, we must have by the pigeonhole principle that two of these numbers are in the same pile, and hence sum to a square. Solving for $a, b$ and $c$ yield the solutions $(p^2 + r^2 - q^2)/2, (p^2 + q^2 - r^2)/2, (r^2 + q^2 - p^2)/2$. We now have $p,q$ are odd and $r$ is even, and so by way of virtue, we may suppose that $p = 2k + 1, q = 2k - 1,$ and $r = 2k$ for some integer $k$. Then we obtain $a = 2k(k + 2), b = 2k^2 + 1, c = 2k(k-2)$. Thus we must have \[n < 2k(k-2) < 2k^2 + 1 < 2k(k + 2) < 2n.\] This is equivalent to \[\frac{2 + \sqrt{4+2n}}{2} < k < \sqrt{n+1} - 1.\]Therefore we must show that $\sqrt{1+n} - (2 + \sqrt{4 + 2n})/2 - 1 \geq 1$, which gives us $n \geq 100$, as desired. $\blacksquare$

Claim: For $n\geq 100$ there exists a $k$ such that $n\leq 2k^2-4k,2k^2+1,2k^2+4k\leq 2n$. Proof. One can check that $k=9$ works for $100\leq n \leq 126$. Then, fix $k$, note that \[2(2(k-1)^2-4(k-1)+1)\geq 2k^2+4k \iff 2k^2-20k+6\geq 0\]is true for $k\geq 10$. This takes care of $2(k-1)^2-4k+1\leq n \leq 2k^2-4k$ proving the claim. $\blacksquare$ This finishes since any two of $2k^2-4k,2k^2+1,2k^2+4$ sum to a perfect square.

we can easily see that the total possible sums of two cards are $2n+1, 2n+2, \ldots, 4n-1$ given that $n \geqslant 100$, there should be at least five perfect squares in the range $[2n+1,4n-1]$ out of the five perfect squares, at least two are odd and at least two are even. if no matter what one of the piles has two cards such that the sum of their numbers is a perfect square, then we have $x+y=a^2$, $y+z=b^2$, and $z+x=c^2$. there exists a solution to that system of equations if $a^2+b^2+c^2$ is even since $a^2$, $b^2$, and $c^2$ are among the five or more perfect squares in the range $[2n+1,4n-1]$, we can have $a^2$ and $b^2$ be odd and $c^2$ be even. thus, there exists $(x,y,z)$ that satisfy $x+y=a^2$, $y+z=b^2$, and $z+x=c^2$, and therefore no matter how the cards are shuffled, at least one of the piles contains two cards that sum to a perfect square.

Consider a graph $G$ on $n+1$ vertices such that each vertex represents a unique number from $n, n+1, \ldots, 2n$. Two vertices are adjacent if the sum of the corresponding numbers is a perfect square. The problem is equivalent to showing that $G$ is not bipartite, i.e., $G$ has an odd cycle. Consider solutions to the following equations: $a + b = 4 \lfloor 0.99 \sqrt n \rfloor^2$ $b + c = 4 \lfloor 0.75 \sqrt n \rfloor^2$ $c + a = 4 \lfloor 0.90 \sqrt n \rfloor^2$ Note that for $n\geq 100$ we always have $4 \lfloor 0.99 \sqrt n \rfloor^2 > 4 \lfloor 0.90 \sqrt n \rfloor^2 > 4 \lfloor 0.75 \sqrt n \rfloor^2 $ which means $a > b > c$. Moreover, since $2\mid a + b, b + c, c + a$, we also ensure that $a, b, c$ are integers. Since $a > b > c$, and they are integers and they lie in $[n, 2n]$, we have found a 3-cycle, which means $G$ cannot be bipartite. $\blacksquare$

We will three numbers $a$, $b$, and $c$ so that the three sums $$a+b=(2x-1)^2=4x^2-4x+1$$$$b+c=(2x)^2=4x^2$$$$c+a=(2x+1)^2=4x^2+4x+1$$are perfect squares. This will finish the problem. Solving gives $$a=2x^2+1$$$$b = 2x^2-4x$$$$c=2x^2+4x.$$We need to prove that $x$ exists, and we are done. We need $$n\le 2x^2-4x<2x^2+1<2x^2+4x\le 2n.$$In particular, we want $$n\le 2x^2-4x$$and $$x^2+2x\le n.$$The intervals of $n$ near $100$ that work using this approach are $$x=8\implies 80\le n\le 96$$$$x=9\implies 99\le n\le 126$$$$x=10\implies 120\le n\le 160.$$We need to prove that these intervals cover every number $n\ge 100$. In other words, we want to prove that the right endpoint of any interval $x\ge 9$ is larger than the left endpoint of the interval corresponding to $x+1$. This is showing that $$2x^2-4x\ge (x+1)^2+2(x+1) = x^2+4x+3,$$or $$x^2-8x-3\ge 0.$$This is clear for $x\ge 9$.

I solve it using $\lfloor \sqrt{n} \rfloor$. short solution here. Let $k=\lfloor \sqrt{n} \rfloor$. Note that $k^2\le n\le (k+1)^2$, and $k\ge 10$. It is suffice to show that there exists $x,y,z$ with $x,y,z\in [n, 2n]$ such that three numbers $x+y, y+z, z+x$ are all perfect square. let that perfect square be $a^2, b^2, c^2$, respectively. claim $(a,b,c) = (2k-3, 2k-2, 2k-1)$ works proof quick calculation gives that $x=2k^2-8k+6$, and $z=2k^2-2$. As $x\le y\le z$, one can easily check that $x, y, z$ are in the interval $[n, 2n]$ , so we're done.