A set of numbers whose product is a square Let $p_{1}, . . . p_{10}$ be a set of ten prime numbers. We can
construct $1023$ integer numbers by choosing any non empty subset of this
set and multiplying all numbers in this subset. Find the smallest number
$k$ that satisfies the following condition, if you choose any $k$ numbers from
those $1023$ numbers then it is possible to find a non-empty subset of those
$k$ numbers such that the product of the numbers in this subset is an exact
square.
 A: Here is a way to convert this to a linear algebra question.
Let $S$ be the set of 1023 numbers and $\mathbb{F}_2$ denote the field with two elements.  Consider the map given by
$$
\begin{array}{rcl} S&\longrightarrow&\mathbb{F}_2^{10}\\p_1^{e_1}p_2^{e_2}\cdots p_{10}^{e_{10}}&\longmapsto&(e_1,e_2,\ldots,e_{10}).\end{array}
$$
Note that a subset, $U$, of $S$ contains a subset whose product is a square iff the image of $U$ under the above map is linearly dependant.
A: I guess this is a trick question. 
For $p_i$ co-prime $p_j$, which is not implied by the question, you would never find an exact square, there are simply not enough factors in the product that appear twice.
So a first step would be to check whether all prime numbers $p_1, .., p_{10}$ are distinct. If this is the case you can already answer the question to the negative.
BTW: The problem appears here, I am only beginning to understand algorithms,
and would be interested in any newer developments along it.
Borodin, A., Fagin, R., Hopcroft, J.E. and Tompa, M. (1985):
Decreasing the Nesting Depth of Expressions Involving Square Roots,
J . Symbolic Computation (1985) 1, 169-188
http://www.sciencedirect.com/science/article/pii/S0747717185800134
(See section 3. Finding a Perfect Square Among Products of a Set of Numbers)
