0
$\begingroup$

Let $S = \{1, 2, \dots, 24, 25\}$. Show that for any subset $R \subset S$ with $|R| = 14$, there are $a,b \in R$ such that $a|b$.

I know that it is a pigeonhole problem but i don't know how to solve it.

Can anyone give me any hint ?

$\endgroup$
  • 1
    $\begingroup$ Can you clarify what you mean by "taken 14?" I assume you mean "take 14 of the numbers that fall between 1-25," but I'm not sure. $\endgroup$ – Florian D'Souza Oct 13 '14 at 18:53
  • $\begingroup$ yes, 14 numbers that fall between 1-25 $\endgroup$ – Carlos Oct 13 '14 at 18:56
10
$\begingroup$

Label $13$ pigeonholes with the odd numbers $1,3,5,...,25$. In the pigeonhole labelled $2i+1$, put the numbers $(2i+1)\times 2^j \;\; (j=0,1,2,...)$. Then:

  • each positive integer $\le 25$ occurs in exactly one pigeonhole;
  • if two numbers are in the same pigeonhole, then one is a multiple of the other.

Which is all we need.

$\endgroup$
3
$\begingroup$

Let us try to pick as many numbers as possible without multiples from 1 to 25.

First, we shouldn't pick 1, as we could not go on.

Second, any prime number from 13 onwards essentially comes free, so we include 13, 17, 19, 23.

Third, we should include 16 and 25, as no candidate is a multiple of 16, and its a prime power (we couldn't gain more than 1 by avoiding it).

So in are 13, 16, 17, 19, 23, 25 and out are 1, 2, 4, 5, 8.

Next, 14, 18, 20, 22 and 24 should go in (same reasoning as for 16, we cannot gain more than 1 by excluding them).

So in are 13, 14, 16, 17, 18, 19, 20, 22, 23, 24, 25 and out are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.

Now adding 21 and 15 remains, so it should follow that [13,25] is the maximum choice.

And now that I've typed this all, I presume that this no accident..

$\endgroup$
1
$\begingroup$

Define property $P$ of a finite set of numbers $S_n$ such that $S$ has property $P$ if no element of $S$ divided another element of $S$. And say $M(N)$ is the set with largest size such that $M(N)$ has property $P$ and $\forall M_n \in M(N): M_n < N$. Thus we are interested in the size $C(N)$ of the set $M(N)$ or $N=25$, because any set of numbers not exceeding $N$ that has more than $C(N)$ elements cannot have property $P$, and thus if you have $C(N)+1$ numbers from 1 to $N$, at least one of them must be a multiple of another.

There may, of course, by several sets $M(N)$, having in common property $P$ and having the same size. We can talk about the collection of sets $\left\{ M(N) \right\}$.

A first observation will be that $1$ will not be an element member of any member of $\left\{ M(N) \right\}$.

A second observation is that some member $\left\{ M(N) \right\}$ contains all numbers $k\leq N$ of the form $p^r$ where $p$ is a prime and $r$ is the highest integer such that $p^r \leq N$. You can see this because if a element $m$ of $\left\{ M(N) \right\}$ does not contain $k$ nor any divisors of $k$, you could add $k$ to that set (contradicting the premise that $m$ is in $\left\{ M(N) \right\}$. And if $m$ does contain a divisor $d$ of $k$, then it can contain at most one such divisor, and you could replace that element with $k$ -- if $d$ did not divide any other element of $m$, then $k$ will not either.

So there is a member of $\left\{ M(N) \right\}$ containing all numbers of the form $p^r$ where $p$ is a prime and $r$ is the highest integer such that $p^r \leq N$. Let's call such a member $M^*(N)$. In particular for $N=25$, $$M^*(25) \supset \left\{ 16, 9, 25, 7, 11, 13, 17, 19, 23\right\} $$

Next, you can add to that maximal set any number of the form $p_1^s p_2^t p_3^u \ldots$ for distinct $p_1, p_2, p_3 \ldots \leq N$ such that $p_1, p_2, p_3 \ldots \not \int M^*(N)$. And using the same reasoning as before, you can demand that $s, t, u \ldots$ are all maximal, that is, that if any of those exponents were increased, the producnt would no longer be less than $N$. For the case of $N=25$, that adds $2^3\cdot 3 = 24$, $2 \cdot 3^2=18$, $2^2 \cdot 5 = 20$, and $3 \cdot 5 = 15$, and what we have proven is that there is a maximal-size set $M(25)$ of elements between 1 and 25 such that $$ M^*(25) \supset \left\{ 16, 9, 25, 7, 11, 13, 17, 19, 23, 24, 18, 20, 15\right\} $$ Finally, assume that some trial set $M^t(N)$ contains all the maximal prime-powers discussed in the first part and all the maximual prime-power-products discussed in the second, and assume there is another number $q \not \in M^t(N)$ such that $q \in M(N)$: Then the prime factorization of $q$ is of the form $p_1^s p_2^t p_3^u \ldots$ with the exponents such that they are all less than or equal to the corresponding exponents of an element of $M^t(N)$. Thus either $q \in M^t(N)$ or $q$ divides some member of $M^t(N)$; either of those contradicts the assumption that there is another element of $M(N)$. So this trial set is maximal.

Hence the maximal set for $N=25$ has $13$ elements, hence any set of 14 or more distinct integers less than $25$ must contain a pair one of which is a multiple of the other.

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