Globe Trotting Problem

It’s been such a long time since my last post. Since then, I’ve graduated from Carleton College, moved to Brooklyn, and starting developing software for a firm over in Manhattan. Now that I’ve found my new groove, and now that I have some down time due to the holidays, I figure it’s time to write a new post!

One awesome perk about my job is that on Fridays, the developers get sent these brain teasers to solve. Today I’d like to share one particularly interesting problem.

The Problem: How many points are there on Earth such that you can walk one mile south, one mile east, and one mile north only to end up at the same starting point? Describe these points. Assume that the Earth is a perfect sphere.

Continue reading

Advertisements

The Birthday Problem

I was watching Law and Order: Special Victims Unit the other day (great show!) and I noticed a highly improbable outcome when the SVU team was struggling to find the twin brother of a detained suspect. The following is a summary of what occurs in the episode:

“Fin says he is already looking for Brian Smith and Munch comments about how many have that name. Benson wonders how many follow their twin to New York. Fin says there are 126 Brian Smiths [the twin of interest] in New York City. Rollins comments that as they are twins to look at their birthdates. Fin finds a match.” [1]

Probabilistically speaking, there is an approximate 2.097\times10^{-9}\% = 0.000000002097\% chance that Fin finds exactly one Brian Smith with the same birthday as the detained suspect [2]; that is a very low probability that luckily works out for our SVU team!

How did I get to this number?

Continue reading

Another Brain Teaser!

This past week, I flew out to New York. Unfortunately, I forgot my phone charger and used the majority of my laptop’s battery life while working at the gate (doh!). Thus, after completing the Sudoku in the airline magazine and getting my fill of the SkyMall catalog, I began to look around. After a while, I felt like David Puddy from Seinfeld (see video for reference)!

Then, for whatever reason, my eye caught those overhead cabinets and I began to think of a brainteaser. I share it with you today.

For arguments sake, let’s imagine a very large plane where there are 100 overhead cabinets on one side of the aisle. Suppose I start from the back of the plane and open every single one of them, one at a time, until I open the last one in first class. Then, suppose I go to the back of the plane again and proceed to close every other cabinet starting with the second one. Now suppose on this third round, I go to every third cabinet and close it if it’s open, or open it if it’s closed.

Define: An n-round to be the round of walking from the back to the front of the plane opening (or closing if appropriate) every nth cabinet.

The Question: For n from 1 to 100, suppose I perform an n-round. After the 100th n-round, where I either open or close the 100th cabinet, how many cabinets are left open? Continue reading

The Gauss-Markov Theorem (pt. 3)

Today, we will finish up proving the \hat \beta_2 case of the Gauss-Markov Theorem. Recall that this theorem goes as follows:

Theorem: By respecting assumptions described in this post, the estimators \hat \beta_1 and \hat \beta_2, in the class of unbiased linear estimators, are best linear unbiased estimators of \beta_1 and \beta_2 respectively. That is, they are linear unbiased estimators that have minimium variance.

So where are we in our journey of proving this theorem? I have shown that \hat \beta_2 is linear and that it is unbiased–that the expected value of \hat \beta_2 is equal to \beta_2. Today, I show that it has minimum variance.

Continue reading

The Gauss-Markov Theorem (pt. 2)

I continue the proof from my last post of the Gauss-Markov Theorem.

Theorem: By respecting assumptions described last time, the estimators \hat \beta_1 and \hat \beta_2, in the class of unbiased linear estimators, are best linear unbiased estimators of \beta_1 and \beta_2 respectively. That is, they are linear unbiased estimators that have minimium variance.

Last time I showed that \hat \beta_2 is linear. Today, I show that it is unbiased–that the expected value of \hat \beta_2 is equal to \beta_2.

Continue reading

The Gauss-Markov Theorem (pt. 1)

Anyone who runs linear regression on two-variables nowadays probably clicks a button or writes some code in a command line in some application—R, S plus, Gretl, or Microsoft Excel to name a few—and lets the method of ordinary least squares (OLS) do its magic. Seldom do we remember why we can use OLS to approximate our dependent variable. This post today discusses the why.[1]

The math behind the following was made available to me through Damodar N. Gujarati’s [2].

First, some background: Let variables Y and X be given such that their population regression function (PRF) is of the form E(Y|X_i) = \beta_1 + \beta_2 X_i, where \beta_1 is the y-intercept of the line and \beta_2 is the slope. For each value of X_i, Y_i is found using the PRF for these two variables, Y_i =E(Y|X_i) + u_i = \beta_1 + \beta_2X_i + u_i. That is to say, the value of Y_i is its expected value conditioned on X_i (positioned on the line), plus its residual value u_i (the distance from the population line to the actual Y_i value).

In reality, we do not deal with entire populations of data. Rather, we spend our time Continue reading

The Power of the Four Color Theorem

Today, I will prove last post‘s theorem in a different way assuming the four color theorem. This should illustrate the power of the four color theorem quite nicely. Again, please refer to this post for the definitions of the terms I use.

The four color theorem is as follows: Given a planar graph G, the chromatic number \chi(G)\leq 4.

I assume the four color theorem in order to prove the following theorem about outerplanar graphs.

Theorem: Given an outerplanar graph G, its chromatic number \chi(G)\leq 3.

Proof: If a maximal outerplanar graph on a set of vertices yields a chromatic number less than or equal to 3, then surely, Continue reading

Coloring Outerplanar Graphs

Today, I will talk about a powerful, yet simple theorem from combinatorics that deals with chromatic numbers of graphs–specifically, outerplanar graphs. If you are unfamiliar with the terms I discuss here, please read my previous post that defines what what I am talking about.

Now, the theorem that I want to prove today is the following:

Theorem: Given an outerplanar graph G, its chromatic number \chi(G) \le 3.

Proof: If a maximal outerplanar graph on a set of vertices yields a chromatic number less than or equal to 3, then Continue reading