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.