# Problem about the generalized pigeonhole principle

This problem from Discrete Mathematics and its application's for Rosen

What is the least number of area codes needed to guarantee that the 25 million phones in a state can be assigned distinct 10-digit telephone numbers? (Assume that telephone numbers are of the form NXX-NXX-XXXX, where the first three digits form the area code, N represents a digit from 2 to 9 inclusive, and X represents any digit.)

The answer I found in the book is :

There are eight million different phone numbers of the form NXX-XXXX (as shown in Example 8 of Section 6.1). Hence, by the generalized pigeonhole principle, among 25 million telephones, at least $$\lceil25,000,000/8,000,000\rceil = 4$$ of them must have identical phone numbers. Hence, at least four area codes are required to ensure that all 10-digit numbers are different

Can anyone please explain this answer as I tried a lot to understand it but I can't.

• Do you understand that there are eight million distinct phone numbers? Jul 14, 2020 at 15:34
• yes of the form NXX-XXXX Jul 14, 2020 at 15:35

Since there are at most $$8,000,000$$ distinct numbers in an area code, if we had $$3$$ areas codes, we could only accommodate $$3\cdot8,000,00=24,000,000$$ phone numbers. If we have $$4$$ area codes, we can accommodate $$4\cdot8,000,00=32,000,000$$ numbers, so we need $$4$$.

The short way to do this is to notice that $$\frac{25,000,000}{8,000,000}=\frac{25}8=3.125$$ so that $$3$$ area codes won't be enough, but $$4$$ will be. The most compact way of writing it is that we need $$\left\lceil\frac{25,000,000}{8,000,000}\right\rceil$$ area codes.

• why 4 area codes give us 4 * 8,000,000 ? I think it will give us 10^4 * 8,000,000 as 4 area codes is a number with 4 digits as i think Jul 14, 2020 at 15:48
• @HUMAN An area code is a sequence of $3$ digits like $123$ For any fixed area code, there are $8,000,000$ possible numbers. Jul 14, 2020 at 15:54
• @saulspatz. Amazing explanation. Thank you. In case of 8 million numbers, this is a permutation, but this is not arrangement of numbers, so how do we know if we should use arrangement or not please?
– Avv
Jun 27, 2021 at 11:55
• @Avra I don't understand. We are told that we have $8,000,000$ numbers for each area code. This is not a permutation. (The problem says that the numbers are of the form NXX-XXXX, so I suppose that there are $8$ choices for N and $10$ choices for each of the X's.) Jun 27, 2021 at 13:52

I honestly think the answer is a bit unclear as well, but here is my similar explanation. There are $$8$$ million possible numbers of the form NXX - XXXX since: $$8 \times 10^6 = 8,000,000.$$ Imagine you divide the $$25$$ million phones into groups of $$8$$ million phones. Evidently you get $$4$$ groups, the last group (only $$1$$ million) of course not being all the way full (hence the ceiling function in the answer). Each of the first $$3$$ groups use all of the numbers exactly once, and then there is guaranteed repetition again when assigning the fourth group of $$1$$ million people phone numbers. However, no number is repeated more than $$4$$ times. Thus, by having $$4$$ distinct area codes NXX, we can avoid any repetition.

• It’s not unclear: it just requires the reader to recognize that taking the ceiling of a positive number has the effect of rounding it up, so that any leftover ‘fractional’ group — in this case the extra million — is correctly counted as needing an area code. Jul 14, 2020 at 17:40

There are 8000000 telephone numbers of the form NXX-XXXX .( For first element i.e N we have 8 choices and for remaining 6 elements we have 10 choices for each so by product rule we have 8000000 choices).Then by generalized pigeon hole principle there must be at least [25000000/8000000]=4 of 25 millions telephones which have identical phone numbers. So at least 4 area codes are required to guarantee that all 10 digit numbers are different.