Dried Apricots

The Fall 2018 semester is less than 2 weeks away, and so what better time to talk to you about drying some Apricots. This is a very basic problem that I hope many of you can solve on your own. For those of you that cannot, I believe you will be able to understand the solution without too much difficulty.

The 133rd Riddle put out by The Riddler included the following Eternal question about percentages:

You loaded a drying shed containing 1,000 kilograms of apricots. They were 99 percent water. After a day in the shed, they are now 98 percent water. How much do the apricots weigh now?

First of all, you should try this problem on your own.  I think you can get it.  Before you do, however, at least get a guess.  That is the point of the problem, since even I was a little surprised by the answer.

The Solution

I’ll talk you through it first, so that you can perhaps follow how a mathematician would do it afterwards.

If 99% of 1000 kilograms is water, than 990 kilograms of the apricots is water, leaving 10 kilograms (1%) of what will eventually be the purely dried-out apricots. These are all the initial values prior to the apricots going in the shed.

Now, they are left in the shed for a day, and some of the water has evaporated out of the apricots. We need to understand that the total weight of the apricots and the weight of the water has both decreased by some amount (the water that evaporated).  We also need to understand that the 10 kilograms of dried apricots to-be has not changed.

If we are given that the apricots are now 98% water we want to deduce that the 10 kilograms of dried apricots to-be now represents 2% of the entire weight, rather than the original 1%.

So, 2% of what is equal to 10?  That can be quickly found by dividing 10 by .02, which gives you 500. The answer is 500 kg.

Wait, what? The weight decreased by half?  Did I do this right?

Indeed, we have, as you can check the answer seeing that both 500-10=490 and 0.98*500 = 490.

A mathematician would have given the unknown and desired quantity of the weight of apricots after a day some variable name, like w. Then, she would have set up the equation .02w=10, and solved for w by dividing both sides by .02.

Gambler’s Ruin: A Lesson in Probability

The Riddler Express for Friday, February 23 was a gambler’s ruin problem, so I thought I would walk you through the solution and show you how the following problem can be solved.

Suppose you have one quarter, and I have two quarters.  Each round, a die is rolled. If a 1, 2, 3, or 4 is rolled, you will win a quarter from me.  If a 5 or 6 is rolled, I will win a quarter from you.  The game is won when someone retrieves all 3 quarters.

What is the probability that you will win the game?

Breaking it down into cases

Let’s use W to represent you winning a round, and L can represent you losing a round.  We can see that you will win this game if you win the next two rounds and capture both my quarters: WW.

You could also win by first winning, then losing, and then winning twice in a row: WLWW.

You could also win along the path WLWLWW.  And WLWLWLWW.  And so on.

The probability of any given W is 2/3.  The probability of any given L is 1/3.  To find the probability of two wins in a row, we would need to multiply and get (2/3)(2/3)=(2/3)^2.

The probability of WLWW occurring is (2/3)(1/3)(2/3)(2/3)=(1/3)(2/3)^3.  Similarly, the probability of WLWLWW occurring is (1/3)^2(2/3)^4.  And so on.

So, we would need to calculate the difficult infinite sum

\displaystyle (2/3)^2+(1/3)(2/3)^3+(1/3)^2(2/3)^4+\ldots .

This is not too difficult for the savvy statistician/mathematician, but it seems like a headache for the rest.  There is an easier approach.

A Recursive Relationship

Let P_i represent the probability that you will eventually win this game if you are holding i quarters.

If you are not holding any quarters, then i=0 and P_0 =0 since you have a zero probability of winning (indeed, you have lost).

If you are holding all three quarters, then i=3 and P_3=1 since you have won the game (and therefore have a probability 1 of winning).

Since we are holding one quarter in this problem, i=1, and we want to find P_1.  Here is the weird trick.  We will solve for this by also solving for P_2, the probability that you will eventually win when holding 2 quarters.

We need to recognize the following two relationships:

  1. The probability that we will eventually win the game when we hold 1 quarter is the probability that we win the next round AND eventually win the game from holding 2 quarters. The equation that results from this logic is P_1 = (2/3)P_2.
  2. The probability that we will eventually win the game when we hold 2 quarters is the probability that we lose the next round AND eventually win the game from holding 1 quarter OR we simply win the next round.  The equation that results in this logic is P_2 = (1/3)P_1+2/3.

Now, we use some substitution. Using the equation from 1 inside the equation from 2, we get

\displaystyle P_2 = (1/3)(2/3)P_2+2/3.

Multiplying the constants together gives you P_2=2/9P_2+2/3. Subtracting 2/9P_2 from both sides gives you 7/9 P_2 = 2/3.  Finally, multiplying both sides by the 9/7 will give P_2 = (9/7)(2/3) = 6/7.

Now, using the original equation from 1 we get P_1 = (2/3)(6/7) = 4/7.

Gambler’s Ruin Equation: The General Result

To explain how to obtain the general result would be over most people’s heads, so I’ll simply give it to you.

Suppose on each individual round you have a probability p of winning and a probability q = 1-p of losing.

When you begin with a bank of i, and you are interested in reaching a fortune of N, then the probability that you will reach that fortune is given as

\displaystyle \frac{1-(q/p)^i}{1-(q/p)^N}.

To see how this applies to our problem, you will need to recognize that p=2/3, q=1/3, i=1, and N=3.

Notice that q/p = (1/3)/(2/3) = 1/2, so when we plug everything into that equation, we get

\displaystyle \frac{1-(1/2)^1}{1-(1/2)^3} = \frac{(1/2)}{1-(1/8)} = \frac{(1/2)}{(7/8)} = \frac12\cdot\frac87 = \frac47.

 

The Yanghui Triangle, Part II

Welcome back for round two!  If you missed Part I, you can catch up here.

An Alternative Explanation

In the first part of this post, we explored the following specific consequence of the triangle that we generalized:

\displaystyle \binom{6}{2} = \binom{5}{1}+\binom{5}{2}.

I recognized that I lacked an example of why this might be true from a counting perspective.  Using the triangle below, we see that the equation above is saying that 15=5+10.

YanghuiTriangle
Here is Yanghui’s Triangle for convenience.

So, why is this true from a counting perspective?

Let’s say we want to select 2 of these 6 letters: ABCDEF.  There should be 15 ways of doing this according to the triangle.  Let’s list them below.

AB, AC, AD, AE, AF, BC, BD, BE, BF, CD, CE, CF, DE, DF, ED

Now, let’s try it another way.  Let’s first make a decision on the F.  We can either select it, or not select it.  Let’s explore both cases.

We Select The F. Now, our task is to select 1 more of the 5 letters ABCDE.  We can do this in \binom{5}{1}=5 different ways.  We are left with AF, BF, CF, DF, and EF.

We Do Not Select F. Now, our task is to select 2 of the 5 letters ABCDE.  We can do this in \binom{5}{2} = 10 ways. Here they are: AB, AC, AD, AE, BC, BD, BE, CD, CE, DE.

Now, combine these two together for the total number of ways to select 2 of 6 letters.

OK, now onto some more fun properties.

Powers of 2

If we sum each row of Yanghui’s Triangle, you will notice a pattern.

  1. Sum of 0th row: 1
  2. Sum of 1st row: 2
  3. Sum of 2nd row: 4
  4. Sum of 3rd row: 8
  5. Sum of 4th row: 16

And so on.  From the title of this section, you probably have already guessed the pattern.  If we think of the first row as the zeroth row instead, then we simply take 2 to the power of the row to get the sum.

Why does this work? You may have to review the first post to recall that the numbers in each row can be used as the coefficients when expanding expressions such as (x+y)^6.  From the previous post,

\displaystyle (x+y)^6 = x^6+6x^5y+15x^4y^2+20x^3y^3+15x^2y^4+6xy^5+y^6.

Let’s use this result, and plug in 1 for both x and y. The left part of the equation says that this is just 2^6.  The right part of the equation says that this is the sum of the numbers in the 6th row of Yanghui’s Triangle.

Fibonacci Sequence

PascalsTriangleFibonacci
By using hexagons to construct the triangle, the lines that create Fibonacci are easy to construct

The picture above says it all.  By creating lines that run parallel to the top left side of the hexagons and summing up the numbers that it passes through, we get Fibonacci’s Sequence.

Why is this?

Let’s explore the line that goes through 1, 4, and 3, which sums to 8.  The 1, 4, and 3 correspond with the following counting principles: choosing 0 of 5 things, 1 of 4 things, and 2 of 3 things.  To see why this must sum up to the 5th Fibonacci number (again, thinking that the first 1 in Fibonacci’s sequence is the null, or zeroth number), review my explanations in Approach 1 and Approach 2 in Jumping Lily Pads. You can also watch the quick video there.

For a brief explanation of why \binom{5}{0}+\binom{4}{1}+\binom{3}{2} sums up to the fifth Fibonacci number, it is like counting the number of ways that a frog can jump from shore to the fifth lily pad if the frog can jump one or two lily pads at a time.

He can make 5 total jumps, 0 of which are skipping any lily pads: \binom{5}{0}=1.

He can make 4 total jumps, 1 of which must be a double: \binom{4}{1} = 4.

He can make 3 total jumps, 2 of which must be doubles: \binom{3}{2} = 3.

As was described in that post, this is equivalent to summing up the number of ways you can jump to lily pad 3 (3) and the number of ways you can jump to lily pad 4 (5).

Shortest Line Segment

This week’s Riddler Express has interested readers solving for the shortest possible distance between two diagonals in a cube.  The solution in this post will involve some higher level mathematics toward the end. You’ve been warned.

I’ve changed the coordinates from the original posed problem with the one below.  On this cube, there is a diagonal on one face of the cube connecting the points (1,0,0) and (0,0,1).  There is also a diagonal of the cube itself connecting the points (0,0,0) with (1,1,1).

Riddle101Box
Inspired by Riddle 101 on FiveThirtyEight

Our goal is to find the points p1 on the first diagonal and p2 on the second diagonal for which the distance between p1 and p2 is at a minimum.

Distance Between Two Points

A general point in three dimensional space is given as (x,y,z). The first two coordinates (x,y) tell you where along the plane the point is, while the third coordinate z tells you your height (positive values) or depth (negative values).

The distance between two points on a plane can be solved using Pythagorean’s Theorem.  Let’s begin with the two points (x1, y1) and (x2, y2) in two-dimensions.

DistanceBetweenTwoPoints

Two find the distance between the two points, we construct a right triangle with the segment connecting the two points behaving as the hypotenuse of a right triangle. If you are familiar with Pythagorean’s Theorem, you know that a right triangle with side lengths a and b and hypotenuse c will satisfy the equation a^2+b^2=c^2.

Using the figure above, if we label the hypotenuse c and use a=|x2-x1| and b = |y2-y1|, then we know that

\displaystyle c^2 = (x2-x1)^2+(y2-y1)^2,

or better yet, we know the distance between the two points is the length

\displaystyle c = \sqrt{(x2-x1)^2+(y2-y1)^2}.

For three dimensions, it is very similar.  The distance between two points (x_1,y_1,z_1) and (x_2, y_2, z_2) is given as

\displaystyle d = \sqrt{(x_2-x_1)^2+(y_2-y_1)^2+(z_2-z_1)^2}.

We will use this in solving the problem.

The Form of p1 and p2

Looking at our original cube, we notice that p1 is a point on the line connecting points (1,0,0) with (0,0,1).  Let’s parametrize this point.  We do this by letting a variable t (think of it as time) go from 0 to 1, and as it does so, the point p1 will move from (1,0,0) to (0,0,1).

This point can be represented by (1-t, 0, t).  When t=0, we are at (1,0,0), and when t=1, we are at (0,0,1).

Doing the same for p2, but using a variable s instead (you can still think of it as time), a point p2 can be represented as (s,s,s) as s ranges from 0 to 1.

So, we have the general form of two points p1 and p2 on the two lines.  That is,

p1 = (1-t,0,t) and p2=(s,s,s) for some t,s \in [0,1].

The distance between these two points, using the equation derived previously is

\displaystyle \sqrt{(1-t-s)^2+(0-s)^2+(t-s)^2}.

Our goal is to minimize this distance.  It turns out that it is much easier to minimize the square of the distance instead (the value underneath the square root).

WARNING! Calculus is about to occur.

Finding the Minimum Distance

As was stated, we will minimize the square of the distance. Notice that this is a function of two variables t and s, and can be written

\displaystyle d(s,t) = (1-t-s)^2+s^2+(t-s)^2.

To minimize this function, we will need to set both partial derivatives equal to zero and solve the resulting equations. These equations are

\displaystyle \frac{\partial d}{\partial s} = -2(1-t-s)+2s-2(t-s) = 0, and

\displaystyle \frac{\partial d}{\partial t} = -2(1-t-s)+2(t-s) = 0.

Solving the first equation will reveal that s=\frac13. Solving the second provides us with t=\frac12.

So, it is when p1 = (1/2, 0, 1/2) and p2=(1/3, 1/3, 1/3) where the minimum distance occurs.  Noticing that \frac12 - \frac13 = \frac16, we can compute the minimum distance as

\displaystyle d = \sqrt{(1/6)^2+(1/3)^2+(1/6)^2} = \sqrt{1/6} \approx 0.408.

 

The Yanghui Triangle, Part I

Many of you know Yanghui’s Triangle as Pascal’s triangle.  However, about 500 years earlier (according to Wolfram Mathworld), a Chinese mathematician Yanghui studied this triangle. In China, it is referred to as the Yanghui Triangle.

YanghuiTriangle

How is it produced? In my previous blog post, Counting Can Be Really Tough, I introduced you to combinations.  As a quick review, we use combinations when we want to count the number of ways you want to select things from a total of n different things.  The notation and formula for it are given as

{}_nC_r = \frac{n!}{r!(n-r)!}

Examples: Say you want 5 cards from 52 randomly.  You can plug this into your calculator using the {}_nC_r button by first putting in 52 and then pressing that key, plugging in 5, and then pressing Enter.

If you don’t have a calculator handy, open up another window for WolframAlpha, and plug any of the following in: “nCr(52,5)”, “52 nCr 5”, or “Binomial[52,5]”.  Confirm you answer at the bottom of this post.

In the mathematics world, the notation \binom{n}{r} is used instead of {}_nC_r, as you’ll find it on your calculator.

Construction of the Triangle

WE begin with n=0. The only value that r can be is 0 in the combination formula.  The very top value of the triangle is {}_0C_0 = \binom{0}{0} = 1.

Now, we will derive the second row (or the first row if you want to think of the top row as the zeroth row). For this row, n increases to 1.  We can either choose nothing from 1 thing, or we can choose the 1 thing, so r can either be 0 or 1.  You can confirm with a calculator or WolframAlpha that

\displaystyle \binom{1}{0}=\binom{1}{1}=1.

We’ll analyze one more row and let the reader generalize to further rows.

With n=2 now, we can either select nothing, 1 thing, or both things.  There is 1 way, 2 ways, and 1 way of doing this, respectively.  Again, you can confirm that

\displaystyle \binom{2}{0}=1, \,\,\, \binom{2}{1}=2, \,\,\, \binom{2}{2}=1.

At each new level n, there are n+1 values along the row as r ranges from 0 to n. 

A Few Properties

Upon construction of the triangle, we notice that it could have been constructed by

  1. Putting 1’s down the diagonals, and then
  2. Add the two numbers above to get the number below.

Let’s think about what these mean mathematically.  We’ll begin with number 1. If we think in terms of selecting r things from a total of things, number 1 above means that there is only 1 way of selecting 0 things from n things (vacuous), and there is only 1 way of selecting n things from n things (you must select them all).  This works for any number n.

What can we deduce from number 2?  Let’s choose a specific example to start.  Using the value 15 in the row that begins 1, 6, 15, 20, etc., we see that this is the sum of 5 and the 10 in the previous row.  The 5 and the 10 in that row were results from choosing 1 thing from 5 things, that is \binom{5}{1}=5, and choosing 2 things from 5 things, that is \binom{5}{2}=10.

The 15 in the row below it is a result of choosing 2 things from 6 things, that is \binom{6}{2}=15.  Putting these together, we have

\displaystyle \binom{6}{2}=\binom{5}{1}+\binom{5}{2}.

For the more general result, lets pretend the 6 above is n and that the 2 we select from the 6 is r. Then the general result can be written as

\displaystyle \binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r},

which can also be shown algebraically with formulas. But who wants to do that?

This is what mathematicians do. We generalize and look for patterns.  Using this relationship instead of a calculator, try and find \binom{9}{3}.  Answer is below.

An Alternative to the “FOIL” Method

Remember FOIL?  These letters stand for “First, Outer, Inner, Last,” and the mnemonic is used when wanting to multiply expressions such as (x+2y)(3x-y).

First, you multiply the first terms in each expression to get 3x^2.

Next, you multiply the outer terms of the expression to get -xy.

Third, you multiply the inner terms of the expression to get 6xy.

Finally, you multiply the last terms of the expression to get -2y^2.

When you add these together and combine the like terms you get

\displaystyle 3x^2-xy+6xy-2y^2 = 3x^2+5xy-2y^2.

Let’s try another that will lead to the usefulness of Yanghui’s Triangle. That is, expanding expressions like (x+y)^2.  Writing it as (x+y)(x+y) and following the same procedure above produces x^2+2xy+y^2.

If you’ll allow me to write that 1x^2+2xy+1y^2, it is easier to see that the coefficients of each of the terms matches the specific row when n=2. It is no coincidence that the n=2 matches the power to which (x+y) is raised.

Indeed, Yanghui’s Triangle can be used to quickly expand expressions in the form (x+y)^n.  See if you can recognize the pattern in the expansion of (x+y)^6:

\displaystyle x^6+6x^5y+15x^4y^2+20x^3y^3+15x^2y^4+6xy^5+y^6.

Try to expand the much easier (x+y)^4. Answer is below.

Why do these combination values match up with the coefficients in this expansion?  Suppose we were to attempt to expand (x+y)^6 manually:

\displaystyle (x+y)^6 = (x+y)(x+y)(x+y)(x+y)(x+y)(x+y).

From a counting perspective, you can get a x^2y^4 term by multiplying the x from the 1st and the 4th expressions with the y’s in the 2nd, 3rd, 5th, and 6th expressions.  Since there are 6 expressions you are multiplying together, 2 of which need to be x’s, then there are \binom{6}{2} = 15 ways of getting the x^2y^4 term.

Pretty cool, huh?  Again, this is what mathematicians love.  Seeking and understanding patterns.  For Part II of this post, we will explore some other properties and how the Fibonacci sequence emerges from Yanghui’s Triangle.

Answers to above posed questions

{}_{52}C_{5} = 2598960

\binom{9}{3} = \binom{8}{2}+\binom{8}{3} = 28+56 = 84 directly from triangle.

(x+y)^4 = x^4+4x^3y+6x^2y^2+4xy^3+y^4.