2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Do you understand that there are eight million distinct phone numbers? $\endgroup$
    – saulspatz
    Jul 14, 2020 at 15:34
  • $\begingroup$ yes of the form NXX-XXXX $\endgroup$
    – Blue Fire
    Jul 14, 2020 at 15:35

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – Blue Fire
    Jul 14, 2020 at 15:48
  • 1
    $\begingroup$ @HUMAN An area code is a sequence of $3$ digits like $123$ For any fixed area code, there are $8,000,000$ possible numbers. $\endgroup$
    – saulspatz
    Jul 14, 2020 at 15:54
  • $\begingroup$ @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? $\endgroup$
    – Avv
    Jun 27, 2021 at 11:55
  • 1
    $\begingroup$ @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.) $\endgroup$
    – saulspatz
    Jun 27, 2021 at 13:52
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 14, 2020 at 17:40
-1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .