0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wait, so what if I decide to put only distinct prime numbers in S, except for one that's a product of two primes? $\endgroup$ – greenturtle3141 Apr 29 '17 at 3:20
  • $\begingroup$ @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. $\endgroup$ – Kay K. Apr 29 '17 at 3:26
  • $\begingroup$ 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. $\endgroup$ – Kay K. Apr 29 '17 at 3:31
2
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ Thanks a lot. Would there be another solution using combinatorics? $\endgroup$ – Kay K. Apr 29 '17 at 4:09
  • $\begingroup$ 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. $\endgroup$ – Kay K. May 1 '17 at 2:04
0
$\begingroup$

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.

$\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.