Suppose $S \subset \{1,2,3,\ldots, 200\}$ such $|S|=50 $. Prove there exist a non empty subset of $S$ such that the product of its elements is a perfect square.
I have a solution, but I want to know whether there any flaw in it, because I think we could solve this question using pigeonhole too, and maybe it is the only way, but I used contradiction. I'd really appreciate if you could help me to check my solution, thanks.
Assume to the contrary it is not true, thus there is no non empty subset of $S$ such its elements' product is a perfect square. If $A \subset S$, we denote the product of its elements by $\prod A$. Now suppose $P_1,P_2,\ldots,P_{46}$ are the primes smaller than $200$. Thus, for any subset of $S$, $\prod A$ has the $P_1^{\alpha_1}P_2^{\alpha_2} \cdots P_{46}^{\alpha_{46}}$ form. Define the map $L: \prod A \to (b_1,b_2,\ldots,b_{46})$ such that $b_i=0 \iff \alpha_i \equiv 0 \pmod{2}$ and $b_i=1 \iff \alpha_i \equiv 1 \pmod{2}$. Now since there is no subset such $\prod A$ is a perfect square, there always exists an $\alpha_i$ such that it is a an odd number. We know for our map, we have at most $2^{46}$ values, and since $2^{46} \le 2^{50}-1$, there exist two distinct non empty subsets $A,B \subset S$ such $L (\prod A) = L (\prod B)$.Now we can write $$L( \prod (A- (A \cap B )) )=L( \prod A)-L( \prod (A \cap B))=L( \prod B)-L( \prod (A \cap B))=L( \prod (B- (A \cap B )) )$$ Since adding two odd numbers gives an even number and adding two even numbers gives the same result, $\prod ( (A \cup B ) - (A \cap B))$ is a perfect square which is a contradiction.
This is almost correct: When you do $\Pi (A\cup B)$ it should really be $A\otimes B $ where the symbol in the middle means XOR. (think about why this is needed). Otherwise, it looks good!