How many integers to pick such that 2 of them have digit in common

[jonroberts74]

Homework Statement

How many integers from 100 through 999 must you pick in order to be sure that at least two of them have a digit in common? (they don't have to be in the same place value)

The Attempt at a Solution

worst case scenario involves picking integers such that none have had a digit in common

the other questions I've had like this have been all the possible combinations + 1 which is 9x10x10+1 = 901 but that doesn't seem correct.

seems like the only integers I could choose first that won't have a digit in common up to that point is 111,222,333,444,555,666,777,888,999 [assuming those are the first 9 integers I chose] then whatever I chose next will have a common digit with one of those.

 

[Simon Bridge]

worst case scenario involves picking integers such that none have had a digit in common

Try finding 20 numbers from the range which do not have a digit in common.
Write them down.

seems like the only integers I could choose first that won't have a digit in common up to that point is 111,222,333,444,555,666,777,888,999 [assuming those are the first 9 integers I chose] then whatever I chose next will have a common digit with one of those.

That's right - so what is your conclusion?

 

[jonroberts74]

Try finding 20 numbers from the range which do not have a digit in common.
Write them down.
That's right - so what is your conclusion?

In the worst case scenario, ten is the greatest number of integers I would have to choose in order to find another integer that had a digit in common with an already chosen integer because the first place value only has 9 choices to choose from and the tenth would cause a repeat of a digit. Assuming the other two place values have not had any shared digits--they would repeat on the 11 choice.

 

[haruspex]

In the worst case scenario, ten is the greatest number of integers I would have to choose in order to find another integer that had a digit in common with an already chosen integer because the first place value only has 9 choices to choose from and the tenth would cause a repeat of a digit. Assuming the other two place values have not had any shared digits--they would repeat on the 11 choice.

How can you find ten with no digits in common if the first position only has nine possibilities?

 

[jonroberts74]

How can you find ten with no digits in common if the first position only has nine possibilities?

Not 10 without, the worst case scenario would be the 10th choice would have a digit in common with the others because the first place value only has 9 choices.

Because I could somehow randomly choose

111
222
333
444
555
666
777
888
999

Then no matter what I choose next which is the tenth integer will have a common digit with one of the previous choices.

 

[haruspex]

Not 10 without, the worst case scenario would be the 10th choice would have a digit in common with the others because the first place value only has 9 choices.

Because I could somehow randomly choose

111
222
333
444
555
666
777
888
999

Then no matter what I choose next which is the tenth integer will have a common digit with one of the previous choices.

OK, I thought you were saying the answer was 11.

 

[Simon Bridge]

Assuming the other two place values have not had any shared digits--they would repeat on the 11 choice.

... that does sort-of sound like you are saying that the answer is 11 doesn't it?

Then no matter what I choose next which is the tenth integer will have a common digit with one of the previous choices.

So you have your answer?

 

[Simon Bridge]

Assuming the other two place values have not had any shared digits--they would repeat on the 11 choice.

... that does sort-of sound like you are saying that the answer is 11 doesn't it?

Then no matter what I choose next which is the tenth integer will have a common digit with one of the previous choices.

So you have your answer?

 

[vela]

OK, I thought you were saying the answer was 11.

I was initially confused by that bit at the end too, but all the OP meant was that the second and third digits would definitely be a repeat on the 11th number because there are 10 choices for those positions.

 

[Mitchel Haas]

There are 9*9*8 = 648 integers which do not have a repeating digit.
(1 - 9) * (0 - 9 -1) * (0 - 9 - 2)
So, you must pick 649 to insure you have an integer with a repeating digit.

 

[haruspex]

There are 9*9*8 = 648 integers which do not have a repeating digit.
(1 - 9) * (0 - 9 -1) * (0 - 9 - 2)
So, you must pick 649 to insure you have an integer with a repeating digit.

Indeed, but that is not the question in this thread.