Author: John Quintanilla

I'm a Professor of Mathematics and a University Distinguished Teaching Professor at the University of North Texas. For eight years, I was co-director of Teach North Texas, UNT's program for preparing secondary teachers of mathematics and science.

Stay Focused

From Kirk Cousins, quarterback of the Washington Redskins:

Sometimes our guests ask why I have this hanging above my desk. It’s an old high school math quiz when I didn’t study at all and got a C+… just a subtle reminder to me of the importance of preparation. If I don’t prepare I get C’s!

Source: https://www.facebook.com/redskins/photos/a.118304319573.96677.102381354573/10155470824244574/?type=3&theater

Pizza Hut Pi Day Challenge: Index

I’m doing something that I should have done a long time ago: collecting a series of posts into one single post. The following links comprised my series on the 2016 Pizza Hut Pi Day Challenge.

Part 1: Statement of the problem.

Part 2: Using the divisibility rules for 1, 5, 9, 10 to reduce the number of possibilities from 3,628,800 to 40,320.

Part 3: Using the divisibility rule for 2 to reduce the number of possibilities to 576.

Part 4: Using the divisibility rule for 3 to reduce the number of possibilities to 192.

Part 5: Using the divisibility rule for 4 to reduce the number of possibilities to 96.

Part 6: Using the divisibility rule for 8 to reduce the number of possibilities to 24.

Part 7: Reusing the divisibility rule for 3 to reduce the number of possibilities to 10.

Part 8: Dividing by 7 to find the answer.

 

Predicate Logic and Popular Culture: Index

I’m doing something that I should have done a long time ago: collecting a series of posts into one single post. The following links comprised my series on using examples from popular culture to illustrate principles of predicate logic. My experiences teaching these ideas to my discrete mathematics students led to my recent publication (John Quintanilla, “Name That Tune: Teaching Predicate Logic with Popular Culture,” MAA Focus, Vol. 36, No. 4, pp. 27-28, August/September 2016).

Unlike other series that I’ve made, this series didn’t have a natural chronological order. So I’ll list these by concept illustrated from popular logic.

green lineLogical and \land:

  • Part 1: “You Belong To Me,” by Taylor Swift
  • Part 21: “Do You Hear What I Hear,” covered by Whitney Houston
  • Part 31: The Godfather (1972)
  • Part 45: The Blues Brothers (1980)
  • Part 53: “What Does The Fox Say,” by Ylvis
  • Part 54: “Billie Jean,” by Michael Jackson
  • Part 98: “Call Me Maybe,” by Carly Rae Jepsen.

Logical or \lor:

  • Part 1: Shawshank Redemption (1994)

Logical negation \lnot:

  • Part 1: Richard Nixon
  • Part 32: “Satisfaction!”, by the Rolling Stones
  • Part 39: “We Are Never Ever Getting Back Together,” by Taylor Swift

Logical implication \Rightarrow:

  • Part 1: Field of Dreams (1989), and also “Roam,” by the B-52s
  • Part 2: “Word Crimes,” by Weird Al Yankovic
  • Part 7: “I’ll Be There For You,” by The Rembrandts (Theme Song from Friends)
  • Part 43: “Kiss,” by Prince
  • Part 50: “I’m Still A Guy,” by Brad Paisley
  • Part 76: “You’re Never Fully Dressed Without A Smile,” from Annie.
  • Part 109: “Dancing in the Dark,” by Bruce Springsteen.
  • Part 122: “Keep Yourself Alive,” by Queen.

For all \forall:

  • Part 3: Casablanca (1942)
  • Part 4: A Streetcar Named Desire (1951)
  • Part 34: “California Girls,” by The Beach Boys
  • Part 37: Fellowship of the Ring, by J. R. R. Tolkien
  • Part 49: “Buy Me A Boat,” by Chris Janson
  • Part 57: “Let It Go,” by Idina Menzel and from Frozen (2013)
  • Part 65: “Stars and Stripes Forever,” by John Philip Sousa.
  • Part 68: “Love Yourself,” by Justin Bieber.
  • Part 69: “I Will Always Love You,” by Dolly Parton (covered by Whitney Houston).
  • Part 74: “Faithfully,” by Journey.
  • Part 79: “We’re Not Gonna Take It Anymore,” by Twisted Sister.
  • Part 87: “Hungry Heart,” by Bruce Springsteen.
  • Part 99: “It’s the End of the World,” by R.E.M.
  • Part 100: “Hold the Line,” by Toto.
  • Part 101: “Break My Stride,” by Matthew Wilder.
  • Part 102: “Try Everything,” by Shakira.
  • Part 108: “BO$$,” by Fifth Harmony.
  • Part 113: “Sweet Caroline,” by Neil Diamond.
  • Part 114: “You Know Nothing, Jon Snow,” from Game of Thrones.
  • Part 118: “The Lazy Song,” by Bruno Mars.
  • Part 120: “Cold,” by Crossfade.
  • Part 123: “Always on My Mind,” by Willie Nelson.

For all and implication:

  • Part 8 and Part 9: “What Makes You Beautiful,” by One Direction
  • Part 13: “Safety Dance,” by Men Without Hats
  • Part 16: The Fellowship of the Ring, by J. R. R. Tolkien
  • Part 24 : “The Chipmunk Song,” by The Chipmunks
  • Part 55: The Quiet Man (1952)
  • Part 62: “All My Exes Live In Texas,” by George Strait.
  • Part 70: “Wannabe,” by the Spice Girls.
  • Part 72: “You Shook Me All Night Long,” by AC/DC.
  • Part 81: “Ascot Gavotte,” from My Fair Lady
  • Part 82: “Sharp Dressed Man,” by ZZ Top.
  • Part 86: “I Could Have Danced All Night,” from My Fair Lady.
  • Part 95: “Every Breath You Take,” by The Police.
  • Part 96: “Only the Lonely,” by Roy Orbison.
  • Part 97: “I Still Haven’t Found What I’m Looking For,” by U2.
  • Part 105: “Every Rose Has Its Thorn,” by Poison.
  • Part 107: “Party in the U.S.A.,” by Miley Cyrus.
  • Part 112: “Winners Aren’t Losers,” by Donald J. Trump and Jimmy Kimmel.
  • Part 115: “Every Time We Touch,” by Cascada.
  • Part 117: “Stronger,” by Kelly Clarkson.

There exists \exists:

  • Part 10: “Unanswered Prayers,” by Garth Brooks
  • Part 15: “Stand by Your Man,” by Tammy Wynette (also from The Blues Brothers)
  • Part 36: Hamlet, by William Shakespeare
  • Part 57: “Let It Go,” by Idina Menzel and from Frozen (2013)
  • Part 93: “There’s No Business Like Show Business,” from Annie Get Your Gun (1946).
  • Part 94: “Not While I’m Around,” from Sweeney Todd (1979).
  • Part 104: “Wild Blue Yonder” (US Air Force)
  • Part 106: “No One,” by Alicia Keys.
  • Part 116: “Ocean Front Property,” by George Strait.

Existence and uniqueness:

  • Part 14: “Girls Just Want To Have Fun,” by Cyndi Lauper
  • Part 20: “All I Want for Christmas Is You,” by Mariah Carey
  • Part 23: “All I Want for Christmas Is My Two Front Teeth,” covered by The Chipmunks
  • Part 29: “You’re The One That I Want,” from Grease
  • Part 30: “Only You,” by The Platters
  • Part 35: “Hound Dog,” by Elvis Presley
  • Part 73: “Dust In The Wind,” by Kansas.
  • Part 75: “Happy Together,” by The Turtles.
  • Part 77: “All She Wants To Do Is Dance,” by Don Henley.
  • Part 90: “All You Need Is Love,” by The Beatles.

DeMorgan’s Laws:

  • Part 5: “Never Gonna Give You Up,” by Rick Astley
  • Part 28: “We’re Breaking Free,” from High School Musical (2006)

Simple nested predicates:

  • Part 6: “Everybody Loves Somebody Sometime,” by Dean Martin
  • Part 25: “Every Valley Shall Be Exalted,” from Handel’s Messiah
  • Part 33: “Heartache Tonight,” by The Eagles
  • Part 38: “Everybody Needs Somebody To Love,” by Wilson Pickett and covered in The Blues Brothers (1980)
  • Part 46: “Mean,” by Taylor Swift
  • Part 56: “Turn! Turn! Turn!” by The Byrds
  • Part 63: P. T. Barnum.
  • Part 64: Abraham Lincoln.
  • Part 66: “Somewhere,” from West Side Story.
  • Part 71: “Hold On,” by Wilson Philips.
  • Part 80: Liverpool FC.
  • Part 84: “If You Leave,” by OMD.
  • Part 103: “The Caisson Song” (US Army).
  • Part 111: “Always Something There To Remind Me,” by Naked Eyes.
  • Part 121: “All the Right Moves,” by OneRepublic.

Maximum or minimum of a function:

  • Part 12: “For the First Time in Forever,” by Kristen Bell and Idina Menzel and from Frozen (2013)
  • Part 19: “Tennessee Christmas,” by Amy Grant
  • Part 22: “The Most Wonderful Time of the Year,” by Andy Williams
  • Part 48: “I Got The Boy,” by Jana Kramer
  • Part 60: “I Loved Her First,” by Heartland
  • Part 92: “Anything You Can Do,” from Annie Get Your Gun.
  • Part 119: “Uptown Girl,” by Billy Joel.

Somewhat complicated examples:

  • Part 11 : “Friends in Low Places,” by Garth Brooks
  • Part 27 : “There is a Castle on a Cloud,” from Les Miserables
  • Part 41: Winston Churchill
  • Part 44: Casablanca (1942)
  • Part 51: “Everybody Wants to Rule the World,” by Tears For Fears
  • Part 58: “Fifteen,” by Taylor Swift
  • Part 59: “We Are Never Ever Getting Back Together,” by Taylor Swift
  • Part 61: “Style,” by Taylor Swift
  • Part 67: “When I Think Of You,” by Janet Jackson.
  • Part 78: “Nothing’s Gonna Stop Us Now,” by Starship.
  • Part 89: “No One Is Alone,” from Into The Woods.
  • Part 110: “Everybody Loves My Baby,” by Louis Armstrong.

Fairly complicated examples:

  • Part 17 : Richard Nixon
  • Part 47: “Homegrown,” by Zac Brown Band
  • Part 52: “If Ever You’re In My Arms Again,” by Peabo Bryson
  • Part 83: “Something Good,” from The Sound of Music.
  • Part 85: “Joy To The World,” by Three Dog Night.
  • Part 88: “Like A Rolling Stone,” by Bob Dylan.
  • Part 91: “Into the Fire,” from The Scarlet Pimpernel.

Really complicated examples:

  • Part 18: “Sleigh Ride,” covered by Pentatonix
  • Part 26: “All the Gold in California,” by the Gatlin Brothers
  • Part 40: “One of These Things Is Not Like the Others,” from Sesame Street
  • Part 42: “Take It Easy,” by The Eagles

Facebook Birthday Problem: Part 5

Recently, I devised the following problem:

Suppose that you have n friends, and you always say “Happy Birthday” to each friend on his/her birthday. On how many days of the year will you not say “Happy Birthday” to one of your friends?

Until somebody tells me otherwise, I’m calling this the Facebook birthday problem in honor of Facebook’s daily alerts to say “Happy Birthday” to friends.

Here’s how I solved this problem. Let I_k be an indicator random variable for “no friend has a birthday on day k, where k = 366 stands for February 29 and k = 1, \dots, 365 stand for the “usual” 365 days of the year. Therefore, the quantity N, representing the number of days of the year on which no friend has a birthday, can be written as

N = I_1 + \dots + I_{365} + I_{366}

In yesterday’s post, I began the calculation of the standard deviation of N by first computing its variance. This calculation is complicated by the fact that I_1, \dots, I_{366} are dependent. Yesterday, I showed that

\hbox{Var}(N) = 365\displaystyle \left( \frac{1457}{1461} \right)^n \left[ 1 - \left( \frac{1457}{1461} \right)^n \right] + \displaystyle \left( \frac{1460}{1461} \right)^n \left[ 1 - \left( \frac{1460}{1461} \right)^n \right]

+ \displaystyle (365)(364) \left[ \displaystyle \left( \frac{1453}{1461} \right)^n - \displaystyle \left( \frac{1457}{1461} \right)^{2n} \right] + 2 \sum_{k=1}^{365}\hbox{Cov}(I_k,I_{366}).

To complete this calculation, I’ll now find \hbox{Cov}(I_k,I_{366}), where 1 \le k \le 365. I’ll use the usual computation formula for a covariance,

\hbox{Cov}(I_k,I_{366}) = E(I_k I_{366}) - E(I_k) E(I_{366}).

We have calculated E(I_k) earlier in this series. In any four-year span, there are 4 \times 365 + 1 = 1461 days, of which only one is February 29. Assuming the birthday’s are evenly distributed (which actually doesn’t happen in real life), the chance that someone’s birthday is not on day k is

\displaystyle 1 - \frac{4}{1461} = \displaystyle \frac{1457}{1461},

so that the probability that no friend has a birthday on day k is

\displaystyle \left( \frac{1457}{1461} \right)^n.

Therefore, since the expected value of an indicator random variable is the probability that the event happens, we have

E(I_k) = \displaystyle \left( \frac{1457}{1461} \right)^n

for k = 1, \dots, 365. Similarly,

E(I_{366}) = \displaystyle \left( \frac{1460}{1461} \right)^n,

so that

\hbox{Cov}(I_k,I_{366}) = E(I_k I_{366}) - \displaystyle \left( \frac{1457}{1461} \right)^n \left( \frac{1460}{1461} \right)^n.

To find E(I_k I_{366}), we note that since I_k is equal to either 0 or 1 and I_{366} is equal to either 0 or 1, the product I_k I_{366} can only equal 0 and 1 as well. Therefore, I_k I_{366} is itself an indicator random variable. Furthermore, I_k I_{366} = 1 if and only if I_k = 1 and I_{366} = 1, which means that no friends has a birthday on either day k or day 366 (that is, February 29). The chance that someone doesn’t have a birthday on day k or February 29 is

\displaystyle 1 - \frac{4}{1461} - \frac{1}{1461} = \displaystyle \frac{1456}{1461},

so that the probability that no friend has a birthday on day k or February 29 is

\displaystyle \left( \frac{1456}{1461} \right)^n.

Therefore, as before,

E(I_k I_{366}) = \displaystyle \left( \frac{1456}{1461} \right)^n,

so that

\hbox{Cov}(I_k,I_{366}) = \displaystyle \left( \frac{1456}{1461} \right)^n - \displaystyle \left( \frac{1457}{1461} \right)^n \left( \frac{1460}{1461} \right)^n.

Therefore,

\hbox{Var}(N) = 365\displaystyle \left( \frac{1457}{1461} \right)^n \left[ 1 - \left( \frac{1457}{1461} \right)^n \right] + \displaystyle \left( \frac{1460}{1461} \right)^n \left[ 1 - \left( \frac{1460}{1461} \right)^n \right]

+ \displaystyle (365)(364) \left[ \displaystyle \left( \frac{1453}{1461} \right)^n - \displaystyle \left( \frac{1457}{1461} \right)^{2n} \right] + 2(365) \left[ \left( \frac{1456}{1461} \right)^n - \displaystyle \left( \frac{1457}{1461} \right)^n \left( \frac{1460}{1461} \right)^n \right],

and we find the standard deviation of N using

\hbox{SD}(N) = \sqrt{\hbox{Var}(N)}.

The graph below shows the expected value of N, which was shown earlier to be

E(N) = 365 \displaystyle \left( \frac{1457}{1461} \right)^n + \left( \frac{1460}{1461} \right)^n,

along with error bars representing two standard deviations.

Interestingly, the standard deviation of N changes for different values of n; a direct calculation shows that the \hbox{SD}(N) is maximized at n = 459 with maximum value of approximately 6.1. Accordingly, for n = 450 and n = 500, the error bars in the above figure have a total width of approximately 24 days (two standard deviations both above and below the expected value).

Facebook Birthday Problem: Part 4

Recently, I devised the following problem:

Suppose that you have n friends, and you always say “Happy Birthday” to each friend on his/her birthday. On how many days of the year will you not say “Happy Birthday” to one of your friends?

Until somebody tells me otherwise, I’m calling this the Facebook birthday problem in honor of Facebook’s daily alerts to say “Happy Birthday” to friends.

Here’s how I solved this problem. Let I_k be an indicator random variable for “no friend has a birthday on day k, where k = 366 stands for February 29 and k = 1, \dots, 365 stand for the “usual” 365 days of the year. Therefore, the quantity N, representing the number of days of the year on which no friend has a birthday, can be written as

N = I_1 + \dots + I_{365} + I_{366}

In yesterday’s post, I began the calculation of the standard deviation of N by first computing its variance. This calculation is complicated by the fact that I_1, \dots, I_{366} are dependent. Yesterday, I showed that

\hbox{Var}(N) = 365\displaystyle \left( \frac{1457}{1461} \right)^n \left[ 1 - \left( \frac{1457}{1461} \right)^n \right] + \displaystyle \left( \frac{1460}{1461} \right)^n \left[ 1 - \left( \frac{1460}{1461} \right)^n \right]

+ \displaystyle 2 \!\!\!\!\! \sum_{1 \le j < k \le 365} \!\!\!\!\! \hbox{Cov}(I_j,I_k) + 2 \sum_{k=1}^{365} \hbox{Cov}(I_k,I_{366})

To complete this calculation, I’ll now find the covariances. I’ll begin with \hbox{Cov}(I_j,I_k) if 1 \le j < k \le 365; that is, if j and k are days other than February 29. I’ll use the usual computation formula for a covariance,

\hbox{Cov}(I_j,I_k) = E(I_j I_k) - E(I_j) E(I_k).

We have calculated E(I_k) earlier in this series. In any four-year span, there are 4 \times 365 + 1 = 1461 days, of which only one is February 29. Assuming the birthday’s are evenly distributed (which actually doesn’t happen in real life), the chance that someone’s birthday is not on day k is

\displaystyle 1 - \frac{4}{1461} = \displaystyle \frac{1457}{1461},

so that the probability that no friend has a birthday on day k is

\displaystyle \left( \frac{1457}{1461} \right)^n.

Therefore, since the expected value of an indicator random variable is the probability that the event happens, we have

E(I_k) = \displaystyle \left( \frac{1457}{1461} \right)^n

for k = 1, \dots, 365. Therefore,

\hbox{Cov}(I_j,I_k) = E(I_j I_k) - \displaystyle \left( \frac{1457}{1461} \right)^n \left( \frac{1457}{1461} \right)^n = E(I_j I_k) - \displaystyle \left( \frac{1457}{1461} \right)^{2n}.

To find E(I_j I_k), we note that since I_j is equal to either 0 or 1 and I_k is equal to either 0 or 1, the product I_j I_k can only equal 0 and 1 as well. Therefore, I_j I_k is itself an indicator random variable, which I’ll call I_{jk}. Furthermore, I_{jk} if and only if I_j = 1 and I_k = 1, which means that no friends has a birthday on either day j or day k. The chance that someone doesn’t have a birthday on day j or day k is

\displaystyle 1 - \frac{4}{1461} - \frac{4}{1461} = \displaystyle \frac{1453}{1461},

so that the probability that no friend has a birthday on day j or k is

\displaystyle \left( \frac{1453}{1461} \right)^n.

Therefore, as before,

E(I_j I_k) = \displaystyle \left( \frac{1453}{1461} \right)^n,

so that

\hbox{Cov}(I_j,I_k) = \displaystyle \left( \frac{1453}{1461} \right)^n - \displaystyle \left( \frac{1457}{1461} \right)^{2n}.

Since there are \displaystyle {365 \choose 2} = \displaystyle \frac{365\times 364}{2} pairs (j,k) so that 1 \le j < k \le 365, we have

\hbox{Var}(N) = 365\displaystyle \left( \frac{1457}{1461} \right)^n \left[ 1 - \left( \frac{1457}{1461} \right)^n \right] + \displaystyle \left( \frac{1460}{1461} \right)^n \left[ 1 - \left( \frac{1460}{1461} \right)^n \right]

+ \displaystyle 2 \times \displaystyle \frac{365\times 364}{2} \left[ \displaystyle \left( \frac{1453}{1461} \right)^n - \displaystyle \left( \frac{1457}{1461} \right)^{2n} \right] + 2 \sum_{k=1}^{365}\hbox{Cov}(I_k,I_{366}),

or

\hbox{Var}(N) = 365\displaystyle \left( \frac{1457}{1461} \right)^n \left[ 1 - \left( \frac{1457}{1461} \right)^n \right] + \displaystyle \left( \frac{1460}{1461} \right)^n \left[ 1 - \left( \frac{1460}{1461} \right)^n \right]

+ \displaystyle (365)(364) \left[ \displaystyle \left( \frac{1453}{1461} \right)^n - \displaystyle \left( \frac{1457}{1461} \right)^{2n} \right] + 2 \sum_{k=1}^{365}\hbox{Cov}(I_k,I_{366}).

The calculation of \hbox{Cov}(I_k,I_{366}) is similar to the above calculation; I’ll write this up in tomorrow’s post.

Facebook Birthday Problem: Part 3

Recently, I devised the following problem:

Suppose that you have n friends, and you always say “Happy Birthday” to each friend on his/her birthday. On how many days of the year will you not say “Happy Birthday” to one of your friends?

Until somebody tells me otherwise, I’m calling this the Facebook birthday problem in honor of Facebook’s daily alerts to say “Happy Birthday” to friends.

Here’s how I solved this problem. Let I_k be an indicator random variable for “no friend has a birthday on day k, where k = 366 stands for February 29 and k = 1, \dots, 365 stand for the “usual” 365 days of the year. Therefore, the quantity N, representing the number of days of the year on which no friend has a birthday, can be written as

N = I_1 + \dots + I_{365} + I_{366}

In yesterday’s post, I showed that

E(N) = E(I_1) + \dots + E(I_{365}) + E(I_{366}) = 365 \displaystyle \left( \frac{1457}{1461} \right)^n + \left( \frac{1460}{1461} \right)^n.

The calculation of the standard deviation of N is considerably more complicated, however, since the I_1, \dots, I_{366} are dependent. So we will begin by computing the variance of N:

\hbox{Var}(N) = \displaystyle \sum_{k=1}^{366} \hbox{Var}(I_k) + 2 \!\!\!\!\! \sum_{1 \le j < k \le 366} \!\!\!\!\! \hbox{Cov}(I_j,I_k),

or

\hbox{Var}(N) = \displaystyle \sum_{k=1}^{365} \hbox{Var}(I_k) + \hbox{Var}(I_{366}) + 2 \!\!\!\!\! \sum_{1 \le j < k \le 365} \!\!\!\!\! \hbox{Cov}(I_j,I_k) + 2 \sum_{k=1}^{365} \hbox{Cov}(I_k,I_{366})

For the first term, we recognize that, in any four-year span, there are 4 \times 365 + 1 = 1461 days, of which only one is February 29. Assuming the birthday’s are evenly distributed (which actually doesn’t happen in real life), the chance that someone’s birthday is not on day k is

\displaystyle 1 - \frac{4}{1461} = \displaystyle \frac{1457}{1461}.

Therefore, the chance that all n friends don’t have a birthday on day k is

\displaystyle \left( \frac{1457}{1461} \right)^n.

Using the formula \hbox{Var}(I) = p(1-p) for the variance of an indicator random variable, we see that

\hbox{Var}(I_k) = \displaystyle \left( \frac{1457}{1461} \right)^n \left[ 1 - \left( \frac{1457}{1461} \right)^n \right]

for k = 1, \dots, 365. Similarly, for the second term,

\hbox{Var}(I_{366}) = \displaystyle \left( \frac{1460}{1461} \right)^n \left[ 1 - \left( \frac{1460}{1461} \right)^n \right]

Therefore, so far we have shown that

\hbox{Var}(N) = 365\displaystyle \left( \frac{1457}{1461} \right)^n \left[ 1 - \left( \frac{1457}{1461} \right)^n \right] + \displaystyle \left( \frac{1460}{1461} \right)^n \left[ 1 - \left( \frac{1460}{1461} \right)^n \right]

+ \displaystyle 2 \!\!\!\!\! \sum_{1 \le j < k \le 365} \!\!\!\!\! \hbox{Cov}(I_j,I_k) + 2 \sum_{k=1}^{365} \hbox{Cov}(I_k,I_{366})

In tomorrow’s post, I’ll complete this calculation by finding the covariances.

Facebook Birthday Problem: Part 2

Recently, I devised the following problem:

Suppose that you have n friends, and you always say “Happy Birthday” to each friend on his/her birthday. On how many days of the year will you not say “Happy Birthday” to one of your friends?

Until somebody tells me otherwise, I’m calling this the Facebook birthday problem in honor of Facebook’s daily alerts to say “Happy Birthday” to friends.

Here’s how I solved this problem. Let I_k be an indicator random variable for “no friend has a birthday on day k, where k = 366 stands for February 29 and k = 1, \dots, 365 stand for the “usual” 365 days of the year. Therefore, the quantity N, representing the number of days of the year on which no friend has a birthday, can be written as

N = I_1 + \dots + I_{365} + I_{366}

Let’s start with any of the “usual” days. In any four-year span, there are 4 \times 365 + 1 = 1461 days, of which only one is February 29. Assuming the birthday’s are evenly distributed (which actually doesn’t happen in real life), the chance that someone’s birthday is not on day k is

\displaystyle 1 - \frac{4}{1461} = \displaystyle \frac{1457}{1461}.

Therefore, the chance that all n friends don’t have a birthday on day k is

\displaystyle \left( \frac{1457}{1461} \right)^n.

Since the expected value of an indicator random variable is the probability of the event, we see that

E(I_k) = \displaystyle \left( \frac{1457}{1461} \right)^n

for k = 1, \dots, 365. Similarly, the expected value for the indicator for February 29 is

E(I_{366}) = \displaystyle \left( \frac{1460}{1461} \right)^n.

Since E(X+Y) = E(X) + E(Y) even if X and Y are dependent, we therefore conclude that

E(N) = E(I_1) + \dots + E(I_{365}) + E(I_{366}) = 365 \displaystyle \left( \frac{1457}{1461} \right)^n + \left( \frac{1460}{1461} \right)^n.

This function is represented by the red dots on the graph below.

In tomorrow’s post, I’ll calculate of the standard deviation of N.

Facebook Birthday Problem: Part 1

The “birthday problem” is one of the classic problems in elementary probability because of its counter-intuitive solution. From Wikipedia:

In probability theory, the birthday problem or birthday paradox concerns the probability that, in a set of n randomly chosen people, some pair of them will have the same birthday. By the pigeonhole principle, the probability reaches 100% when the number of people reaches 367 (since there are only 366 possible birthdays, including February 29). However, 99.9% probability is reached with just 70 people, and 50% probability with 23 people. These conclusions are based on the assumption that each day of the year (except February 29) is equally probable for a birthday.

Recently, I devised the following different birthday problem:

Suppose that you have n friends, and you always say “Happy Birthday” to each friend on his/her birthday. On how many days of the year will you not say “Happy Birthday” to one of your friends?

Until somebody tells me otherwise, I’m calling this the Facebook birthday problem in honor of Facebook’s daily alerts to say “Happy Birthday” to friends.

In this series, I will solve this problem. While this may ruin the suspense, here’s a graph of the solution for 100 \le n \le 1000 along with error bars indicating two standard deviations.

Before deriving this solution, I’ll start with a thought bubble if you’d like to take some time to think about how to do this.