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.
Best Answer
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.