Note that no number congruent to $2 \bmod 4$ is ever of the form $x^2-y^2$. Using this fact, we establish that the initial list must have contained all numbers of the form $4k+2$ where $0 \leqslant k \leqslant 249$. From simple checking, it should also have contained $1$ (how do you plan on generating $1$ as $x^2-y^2$) We also need $4$ since even that cannot be generated. Now note the following fun stuff: 1) If we have $n, n+1$ we can get $2n+1$. 2) If we have $n-1, n+1$ we can get $4n$ (for $n > 1$). Now we claim that the answer is $251$ a lower bound of which was already obtained earlier. Let's induct and show that we can get all numbers from $1$ to $1000$ on the list. If $n$ is odd, use 1) to get it. If $n$ is even, and congruent to $2 \bmod 4$, it's already there, otherwise use 2) to get it. This finishes and gives answer of $252$. [EDIT: Thanks to SPHS1234 for pointing out a error in my original solution, which missed the fact that we cannot get $4$ bt step 2.]

I think the answer is $252$. Note that all the $250 $numbers of the form $4k+2$ will have to be there.Also we will need atleast one odd number or else all the numbers obtained will be even.Also we will need $4$ , otherwise it is not possible to obtain. For construction, take $\{4k+1\}|0 \leqslant k \leqslant 249$, $1$ and $4$ .Then easy induction gives us the first $1000$ numbers Quote: If we have $n-1, n+1$ we can get $4n$. for $n>1$ Also where are P2,4,5?

SPHS1234 wrote: I think the answer is $252$. Note that all the $250 $numbers of the form $4k+2$ will have to be there.Also we will need atleast one odd number or else all the numbers obtained will be even.Also we will need $4$ , otherwise it is not possible to obtain. For construction, take $\{4k+1\}|0 \leqslant k \leqslant 249$, $1$ and $4$ .Then easy induction gives us the first $1000$ numbers Quote: If we have $n-1, n+1$ we can get $4n$. for $n>1$ Ahh I think you're right. I will edit my post to reflect this.

SPHS1234 wrote: I think the answer is $252$. Note that all the $250 $numbers of the form $4k+2$ will have to be there.Also we will need atleast one odd number or else all the numbers obtained will be even.Also we will need $4$ , otherwise it is not possible to obtain. For construction, take $\{4k+1\}|0 \leqslant k \leqslant 249$, $1$ and $4$ .Then easy induction gives us the first $1000$ numbers Quote: If we have $n-1, n+1$ we can get $4n$. for $n>1$ Also where are P2,4,5? The entire problemset can be found here.

Oh yeah .already used !gimme to get them

The answer is 252. First note that no $n$ satisfying $\nu_2(n)=1$ can be written in the form $(x+y)(x-y)$ since one of these must have a factor of $2$ and the other doesn't, so $2x$ becomes odd which is a contradiction. Also note that we need to write $1$ and $4$ compulsorily, since these two are the only other numbers which cannot be written as $(x+y)(x-y)$. Therefore $N \geq 252$. To prove that we can write all numbers $\leq 1000$ in the form of $x^2-y^2$, we induct. The base case is clear. Now say that $1,2, \dots, n$ are already written on the board. If $n+1=4m$ for some natural number $m$, we can let $x=m+1$, we can let $x=m+1, y=m-1$ (which were already present on the board). If $n+1=2m+1$ for some $m$, let $x=m+1$ and $y=m$, and we are done by the induction hypothesis. Nice steins;gate reference btw

Firstly,any number of the form $4k+2$, cannot be represented as the difference of two squares.Thus these numbers are already present on the board. However,considering difference of squares among these,numbers of the form $4k+1,4k+3$ cannot be represented.For this ,atleast one number from the two forms must be present .Also,using the numbers that we have selected,their difference of squares is never of the form $8a+4$.Thus,one such number is present as well.So,$N \ge 252$. We can prove this prove this inductively by taking the initial numbers as $1,2,4,6,10,14...998$.Thus,$N=252$ Also,where are the other Inidian EGMO TSTs? thanks@below

Pre-CoViD, the EGMO TST was not conducted separately as the IMO TST served the purpose but since for last 2 years IMO TST could not be done, EGMO TST is done separately. I've posted all of last year's problems, this year's will also follow in 10ish days once the exams are done.

Hououin Kyouma here, the organisation has put another combo problem, but this one doesnt look hard, i dont know what intentions they have in their minds, but its scary. Clearly numbers of the form $2 \pmod{4}$ cant be generated with two distinct numbers, so we need the $250$ numbers of the form $2 \pmod{4}$, also there is no way one can generate $1$ and $4$, so now we have $252$ numbers. Now, any number $>4$ can be generated if we have all the numbers less than it, we can easily generate the numbers $1$, $2$, $3$, $4$ and $5$ and in turn generate all the numbers till $1000$. For a number $k$ which is odd, we let $x+y=k$ and $x-y=1$, and for $4 \mid k$ we just let $x+y=2i$ and $x-y=2j$ where $i > j$. So $N_{\text{min}} = 252$. I really wanna know who proposed this problem such a proposer of culture(i <3 the flavourtext)

Solution: We will show that $N= 252$ is the absolute minimum. Let \[X = \{x: x = 4k+2, k \in \mathbb{Z}, 0 \le k \le 249\}.\]Then $S = \{1,4\} \cup X$ is precisely the set of numbers which are initially written on the board. We now proceed to show that this works. Claim: Any element in $\Phi = \{x: x = 4k+2, k \in \mathbb{Z}_{\ge 0}\} \cup \{1,4\}$ cannot be written as a difference of two squares but every number in $\mathbb{N} - \Phi$ can. Proof: We first show any 2 modulo 4 number can't be written as a difference of two squares. Assume there exists $x,y$ such that $x^2-y^2 = 4m+2$ for some integer $m$, then both of $x$ and $y$ will have the same parity. Reducing equation modulo 4, we get $x^2-y^2 \equiv 2 \pmod{4}$. We know $x^2$ either 0 or 1 modulo 4. This immediately gives us a contradiction. One can check by hand that 4 and 1 can't be written as difference of two squares due to size reason. For other any other number $Z$, we have the following constructions: If $Z = 4l$ for $l > 1$, then we have $(l+1)^2 - (l-1)^2 = 4l$ If $Z = 4l+1$ for $l \ge 1$, then we have $(2l+1)^2 - (2l)^2 = 4l+1$. If $Z = 4l+3$ for $l \ge 0$, then we have $(2l+2)^2 - (2l+1)^2 = 4l+3$. and this proves the claim. $\square$ Observe that 3 will be eventually on the board since $2^2-1^2 = 3$. Also see that 5 will be on the board since $3^2- 2^2 = 5$. So all numbers from 1 to 6 will be there. From there due the above constructions, we know that every other can be written as a difference a of two squares so the given construction works. To prove the minimality, board must that we have every 2 modulo 4 number less than 1000 on the board because they can't be generated via difference of squares which just proved in the claim. Further 1 and 4 also cannot be generated, which means they must be on the board. This means we need at least 252 numbers on the board. Since we have already shown that it works, we are done. $\blacksquare$

Nice Steins Gate reference . Posting for storage

Claim:- 4k +2 can't be constructed Proof:- (x+y)(x-y) = 4k+2 Now note that their parities must be the same so v_2(4k+2) = 2 contradiction so 1000/4 floored = 250 already there Also notice that 1 can't be constructed and 4 cant be constructed so 250+2 = 252 minimum number of moves Also inductively its easy to show all number between 1 and 1000 can be written

OG! The answer is 252. I will give a walkthrough: 1. Notice that initially all numbers of the form $2 \pmod2$ must be there and $1,4$ must also be there. This gives the lower bound of 252. 2. To see this is sufficient see that we can construct $[1,4]$ using these numbers and also if we can construct $[1,4k]$ we can construct $4k+1,4k+2,4k+3,4(k+1)$. Thus, induction on $k$ finishes.