Perfect square product among 17 integers

Question

Using pigeon hole principle prove that:
a) among 17 positive integers solely consisting of prime factors 2,3,5,7 product of two of them is a perfect square
b) among 49 positive integers solely consisting of prime factors 2,3,5,7 product of four of them is 4th power of a positive integer.

Please judge my solution for part a: because we have more than 2 numbers and hence more than 2 different powers for each prime in each number,so certainly there are at least 2 odd or 2 even powers for each prime in 17 numbers,so the product of such numbers is certainly perfect square.
By the way,I have no solution for part b.

Answer 1

Solution for b): For a solution we will use a). Say a pair of numbers $x,y$ is good if their product is a perfect square.

From $49$ numbers take any $17$ numbers, then we have a good pair $a_1,a_2$ among them.

Now from the rest of the $47$ numbers take any $17$ numbers, then we have a good pair $a_3,a_4$ among them.

Now from the rest of the $45$ numbers take any $17$ numbers, then we have a good pair $a_5,a_6$ among them.

and so on. We repeat this process until we get last good pair $a_{33},a_{34}$ (and we are left wit $15$ numbers so that we can't repeat the process).

Now calculate their products $b_i:=a_{2i-1}a_{2i}$. So we have $17$ perfect squares $b_1,b_2,...b_{17}$. Each $b_i$ we can write like this

$$b_i = 4^x 9^y 25^z 49^t$$

Again we assign to each $b_i$ $4$-tuple $(x',y',z',t')$ where $w'$ is remainder of $w$ modulo $2$. Again two of the $b_i$ must have the same $4$-tuple, since we have $17$ numbers and only $16$ $4$-tuples. So, their product is perfect $4$-power.

Answer 2

For a)

Let's $M$ be the set of that $17$ numbers and make a map $\phi : M\to \mathbb{Z}_2^4$ such that each $$2^a3^b5^c7^d \mapsto (a_{\pmod 2}, b_{\pmod 2}, c_{\pmod 2}, d_{\pmod 2})$$ Then since $|\mathbb{Z}_2^4|=16$ we have $m\ne n$ such that $\phi (m) =\phi (n)$, thus $m\cdot n $ is a perfect square.

---

So we assign to each number $2^a3^b5^c7^d$ in $M$ a $4$-tuple $(a',b',c',d')$ where $x'$ is $0$ if $x$ is even and $1$ if $x$ is odd, for each $x\in\{a,b,c,d\}$. Now since the number of all such $4$-tuples is $16$ and we have $17$ numbers, two of them must have the same $4$-tuple and therefore their product is a perfect square.

Answer 3

a) Let's define the function:
$f:\{n\in\mathbb{N} | (d, t, f, s) \in \mathbb{N}^4$ and $n= 2^d*3^t*5^f*7^s\} \to (\mathbb{Z}/2\mathbb{Z})^4$
$n\mapsto f(n)=(\bar d, \bar t, \bar f, \bar s)$
where d is the power of 2 in n; ($d \equiv \bar d [2]$ )
t is the power of 3 in n; ($t \equiv \bar t [2]$ )
f is the power of 5 in n; ($f \equiv \bar f [2]$ )
s is the power of 7 in n. ($s \equiv \bar s [2]$ )
$f(2)=(\bar 1,\bar 0,\bar 0,\bar 0); f(3)=(\bar 0,\bar 1,\bar 0,\bar 0); f(6)=(\bar 1,\bar 1,\bar 0,\bar 0)$; etc.

Check that $f(n_1*n_2)=(\bar d_1+\bar d_2, \bar t_1+\bar t_2, \bar f_1+\bar f_2, \bar s_1+\bar s_2)$
Check that $f(p)=(\bar 0,\bar 0,\bar 0,\bar 0) \iff$ p is a square.

$ Card((Z/2Z)^4)$ is $2^4$, so there are at most 16 distinct values for f(n). Using the pigeonhole principle, out of 17 integers, at least two of them share the property $f(n_1)=f(n_2)$.
$\begin{align} f(n_1*n_2) & =(\bar d_1+\bar d_2, \bar t_1+\bar t_2, \bar f_1+\bar f_2, \bar s_1+\bar s_2) \\ & =(2*\bar d_1, 2*\bar t_1, 2*\bar f_1, 2*\bar s_1) \\ & =(\bar 0, \bar 0, \bar 0, \bar 0) \end{align}$

... which shows that $n_1*n_2$ is a square.

b) Use the same function as in a). Using the pigeonhole principle, out of 49 integers, at least four of them share the property $f(n_1)=f(n_2)=f(n_3)=f(n_4)$. (put 3 items in 16 boxes, that makes 48 items; now the 49th item must fit in a box where there are already three of them).

$\begin{align} f(n_1*n_2*n_3*n_4) & =(\bar d_1+\bar d_2+\bar d_3+\bar d_4, \bar t_1+\bar t_2+\bar t_3+\bar t_4, \bar f_1+\bar f_2+\bar f_3+\bar f_4, \bar s_1+\bar s_2+\bar s_3+\bar s_4) \\ & =(4*\bar d_1, 4*\bar t_1, 4*\bar f_1, 4*\bar s_1) \\ \end{align}$

... so, if I write (back in $\mathbb{N}$) $n_1*n_2*n_3*n_4$ in the form of $2^d*3^t*5^f*7^s$, then we know from above that d, t, f, s are all multiples of four. We have found at least one product of four numbers that is the fourth power of an integer.

I hope this helps!

Answer 4

This approach is not different from the others proposed, but I wanted to illustrate a point which may help you to express yourself.

The point is that we can start with a definition, and if we are clear about that, other things fall more easily into place.

So if $n=2^a3^b5^c7^d$ we define the signature of $n$ to be $(a, b, c, d) \bmod 2$ meaning that each entry in the signature is $0$ or $1$ depending on whether each of $a, b, c, d$ is respectively even or odd.

There are sixteen $(2^4)$ possible signatures, so amongst the seventeen numbers two of the signatures must be equal. When you multiply two numbers with equal signatures together you get a number with zero signature. And a number with zero signature has every exponent even, and therefore must be a square.

I wanted to illustrate what was in my comment, and also to show that if there is something slightly complicated, giving it a name means you only have to deal with the complications once.

For the second bit, John Watson has shown how to take out seventeen pairs which multiply to give a square. You might use the factorisation $4^a9^b25^c49^d$ to define the "second signature" or some such, and the same argument essentially goes through to give you a fourth power.