# Math Problem

1. Nov 7, 2004

### Jin314159

Consider the set of integers from 1 to 100, inclusive. Prove that if I pick any 51 numbers from this set, at least one number is divisible by another.

2. Nov 7, 2004

### recon

1 divides 2.
2 divides 4.
3 divides 6.
..........
.........
.
.
.
50 divides 100.

Looking at this, choosing 51 different numbers between from 1 to 100 inclusive would guarantee that there is at least a pair of numbers where one number is twice as large as the other.

This shouldn't belong in "Brain Teasers".

3. Nov 7, 2004

### Noticibly F.A.T

That takes too long!

4. Nov 7, 2004

### ceptimus

Make the question tougher, so that more than just the 'doubling' rule has to be considered.

Given the set of integers from 1 to 100 (inclusive), what is the largest subset of numbers that can be picked so that no member of the subset is exactly divisible by another member?

5. Nov 7, 2004

### Gokul43201

Staff Emeritus
But ceptimus, the solution to this is the the same as the original question, since, for a set of the first n consecutive naturals, no two elements in the subset {$[\frac{n+1}{2}],[\frac{n+1}{2}]+1,...,n-1,n$} divide each other.

So, I can always find a subset with [(n+1)/2] members.

Last edited: Nov 7, 2004
6. Nov 7, 2004

### Gokul43201

Staff Emeritus
What does ?? That's really quite a nice and short solution.

7. Nov 7, 2004

### Jin314159

That is not a proof.

It is as if I were trying to prove the Pythagorean Theorem by drawing a 3,4,5 triangle.

Last edited by a moderator: Nov 7, 2004
8. Nov 7, 2004

### Jin314159

Okay, so far. No one has given a satisfactory proof. Note: This problem was taken from a Russian Math Circle handbook (meaning, it's not as trivial as Recon suggests).

9. Nov 7, 2004

### NPN

The orignial proof by recon is just fine - this problem is just as trivial as it seems.

Let's say you have some subset S of {1,2,3...100} containing 51 (distinct) elements. We cannot allow S to contain both N and 2N; so, we can't have both 1 and 2, for instance. Or 2 and 4. In general, we can have at most one element from each of {{1,2},{2,4},...{N,2N}...{50,100}} - but since there are only 50 such choices, by the pigeonhole principle we must end up using at least two elements from at least one of these sets - namely, an N and a 2N. Therefore there is no 51-element subset of {1...100} in which not one element divides another.

10. Nov 7, 2004

### Hurkyl

Staff Emeritus
You forget that some of the 51 numbers can be chosen from the set {51, 53, 55, ..., 99}.

11. Nov 7, 2004

### recon

I concede that my solution isn't adequate. I never said that the problem was trivial. I just thought that this belonged under the Math forum. A new approach:

There are 25 prime numbers and 75 composite numbers. Considering that we enter all 25 prime numbers as part of the 51-member group, there are still 26 numbers that we need to choose. But we can't choose the other 26 numbers because they ALL share the same common factors as some of the 25 numbers already chosen (i.e. the prime numbers can divide into them).

EDIT: I know this is wrong, but perhaps the proof lies somewhere along this line of attack.

Last edited: Nov 7, 2004
12. Nov 7, 2004

### Gokul43201

Staff Emeritus
Ouch, why did I think that the two columns contained all the numbers in {1,..100} ??

13. Nov 7, 2004

### recon

I did too... :grumpy: But all is not lost. I think I'm almost coming to a solution. First of all, I think we have to consider why he said 51 instead of 50 or some smaller number. Hmm...

14. Nov 7, 2004

### recon

{51,53,...,99} x 1 [25]
{27,29,...,49} x 2 [12]
{13,15,...,25} x 4 [7]
{7,9,11} x 8 [3]
{5} x 16 [1]
{3} x 32 [1]
{1} x 64 [1]

50.

15. Nov 8, 2004

### Gokul43201

Staff Emeritus
Here's my shot at it : Let U = {1,2,...,100}

Assume that we can make a set with 51 elements such that no element divides another. Let's call this desired set a. To get to this set, start with the set S = {51, 52, ..., 99, 100} ; this set has 50 elements. Now either (i) S is a subset of A or (ii) it is not. If (i) is true then A can be constructed by adding elements to S. If not, then A must be constructed by replacing each element of S with at least one element from U-S (or S'), with one of these replacements necessarily bringing in more than one element from S'.

(i) If we add an element to A, this element must be chosen from S' = {1,2,...,50}. However, for every $x~\epsilon~S', 2x~\epsilon~S ~and~x|2x$, so it is not possible to add elements to S', without removing some. So we're down to ...

(ii) Remove one element at a time from S, and replace with one or more elements from S'. Let the first element to be removed be some y. But y can, if at all, only be replaced by a number of the form y' = y/2. The reason for this is as follows :

Assume y' <> y/2. If $y'~\epsilon~(26,27,...,49,50),~then~2y'~\epsilon~S$. So we are left with y' in {1,2,...,24,25}. Let n be the largest integer such that $ny' \leq 25.$ Clearly n>0. Now we have $2ny’ \leq 50~and~4ny’ \leq 100$. So, for all m in the set N={2n+1, 2n+2,…,4n-1, 4n}, my’ is an element of S. Now, N has 2n elements, so the smallest set N must have 2 elements. This means that for at least two values of m, $my’ \epsilon S$. Even if y is one of these, there is at least one other number of the form my’ in S. Hence no number not of the form y’ = y/2 can replace any y. So each y can be replaced by at most one number (y/2).

So we can’t make a set bigger than 50 elements.

Last edited: Nov 8, 2004
16. Nov 8, 2004

### Gokul43201

Staff Emeritus
I see an error in this...ignore it.

17. Nov 8, 2004

### Galileo

Having no two numbers which divide each other means they are all coprime.
(That is gcd(a,b)=1, for any a,b in the list of 51 numbers <100)

There's a function which counts the number of integers (x) less than n, such that gcd(x,n)=1.

It's the Euler-phi (or Totient) function.
Here's a list of values:
http://www.users.globalnet.co.uk/~perry/maths/phi/morephi.htm

I counted 18 numbers n<=100 with phi(n)>=50.

Not a proof, but a step forwards.

Last edited: Nov 8, 2004
18. Nov 8, 2004

### Jin314159

Consider partitioning the set {1,2...100} into

(2,4,6,8,10,12,14,16,18,20...100)
(3,6,9,12,15,18,21...99)
(5,10,15,20,25...95)
(7,14,21,28,...91)
.
.
.
(43,86)
(47,98)
(53)
(59)
.
.
.
(97)

I've essentially partitioned {1,2...100} into sets of multiples of prime numbers less than 50. There are 25 of these sets. Afterwards, I just listed all 10 prime numbers bigger than 50. In order for me to pick 51 numbers such that no number is a multiple of another, I can pick only one number from each of these sets. However, there are only 50 of these sets. By Pigeon-hole principle, I have to pick twice from one set.

19. Nov 8, 2004

### Hurkyl

Staff Emeritus
I can pick two numbers in the set {2, 4, 6, ..., 100} such that neither divides the other.

20. Nov 8, 2004

### Jin314159

doh! So much for impulsive posting.

21. Nov 8, 2004

### Jin314159

Consider partitioning the set {1,2...100} into

(2,4,8,16,32,64)
(3,6,12,24,48,96)
(5,10,20,40,80)
(7,14,28,56)
(9,18,36,72)
(11,22,44,88)
.
.
.
(49, 98)
(51)
(53)
(55)
.
.
.
(99)

I've essentially partitioned {1,2...100} into sets [X*2^n | where x are odds, n are natural numbers and x^n <= 100]. There are 50 of these sets. But in order for me to pick 51 numbers such that no number is a multiple of another, I can pick only one number from each of these sets. Therefore, by the pigeon-hole principle, I have to pick twice from one set.

22. Nov 8, 2004

### recon

OK, I don't understand what you math geniuses are going on about here, especially Gokul's... :surprised:

I am very confident that the largest set that can be produced such that its members do not divide into each other is a 50-member set consisting of members {51,52,53,...,100}.

Let us consider the even numbers within {1,2,...,100}. We divide each of the even numbers by the highest power of 2 that it can be divided by. This results in 25 different odd numbers. However, if 51 members are chosen, invariably, one or more of the odd numbers will be the common factor between two or more numbers.

I think this is right. I just do not know how to express it very mathematically.

Last edited: Nov 8, 2004
23. Nov 8, 2004

### Hurkyl

Staff Emeritus
Recon, jin said what you're trying to say, I think.

(p.s. he forgot to put 1 in his first set)

24. Nov 9, 2004

### recon

Yeah, he forgot to include {1}. I can see now that his solution was identical to mine.

25. Nov 9, 2004

### shmoe

If you know 1 is one of the 51 numbers, you're finished, so it wouldn't hurt to assume it's not.;)

It's maybe worth pointing out that the same idea will work with chosing n+1 numbers from {1,...,2n}, there's nothing special about n=50 except that some people like to count to 100.