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

  • Thread starter jonroberts74
  • Start date
  • Tags
    Integers
In summary: The question is how many integers must be picked to be sure at least two of them have a digit in common. So the answer is 10.In summary, the worst case scenario involves picking 10 integers from 100 to 999 in order to be sure that at least two of them have a digit in common. This is because the first place value only has 9 choices and the tenth integer will have a common digit with one of the previous choices.
  • #1
jonroberts74
189
0

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.
 
Physics news on Phys.org
  • #2
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?
 
  • #3
Simon Bridge said:
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.
 
  • #4
jonroberts74 said:
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?
 
  • #5
haruspex said:
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.
 
  • #6
jonroberts74 said:
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.
 
  • Like
Likes 1 person
  • #7
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?
 
  • #8
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?
 
  • #9
haruspex said:
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.
 
  • Like
Likes 1 person
  • #10
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.
 
  • #11
Mitchel Haas said:
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.
 
  • Like
Likes SammyS

1. How many integers should be picked to guarantee that at least 2 of them have a digit in common?

The minimum number of integers that need to be picked is 11. This is because there are 10 possible digits (0-9) and if we pick 11 integers, at least one of them must have a digit in common with another integer.

2. Is there a maximum number of integers that can be picked to ensure that at least 2 of them have a digit in common?

No, there is no maximum number of integers that can be picked to guarantee this. As long as we continue to pick more and more integers, the chances of two of them having a digit in common also increases.

3. Can the integers that are picked have repeating digits?

Yes, the integers can have repeating digits. As long as there is at least one digit that is the same in two different integers, then the requirement of having a digit in common is met.

4. Does the order in which the integers are picked matter?

No, the order in which the integers are picked does not matter. As long as there are at least two integers with a common digit, it does not matter which order they were picked in.

5. Is there a specific set of integers that can be picked to guarantee that at least 2 of them have a digit in common?

No, there is no specific set of integers that can be picked to guarantee this. As long as we pick enough integers, there will always be at least two with a common digit.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
22
Views
2K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
8
Views
808
Replies
4
Views
253
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
5K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
5K
Replies
12
Views
1K
Back
Top