Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Here's a little question that we were shown in class:

Let $S = \{1,2,\ldots,200\}$ and let $A \subseteq S$ such that $|A| = 101$. Prove that there are two elements of $A$ such that one is a divisor of the other.

The proof was fairly easy: the pigeonholes were the pattern $(2k+1)2^i$. You have a $100$ of those and therefor two elements must be in the same pigeonhole.

My question: Why a $100$ pigeonholes? Other than that face that this is comfortable and it works, is there any other reason? Can I do the same for $50$ and still be able to give such representation to every number?

Thanks

share|improve this question
    
In (2k+1)a^i, you mean a=2, right? –  Lopsy Dec 26 '11 at 17:34
    
Yes, indeed. I've fixed it –  yotamoo Dec 26 '11 at 18:04
4  
For this problem 100 is the "correct" answer: there exists some $A \subseteq S$ of size 100 such that no element of it divides another. (Exercise: Find such an $A$.) I do not know what you mean by "representation", but certainly you would not be able to prove that 50 is an upper bound. // This problem is also discussed elsewhere in this site: math.stackexchange.com/a/62613/13425. –  Srivatsan Dec 26 '11 at 18:25
2  
Concerning the sentence "My question: Why a $100$ pigeonholes? Other than that face that this is comfortable and it works, is there any other reason?": Srivatsan's comment aside; there is no general algorithm that solves any problem you come up with in a sleeping carriage. –  Christian Blatter Dec 26 '11 at 19:54

1 Answer 1

up vote 2 down vote accepted

Well, you're absolutely right; if you could partition $S$ up into $50$ subsets such that every member of every subset was either a divisor or a multiple of every other element in the same subset, then you'd have proved the even stronger statement that any $A \subseteq S$ with $|A| = 51$ would contain divisor-dividend pair.

But you can't make that partition. To show this, we again use the pigeonhole principle: suppose that you have fewer than 100 pigeonholes. Then some two of the numbers from $101$ to $200$ will be in the same pigeonhole. This pigeonhole thus fails to contain only numbers that divide each other.

So a $101$-element subset is in fact not only sufficient but also necessary to guarantee that it has two elements with one dividing the other.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.