Hi, I am new to the forum and need help desperately.

I am having trouble with this homework problem.

Bill has a bag of 100 balls numbered from 1 tgo 100. What is the minimum number of ablls that would have to be picked to be sure of having at least one number that is a multiple of another number already picked?

I know the answer is 51 but am unsure how that is so. Please help!! Thanks.

Quote:

---

Originally Posted by 22tango

Please help!!!! Thanks.

---

Hello Tango !

You could first pull out all prime numbers under 100 (so the not multiple numbers - 1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97) - a total of 26.

The next numbers you may draw that are neither multiples of already picked numbers : 4, 6, 8, 9, 10, 12, 14, 16, 18, 20, 22, 24, 26, 27, 28, 30, 32, 34, 36, 38, 40, 42, 44, 45, 46, 48, 49, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 75, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 99, 100.

Now take off the highest numbers from that list that are not multiples yet :
100 - 1 , 99 - 2 , 98 - 3 , 96 - 4 , 94 - 5 , 90 - 6 , 88 - 7 , etc. etc. etc.

Below number 50 : are there any numbers that are part of any of the already picked numbers? If so, select them and count them.
Continue doing this till you end up with the last number "2". Now you have all balls you have to pick to make sure !

Now add all totals together...

===

Note : the question is about making SURE to get a multiple number.
Chance calculation would give you a chance of around 1 in 4 or 5 that you have a multiple, but that is not fully sure !

:)

Hello 22tango. I wonder if you what you meant to ask is how many balls can you withdraw before have two that are multiples of each other - is that correct? The way you wrote it - how many before you have a number that is a multiple of another number already picked would have a different answer. You could pick 100, then 99, then 98, etc all the way down to 1 without ever picking a number that is a multiple of one already picked. So, assuming my interpretation of the question is correct --

Suppose you withdraw number 100 first, then 99, then 98, etc. Going in reverse order like this allws you to withdraw half the balls without one being a multiple of another - that is, all the balls from 100 down to 51. So you can take out up to 50 balls without having a multiple. The next ball you draw however, is guaranteed to be equal to 1/2 or 1/3 or 1/4 etc of one of the balls you already drew. For example if you next withdraw number 50, the 100 ball you already took out is 2 times that. If the next ball is 21, then it has multiples of 63 and 84. Hence the aswer is 51.

Credendovidis: sorry, but your approach doesn't seem to work. Once you withdraw all the primes then whatever you pick next is guarranteed to be a multiple. Also - 2 is a prime, and 1 is not. And once you pick the 1, then no matter what you pick next you are guarranteed to have a multiple.