Answered

Explore Westonci.ca, the top Q&A platform where your questions are answered by professionals and enthusiasts alike. Get quick and reliable solutions to your questions from a community of experienced experts on our platform. Join our platform to connect with experts ready to provide precise answers to your questions in different areas.

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 :

MrRoyal

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 your visit. We're dedicated to helping you find the information you need, whenever you need it. Thank you for visiting. Our goal is to provide the most accurate answers for all your informational needs. Come back soon. Get the answers you need at Westonci.ca. Stay informed by returning for our latest expert advice.