# Prove or disprove there always exists a subset $S'\subset S$ where product of all the elements in $S'$ is a perfect square where $S$ is …

Question: Assume you choose a multiset [elements of $S$ are not necessarily distinct] ($=S$) of arbitrarily chosen $1986$ positive integers so that the number of distinct prime factors of all those numbers is $1985$. Prove or disprove there always exists a subset $S' \subset S$ where product of all the elements in $S'$ becomes a perfect square.

I believe that it also uses the pigeon hole principle.

• Wait, so what if I decide to put only distinct prime numbers in S, except for one that's a product of two primes? – greenturtle3141 Apr 29 '17 at 3:20
• @greenturtle3141 Maybe I didn't state the question clear enough again. The problem is to prove/disprove for all possible cases of $S$ that meets only the condition that those have $1985$ distinct prime factors. So your example is just one of those cases. – Kay K. Apr 29 '17 at 3:26
• Actually I translated this question from a foreign language, so my description may not be super clear. If anyone can improve, it would be appreciated. – Kay K. Apr 29 '17 at 3:31

Does this problem date from 1986?

Anyway, this is just linear algebra modulo $2$. Let the numbers be $a_1,\ldots,a_m$ ($m=1986$) and the primes be $p_1,\ldots,p_n$ ($n=1985$). Write $$a_i=p_1^{c_{i,1}}p_2^{c_{i,2}}\cdots p_n^{c_{i,n}}.$$ This defines $m$ vectors $\mathbf{c}_k=(c_{i,1},\ldots,c_{i,n})$. OK, these are vectors with integer coordinates, but think of them as vectors over the finite field $\Bbb F_2=\Bbb Z/2\Bbb Z$ of integers modulo $2$. As $m>n$ they are linearly dependent; there are $b_1,\ldots,b_m\in\{0,1\}$ with $\sum_i b_i \mathbf{c}_i=(0,\ldots,0)$ as vectors over $\Bbb F_2$. Now think about $a_1^{b_1}a_2^{b_2}\cdots a_m^{b_m}$.

• Thanks a lot. Would there be another solution using combinatorics? – Kay K. Apr 29 '17 at 4:09
• Actually this is a problem given to high school students (maybe a math contest). I've been struggling to convert your solution to something that can be accepted as a high school level solution. I am stuck at the step to prove that all $b_k$'s are either $0$ or $1$, or, to prove that inverse matrix of a $(0,1)$ matrix over $\mathbb{GF}_2$ has only $0$ or $1$ as its elements, or, etc. Please give me any advice. – Kay K. May 1 '17 at 2:04

I could convert the other answer (by Lord Shark the Unknown) into a solution using combinatorics, so let me post here. (I also generalized to $n=1985$ and $n+1=1986$ here.)

There can be $2^n$ distinguishable (in terms of whether each exponent is even or odd) numbers for products of $a_i$'s.

Now remove one number $q$ and choose $m$ numbers out of the rest of $n$ $a_i$'s and get a product. The total number of cases is:

$$\sum_{m=0}^n \binom{n}{m}=2^n$$

Therefore, one of those products is not distinguishable from $q$. Multiplying the product and $q$ gives us a perfect square.