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.

Happy Pythagoras Day!

Happy Pythagoras Day! Today is 8/15/17 (or 15/8/17 in other parts of the world), and 8^2+15^2=17^2.

We might as well celebrate today, because the next Pythagoras Day won’t happen for over 3 years. (Bonus points if you can figure out when it will be.)

Passenger Delays Flight After Mistaking Math Equations for Terrorist Code

I wish I could say that this came from The Onion, but sadly this really happened:

http://www.slate.com/blogs/the_slatest/2016/05/07/passenger_delays_flight_after_mistaking_professor_s_math_equations_for_terrorist.html?wpsrc=sh_all_mob_em_ru

A flight from Philadelphia to Syracuse, New York, was delayed for two hours on Thursday after a woman expressed fears to the cabin crew that the man sitting next to her was a terrorist scribbling some sort of terrorist code into a notepad. In reality, he was a 40-year-old tenured professor at the University of Pennsylvania who was working on a differential equation…

Menzio insists he was “treated respectfully throughout” but says the whole incident served to illustrate a “broken system that does not collect information efficiently” and that anyone can end up causing a flight to be delayed for hours, no matter how ridiculous the suspicion.

Constructing an angle’s trisectors

I really enjoyed this video about how to trisect angles. Trisection of arbitrary angles is impossible using only a straightedge and compass; however, it is possible by carefully folding a piece of paper.

For further reading:

http://mars.wne.edu/~thull/papers/amer.math.monthly.118.04.307-hull.pdf

https://en.wikipedia.org/wiki/Huzita%E2%80%93Hatori_axioms

Solving a Math Competition Problem: Part 9

This series of posts concerns solving the following problem from the 2016 University of Maryland High School Mathematics Competition.

A sphere is divided into regions by 9 planes that are passing through its center. What is the largest possible number of regions that are created on its surface?

a. 2^8

b. 2^9

c. 81

d. 76

e. 74

This series was actually written by my friend Jeff Cagle, department head for mathematics at Chapelgate Christian Academy, as he tried technique after technique to solve this problem. I thought that his resolution to the problem was an excellent example of the process of mathematical problem-solving, and (with his permission) I am posting the process of his solution here. (For the record, I have no doubt that I would not have been able to solve this problem.)

Reflection
I didn’t really need the projection into the plane for the solution, but my problem-solving self needed it to be able to count points and regions in slow motion. So, I should present a cleaned-up solution:

 

Solution
Since there are 9 planes, each plane must intersect with every other in a line, creating two points on the surface of the sphere. Thus, there are (9∗8)/2 * 2 = 72 points of intersection, and for n planes, there are 𝑛(𝑛 − 1) points of intersection. With the first plane, there are zero points of intersection and two regions. Suppose we now have n planes and N regions. We add another plane, creating a circle on the sphere. For each segment that the circle intersects, it creates an additional intersection point as it enters, and it divides the region into two parts, adding one additional region. Hence, for each point added, a region is added as well. Since there are two
regions with zero points, there are thus 74 regions with 72 points of intersection.

Solving a Math Competition Problem: Part 8

This series of posts concerns solving the following problem from the 2016 University of Maryland High School Mathematics Competition.

A sphere is divided into regions by 9 planes that are passing through its center. What is the largest possible number of regions that are created on its surface?

a. 2^8

b. 2^9

c. 81

d. 76

e. 74

This series was actually written by my friend Jeff Cagle, department head for mathematics at Chapelgate Christian Academy, as he tried technique after technique to solve this problem. I thought that his resolution to the problem was an excellent example of the process of mathematical problem-solving, and (with his permission) I am posting the process of his solution here. (For the record, I have no doubt that I would not have been able to solve this problem.)

OK, so I wanted to prove that each region would be a triangle. So I decided to project the sphere onto a plane.

The projection of four planes:

Conjecture: The max number of regions is the number of intersection points plus 2.
Proof (by induction)
If we have 1 plane, we have no intersection points and 2 regions. Suppose we have n planes with 𝑛(𝑛 − 1) intersection points and 𝑛(𝑛 − 1) + 2 regions. Now we add the next plane to our figure. The plane creates a circle on the sphere. To maximize the number of regions, we angle the plane so that our circle does not intersect any already-existing intersection points. So the circle goes through a number of segments. Each time it does, it cuts the region bounded by that segment into two. So for each new intersection point, we lose one region and gain two, for a net gain of one region. That is, however many intersection points are added, that will be the number of regions added as well. And since 𝑛 + 1 planes have (𝑛 + 1)(𝑛) intersection points, we will
have (𝑛 + 1)(𝑛) + 2 max regions. DONE.
For the original competition problem, we have 9 planes and hence 9*8 + 2 = 74 regions, answer e.

Solving a Math Competition Problem: Part 7

This series of posts concerns solving the following problem from the 2016 University of Maryland High School Mathematics Competition.

A sphere is divided into regions by 9 planes that are passing through its center. What is the largest possible number of regions that are created on its surface?

a. 2^8

b. 2^9

c. 81

d. 76

e. 74

This series was actually written by my friend Jeff Cagle, department head for mathematics at Chapelgate Christian Academy, as he tried technique after technique to solve this problem. I thought that his resolution to the problem was an excellent example of the process of mathematical problem-solving, and (with his permission) I am posting the process of his solution here. (For the record, I have no doubt that I would not have been able to solve this problem.)

OK, so I wanted to prove that each region would be a triangle. So I decided to project the sphere onto a plane.

The projection of four planes:

After a while, I had a chart for max possible regions.

  • 1 plane: Max regions = 2
  • 2 planes: Max regions = 4
  • 3 planes: Max regions = 8 (exponential?)
  • 4 planes: Max regions = 14 (nope!)
  • 5 planes: Max regions = 22 (huh?)

Then, really because I had no other ideas, I tried counting intersection points AND max regions
(remembering that one intersection point is “at infinity” – that is, the north pole).

  • 1 plane: Intersection Points = 0, Max regions = 2
  • 2 planes: Intersection Points = 2, Max regions = 4
  • 3 planes: Intersection Points = 6, Max regions = 8
  • 4 planes: Intersection Points = 12, Max regions = 14
  • 5 planes: Intersection Points  20, Max regions = 22

Oh. My. Goodness. The max regions are simply the number of intersection points plus 2. Could it really REALLY be that simple?

Solving a Math Competition Problem: Part 6

This series of posts concerns solving the following problem from the 2016 University of Maryland High School Mathematics Competition.

A sphere is divided into regions by 9 planes that are passing through its center. What is the largest possible number of regions that are created on its surface?

a. 2^8

b. 2^9

c. 81

d. 76

e. 74

This series was actually written by my friend Jeff Cagle, department head for mathematics at Chapelgate Christian Academy, as he tried technique after technique to solve this problem. I thought that his resolution to the problem was an excellent example of the process of mathematical problem-solving, and (with his permission) I am posting the process of his solution here. (For the record, I have no doubt that I would not have been able to solve this problem.)

OK, so I wanted to prove that each region would be a triangle. So I decided to project the sphere onto a plane.

The projection of four planes:

After a while, I had a chart for max possible regions.

  • 1 plane: Max regions = 2
  • 2 planes: Max regions = 4
  • 3 planes: Max regions = 8 (exponential?)
  • 4 planes: Max regions = 14 (nope!)
  • 5 planes: Max regions = 22 (huh?)

Solving a Math Competition Problem: Part 5

This series of posts concerns solving the following problem from the 2016 University of Maryland High School Mathematics Competition.

A sphere is divided into regions by 9 planes that are passing through its center. What is the largest possible number of regions that are created on its surface?

a. 2^8

b. 2^9

c. 81

d. 76

e. 74

This series was actually written by my friend Jeff Cagle, department head for mathematics at Chapelgate Christian Academy, as he tried technique after technique to solve this problem. I thought that his resolution to the problem was an excellent example of the process of mathematical problem-solving, and (with his permission) I am posting the process of his solution here. (For the record, I have no doubt that I would not have been able to solve this problem.)

OK, so I wanted to prove that each region would be a triangle. So I decided to project the sphere onto a plane.

For a while, I toyed with the situation where we have

  • Plane 1 – equator (this always happens: Just make plane 1 the equator) 𝑃1(0𝑁, 0𝐸).
  • Plane 2 – Prime Meridian 𝑃2(90𝑁, 0𝐸)
  • Plane 3 – Intl Date Line 𝑃3(90𝑁, 90𝐸)
  • Plane 4 – at an angle to all of those 𝑃4(45𝑁, 45𝐸)

Here is our mapping with P1, P2, and P3 on it:

Now, how to represent P4? Aha! The inside of the unit circle is the southern hemisphere, and the outside is the northern. P4 must hit the equator a two points 180 degrees apart, go inside the southern hemisphere, and then outside to the northern. Thus:

The white region is a NONtriangular region created by the intersection of four planes. These are strange-looking regions, and I spent a long time – several days – vainly trying to count max regions created when I added P5, P6 etc. But one thing was clear: not all of the regions are triangular, nor can they be. For if a plane (say P4) cuts through a triangular region, it will create a new triangular region and a non-triangular “quadrilateral”, as in the figure below. So counting triangles from points is NOT the solution here!