Two Daughters

Season 3, episode 2

This is the sequel to Spree, Crystal tries to find her daughter and erase mistakes of her past. Crystal kidnaps Megan and the FBI team tries to capture her before someone else gets hurt. Charlie uses math to locate Crystal's position and understand what she is trying to accomplish.

Changing the Rules of the Game

Charlie illustrated the fact that Tic-Tac-Toe is a game where there is no winner assuming that both players do not make mistakes. He point out that in order for a player to win one needs to change the rules a bit. Let us consider some variations of Tic-Tac-Toe.
Tic-Tac-Toe is an ancient game, and it has been played since as early as 1300 BC by the Egyptians. It has many other names, and its simplicity makes it a good introductory example of a combinatorial game.

Activity 1: Variations of Tic-Tac-Toe

  1. Suppose that the first player is allowed to make two moves consecutively. Show that the first player is always able to win.
  2. Now suppose that both players are allowed to make two consecutive moves. Show that in this case the first player is also always able to win.
  3. Suppose we now play Tic-Tac-Toe in a 3x3x3 cube. Here a player wins if he/she is able to place three X's (or 0's) in a row, column, or diagonal. This game can be won by either the first or second player (as supposed to a draw). Which player can always win? What is the winning strategy (list of moves) needed for that player to win?
  4. Consider the following game: Two players take turns selecting integers from 1 to 9, without repetition. The player who is able to select three numbers (not necessarily in consecutive moves) so that their sum is 15 is the winner. Show that this game is just Tic-Tac-Toe in disguise.
  5. Can you think of a version of Tic-Tac-Toe where the second player is always able to win?

Trawler Boat Problem

When trying to rescue Megan, Charlie suggests using the solution to the Trawler Boat Problem to narrow down the possible locations of Crystal. The problem is the following: There are two boats traveling at constant speeds, and the faster boat is chasing the slower. At some point the slower boat enters a fog bank, and the faster boat cannot see it anymore. What should the faster boat do to catch the slower boat? In this episode, the FBI is the faster boat and Crystal is the slower boat. The solution is quite surprising, but before explaining it in detail, we simplify the problem a bit. Let us denote by F the faster boat and by S the slower boat, and let us say that S's is moving at a speed of v m/s. We also assume that the boats were moving in a straight line, and that the S keeps moving in a straight line after F cannot see it anymore (that is, S just changed directions)

The logarithmic spiral (a.k.a. equiangular spiral) was first described by René Descartes in 1638. Later Jakob Bernoulli named it spira mirabilis, latin for "miraculous spiral" because of the nice property that the size of the spiral increases but its shape is unaltered with each successive curve. Bernoulli was so fascinated by the curve that he asked that it be engraved on his head stone. Unfortunately the carver put an Archimedes spiral instead by accident. Perhaps people have described this curved as miraculous due to its presence in nature, as depicted below.

Simplified version

Suppose that both boats start their movement at the same point A, and at the same time. The slower boat S moves away from A, but the faster boat F cannot see S's direction, but knows that at time t (in seconds), B will be vt meters away from A. So to catch S it is enough for F to be vt meters away from A at every moment. But since F does not know S's direction, it also needs to cover all possible directions S might have chosen. To do this, S needs to travel along a logarithmic spiral. The picture below describes what is going on: The blue curve represents F's movement, and the red line represents S's movement. At time t S is at the intersection of the red line and the circle of center A and radius t, while F is at the intersection of the blue curve and the same circle.

That is, at time t, F is vt meters away from A, just like S. So F will eventually catch up with S, and this will happen at the intersection of both curves.

Version in the show

Now let us revisit the original problem. Here the boats do not start at the same point, but the problem can be reduced to the simple version discussed above by taking island to be the point where the S disappeared from F's sight.

However, we do not need to go all the way to A and the start the spiral. The solution is for F to assume that S is heading towards it. If this is the case, F will catch it for sure, otherwise we move along the spiral with center the point where S disappear. As before, F and S will both be at the same distance from A (the point where S disappeared) and F will eventually catch S. A natural question to ask is how fast does F need to be traveling? You are given the chance of thinking about this exact question in Activity 2.

Equations of the logarithmic Spiral

In polar coordinates, the equation for the logarithmic spiral is simply where a and b are positive real numbers. Recall that in polar coordinates, (r, θ) represents the point at distance r from the origin and angle θ from the horizontal line going through the origin. Doing the standard conversion x(t) = r cos(t) and y(t) = r sin(t) we get the parametric equations of this curve. It has the nice property that the angle φ between the tangent and radial line at the point (r, θ) constant. Since since , the said property can be represented with the following equation below

Activity 2

  1. In the equations described for a logarithmic spiral, consider and describe the curve obtained in this manner.
  2. In the case as above, what is φ approaching?
  3. Give conditions for F to be able to catch S in terms of S's velocity. How fast must F be traveling?

Galton Board

When the FBI team is closed to capture Crystal, Charlie (inadvertently) compares the situation to the Galton Board. The picture to the right describes the basic idea of this object. It consists of a funnel-shaped vertical board with nails arranged as the green dots in the picture, with transparent walls fixed by the nails. The Galton board is used to perform the following experiment: We place a ball at the top of the board (represented by the red dot) and let it fall until it falls in one of the containers at the bottom. If we repeat the experiment enough times, we will notice that the piles of balls describe a bell curve.The picture to the right has 5 rows of nails, but we can construct as many rows as we want.

Let us study what is going one in more detail. Notice that every time the ball hits a pin, it can either go to the right with some probability p, or go to the left with probability q = 1 - p. One would expect that p = q = 1/2, but the board could be built with a material that favors right turns. So it makes sense to make no assumptions about p and q. Similarly, we assume that the board has n rows of pins (with n = 5 in our picture).

To argue that the results of the experiment look like a bell curve, we notice that it is easier for a ball to fall in one of the containers in the middle of the board than at one of the containers at the extremes. This is because there are more ways to get to the center than, say, to the first container. For instance, the probability of a ball falling in the first container (from left to right) is q^n, since at each row we decided to go to the left each time. Now, let us compute the probability of a ball falling into the second container: Notice that in order for a ball to fall in the first container, it must have gone once to the right of a pin, and the rest of the time it must have gone left, and so there are n paths that lead to the second container (why?). So the probability of falling into the second container is npq^(n-1). In the activity below you are given the chance of computing the probabilities for a general board.

Activity 3

  1. Recall the construction of Pascal's triangle. We can place the numbers of every row of Pascal's triangle between two nails and between the edge and the first and last row, as shown in the picture to the right. What are these numbers counting? It may be helpful to notice that the path a ball takes from the top to one of the containers can be encoded with a sequence of letters L (for left) and R (for right).
  2. Using the picture to the right, and assuming that every time a ball hits a nail it has probability p to go to the right and probability q = 1 - p to go to the left, compute the probability of a ball to end up in the first container (from left to right). [Hint: If a ball ends up in the first container, then it must go to the left every time it hits a nail] Do the same for all the other containers, and generalize the result for a board with n rows. You will need the result from part a. to do this correctly.
  3. Take n = 6, p = q = 1/2. Use your results from c. to make a draw a graph in the x-y plane, where x = i represent the containers i of the Galton board and y being the probability of a ball reaching container i. Compare your points to a bell curve. This is an illustration that the normal distribution approaches the binomial distribution.
  4. Now suppose you want each ball to fall in the first 4 containers, so you place some obstacles on the board to avoid the balls from falling into the remaining containers. What is the minimal number of obstacles that you have to place?
  5. In the situation of d., for each container, compute the probability of a ball ending up in it.