Question

How many 7 digit numbers must you have to guarantee that at least two of them sum to the same number?

Answer 1

Is this the correct approach? Since the sums can be from 0 to 9^7, we would at least need 9^7+1 possibilities. So if we have 1 more to that then, we would have overlapping sum to the two sets of 7 digit number.

Answer 2

So would the answer be 9^7+2?

Answer 3

How many 7-digit numbers are there? Can they start with "0"or "00" or etc.?

Answer 4

all 7 digit numbers are from 0 - 9, they can start with 0, or 00.

Answer 5

ie, 0000001.

Answer 6

There are 10^7 possible 7-digit numbers.

Answer 7

You have the right idea. You can see this using the Pigeon Hole Principle -

https://en.wikipedia.org/wiki/Pigeonhole_principle

Basically, once you exceed all possible permutations of 7-digit numbers (holes) any other numbers must be a repeat of the previous (pigeons). Therefore, at least one hole will have two pigeons. This is equivalent to saying that at least two numbers will have the same sum.

For example, if there are only 4 possible numbers, a,b,c,d then after you have 4 numbers listed, you'll always have at least two that sum to the same number. Say these numbers were c,d,a,b then you have no other option but to select a repeat number, like d. Then the 1st d plus any number selected, like c, will equal the last d plus that c:

c+d(first one)=d(last one)+c

But you want at least two numbers to have the same sum, here both c's are the same, so we need to have one more: 10^7+2 will guarantee that two numbers will have the same sum.

Hope this helps.