Finding the least value of $k$ means find the maximum value of $t$(which not satisfy $x^2|y$) and adding $1$. ${n+1,n+2,,,,,(n-1)^2,n^2}$ is the subset of $X$ from this we can see that $t$ can be $n^2-n$. Lets show $t$ cant be bigger than $n^2-n$, If we can show for $0 \leq k \leq (n-1)$, $(n-k)<(n-k)^2<n^2$ we will be done. $$k<n<2n$$$$k^2-2nk<0$$$$(n-k)^2<n^2$$Thus the maximum value of $t$ is $n^2-n$. Henceforth,the answer is $\boxed{n^2-n+1}$

LeonhardEuler0 wrote: , If we can show for $0 \leq k \leq (n-1)$, $(n-k)<(n-k)^2<n^2$ we will be done. We is this true? I don't aderstand.

P2nisic wrote: LeonhardEuler0 wrote: , If we can show for $0 \leq k \leq (n-1)$, $(n-k)<(n-k)^2<n^2$ we will be done. We is this true? I don't aderstand. Its true because if you want to increase $t$ you have to take extra numbers,it says if you take extra numbers from $[1,n]$ then there is a $y$ such that $(n-k)<(n-k)^2=y<n^2$ So,$y$ or $(n-k)$ has to be deleted. Thus,For each extra number one number has to be deleted so $t$ wont change.If $t$ wont change then you cant increase the value of $t$.So,for all numbers in $[1,n]$ and $[(n+1),n^2]$ are the inverses of each others.I mean if one can then other one cant.So,if we take the interval of $[(n+1),n^2]$,we get $n^2-n+1$.

Lemme provide a cleaner write-up. For $k=n^2-n$, we consider $S=\{n+1,n+2,\dots,n^2\}$, as was done by ``Leo Euler" above (btw why Euler0 but not Euler07 ?) Note that $x^2\mid y$ implies $(n+1)^2 \le x^2\le y \le n^2$, a contradiction; hence $S$ does not satisfy this condition. We now show if $k = n^2-n+1$, then for any $S\subset X$ with $|S|=k$, there exists $x,y\in S$ such that $x^2\mid y$. It is evident that if $1\in S$, the condition holds trivially, hence assume in the remainder that $1\notin S$. Consider pairs $P_i=\{i,i^2\}$, where $2\le i\le n$. Note that for the set $\mathcal{P} = \bigcup_{2\le i\le n}P_i$, \[ |\mathcal{P}| = 2(n-1) - \left(\lfloor \sqrt{n}\rfloor -1\right) = 2n-\lfloor \sqrt{n}\rfloor -1. \]Hence, the set $\{2,3,\dots,n^2\}\setminus \mathcal{P}$ contains $n^2-2n+\lfloor \sqrt{n}\rfloor$ elements. From here, we conclude that $S$ has at least $n-\lfloor \sqrt{n}\rfloor +1$ common elements with $\mathcal{P}$. Now, we ``partition" the pairs in $\mathcal{P}$ into two classes. Specifically, let $C_1$ be the set of all $(i,i^2)$ where (a) $2\le i\le n$ and (b) $i$ is not a square. There are $n-\lfloor \sqrt{n}\rfloor$ such pairs. Likewise, let $C_2$ be the set of all $(i,i^2)$ such that $i=k^2$ for $2\le k\le \lfloor \sqrt{n}\rfloor$. Our goal is to show that $S$ contains both elements of at least one pair. Assume the converse. Let $t$ be the number of elements in $S$ belonging to a pair in $C_2$ (thus we ``sweep" $t$ pairs in $C_2$). Consider such a pair $(k_j^2,k_j^4)$. Note that the corresponding pair $(k_j,k_j^2)\in C_1$. Hence, one must ``kill" $t$ pairs from $C_1$: we are left with at most $n-\lfloor \sqrt{n}\rfloor-t$ such pairs in $C_1$. This will yield a total of at most $n-\lfloor \sqrt{n}\rfloor$ elements; while we have already shown one must take at least $n-\lfloor \sqrt{n}\rfloor +1$ elements from $\mathcal{P}$. A contradiction is reached.

Define $S_2,S_3,\cdots,S_{n^2}$ inductively as follow: $$S_t= \{ t^{2^r} : 1 < t^{2^r} \le n^2, r \in \mathbb Z_{\ge 0} \} - \bigcup_{2 \le j <t} S_j $$Suppose that $Y \subset X$ satisfies the condition, then $|Y \cap S_t| \le 1$ for all $t$. Moreover, $S_t=\varnothing$ if $t$ is a square, since the former set is contained in $S_{\sqrt{t}}$. There are $n-1$ squares between $2$ and $n^2$. Thus $$|Y|=\sum_{2 \le t \le n^2} |Y \cap S_t| \le (n^2-1)-(n-1)=n^2-n$$

Slightly cleaner: Consider two numbers equivalent if $x^{2^m}=y$ for some integer $m$. Clearly, each equivalence class hitting $X$ contains an element from $\{n+1,n+2,\dots,n^2\}$. Hence there can be at most $n^2-n$ equivalence classes hitting $X$. So if our set has $k \ge n^2-n+1$ elements, it has to contain two elements from one class which is what we wanted to prove.

My not-so-elegant solution: The answer is $n^2-n+1$. Firstly, if $k \le n^2-n$, we could select $\{n+1,n+2 ... n^2\}$ (or a subset of it) but even when we pick the least element$, n+1, $ as $ x $ and the greatest element$, n^2,$ as $y$ we still get $(n+1)^2 \le n^2 $, a clear contradiction. Now we will use induction to show that if we chose a subset of $n^2-n+1$ elements, the condition will always be satisfied. For $ n=2 $, with $ X= \{1,2,3,4\} $, it can be manually checked and seen that the condition is satisfied. Now for the inductive step assume the condition is satisfied for $m$. For $ m+1 $, we will have $X=\{1,2,...,(m+1)^2\}=\{1,2,...,m^2\} \cup\{m^2+1,m^2+2,...,(m+1)^2\}$ Let $A=\{1,2,...,m^2\} $ and $B=\{m^2+1,m^2+2,...,(m+1)^2\}$ and let the subset of $X$ we are working with be $C$. Now $C$ will have $(m+1)^2-(m+1)+1=m^2+m+1$ elements. If $C$ has at least $m^2-m+1$ elements from $A$, the condition will be satisfied because of the induction hypothesis. Assume otherwise, meaning that $C$ will have all $2m+1$ elements from $B$, and $m^2-m$ elements from $A$. We will divide the situation into two cases: 1) $m+1\in C$: Take $m+1$ as $x$ and $(m+1)^2$ as $y$ and we are done. 2) $m+1\notin C$: If the condition is already satisfied within the $m^2-m$ elements of $C$ from $A$, we are done. Assume it is not. So if we add any new element from $A$, the condition must be satisfied due to the induction hypothesis because then we will have $m^2-m+1$ elements from $A$. Let that number be $m+1$, meaning there either exists an $x$ already in $C$ such that $x^2 | m+1$ or a $y$ such that $(m+1)^2 | y$. But the latter is impossible within $A$ (due to the same inequality we showed at the beginning). So, the former must be true. Let's take that same $x$ and its square will divide $(m+1)^2$ as it also divides $m+1$. And we are done.