Home Profile Projects Articles

Answer: Pick-up Sticks Game

Saturday, 12 of January , 2008 at 12:01 am

Question: The Fort Boyard TV Series had a game where 19 sticks were placed on the ground. Two players would take turns picking up sticks. A player is only allowed to pick up 1, 2, or 3 sticks each round. The person who picks up the last stick loses. What is each player’s “optimal” strategy? If both players play “optimal” strategies, who will win?

Answer: According to the Axiom of Determinacy, any finite two-person game, with perfect information, will have a winning strategy for one of the players. This will mean that one of the two players in our game will have an “optimal” strategy.

In order to determine the optimal strategy, will need to make a decision tree. For the Pick-up Sticks Game, we will have the following decision tree:

Player one starts the game on node 19 and is allowed to move to any connected node. Player two then moves to another connected node. This continues until one of the players reaches node 1 and wins the game.

Next, we will need to start coloring the nodes with P and N which are defined as:

N: The node is a winning position for the next player.
P: The node is a winning position for the previous player.

This would mean, if node 19 was colored N, player one would win. However, if node 19 was colored P, player two would win. Also, we already know that node 1 has to be colored P.

In order to find the coloring of the other nodes, we need to follow two simple rules.

1) If all children are N nodes, the color of the parent has to be P.

2) If at least one of child is P, then the parent has to be labeled N.

If we apply these rules to our decision tree, we will get:

Since node 19 is labeled N, player one will win. Player one’s optimal strategy is to always move to a P colored node.

Comments (1)

Category: AI, Answers

Answer: Area of a Koch Snowflake

Thursday, 3 of January , 2008 at 9:58 pm

I am a bit late posting a solution to this problem because I was on holidays. However, I am now back to my regular routine. As for finding the area of the Koch Snowflake, Reasonable Deviations has already posted a solution to this problem. Also, Rod has posted a variation of the problem which finds the perimeter of a Koch Snowflake. Since the problem has already been solved, I will only do a quick overview of the solution.

Answer: The easiest way to solve solve this problem is to calculate the area added to the Koch Snowflake after each iteration.

Area of the first iteration can easily be calculated by using Pythagoras.

x^2 = (\frac{x}{2})^2 + h^2
h^2 = \frac{3}{4} x^2
h = \frac{\sqrt{3}}{2} x

\therefore area = (\frac{\sqrt{3}}{2} x)(\frac{x}{2}) = \frac{\sqrt{3}}{4} x^2

Using the solution for the first iteration, we can easily calculate the area of the second iteration. The area will be the area of the original equilateral triangle plus the area of 3 smaller equilateral triangles.

area =  \frac{\sqrt{3}}{4} x^2 + 3 \frac{\sqrt{3}}{4} (\frac{x}{3})^2

The area of the third iteration would, therefore, be:

area =  \frac{\sqrt{3}}{4} x^2 + 3 \frac{\sqrt{3}}{4} (\frac{x}{3})^2 + 3 \cdot 4 \frac{\sqrt{3}}{4} (\frac{x}{3^2})^2

If we continue doing this, we will get the following summation.

area =  \frac{\sqrt{3}}{4} x^2 + 3 \frac{\sqrt{3}}{4} (\frac{x}{3})^2 + 3 \cdot 4 \frac{\sqrt{3}}{4} (\frac{x}{3^2})^2 + 3 \cdot 4 \cdot 4 \frac{\sqrt{3}}{4} (\frac{x}{3^3})^2 \ldots
area =  \frac{\sqrt{3}}{4} x^2 + \sum_{i=0}^{\infty}3 \cdot 4^i \frac{\sqrt{3}}{4} \frac{x^2}{3^{2(i+1)}}
area =  \frac{\sqrt{3}}{4} x^2 + \sum_{i=0}^{\infty} \frac{3^{\frac{3}{2}}}{4} x^2 \frac{4^i}{9^{i+1}}
area =  \frac{\sqrt{3}}{4} x^2 + \sum_{i=0}^{\infty} \frac{1}{4 \sqrt{3}} x^2 (\frac{4}{9})^i

Since the summation is a geometric series, we know that \sum_{i=0}^{\infty} a r^i = \frac{a}{1-r} when r < 1.

Therefore,

area =  \frac{\sqrt{3}}{4} x^2 + \frac{1}{4 \sqrt{3}} x^2 \cdot \frac{1}{1 - \frac{4}{9}}
area =  \frac{\sqrt{3}}{4} x^2 + \frac{1}{4 \sqrt{3}} x^2 \cdot \frac{9}{5}
area =  \frac{2 \sqrt{3}}{5} x^2

Comments (3)

Category: Answers, General Math

Answer: Christmas Counting Problem

Wednesday, 26 of December , 2007 at 10:15 am

Question: If we take the 12 days of Christmas literally, what is the total number of items you will have received at the end of the twelve days? For example, on the first day you have received one item (1 partridge), on the second day you will receive three items (1 partridge, and 2 doves), on the third day you would receive six items (1 partridge, 2 doves, and 3 french hens), etc.

Solution: From my analysis, I have come up with three different ways to count the total number of items you will have received at the end of the twelve days.

1) The first method to solve this problem is to use brute force. On the first day, we will receive 1 item. On the second day, we will receive 1 + 2 items. On the third day, we will receive 1 + 2 + 3 items. Therefore, on nth day, we will receive \sum_{i=1}^n i items. Since we want the number of items received for all 12 days, we need to calculate the following summation: \sum_{n=1}^{12} \sum_{i=1}^n i. We can easily calculate the answer with the following perl script:

$soln = 0;
 
for ($i = 1; $i < 13; $i++) {
   for ($j = 1; $j < $i+1; $j++) {
      $soln = $soln + $j;
   }
}
print $soln;

2) The second method to solve this problem is to use recursion. On the nth day, you are going to get n items plus the number of items you got the day before. Therefore, if S_n is the number of items you receive on the nth day, S_n will follow this recursive pattern:

S_n = S_{n-1} + n
S_0 = 0

In order to calculate the number of items received on all 12 days, we need to calculate the following summation: S = \sum_{n=1}^{12} S_{n-1} + n. The solution can be calculated with the following script:

$soln = 0;
$prevDay = 0;
 
for ($i = 1; $i < 13; $i++) {
   $prevDay = $prevDay + $i;
   $soln = $soln + $prevDay;
}
 
print $soln;

3) The third method to solve this problem is to group items by type instead of days. For example, you will receive 1 partridge for twelve days, 2 doves for eleven days, 3 french hens for ten days, etc. In general, this means that you will receive n items for (13 - n) days. This would mean that the total number items you would receive would be \sum_{n=1}^{12} n (13 - n). This summation can be calculated by the following script:

$soln = 0;
 
for ($i = 1; $i < 13; $i++) {
   $soln = $soln + $i*(13- $i);
}
print $soln;

In the end, however, we come back to the same solution which is 364.

Leave a comment

Category: Answers, General Math

Answer: Fluid leaving a hemispherical vessel

Thursday, 20 of December , 2007 at 11:56 pm

Question: A hemispherical vessel of radius R has a small rounded orifice of area A_0 at the bottom. If A_h \gg A_0, how much time does it require to lower the level from h_1 to h_2?

Answer: First, lets assume fluid is incompressible and has a inviscid, steady, barotropic flow. If this is the case, the rate fluid leaves the vessel will be equal to the rate the fluid drops in the vessel. Therefore,

A_h \frac{\partial h}{\partial t} = A_0 u
\therefore \frac{\partial h}{\partial t} = \frac{A_0}{A_h} u

where \frac{\partial h}{\partial t} is the rate the water level drops and u is the rate the water leaves the orifice.

Now, if we use Bernoulli’s equation, we will get:

\frac{1}{2} (\frac{\partial h}{\partial t})^2 + \frac{P_{atm}}{\rho_0} + gh = \frac{1}{2}u^2 + \frac{P_{atm}}{\rho_0}
\frac{1}{2} (\frac{A_0}{A_h})^2 u^2 + gh = \frac{1}{2}u^2

Since A_h \gg A_0, \therefore (\frac{A_0}{A_h})^2 \approx 0. Using this approximation, we find that

u = \sqrt{2gh}

Next, we will need to find A_h.

According to Pythagoras ,

R^2 = r^2 + (R-h)^2
r = (R^2 - R^2 - h^2 +2hR)^{\frac{1}{2}} = (2hR - h^2)^{\frac{1}{2}}

Therefore,

A_h = \pi r^2 = \pi (2hR-h^2)

Now using the fact that A_h \frac{\partial h}{\partial t} = A_0 u, we have

\pi(2hR - h^2)\frac{\partial h}{\partial t} = A_0  \sqrt{2gh}
\int_{h_1}^{h_2} \pi (2 h^{\frac{1}{2}}R - h^{\frac{3}{2}})dh = \int_0^t A_0 \sqrt{2g}dt
\pi(\frac{4}{3}Rh^{\frac{3}{2}} - \frac{2}{5}h^{\frac{5}{2}}) \arrowvert_{h_1}^{h_2} = A_0 \sqrt{2g}t
t = \frac{2\pi}{A_0 \sqrt{2g}}(\frac{2}{3}R(h_1^{\frac{3}{2}}-h_2^{\frac{3}{2}}) - \frac{1}{5}(h_1^{\frac{5}{2}} - h_2^{\frac{5}{2}}))

Leave a comment

Category: Answers, Fluid Dynamics

Answer: A bead sliding on a rotating parabola

Thursday, 13 of December , 2007 at 9:33 pm

After looking at Rod’s Solution on Reasonable Deviations, I have come to the conclusion that my solution was way to complicated. Instead of using high school physics, I decided to solve the problem using Hamiltonian Mechanics.

Question: A bead slides along a smooth wire bent in the shape of a parabola, z = cr^2. The bead rotates in a circle, of radius R, when the wire is rotating about its vertical symmetry axis with angular velocity \omega. Find the constant c.

Answer: To solve this problem using Hamiltonian Mechanics, we first need to find the Hamiltonian (which is the Kinetic Energy + Potential) of the system.

The system can easily be shown to have the following form:

L = K + P = \frac{1}{2} m \arrowvert \vec{v} \arrowvert ^{2} - mgz

If we use cylindrical coordinates and constrain the path of the bead to the parabola, we can simplify the Hamiltonian to a single degree of freedom. Since the velocity \vec{v} in cylindrical coordinates is \dot{r}\hat{r} + r \dot{\theta}\hat{\theta} + \dot{z}\hat{k} and z = cr^2, the Hamiltonian reduces to:

L = \frac{1}{2} m (\dot{r}\hat{r} + r \dot{\theta}\hat{\theta} + \dot{z}\hat{k})\cdot(\dot{r}\hat{r} + r \dot{\theta}\hat{\theta} + \dot{z}\hat{k}) - mgcr^2

and since \dot{\theta}=\omega and \dot{z}=\frac{d}{dt}(cr^2) = 2 c r \dot{r}, the equation becomes:

L = \frac{1}{2} m (\dot{r}^2 + r^2\omega^2 + 4c^2r^2\dot{r}^2) - mgcr^2

Now that we have the Hamiltonian reduced to its generalized coordinates, we can apply it to the Euler-Lagrange equation. Since our Hamiltonian has only one degree of freedom, the Euler-Lagrange equation will have the following form:

\frac{\partial L}{\partial r} - \frac{\partial}{\partial t}(\frac{\partial L}{\partial \dot{r}}) = 0

First, lets take the derivatives needed for the differential equation. They can be shown to be:

\frac{\partial L}{\partial r} = m ( 4c^2r\dot{r}^2 + r \omega ^2) - 2mgcr
\frac{\partial L}{\partial \dot{r}} = m (\dot{r} + 4 c^2 r^2 \dot{r})
\frac{\partial}{\partial t}(\frac{\partial L}{\partial \dot{r}}) = m (\ddot{r} + 4 c^2 r^2 \ddot{r} + 8 c^2 r \dot{r}^2)

When we put these values into the differential equation, we will get:

m(4c^2r\dot{r}^2 + r \omega^2) - 2mgcr - m(\ddot{r} + 4c^2r^2\ddot{r} + 8c^2r\dot{r}^2) = 0
m(1 + 4 c^2 r^2)\ddot{r} + m(4 c^2 r)\dot{r}^2 + m(2gc - \omega ^2)r = 0

Since the position of the bead is confined to a circle of radius R, we can simplify the differential equation by using the following conditions: \ddot{r} = 0, \dot{r} = 0, and r = R. The differential equation will then reduce to:

m(2gc - \omega ^2)R = 0

Therefore, the value of c must be:

c = \frac{\omega ^2}{2g}

Comments (4)

Category: Answers, Classical Mechanics