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.

  • 2
    $\begingroup$ Since you tagged it with pigeonhole-principle, maybe you could be a bit more explicit about exactly what your pigeon holes are. I can see that somewhere behind your text all the right ideas are present, but I can't quite see that you have put them together the right way. $\endgroup$ – Arthur Dec 15 '17 at 16:15
  • $\begingroup$ Not following your solution for $a$. You are right to look at the parity of the exponents, and as there are two options for parity and four primes there are $2^4=16$ possible parity choices. As you have $17$ numbers.... $\endgroup$ – lulu Dec 15 '17 at 16:16
  • $\begingroup$ @Arthur The holes are possible remainders modulo 2 $\endgroup$ – Hamid Reza Ebrahimi Dec 15 '17 at 16:17
  • $\begingroup$ @lulu So do you think part might be true for 3 numbers instead of 17?! $\endgroup$ – Hamid Reza Ebrahimi Dec 15 '17 at 16:18
  • $\begingroup$ The possible remainders of what modulo 2? The chosen numbers? That's only two holes. Be explicit, please. $\endgroup$ – Arthur Dec 15 '17 at 16:18

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.

  • 1
    $\begingroup$ Thank you so much dear John:) $\endgroup$ – Hamid Reza Ebrahimi Dec 15 '17 at 18:38

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.

  • $\begingroup$ Please state your answer in a more elementary manner,this problem is for high school math olympiad,thank you $\endgroup$ – Hamid Reza Ebrahimi Dec 15 '17 at 16:56
  • $\begingroup$ You know,I know nothing about mapping,$\Bbb Z^4,|\Bbb Z|$,... $\endgroup$ – Hamid Reza Ebrahimi Dec 15 '17 at 17:00
  • 1
    $\begingroup$ I have edit it . $\endgroup$ – Aqua Dec 15 '17 at 17:03
  • $\begingroup$ Dear John,would you please provide a hint for part b) too? $\endgroup$ – Hamid Reza Ebrahimi Dec 15 '17 at 17:19
  • $\begingroup$ I'm thinking about it. $\endgroup$ – Aqua Dec 15 '17 at 17:19

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.

  • $\begingroup$ This is almost exactly how I saw it in my head. The other answers are a bit too... erudite for my tastes. This is the kind of thinking that to me is meant to be used for high school math olympics. This answer also makes it clear why 17 is the amount of distinct numbers needed to make it true. $\endgroup$ – Todd Wilcox Dec 15 '17 at 21:45
  • $\begingroup$ Indeed your answer helps a lot to understand John's answer better, thanks. $\endgroup$ – Hamid Reza Ebrahimi Dec 16 '17 at 3:41

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!

  • $\begingroup$ Your notation is not clear to me: for example what do you mean by $\overline 0$ $\endgroup$ – Hamid Reza Ebrahimi Dec 15 '17 at 17:45
  • $\begingroup$ This way, you make the difference between a number in N (no bar) and a number in Z/2Z (with a bar). $\endgroup$ – Taamer Dec 15 '17 at 17:46
  • 1
    $\begingroup$ I like this answer the best. It treats (b) in exactly the same way as (a), no fancy tricks needed. It also reveals where the number 49 came about: 3*2⁴ + 1. $\endgroup$ – Jimmy He Dec 15 '17 at 22:06

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.