Czech-Slovak-Polish Match

After $i$ steps, there will be $k-2i$ heaps left on the table; thus if a single heap is to remain in the end, the number $k$ must be odd and the total number of steps has to be $\frac{1}{2}(k-1)$. Let us distinguish two cases, according as the remainder of $k$ upon division by 4 is 1 or 3.

The case of $k=4c+1$. In the beginning there are $1+\cdots +k=\frac{1}{2}k(k+1)=(4c+1)(2c+1)$ stones on the table, from which in course of the $2c$ steps we will remove $1+\cdots +2c=c(2c+1)$ stones; thus the number of stones in the last heap will be $$p=(4c+1)(2c+1)-c(2c+1)=(2c+1)(3c+1).$$ Since the numbers $2c+1$ and $3c+1$ are coprime, $p$ is a perfect square if and only if both $2c+1$ and $3c+1$ are perfect squares; that is, if and only if their quadruples $4(2c+1)=2k+2$ and $4(3c+1)=3k+1$ are perfect squares.

The case of $k=4c+3$. In the beginning there are $1+\cdots +k=\frac{1}{2}k(k+1)=2(c+1)(4c+3)$ stones on the table, from which we remove in course of all the $2c+1$ steps a total of $1+\cdots +(2c+1)=(c+1)(2c+1)$ stones; thus the last single heap will contain $$p=2(c+1)(4c+3)-(c+1)(2c+1)=(c+1)(6c+5).$$ If $p$ were a perfect square, then so would have to be the two coprime numbers $c+1$ and $6c+5$. Let us show that this is not possible. Assume that there exist natural numbers $x,y$ such that $c+1=x^2$ and $6c+5=y^2$. From the equality $6x^2-y^2=1$ it follows that the number $y$ is odd, hence $y^2$ gives a remainder of 1 upon division by 8. The number $6x^2$ then gives the remainder of 2, which implies that $3x^2$ gives remainder 1 upon division by 4 — a contradiction. Hence in the case of $k=4c+3$ the number $p$ is never a perfect square, and likewise the number $3k+1=12c+10$ is never a perfect square (being an even number not divisible by 4).

Let us finally find the least number $k=4c+1$, $c\ge 1$, for which both numbers $2c+1$ and $3c+1$ are perfect squares. From the equalities $2c+1=x^2$ and $3c+1=y^2$ for suitable integers $x,y>1$ it follows that $3x^2-2y^2=1$, whence $x$ is odd, but then the number $2y^2$ gives remainder 2 upon division by 4, so $y$ is also odd. Set $x=2a+1$, $y=2b+1$ ($a,b>0$ integer) and substitute this into the equality $3x^2-2y^2=1$; upon a small manipulation this leads to the relation $3a(a+1)=2b(b+1)$, and taking successively $a=1,2,\dots$ we soon find the smallest solution $a=4$ and $b=5$, corresponding to $x=9,y=11,c=40$ and $k=161$.