Proving Divisibility in the Set of Integers 1-100 with 51 Numbers

[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.

 

[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".

 

[Noticibly F.A.T]

That takes too long!

 

[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?

 

[Gokul43201]

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?

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.

 

[Gokul43201]

That takes too long!

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

 

[Jin314159]

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".

That is not a proof.

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

 

[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).

 

[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.

 

[Hurkyl]

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

 

[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.

 

[Gokul43201]

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

 

[recon]

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

I did too... 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...

 

[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.

 

[Gokul43201]

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.

 

[Gokul43201]

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

 

[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.

 

[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.

 

[Hurkyl]

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

 

[Jin314159]

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

doh! So much for impulsive posting.

 

[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.

 

[recon]

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

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.

 

[Hurkyl]

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

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

 

[recon]

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

 

[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.

 

[CrankFan]

Bumping this because I'm eager to see a proof.

 

[jcsd]

Bumping this because I'm eager to see a proof.

It's already been solved, but consider this:

the set {51,...,100} has 50 members and clearly none of them are divisble by each other. We might guess that there is no larger set with this property(though there are defintely other sets of the same size with this property).

To obtain a nys et larger than this we would have to add n numbers, but we would also have to take away m numbers to prove that ther is no larger set e have to prove that n is less than or equal to m in all cases.

if we add any of the numbers x = 25-50 we must remove 2x from our set, if we add any of the numbers 13-25 we must remove 4x from our set and we cannot add 2x to our set,, for the numbers 7-12, we must remove 8x from our list and we cannot add the numbers 2x or 4x to our list etc. Unfortuantely this proof is a little messy, but hopefully you can see it is correct.