A harder birthday problem

Posted on December 24, 2016 by possiblywrong

It is a well-known non-intuitive result that in a group of $n=23$ people– conveniently the size of a classroom of students– the probability is at least 1/2 that $k=2$ or more of them share a birthday. This is a nice problem for several reasons:

Its solution involves looking at the problem in a non-obvious way, in this case by considering the complementary event that all birthdays are distinct.
Once the approach in (1) is understood, computing the answer is relatively easy: the probability is $1-(365)_{n}/365^n$ , where $(x)_{n}$ is the falling factorial.
The answer is surprising. When I ask students, “How many people are needed for the probability of a shared birthday to exceed 1/2?”, guesses as high as 180 are common.
Picking on the not-quite-realistic assumption of all $d=365$ birthdays being equally likely actually helps; that is, with a non-uniform distribution of birthdays, the probability of coincidence is higher.

But what about larger $k$ ? For example, suppose that while surveying your students’ birthdays in preparation for this problem, you find that three of them share a birthday? What is the probability of this happening?

The Wikipedia page on the birthday problem doesn’t address this generalization at all. There are several blog and forum posts addressing the $k=3$ case specifically, by grouping the prohibited cases according to the number of pairs of people with shared birthdays. This is generalized to arbitrary $k \geq 2$ on the Wolfram MathWorld page; the resulting recurrence relation is pretty complex, but it’s a nice exercise to prove that it works.

Probability that at least (2,3,4,5) people share a birthday, vs. group size.

The motivation for this post is to describe what I think is a relatively simpler solution, for arbitrary $k$ , including Python source code to perform the calculation. Let’s fix the number of equally likely possible birthdays $d=365$ , and the desired number $k$ of people sharing a birthday, and define the function

$G(x)=(1+x+\frac{x^2}{2} \ldots + \frac{x^{k-1}}{(k-1)!})^d$

Then $G(x)$ is the exponential generating function for the number of “prohibited” assignments of birthdays to $n$ people where no more than $k-1$ share a birthday. That is, the number of such prohibited assignments is $n!$ times the coefficient of $x^n$ in $G(x)$ .

(When working through why this works, it’s interesting how often it can be helpful to transform the problem into a different context. For example, in this case, we are also counting the number of length- $n$ strings over an alphabet of $d$ characters, where no character appears more than $k-1$ times.)

The rest of the calculation follows in the usual manner: divide by the total number of possible assignments $d^n$ to get the complementary probability, then subtract from 1. The following Python code performs this calculation, either exactly– using the fractions module, which can take a while– or in double precision, which is much faster.

import numpy as np
from numpy.polynomial import polynomial as P
import fractions
import operator
 
def p(k, n, d=365, exact=False):
    f = fractions.Fraction if exact else operator.truediv
    q = 0 if n > d * (k - 1) else P.polypow(np.array(
        [f(1, np.math.factorial(j)) for j in range(k)], dtype=object),
        d)[n]
    for j in range(1, n + 1):
        q = q * f(j, d)
    return 1 - q

Strong induction

Posted on December 16, 2016 by possiblywrong

What is the best way to explain induction to a student? That is, given a true-or-false statement $P(n)$ involving a natural number $n \geq 0$ , we would like to prove that the statement is true for all such $n \geq 0$ . How does one prove such a claim, when it seems to require checking an infinite number of cases? My motivation for this thinking-out-loud post involves a particular form of induction whose presentation in some textbooks may cause students some confusion (or at least, it did cause confusion in at least one student).

Often the first exposure to induction is the so-called “weak” form: to show that $P(n)$ is true for all $n \geq 0$ , it suffices to prove the following two claims:

Base step: $P(0)$ is true.
Induction step: For all $n \geq 0$ , if $P(n)$ is true, then $P(n+1)$ is true.

That is,

$(P(0) \land \forall n \geq 0 P(n) \Rightarrow P(n+1)) \Rightarrow \forall n \geq 0 P(n)$

So far, so good. Although this is technically all that we need, that this is referred to as “weak” induction suggests that there is a stronger form. There is… sort of. In his Applied Combinatorics (see Reference 1 below), Tucker skips weak induction altogether, presenting induction in the following “strong” form:

Base step: $P(0)$ is true.
Induction step: If $P(0), P(1), P(2), \ldots, P(n-1)$ are true, then $P(n)$ is true.

The idea is that the induction hypothesis is stronger, which can make the resulting proof simpler; in the process of proving $P(n)$ in the induction step, we have at our disposal not only the assumed truth of $P(n-1)$ , but also all of the other previous statements. (I say “sort of,” and wrap “weak” and “strong” in quotes, because the two forms are actually equivalent. Strong induction isn’t really any stronger in the sense of more “proving power”; statements provable using strong induction are also provable by weak induction, and vice versa.)

Notice that the induction step above, quoted directly from Tucker, lacks some rigor in that there is no explicit universal quantifier for $n$ . That is, for what values of $n$ do we need to demonstrate the induction step? This is important, because it turns out that if we are more careful, we can economize a bit and demonstrate that $P(n)$ is true for all $n \geq 0$ by proving the single more compact claim:

Strong induction “single-step”: For all $n \geq 0$ , if $P(k)$ is true for all $k<n$ , then $P(n)$ is also true.

That is,

$(\forall n \geq 0 (\forall k<n P(k)) \Rightarrow P(n)) \Rightarrow \forall n \geq 0 P(n)$

Velleman (Reference 2) takes this presentation approach, which certainly has elegance going for it. But he then goes on to “note that no base case is necessary in a proof by strong induction [my emphasis].” This is where I think things can get confusing. It’s certainly true that, once we have demonstrated the implication in the single-step version above, then we know that $P(0)$ is true. As Velleman explains, “plugging in 0 for $n$ , we can conclude that $(\forall k<0 P(k)) \Rightarrow P(0)$ . But because there are no natural numbers smaller than 0, the statement $\forall k<0 P(k)$ is vacuously true. Therefore, by modus ponens, $P(0)$ is true. (This explains why the base case doesn’t have to be checked separately in a proof by strong induction [my emphasis]; the base case $P(0)$ actually follows from the modified form of the induction step used in strong induction.)”

There is nothing strictly incorrect here. What may be misleading, though, is the repeated assurance that no special attention is required for treatment of the base case. When writing the actual proof of the implication in the single-step version of strong induction, the argument may “look different” for $n=0$ than it does for $n>0$ . I think Wikipedia actually does the most admirable job of explaining this wrinkle: “Sometimes the same argument applies for $n=0$ and $n>0$ , making the proof simpler and more elegant. In this method it is, however, vital to ensure that the proof of $P(n)$ does not implicitly assume that $n>0$ , e.g. by saying “choose an arbitrary $k<n$ ” or assuming that a set of $n$ elements has an element [my emphasis added].”

From a teaching perspective, what are good examples of induction proofs that highlight these issues? This is a good question. When discussing strong induction, the most common example seems to be the existence part of the fundamental theorem of arithmetic: every integer greater than 1 is the product of one or more primes. Here we really can make just one argument, so to speak, without treating the first prime number 2 as a special base case (interestingly, Wikipedia does address it separately).

In a course on graph theory, I think another nice example is the proof that any round-robin tournament contains a Hamiltonian path. Again, the single-step version of a strong induction argument works here as well (although we have to be a little more careful about what happens when some constructed subsets of vertices end up being empty).

Finally, another common example where strong induction is useful, but special treatment of base case(s) is required, involves postage stamps: show that it is possible to use 4- and 5-cent stamps to form every amount of postage of 12 cents or more.

References:

Tucker, Alan, Applied Combinatorics, 6th ed. New York: Wiley and Sons, 2012
Velleman, Daniel J., How to Prove It: A Structured Approach. New York: Cambridge University Press, 2006

How many dice?

Posted on December 5, 2016 by possiblywrong

The figure below shows an “unfolded” view of a typical 6-sided die (d6), used everywhere from board games to casinos:

An “unfolded” view of a standard d6.

Each of the six faces is uniquely labeled with the integers 1 through 6. But that’s not all; note that the values on opposite faces always sum to 7. This is a standard arrangement applied more generally to other types of dice as well. My set of Platonic solid dice– with $n$ sides for $n \in {4,6,8,12,20}$ — all have this same property. Let us call such an $n$ -sided die standard if all opposite faces sum to $n+1$ .

Problem 1: How many different standard 6-sided dice are there? That is, in how many ways can we label the faces with distinct integers 1 through 6, with opposite faces summing to 7?

Problem 2: What if we relax the standard (constant opposite sum) property? That is, in how many ways can we label the faces with distinct integers 1 through 6, with no other restrictions?

Problem 3: Same as Problem 2, but for the other Platonic solids (d4, d8, d12, d20)?

I think these are great examples of problems for students that straddle whatever line there may be between mathematics and computer science. Problems 1 and 2 can be solved as-is “by hand.” (And they are interesting in part because the answers are perhaps surprisingly small numbers.) But the usual mathematical machinery involved just counts the number of dice in each case; it’s an interesting extension as a programming problem to actually enumerate (i.e., list) them, display visual representations of them, etc.

Problem 3 is more challenging; the machinery is the same, but the larger numbers involved require some amount of automation in the housekeeping.

Now for what I think is a really hard problem motivating this post (Edit: although after a response from a reader in another forum with a very elegant solution, perhaps this is not as difficult as I thought it might be!):

Problem 4: Same as Problem 1, but for the other Platonic solids– that is, how many different standard (d4, d8, d12, d20) are there, with constant opposite sums?

Possibly Wrong

On science, mathematics, and computing

Monthly Archives: December 2016

A harder birthday problem

Strong induction

How many dice?