1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you assume that $\prod(A \cup B) = \prod(A) \cdot \prod(B)$? $\endgroup$ – Fabio Somenzi May 18 '19 at 18:39
  • $\begingroup$ @ Fabio Somenzi ,yes $\endgroup$ – Wiliam Mikayla May 18 '19 at 18:43
  • $\begingroup$ Consider $\{2,3,5\}$ and $\{5,6\}$. Then $\prod(\{2,3,5,6\}) = 180$, but $\prod(\{2,3,5\}) = \prod(\{5,6\}) = 30$. $\endgroup$ – Fabio Somenzi May 18 '19 at 18:55
  • $\begingroup$ you right but $L(\prod(\{2,3,5\})) \neq L( \prod(\{5,6\}))$ $\endgroup$ – Wiliam Mikayla May 18 '19 at 19:00
  • $\begingroup$ I think if $A \cap B = \phi $ we can say what i mentioned , so i guess i need to clear $A \cap B \neq \phi $ case , right? , i guess i should replace my equation with $\prod ( (A \cup B ) - (A \cap B))$ $\endgroup$ – Wiliam Mikayla May 18 '19 at 19:07
1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.