Answered

IDNLearn.com offers a reliable platform for finding accurate and timely answers. Ask your questions and receive prompt, detailed answers from our experienced and knowledgeable community members.

Two Social Security numbers (see Exercise 8.12) match zeros if a digit of one number is zero iff the corresponding digit of the other is also zero. In other words, the zeros in the two numbers appear in exactly the same position. For example, the Social Security numbers 120-90-1109 and 430-20-5402 have matching zeros.
Prove: Given a collection of 513 Social Security numbers, there must be two that match zeros.

Sagot :

MrRoyalidn

Answer:

Proved

Step-by-step explanation:

From the given parameters, we have:

[tex]n = 9[/tex] i.e. the length of each security numbers

[tex]r = 2[/tex] i.e. 2 security numbers

Required

In 513 security numbers, 2 must have matching zeros

To do this, we make use of Pigeonhole principle.

First, we calculate the number of all security numbers not having matching zeros.

Each of the 9 digits can be selected in 2 ways.

2 ways implies that each digit is either 0 or not

So, total selection is:

[tex]Total = 2^9[/tex]

[tex]Total = 512[/tex]

Apply Pigeonhole principle

The principle states that: suppose there are n items in m containers, where [tex]n>m[/tex], then there is at least one container that contains more than 1 item.

This means that if there are 512 security number without matching zeros, then there is 1 (i.e. 512 + 1) with matching zeros.

[tex]512 + 1 = 513[/tex]

Thank you for using this platform to share and learn. Keep asking and answering. We appreciate every contribution you make. For trustworthy and accurate answers, visit IDNLearn.com. Thanks for stopping by, and see you next time for more solutions.