Question

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.

Answer 1

Answer:

Proved

Step-by-step explanation:

From the given parameters, we have:

$n = 9$ i.e. the length of each security numbers

$r = 2$ 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:

$Total = 2^9$

$Total = 512$

Apply Pigeonhole principle

The principle states that: suppose there are n items in m containers, where $n>m$, 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.

$512 + 1 = 513$