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$.

Aliquot Divisors

When the idea came to write about this post, I had never came across the term “aliquot” to my recollection.  Let’s quickly deconstruct that sentence and assign some probabilities.

• I’ve never came across the term “aliquot”: probability = 0.01
• I don’t recall having come across the term “aliquot”: probability = 0.99

From this, I hope you’ve come to understand a few important things.

• Probabilities must sum to 1
• All probabilities must be non-negative and less than (or equal to) 1
• I most likely don’t have a great short term memory.
• I am most likely a pretty funny dude.

Sum of Divisors Function

After searching the term “Sum of Divisors function” a page with a wiki on the Online Encyclopedia of Integer Sequences came up.  On this, they define a function for the sum of the divisors for a number.

Let’s do a quick example before introducing notation and look at the number 40 (that’s how old I am for another month and a half).  What numbers divide 40 evenly?  That is, if you push 40, and then $\div$, what numbers can you push next so that the result is an integer (not a decimal).

Here are the divisors of 40: 1, 2, 4, 5, 8, 10, 20, 40.  A function that computes the sum of the divisors of a number should give an output of $1+2+4+5+8+10+20+40 = 90$ whenever you input the value 40.

Now for the notation.  The sum of the divisors function is given as $\sigma(n)$.  To apply the above example, this means that $\sigma(40)=90$. In other words, you input the value 40 into the sum of divisors function $\sigma(\cdot)$, and the output is 90.

Let’s try a few others. What if we input 10?  That is, what is the value of $\sigma(10)$?

First, let’s find the divisors of 10: 1, 2, 5, 10. Next (and finally), sum them together: $1+2+5+10 = 18$.  Thus, $\sigma(10) = 18$.

How about $\sigma(11)$?  The only divisors of 11 are 1 and 11 (which, as a side note, means that 11 is a prime number).  This means $\sigma(11)=12$.  If you inspect this example thoroughly, you should be able to deduce that the sum of the divisors of any prime number will be one more than the number.

Since 5 is a prime number, $\sigma(5)= 6$ (the sum of 1 and 5).  Likewise, since 7 is a prime number, $\sigma(7)=8$.

Now, try a few on your own.  Find $\sigma(15)$ and $\sigma(24)$.  The answers are below, but you can also check them by typing “sigma(15)” or “sigma(24)” into WolframAlpha. Technically, the correct code is DivisorSigma[1,15] and DivisorSigma[1,24], but you need not concern yourself with that.

So What are Aliquot Divisors?

The aliquot divisors of a number are what I have always known to be proper divisors of a number, which are all the divisors except the number itself.

So, the aliquot divisors of 40 are 1, 2, 4, 5, 8, 10, and 20 (we leave off 40).  And the sum of the aliquot divisors function is denoted by $s(\cdot)$.  For our example, then, $s(40)=1+2+4+5+8+10+20 =50$.

With this sum of aliquot divisor function, $s(n)$, we can now explore some fascinating things about different numbers.

Prime Numbers

For every prime number (a number only divisible by 1 and itself), the only aliquot divisor is 1.  So, by plugging any prime number into the function $s(\cdot)$, the result will be 1.

Deficient Numbers

The numbers 4 and 10 are deficient numbers. Why? When you plug them into the sum of aliquot divisors function, $s(\cdot)$, you will get a value smaller than the number.

The aliquot divisors of 4 are 1 and 2.  So, $s(4)=3$.  The aliquot divisors of 10 are 1, 2, and 5. So, $s(10) = 8$. Notice that each of the output values are smaller than the input values.  That means the numbers are deficient.

Let’s recall what you learned about prime numbers in the previous section.  If p is a prime number, than $s(p)=1$.  From this we can deduce that all prime numbers are deficient.

Furthermore, since we have the above stated examples of 4 and 10 as deficient numbers, and we know they are not prime since they are divisible by something other than themselves and 1, then we can also deduce that not all deficient numbers are prime.

Abundant Numbers

The numbers 12 and 40 are abundant numbers? Why? When you plug them into the sum of aliquot divisors function, $s(\cdot)$, you will get a value larger than the number.

We have already seen that $s(40)=50$. The aliquot divisors of 12 are 1, 2, 3, 4, and 6.  Thus, $s(12) = 1+2+3+4+6=16$.  Each output value is larger than the input value. That means the numbers are abundant.

Perfect Numbers

The numbers 6 and 28 are perfect numbers? Why? When you plug them into the sum of aliquot divisors function $s(\cdot)$, you will get the same value!

The aliquot divisors of 6 are 1, 2 and 3.  Thus $s(6)=1+2+3=6$.  The aliquot divisors of 28 are 1, 2, 4, 7, and 14.  Thus, $s(28) = 1+2+4+7+14 = 28$.  Each output value is the same as the input value!  That means the number is perfect.

Amicable Chains

Recently, I was introduced to the concept of amicable chains.  What if we continue to apply the sum of aliquot divisor function $s(\cdot)$ over and over again?  For example, let’s try it with 12.  As we saw in the Abundant Numbers section, $s(12)=16$.

Now, what if we plug in 16?  Aliquot divisors of 16: 1, 2, 4, and 8.  Thus, $s(16)=15$.

Again? What if we plug in 15? Aliquot divisors of 15?  1, 3, and 5.  Thus, $s(15)=9$.

Again? Aliquot divisors of 9? 1 and 3.  Thus $s(9)=4$. The aliquot divisors of 4 are 1 and 2, so $s(4)=3$.  Since 3 is prime $s(3)=1$ and now we’re trapped at 1 forever.

This created the sequence

$\displaystyle 12\rightarrow 16\rightarrow 15\rightarrow 9\rightarrow 4\rightarrow 3\rightarrow 1$

If you do a lot of exploration, a lot of numbers will produce a sequence that ends at 1 and becomes trapped. Some don’t. Take the perfect numbers 6 and 28 for example.

Since $s(6)=6$, then 6 has a chain of length 1 since it goes directly back to itself.  So does 28.

There are other numbers that do weirder things.  Take 220 and 284 for example (you will definitely need to use WolframAlpha on these if you want to check. However, you’ll need to type in “sigma(220)-220” and “sigma(284)-284”.)  The sum of the aliquot divisors of 220 is 284, and the sum of the aliquot divisors of 284 is 220.  This produces a chain of length 2. There are several chains like this one.

With the aid of a computer program, I’ve found one of length 5 and another of length 28.  Using a similar program, I also stumbled upon interesting numbers like 1230 and 1248.  Although they do not produce chains, they take a while to get back to 1.  Using a very cool trick of emailing a former colleague with a higher level of number theory understanding, he was able to find out that it takes 185 terms to get back to 1 starting at 1230 and 1076 terms to get back to 1 if you start at 1248.

The interesting thing about these sequences are how really, really, big they get.

$\sigma(15) = 24$, and $\sigma(24) = 60$.

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).

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.

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.

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.

${}_{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$.