Needlessly pretentious write-up Let $p_1<p_2<\dots$ be the sequence of prime numbers. Denote by $\mathbb{F}_2^{\omega}$ the $\mathbb{F}_2$ vector space of all binary sequences $(a_1, a_2, \dots)$ with entries in $\mathbb{F}_2$. Consider the set map $\Phi: \mathbb{N} \rightarrow \mathbb{F}_2^{\omega}$ defined by $$\Phi(n) := (v_{p_i}(n) \pmod{2})_{i \geq 1}$$for all $n \in \mathbb{N}$. It is clear that for $x, y \in \mathbb{N}$, the product $xy$ is a perfect square if and only if $\Phi(x)=\Phi(y)$. So we want $|\Phi(S)| \geq 4$. Indeed, decompose $S$ as a union of fibres, $S = \cup_{a \in \Phi(S)} \Phi^{-1}(a)$. Each fibre with size $r$ accounts for $2\binom{r}{2}+r=r^2$ pairs towards the count, so if $\Phi(S)$ has at most three elements, then $a^2+b^2+c^2=2023$ has a solution in non-negative integers. This is a contradiction mod $8$, by simply checking that no triple formed using one of $\{0, 1, 4\}$ can add to $7$ mod $8$. Note. The four-squares theorem states that every non-negative integer can be written as a sum of at most four squares. The only numbers which require exactly four squares are numbers of the forms $4^m(8k+7)$, so $2023$ is one of them! Rejoice, this won't happen again for eight years or so.

A bit less fancy notation: We call two numbers $x,y$ equivalent iff their product is a perfect square. Easy to check that this defines an equivalence relation (i.e. symmetric, reflexive, transitive), hence we can partition $S$ into equivalence classes of $r_1,r_2,\dots,r_k$ elements. Then $r_1^2+r_2^2+\dots+r_k^2=2023$ and hence $k \ge 4$ by mod $8$.

Consider the graph $G$ induced by the elements of $S$ and edges being if the products are perfect squares. Note that if $xy = a^2$ and $xz = b^2$, then $yz = \left( \frac{ab}{x} \right)^2$, since its an integer and square of a rational number its a perfect square and so $yz$ is an edge too. So the graph is a bunch of disjoint cliques, say with sizes $c_1, c_2, \cdots, c_k$. Then $\sum_{i=1}^k c_i^2 = 2023$, which implies $k \geqslant 4$ since $2023 \equiv 7 \pmod 8$. Now pick one element from each of these cliques and it works.

My solution but essentially same as everybody else's We say $x\sim y$ if $xy$ is a square. Now observe that $x\sim y$, $y\sim z$ $\implies x\sim z$ and $x\sim y\implies y\sim x$. Also $x\sim x$ for all $x$. Thus, $\sim$ is an equivalence relation and we need to just show that $S$ has atleast $4$ equivalence classes under this relation. FTSOC, let there be three classes(possibly empty) say $S_1$, $S_2$, $S_3$ with sizes $s_1$, $s_2$, $s_3$. Now, we have that $2023=s_1^2+s_2^2+s_3^2$. This is not possible since $2023\equiv 7\pmod 8$ and squares are either $0$, $1$, or $4$ $\pmod{8}$ and thus the sum of three squares cannot be $7\pmod{8}$. $\square$

My first and only incontest solve Really nice problem though Draw graph with S as vertex set and join x and y iff their product is a square and they are distinct Say S has n elements Then number of ordered pairs = n + 2(no. Of edges) Now main thing is that each connected component is a complete graph Which can be proved by noting that if xy and xz are squares so is yz and then taking any path and inducting up So if we had only 3 connected components we would need to solve a^2+b^2+c^2=2023 But then all of these must be 1 mod 4 and so writing them as a=4x+1 and so on, and subtracting 3 from both sides we will see that both sides are different mod 8 (4 vs 0)

anantmudgal09 wrote: Needlessly pretentious write-up Let $p_1<p_2<\dots$ be the sequence of prime numbers. Denote by $\mathbb{F}_2^{\omega}$ the $\mathbb{F}_2$ vector space of all binary sequences $(a_1, a_2, \dots)$ with entries in $\mathbb{F}_2$. Consider the set map $\Phi: \mathbb{N} \rightarrow \mathbb{F}_2^{\omega}$ defined by $$\Phi(n) := (v_{p_i}(n) \pmod{2})_{i \geq 1}$$for all $n \in \mathbb{N}$. It is clear that for $x, y \in \mathbb{N}$, the product $xy$ is a perfect square if and only if $\Phi(x)=\Phi(y)$. So we want $|\Phi(S)| \geq 4$. Indeed, decompose $S$ as a union of fibres, $S = \cup_{a \in \Phi(S)} \Phi^{-1}(a)$. Each fibre with size $r$ accounts for $2\binom{r}{2}+r=r^2$ pairs towards the count, so if $\Phi(S)$ has at most three elements, then $a^2+b^2+c^2=2023$ has a solution in non-negative integers. This is a contradiction mod $8$, by simply checking that no triple formed using one of $\{0, 1, 4\}$ can add to $7$ mod $8$. Note. The four-squares theorem states that every non-negative integer can be written as a sum of at most four squares. The only numbers which require exactly four squares are numbers of the forms $4^m(8k+7)$, so $2023$ is one of them! Rejoice, this won't happen again for eight years or so. Almost same sol.

More or less same as above sols.. Consider the graph $G$ with vertices as elements of $S$. We say that any two vertices $x$ and $y$ share an edge if their product is a perfect square. Notice that if $x$ share an edge with $y$ and $z$ then the subgraph induced by vertices $x$, $y$ and $z$ is connected. Assume there are $3$ connected components in $G$ with sizes $s_1$, $s_2$ and $s_3$. Then, $s_1^2+s_2^2+s_3^2=2023$ which doesn't have any solutions by three square theorem or using$\pmod 8$.

Nice problem!

Cool problem.

anantmudgal09 wrote: Needlessly pretentious write-up Let $p_1<p_2<\dots$ be the sequence of prime numbers. Denote by $\mathbb{F}_2^{\omega}$ the $\mathbb{F}_2$ vector space of all binary sequences $(a_1, a_2, \dots)$ with entries in $\mathbb{F}_2$. Consider the set map $\Phi: \mathbb{N} \rightarrow \mathbb{F}_2^{\omega}$ defined by $$\Phi(n) := (v_{p_i}(n) \pmod{2})_{i \geq 1}$$for all $n \in \mathbb{N}$. It is clear that for $x, y \in \mathbb{N}$, the product $xy$ is a perfect square if and only if $\Phi(x)=\Phi(y)$. So we want $|\Phi(S)| \geq 4$. Indeed, decompose $S$ as a union of fibres, $S = \cup_{a \in \Phi(S)} \Phi^{-1}(a)$. Each fibre with size $r$ accounts for $2\binom{r}{2}+r=r^2$ pairs towards the count, so if $\Phi(S)$ has at most three elements, then $a^2+b^2+c^2=2023$ has a solution in non-negative integers. This is a contradiction mod $8$, by simply checking that no triple formed using one of $\{0, 1, 4\}$ can add to $7$ mod $8$. Note. The four-squares theorem states that every non-negative integer can be written as a sum of at most four squares. The only numbers which require exactly four squares are numbers of the forms $4^m(8k+7)$, so $2023$ is one of them! Rejoice, this won't happen again for eight years or so. What does $$ v_{p_i}(n)$$in $$\Phi(n) := (v_{p_i}(n) \pmod{2})_{i \geq 1}$$mean

Is Indian NO problems for 2 days or for only one?

It is one day

My solution is necessarily the same as everyone else on this post, but I'll still post it anyways. Consider the relation $R: S\rightarrow S$ defined as $R=$ {$(a,b) : ab=q^2; q\in \mathbb{N}$} It is easy to see that $R$ is an equivalence relation. Now FTSOC, we assume that $R$ can have $\leq 3$ distinct classes. Let the classes have sizes $a,b,c$ such that $a,b,c \in \mathbb{N}\cup 0$. Now notice that any such class of size $k$ has $k^2$ elements. So we have $a^2+b^2+c^2=2023$. Now we consider the above equation as a congruence, modulo $8$. The quadratic residues modulo $8$ are $0,1,4$, while $2023 \equiv -1 \pmod 8$. This is a contradiction. Thus there must be $>3$ classes. Now we take any element from each of these classes. We can find atleast $4$ elements. We cannot form any pair out of these $4$ which make a perfect square, or our proof that there are $>3$ such classes contradicts.

I also will post a solution even if it has been posted by someone before Say , $|S| = k$ and we denote each number with a vertex and we join two vertex iff their product is not a perfect square. We name this graph $G$. Now we claim that $G$ is a multipartite graph with atleast $4$ disjoint sets of vertices. Claim: $G'$ is a union of disjoint cliques.where $G'$ is the complement of the graph $G$ Proof: Note that if $ab$ and $bc$ are perfect squares then $ac$ is also a perfect square. The claim follows from here. Claim: Now, note that number of edges in $G'$ is $\frac{2023-k}{2}$. If there are three such disjoint cliques in $G'$ with sizes $a,b,c$ then $\binom{a}{2}+\binom{b}{2}+\binom{c}{2} = \frac{2023-k}{2}\implies a^2+b^2+c^2 = 2023$ as $a+b+c = k$ now this is not possible by simple $\pmod 8 $ argument . For the case of $2$ cliques $a^2+b^2 = 2023$ which is again not possible by $\pmod 4 $ argument and only one clique is definitely not possible as $2023$ is not a perfect square. So there must be atleast $4$ disjoint cliques in $G'$ and no vertex between them are interconnected. So , take one vertex from each clique and they will be all connected mutually in $G$ and hence done. @below ohh right

@above you don't need to check for all possible numbers of cliques; just three is enough, since the zero case is covered in that

Let $f(m)$ be the number of elements in $S$ with squarefree part $m$ then we just want to prove that there are at least $4$ values of $m$ such that $f$ is non-zero note that the ways is just $f(1)^2+f(2)^2+f(3)^2+f(5)^2+f(6)^2+f(7)^2+f(10)^2+\dots$ $2023$ isn't a square $2023$ isn't a sum of $2$ positive squares cuz $\pmod{4}$ $2023$ isn't a sum of $3$ positive squares cuz $\pmod{8}$ therefore done

We draw a graph with vertices as the numbers in $S$, and an edge is drawn between $x$ and $y$ iff $xy$ is a perfect square. Note that each connected component is a clique. Let there be, FtSoC, at most $3$ cliques with $a, b, c$ vertices respectively. The counting gives us $a^2 + b^2 +c^2 = 2023$, impossible due to $\pmod{8}$. $\square$

did this like three months ago but forgot to post Fix $p_1, p_2, \ldots, p_k$ as primes that divide $\prod S$. For each $x \in S$, we can assign a vector with only zeroes or ones of length $k$ so that the $i$th element of this vector is $0$ if $\nu_{p_i}(x)$ is even, and $1$ otherwise. Call these vectors $v_1, v_2, \ldots, v_{|S|}$. We are trying to find four of the $|S|$ vectors so that no two are the same. Suppose there were at most three different vectors. Let $\mathbf u, \mathbf v, \mathbf w$ be the three vectors. There are $2023$ ordered pairs $(v_i, v_j)$ such that $v_i = v_j$. Now, if $a,b,c$ are the number of vectors in $S$ equal to $\mathbf u, \mathbf v, \mathbf w$, respectively. Note that $2023 = a^2 + b^2 + c^2$, which is not possible since $2023 \equiv 7 \pmod 8$.

Say a pair of natural number(s) $(a,b)$ is "good" if $ab$ is a perfect square and $a,b \in S$. Let $G$ be a simple graph containing $v_1,v_2,\cdots,v_{|S|}$, where $v_i$ denotes the $i^{th}$ smallest element in $S$. The pair of distinct vertex $v_i \sim v_j$ if and only if the number represented by them makes a good pair. Let the number of edge(s) in $G$ be $e$, notice that there are exactly $e$ distinct unordered good pair not in the form of $(n,n)$ and exactly $|S|$ good pair in the form of $(n,n)$. Hence we obtain $$2e+|S|=2023 \Rightarrow |S|=2023-2e$$. So the number of vertex in $G$ is $2023-2e$. Next, we observe that if $(a,b)$ and $(a,c)$ is a good pair then $(b,c)$ must also be a good pair. So if $v_i \sim v_j$ and $v_i \sim v_k$, then $v_j \sim v_k$. We can prove that every connected component in $G$ is a clique by considering the path in every connected component. We can split $G$ into several connected components where each component are pairwise disconnected. Say the size is $a_1,a_2,\cdots,a_k$. What we want to prove is that $k \ge 4$, because if $k\ge 4$ we can take one vertex from each group that forms the desired construction. Notice that $a_1+a_2+\cdots+a_{k}=2023-2e$, and the number of edge(s) in $G$ is exactly $$\sum_{i=1}^{k} \binom{a_i}{2} =e \Rightarrow \sum_{i=1}^{k} \frac{a_i^2-a_i}{2}=e $$$$\Rightarrow \left(\sum_{i=1}^{k} \frac{a_i^2}{2}\right)-\frac{2023-2e}{2}=e \Rightarrow \sum_{i=1}^{k} a_i^2=2023$$. Now use modulo $8$ to prove the case $k\le 3$ is impossible, and we are done .

Consider a graph G of n vertices labeled with some positive integers in S such that the problem condition is true (i.e precisely 2023 order pairs). Now draw an edge between two labeled vertices if their product is a square. Now note that if (x,y) is a valid pair, then (y,x) is one, too. So, two times the number of edges gives the number of ordered pairs (x, y) such that x is not equal to y. But note that we also need to add the number of pairs (x, x) and for that we can just add the number of vertices (because each labeled vertex x has only one ordered pair of form (x, x) so n + 2|E| = 2023. according to the question condition Now comes the most (probably) crucial steps : if xy is a square and yz is a square then xz is also a square (provable using fundamental theorem of arithmetic) So in the graph if vertex (m1, m2) are joined and (m2, m3) are joined, then (m1, m3) are joined.(3 clique) Now note that the graph can't have more than 4 individual components otherwise just pick 1 labeled vertices each from 4 individual components and we are done. Also note that the graph is made up of only complete graphs (because of it being made up of either free vertices, free component of 2 vertices joined by an edge, complete graphs because if a vertex is joined to 3 clique then all the vertices of 3 clique are joined to that vertices to form a 4 clique and so by induction there are only complete graphs) so we can write |E| = a1Choose2 + a2Choose2 + a3Choose3 +...... but since FTSOC we need less than 4 individual components we have |E| = a1Choose2 + a2Choose2 + a3Choose3 Where 0 <= a1,a2,a3 <= n and a1 + a2 + a3 = n. So after simplifications in n + 2|E| = 2023 we find that a1^2 + a2^2 + a3^2 = 2023 but note that this is not possible by quadratic residues mod 8 and hence its a contradiction so we need to have at least 4 individual components which after selecting 1 edge from each component gives the desired result. Comment:- Nice problem and Nice practice

Consider the obvious graph theory interpretation. Note that if the edges $v_1v_2$ and $v_2v_3$ exist, then so do $v_2v_3$. Extending this argument, we have that any connected component is a clique. If a vertex outside this clique is adjacent to a vertex of this clique, then obviously it must be a adjacent to all the other vertices, so the vertex is not actually outside the clique. Hence the graph is a disjoint union of $k$ cliques, where $k$ is a natural number. Obviously, any $(x,y)$ belong to the same clique, so there are $\sum{s_i}^2$ edges, where $s_i$ is the size of the $i^{th}$ clique. Now modulo $8$ gives a contradiction.

Draw an edge b/w two vertices if their product is a perfect square. just notice that the graph is just separated cliques (complete subgraphs) and pick one vertice from each clique which is possible unless there are only 3 such "separated" cliques, which is a contradiction by mod 8