Send to a Friend

LostInParadise's avatar

Brain Teaser - Working with numbers that don't divide into one another?

Asked by LostInParadise (31918points) April 12th, 2009

This is a classic recreational math problem. I have added two additional pieces that I have not found.

I am going to give the problem in terms of the numbers from 1 to 50, but you can work with any range. To simplify things, you may want to start with the numbers from 1 to 10 and select 5 numbers from this range.

From the numbers from 1 to 50, choose as many numbers as you can such that none of the numbers is a divisor of any of the others. For example, you can choose all primes less than 50. None of these numbers divide evenly into any of the others.

1. Show that you can’t select more than 25 numbers from 1 to 50 such that none of the numbers is divisible by any of the others.
Hint: Consider the odd numbers.

2. There is more than one way of choosing 25 mutually non-divisible numbers. Find the collection that contains the largest numbers.

3. Find the collection that contains the smallest numbers.

Using Fluther

or

Using Email

Separate multiple emails with commas.
We’ll only use these emails for this message.