B.9 Examples for Chapter 12 – Introduction to Cryptography with Coding Theory, 3rd Edition

B.9 Examples for Chapter 12

Example 36

Suppose there are 23 people in a room. What is the probability that at least two have the same birthday?


The probability that no two have the same birthday is i=122(1i/365) (note that the product stops at i=22,  not i=23). Subtracting from 1 gives the probability that at least two have the same birthday:

> 1-mul(1.-i/365, i=1..22)


Note that we used 1. in the product instead of 1 without the decimal point. If we had omitted the decimal point, the product would have been evaluated as a rational number (try it, you’ll see).

Example 37

Suppose a lazy phone company employee assigns telephone numbers by choosing random seven-digit numbers. In a town with 10,000 phones, what is the probability that two people receive the same number?

> 1-mul(1.-i/10aˆ7, i=1..9999)

Note that the number of phones is about three times the square root of the number of possibilities. This means that we expect the probability to be high, which it is. From Section 12.1, we have the estimate that if there are around 2(ln2)1073723 phones, there should be a 50% chance of a match. Let’s see how accurate this is:

> 1-mul(1.-i/10aˆ7, i=1..3722)