Archive for Math

Building a Picnic Table

June 7, 2009 at 3:17 am · Filed under Math ·Tagged ,

Someone writes

Jonathan and/or [redacted],

I’ve got a basic geometry question for either of you, that I need a little help with…

I am working on making a picnic table with [redacted] and we wanted to design our own legs for the table which are angled and cross. I have been able to work out all relationships between heights, lengths, widths, angles. etc. and now have two equations with two unknowns that will allow me to solve for the correct angle at which to cut the wood for the legs. Unfortunately I have forgotten how to solve basic cos, sin, and tan when variables are involved. The two equations are (all units are in inches, not that it matters):


$\displaystyle \textrm{sin} (\alpha)$ $\textstyle =$ $\displaystyle \frac{5.5}{x}$ (1)
$\displaystyle \textrm{tan} (\alpha)$ $\textstyle =$ $\displaystyle \frac{29}{35.5-x}$ (2)

How do I solve for $x$ and $\alpha$? Also, what is the answer :-)

Thanks,
[redacted]

Because

\begin{eqnarray*}\textrm{tan} (\alpha) & = & \frac{\textrm{sin} (\alpha)}{\text......rac{\textrm{sin} (\alpha)}{\sqrt{1 - \textrm{sin}^{2} (\alpha)}}\end{eqnarray*}

we have

$\displaystyle \frac{29}{35.5-x}$ $\textstyle =$ $\displaystyle \frac{\frac{5.5}{x}}{\sqrt{1 - \left(\frac{5.5}{x}\right)^{2}}}$ (3)

Simplifying and solving by computer algebra, we get

\begin{eqnarray*}\frac{3243}{841} x^2 + \frac{8591}{841} x - \frac{1017005}{3364} & = & 0\end{eqnarray*}

and

\begin{eqnarray*}x & = & \frac{ \pm 1276\sqrt{2071} - 8591}{6486}\end{eqnarray*}

Only the positive choice is a root of Eqns. (1) and (2), giving

\begin{eqnarray*}x & = &7.62835577107986... \\\alpha & = & 0.805235953662952... \\& = & 46.1366216570791... \textrm{(degrees)}\end{eqnarray*}

Comments (2)

The Biggest Box Fedex Will Take

March 10, 2009 at 5:12 pm · Filed under Math, Uncategorized

My friend Megan Goering asks what is the largest volume box you can send through Fedex given that length + twice the width + twice the height must be less than 165 inches. It might seem odd to care about only the volume instead of the dimensions, but it makes sense if you’re shipping walnuts, balloons or bows for Christmas presents. Anything pourable, that is.

Here’s my solution. Say that the dimensions are $x$, $y$ and $z$. Then we can write the problem as

\begin{eqnarray*}\textrm{max } & & xyz \\\textrm{subject to} & &x + 2y + 2z \le 165 \\& & x,y,z \ge 0 \\\end{eqnarray*}

First, observe that if $x + 2y + 2z < 165$, then the product $xyz$ can be increased by increasing any one of the dimensions. Therefore, the maximum will occur when $x + 2y + 2z = 165$. Thus, we can eliminate $z$ because


$\displaystyle z$ $\textstyle =$ $\displaystyle \frac{165 - 2y -x}{2}$ (1)

Here is the problem

\begin{eqnarray*}\textrm{max } & & xy\left(\frac{165 - 2y -x}{2} \right)\\\textrm{subject to} & &x + 2y \le 165 \\& & x,y \ge 0 \\\end{eqnarray*}

The constraints impose that the maximum be achieved in a triangular area with one vertex at the origin and the other two each on one of the $x$ and $y$ axes. Notice that if we use a point $(x,y)$ on the border of this triangular region, the product $xyz$ will be equal to 0, so this is clearly not the maximum. Therefore, the maximum occurs on the inside of the triangle. This is important, because it means that the maximum is some sort of “bump” which means the problem can be solved directly with calculus.

We want to maximize $xy\left(\frac{165 - 2y -x}{2} \right)$. The choice of $x$ and $y$ that achieves the maximum is unaffected by multiplying that product by a positive constant, so use this opportunity to get rid of the $\frac{1}{2}$. Let $f = xy(165 - 2y -x)$. Then

\begin{eqnarray*}f & = & 165xy - 2xy^{2} -x^{2}y \\\frac{\partial f}{\partial...... -2xy \\\frac{\partial f}{\partial y} & = & 165x - 4xy -x^{2}\end{eqnarray*}

Thus, in order for the maximum to be achieved, we need both derivatives to be equal to 0. Thus, we need

\begin{eqnarray*}165y - 2y^{2} -2xy & = & 0 \\165x - 4xy -x^{2} & = & 0\end{eqnarray*}

Which is, conveniently enough, two equations in two variables, so we can probably solve this. First simplify as

\begin{eqnarray*}165 - 2y -2x & = & 0 \\165 - 4y -x & = & 0\end{eqnarray*}

Then as

\begin{eqnarray*}2y + 2x & = & 165 \\4y + x & = & 165\end{eqnarray*}

And finally

\begin{eqnarray*}x & = & 55 \\y & = & \frac{55}{2}\end{eqnarray*}

and we get

\begin{eqnarray*}z & = & \frac{55}{2}\end{eqnarray*}

from Equation (1).

Thus the maximum volume you can send using this Fedex rule is $55 \times \frac{55}{2} \times \frac{55}{2} = \frac{166375}{4}$ cubic inches, or about 24 cubic feet. This many walnuts weighs over 300 kg, so presumably the problem was motivated by something lighter.

Comments (1)

Final Olympic Medal Race Results

August 24, 2008 at 10:46 am · Filed under Math ·Tagged , , , , , , , ,

A few days ago, when I wrote a post proposing a metric to rank countries in the 2008 Olympics, it wasn’t yet over. Now that we have final results, let’s see how we rank:

China   100%
United States   94%
Russia  60%
Britain 43%
Australia       38%
Germany 36%
South Korea     29%
France  29%
Italy   23%
Japan   21%

Leave a Comment

Who is Winning the Olympic Medal Race?

August 21, 2008 at 10:36 pm · Filed under Math ·Tagged , , , ,

Several rankings have been proposed as to how to determine which country is winning the Olympic medal race.  Here I’m only going to look at the medals in isolation.  Folks have suggested dividing the medals by the countries’ populations, by the GDP or by the number of athletes.  You could factor in the sport popularity, fourth place rankings or time zone differences.  You could even rank the countries by how well they exceeded expectations on online betting sites.  I would like to see that.  But it’s too complicated to do here.

Back to the medals alone.  That means three numbers per country.

Clearly,
1) Using the total number of medals leaves out some important information.  3 golds is obviously better than 3 bronzes.
2) Using the number of golds leaves out some important information.  3 golds and 3 bronzes is obviously better than 3 golds.

I’m not the first one to suggest weighting the numbers.  It’s progress, but it punts on how to do it.  I’ve seen 4, 2 and 1. I’ve also seen 5, 3 and 1.  It’s pretty easy to make up numbers, but it’s more satisfying to have a rationale.  Here I propose the <i>distinguishing power</i> rationale.  There’s only one gold medal.  There’s also only one silver medal, but somebody else did better, so silver has half the distinguishing power of gold.  Similiarly, bronze has 1/3 of gold.  The actual weights don’t matter as long as the ratio is right.  6, 3 and 2 are the smallest integers that express the distinguishing power ratios.

And finally the rankings (today), as a percentage of the leader:

China   100%
United States   93%
Russia  49%
Britain 43%
Australia       36%
Germany 31%
South Korea     27%
Japan   24%
France  24%
Italy   20%

Comments (1)

Permutable Dates

August 11, 2008 at 11:03 pm · Filed under Math, Puzzles ·Tagged , , , ,

Gregorus seems to have already posted about this, but I can post my solution. We came up with the puzzle of finding the 8-digit number (with zeros allowed at the beginning) which has the largest possible number of permutations that are possible dates. Some numbers like 99,999,999 don’t have any. Others like 01,234,567 have a lot (starting with 01/23/4567, and most of those digits can be swapped around).

I wrote my program in the Bash shell language and it has two lines.

Line One:

perl -e 'use  Date::Manip; my $d = ParseDate("01/01/0001");while(UnixDate("%Y") < 10000) {print UnixDate($d,"%m%d%Y\n"); $d = DateCalc($d, "+ 1 day");}' >> all-dates.txt


This just makes all the possible dates, one day at a time. Perl’s Date::Manip module is notoriously slow, and it took almost two hours to make all 3,652,059 dates in this millenium (not quite actually: the last year of the millenium has a five digit year). As for the delay, I rationalized that I had optimized my code for “programmer time”.

Line Two:

perl -ne 'print join("", sort (split("", $_)))' all-dates.txt | sort | uniq -c | sort -n


This sorts the digits in each date to make ordered digit clusters, then orders the clusters of digits by how many times they appear.

The results? 00,123,578 will make 2,472 dates! Of course, it is a 20,160-way tie, because any permutation of 00,123,578, such as 57,800,123 will make the same 2,472 dates.

Unfortunately, I can’t make any dates near to us from 00,123,578. The closest I can get on both sides is 07/08/2135 and 03/20/1875. Can anyone do better?

Comments (2)

Clockwork Powers

August 4, 2008 at 6:49 am · Filed under Math, Puzzles ·Tagged , , , ,

Here’s another problem I’ve been looking at lately:

Find a number $x$, such that if $j$ is any digit from 0 to 9, $x^{j}$ has $j$ as its first digit past the decimal point. For instance, 63.18 works for the first power $(63.18^{\b{1}} = 63.\b{1}8)$ and the third power $(63.18^{\b{3}} = 252196.\b{3}89432)$, but it doesn’t work for the second $(63.18^{\b{2}} = 3991.\b{7}124)$ where the first digit is 7 instead of 2.

Hint: The smallest such number is less than 10.

To prove that the problem is possible to solve quickly, I’ll provide the solution to a more complicated version. Suppose that the first two digits of $x^{j}$ must match $j$ instead of just the first one. This means that $x^{3}$ has “03” just to the right of the decimal point all way to up to $x^{99}$ having “99” just after the decimal point. Then the smallest solution is the following number:

95.01063709417263364386569653065071891390859441647675346849
01552762611728856071543459219055118914594166160224386992990
49592128996983422861693601042135900702684741868297684742429
253949832737577847233354…

The smallest solution’s digits actually never end so I had to cut it off somewhere. I choose the cut off point to be the first place where the remaining digits still worked. In other words, if you truncated the 4 off of the end, the number would be changed too much and would fail to meet all the conditions. Furthermore, I was forced to round up (because anything smaller doesn’t work).

Leave a Comment

The Monkey Problem

July 25, 2008 at 10:59 am · Filed under Math, Puzzles ·Tagged , , , ,

I’ve been forwarded a classic problem, in bold below.

The Monkey Problem

A rope over the top of a fence has the same length on each side, and weighs one-third of a pound per foot. On one end hangs a monkey holding a banana, and on the other end a dead-weight equal to the weight of the monkey. The banana weighs 2 ounces per inch. The length of the rope in feet is the same as the age of the monkey, and the weight of the monkey in ounces is as much as the age of the monkey’s mother. The combined ages of the monkey and its mother are 30 years. One-half the weight of the monkey, plus the weight of the banana is one-fourth the sum of the weights of the rope and the dead-weight.

The monkey’s mother is one-half as old as the monkey will be in when it is three times as old as its mother was when she was one-half as old as the monkey will be when it is as old as its mother will be when she is four times as old as the monkey was when it was twice as old as its mother was when she was one-third as old as the monkey was when it was as old as its mother was when she was three times as old as the monkey was when it was one-fourth as old as it is now.

How long is the banana in inches?

In fact, I’ve seen this problem back when I was kid, though I’ve never tried to solve it, mostly because that last paragraph looked tedious and as though it would require a deeply nested set of multiplied and offset variables. It turns out however, to be simpler than I imagined. Here we go….

A rope over the top of a fence has the same length on each side, and weighs one-third of a pound per foot.

Everything else in the problem uses ounces, so let’s make it consistent. We’ll make up variables as go along. First we need rope weight and rope length.

\begin{eqnarray*}RW = RL * 1/3 * 16\end{eqnarray*}

On one end hangs a monkey holding a banana, and on the other end a dead-weight equal to the weight of the monkey.

Add in variables for Dead Weight and Monkey Weight.

\begin{eqnarray*}DW = MW\end{eqnarray*}

The banana weighs 2 ounces per inch.

Add in variables for banana weight and banana length.

\begin{eqnarray*}BW = 2 * BL\end{eqnarray*}

The length of the rope in feet is the same as the age of the monkey

Rope Length and Monkey Age.

\begin{eqnarray*}RL = MA\end{eqnarray*}

… and the weight of the monkey in ounces is as much as the age of the monkey’s mother.

Add in MMA for Monkey Mother Age.

\begin{eqnarray*}MW = MMA\end{eqnarray*}

The combined ages of the monkey and its mother are 30 years.

\begin{eqnarray*}MA + MMA = 30\end{eqnarray*}

One-half the weight of the monkey, plus the weight of the banana is one-fourth the sum of the weights of the rope and the dead-weight.

\begin{eqnarray*}1/2 * MW + BW = 1/4(RW + DW)\end{eqnarray*}

The monkey’s mother is one-half as old as the monkey will be in when it is three times as old as its mother was when she was one-half as old as the monkey will be when it is as old as its mother will be when she is four times as old as the monkey was when it was twice as old as its mother was when she was one-third as old as the monkey was when it was as old as its mother was when she was three times as old as the monkey was when it was one-fourth as old as it is now.

\begin{eqnarray*}MMA = \frac{1}{2} ( 3 ( \frac{1}{2} ( 4 ( 2 ( \frac{1}{3} ( 3 ( \frac{1}{4} MA)))))))\end{eqnarray*}

How long is the banana in inches?

\begin{eqnarray*}\textrm{Find } BL\end{eqnarray*}

No doubt these equations are easy to solve by hand, but why settle? We can write them in a form that can be solved by computer. Right now, I prefer the mathematical software Sage . Formatted for Sage, the equations look like this:

var('RW, RL, DW, MW, BW, BL, MA, MMA')
equations = [
RW == RL * 1/3 * 16,
DW == MW,
BW == 2 * BL,
RL == MA,
MW == MMA,
MA + MMA == 30,
1/2 * MW + BW == 1/4 * (RW + DW),
MMA == 1/2 * (  3 * ( 1/2 * ( 4 * ( 2 * ( 1/3 * ( 3 * ( 1/4 * MA)))))))]
s = solve(equations, RW, RL, DW, MW, BW, BL, MA, MMA, solution_dict = True) 
print s

And the output is:

18\}\end{eqnarray*}

Notice the banana weighs 11.5 ounces and the monkey only weighs 18 oz., so something is little implausible about the problem, but as mathematicians, that’s not our problem…

Comments (1)

Divisible by 7, Both Ways

July 8, 2008 at 9:16 am · Filed under Math, Puzzles ·Tagged , , , , , , ,

Author’s Update on 7/26/08: I submitted these numbers to the On-Line Encyclopedia of Integer Sequences. You can see a much longer list of the sums here.

I briefly wrote about this several years ago, but with my newfound powers of publishing LaTeX to the web, I feel that it can be made more accessible now.

Here’s the math problem, which sounds innocent enough:
Find the sum of all integers $i$ between 0 and $10^{6}$ (one million) such that both $i$ and the reverse of $i$ are divisible by 7. More generally, replace $10^{6}$ by $10^N$ and find an algorithm that works for any $N$.

Just to work up to this a bit, if those extra conditions did not exist, the problem would be easy. Ignoring 0, there are exactly $10^{6}$ integers between 1 and $10^{6}$, and they can be paired off into $\frac{10^{6}}{2}$ sets: $[1, 10^{6}], [2, 10^{6}-1],$ all the way up to the last set $[\frac{10^{6}}{2}-1,\frac{10^{6}}{2}]$. Each of these sets has the same sum: $10^{6}+1$. Therefore the sum of all the numbers is just $\frac{10^{6}}{2} \times (10^{6}+1) = 500,000,500,000$.

In addition, if the divisible-by-7 condition did exist, but not the condition on the reverse of $i$, it would also be relatively easy. The numbers to add would be the multiples of 7: $0, 7, 14, 21...$ up to $ ..., 999,999$. We can divide each of these numbers by 7, add them, then multiply the product by 7 at the end. That addition can be done the same way as in the above paragraph and we end up with $\frac{142857}{2} \times (142857 + 1) \times 7 = 71,428,928,571$.

It is the condition on $i$‘s reverse that makes this hard. Qualifying numbers start out 0, 7, 70, 77, 161, 168, 252, 259…, and end with …999838, 999922, 999929, 999992, 999999. There doesn’t seem to be anything obvious about the digits themselves, nor anything very regular about the spacing between the numbers (which was the key to the intermediate problem with only one condition).

However, we can solve this problem using Dynamic Programming with Modular Arithmetic. First, let’s look at the more general problem.

Breaking Down

Let $F(n, m, x, y)$ be the number of integers $i$ with $ n \le i < m$ and $i \equiv x$ (mod 7) and $Reverse(i) \equiv y$ (mod 7). Similarly, let $G(n, m, x, y)$ be the sum of those integers. $G(0, 10^N, 0, 0)$ is the answer to the our question, by definition, but first let’s look at $F(0, 10^N, 0, 0)$. It will turn out that we can use this to calculate $G(0, 10^N, 0, 0)$.

Observe that $F(0, 10^N, x, y)$ can be represented as the sum of 10 instances of $F$ over intervals of size $10^{N-1}$, one for each possible first digit (left padding with zeros to ensure N digits).


$\displaystyle F(0, 10^N, x, y) = \sum_{i=0}^9 F(10^{N-1}i, 10^{N-1}(i+1), x, y)$     (1)

As an example, what Equation (1) is saying is that


$\displaystyle F(0, 100, 0, 0) = F(0, 10, 0, 0) + F(10, 20, 0, 0) + ... + F(90, 100, 0, 0)$     (2)

This is because however many numbers there are between 0 and 100 with our divisibility properties, they are divided up among the ranges [0,9], [10,19], [20,29] up to [90,99]. If we count the numbers in those bins up separately and then add the totals for the bins, it will come at the same as if the numbers are counted up all at once.

We will characterize the numbers counted by each of the summands in Equation (2) in order to fold them together. The property we use to relate $F$ functions over different intervals comes from the digits of the numbers. Let $id_1d_2d_3 \dots d_N$ be an $N+1$-digit number, with first digit $i$. Then,


$\displaystyle id_1d_2d_3 \dots d_N$ $\textstyle =$ $\displaystyle i \times 10^{N} + d_1d_2d_3 \dots d_N$ (3)
$\displaystyle d_N \dots d_3d_2d_1i$ $\textstyle =$ $\displaystyle i + 10 \times d_N \dots d_3d_2d_1$ (4)

That is, every number in an interval $\left[10^{N}(i-1), 10^Ni\right]$ can be mapped to a number in $\left[0, 10^{N-1}\right]$ with quantifiable changes to its (and its reverse’s) residue modulo 7, simply by removing the first digit. In particular, by (3) and (4) this reduction is


$\displaystyle F(10^{N}(i-1), 10^Ni, x, y) = F(0, 10^N, x - 10^Ni, 10^{-1}(y - i))$     (5)

For example, each number in the interval [60, 69], can be mapped onto a one digit number by removing the tens digit, 6 (e.g, 62 becomes 2). If we were trying to calculate $F(60, 70, 6, 5)$, we could use this relation:


$\displaystyle F(60, 70, 6, 5)$ $\textstyle =$ $\displaystyle F(0, 10, 2, 2)$ (6)

Here’s why: The first 2 comes from the fact that when you subtract 60 from something with a remainder of 6 when divided by 7, the difference has a remainder of $6 - 60 \equiv 2$ (mod 7). The second 2 in Equation (6) is a little harder to see: Removing an initial 6 from a number whose reverse has a remainder of 5 has the effect of removing the last digit from its reverse. Subtracting 6 from a number that had a remainder of 5 changes the remainder to 6, then dividing by 10 changes the remainder to $6 \times 10^{-1} \equiv 6 \times 5 \equiv 2$ (mod 7).

Returning to Equation (2) and applying Equation (5), we have

\begin{eqnarray*}F(0, 100, 0, 0) & = & F(0, 10, 0, 0) + F(10, 20, 0, 0) + F(20,......) + F(0, 10, 0, 0) + F(0, 10, 4, 2) \\& & + F(0, 10, 1, 4) \\\end{eqnarray*}

Notice anything? Three of the terms, $F(0, 10, 0, 0)$, $F(0, 10, 4, 2)$ and $F(0, 10, 1, 4)$, appear twice. That means that rather than examine each number from 0 to 99 as it looked like we might need to do to find $F(0, 100, 0, 0)$, we need only examine the numbers from 0 to 9, 7 times each. We would then sum up the results of those 7 passes, taking care to count a certain three of them twice. That’s a 30% savings, but it doesn’t end there.

Suppose the original problem had been $F(0, 1000, 0, 0)$. We could divide it into 10 subproblems, each ranging from 0 to 100. Then, we could divide each of those up into 10 smaller problems from 0 to 10, then combining the ones that are copies. How many distinct problems would there be at this stage? They all have the form $F(0, 10, x, y)$ and $x$ and $y$ can only be integers in $[0,6]$. That’s only 49 subsubproblems, at the most. Now we have saved more than half the work. For any larger-sized ranges we could think of, the number of subproblems stays limited to 49.

We could find $F(0, 10^{1000}, 0, 0)$ by only looking at $F(0, 10, x, y)$ for 49 sets of $x$ and $y$, then doing a lot of adding!

There are two things left to do: Figure out how to add these subproblems back together and how to get the sum of those numbers, which was the original question.

Summing

Just to make things a little more compact, let $\alpha(N, x,i)$ be equal to $x - 10^Ni$ (mod 7) and $\beta(N, y,i)$ to $10^{-1}(y - i) \equiv 2(y - i) \equiv 2y + 5i$ (mod 7), we have

\begin{eqnarray*}F(0, 10^{N+1}, x, y) = \sum_{i=0}^9 F(0, 10^N, \alpha(N, x,i), \beta(N, y,i))\end{eqnarray*}

Remember the explanation for how we derived Equation (1)? We can carry out a similar reduction on $G$ to get


$\displaystyle G(0, 10^{N+1}, x, y)$ $\textstyle =$ $\displaystyle \sum_{i=0}^9 \Big{[}G(0, 10^N, \alpha(N, x,i), \beta(N, y,i)) +$  
    $\displaystyle \hspace{1em} 10^NiF(0, 10^N, \alpha(N, x,i), \beta(N, y,i))\Big{]}$ (7)

This is somewhat more complicated because when we map $i$-digit numbers to $i-1$-digit numbers, we aren’t changing $F$, which counts the numbers, but we are changing $G$, their sum. We have to add back in contributions made by the removed digits.

Building Back Up

We’ll maintain tables $\mathcal{F}_i$ and $\mathcal{G}_i$ at each level $i$ that hold the multiplicity of each of the $i$-digit subproblems.
To continue our mission to compute $G(0, 10^6, 0, 0)$, we begin by initializing the lowest order $\mathcal{F}$ table as follows below. The colors will be explained in a moment.

\begin{eqnarray*}\mathcal{F}_0 & = &\begin{tabular}{\vert cc\vert ccccccc\ve......0 & 0 & \cellcolor[rgb]{.1,.4,0.4} 0 & 0 \\\hline\end{tabular}\end{eqnarray*}

Only $\mathcal{F}_0[0,0]$ has the value 1 because the only number with “0 digits” is 0, and it and its reverse have residue 0 modulo 7. We can apply Equation (1) to populate $\mathcal{F}_1$. Notice that each element in $\mathcal{F}_1$ is the sum of 7 elements in $\mathcal{F}_0$, 3 of them counted twice. E.g.,

\begin{eqnarray*}\mathcal{F}_1[2,2] & = & F(0, 10^1, 2, 2) \\& = & \sum_{i=0}...... 2) \\& = & \sum_{i=0}^9 F(0, 1, \alpha(0, 2,i), \beta(0, 2,i)\end{eqnarray*}

with $\alpha(0, 2, i) \equiv 2 - i \equiv 2 + 6i$ (mod 7), and $\beta(0, 2, i) = 4 + 5i$. When $i = 0$, this corresponds to the bluest cell (2,4) in $\mathcal{F}_0$. At $i = 1$, we’ve moved up and to the left to a slighter lighter blue cell. As $i$ ranges up to 9, we take a knight’s tour illustrated by the color fading from blue to green. The other cells visited are (1,2), (0,0), wrapping to (6,5), (5,3), (4,1), (3,6), and back to (2,4), (1,2) and (0,0). Notice that the 3 bluest cells are visited twice. In particular (0,0) is visited third and tenth, giving us two 1′s in the sum and $\mathcal{F}_1[2,2] = 2$.

Filling out the rest of $\mathcal{F}_1$,

\begin{eqnarray*}\mathcal{F}_1 & = &\begin{tabular}{\vert cc\vert ccccccc\ve......& 0 \\& 6 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\hline\end{tabular}\end{eqnarray*}

And continuing with $\mathcal{F}_2$,

\begin{eqnarray*}\mathcal{F}_2 & = &\begin{tabular}{\vert cc\vert ccccccc\ve......& 2 \\& 6 & 2 & 1 & 4 & 2 & 2 & 2 & 1 \\\hline\end{tabular}\end{eqnarray*}

To illustrate the interpretation of this, take $\mathcal{F}_2[5,0]$, in red. This means that are 4 numbers between 0 and 100 which have a remainder of 5 when divided by seven and when reversed, have a remainder of 0. Sure enough, there are four and they are 12, 19, 82 and 89. Continuing,

\begin{eqnarray*}\mathcal{F}_3 & = &\begin{tabular}{\vert cc\vert ccccccc\ve......& 6 & 19 & 19 & 19 & 19 & 19 & 19 & 28 \\\hline\end{tabular}\end{eqnarray*}

and…

\begin{eqnarray*}\mathcal{F}_4 & = &\begin{tabular}{\vert cc\vert ccccccc\ve...... 195 & 203 & 216 & 186 & 235 & 187 & 206 \\\hline\end{tabular}\end{eqnarray*}

and…

\begin{eqnarray*}\mathcal{F}_5 & = &\begin{tabular}{\vert cc\vert ccccccc\ve...... 2021 & 1994 & 2123 & 2035 & 2100 & 2026 \\\hline\end{tabular}\end{eqnarray*}

At this point, we can extract all the needed values of the $F$-function to generate the $\mathcal{G}_i$ tables, via Equation (7). The $\mathcal{G}_i$ table is built in a similar fashion, except it draws from both $\mathcal{G}_{i-1}$ and $\mathcal{F}_{i-1}$. Unlike $\mathcal{F}_0$, $\mathcal{G}_0$ is entirely zeros. Within an asymptotically constant factor, the numbers in $\mathcal{G}_i$ are the squares of those in $\mathcal{F}_i$. As a result, the $\mathcal{G}_i$ tables must be omitted for space. However, ultimately, we do arrive at our answer $\mathcal{G}_6[0,0] = 10,363,989,636$.

Theoretical Analysis:

In general, for a base $b$ the computation of each subproblem is $\Theta(b)$. With forward and backward divisors $d_1$ and $d_2$, there are $d_1d_2$ subproblems on each of $N$ levels, thus this algorithm requires $\Theta(bd_1d_2N)$ operations. Practically speaking, $G(0, 10^{1000}, 0, 0)$, a number with 1,999 digits, can be calculated in only 14 seconds on my laptop.

More Numbers:

For completeness and for the curious, here are some extended results. The numbers in the range on the left that meet our divisibility conditions have their sum equal to the number on the right.

[0, 1] -$>$ 0

[0, 10] -$>$ 7

[0, 100] -$>$ 154

[0, 1000] -$>$ 10787

[0, 10000] -$>$ 1029567

[0, 100000] -$>$ 105714126

[0, 1000000] -$>$ 10363989636

[0, 10000000] -$>$ 1027216680497

[0, 100000000] -$>$ 102184086890270

[0, 1000000000] -$>$ 10205609904879424

[0, 10000000000] -$>$ 1020424310227628614

[0, 100000000000] -$>$ 102049428685193293045

[0, 1000000000000] -$>$ 10204479595989795520404

[0, 10000000000000] -$>$ 1020425244837350504933851

[0, 100000000000000] -$>$ 102041179796115463104759635

[0, 1000000000000000] -$>$ 10204085511291024760949778376

And the list continues….

Leave a Comment

Barrels of Gold

July 6, 2008 at 12:47 am · Filed under Math, Uncategorized ·Tagged

Problem

My friend Brian Marion posed a variant of the following problem:

Suppose I just robbed Fort Knox. I was in a rush and I put the gold in what I had available: 3 large barrels. I didn’t keep track of how much I put in each one, I just threw bars into whichever was closest until the klaxons drove my nerves over the edge. Then I hammered down their lids and bailed – I can’t even be sure that a particular barrel has anything in it.

Since you helped plan the heist, I’ll let you have any one of these three sealed barrels that you want. Of course, even an empty barrel is too heavy to lift by hand, so it’s hard to tell which has the most gold. The only way you can measure their contents is to see if the forklift can lift them. As a safety feature, our forklift can be calibrated to a certain weight, which it will lift no more than. However we can only set this once because changing it a second time requires retooling and a visit from the manufacturer, which would blow our cover.

We know this: these barrels are holding between 0 and 1000 pounds of gold, with a uniform, random distribution. You get to pick a weight, any weight you’d like and test which barrels are heavier than that, and which are lighter. If just one is heavier and two are lighter – great! You found the one with the most gold. If there’s a tie for heaviest, you’ll just have to pick one. But hey, you might eliminate the lightest one and that’s better than no information, right?

Suppose the forklift’s zero calibration is the weight of an empty barrel, so we can ignore that number. Therefore, if you set it to 500 pounds, you have exactly a 1/2 chance of getting a particular barrel too heavy to lift, but a 3/8 chance of getting one too heavy and two too light. On the other hand, you might get two too heavy, and you’ll wish you had set it higher. Obviously, there’s a tradeoff: higher weights are less likely to have a tie among several barrels being the heaviest, but on the other hand they risk overshooting all the barrels and you’ll be stuck just picking one of the three.

What is the weight capacity you should set on the forklift to maximize your average expected gain?

Solution

First we’ll solve a more general problem, then plug in the numbers to solve this one. Without loss of generality, say the amount of gold in a barrel ranges from 0 to 1. Suppose there are $b$ barrels and $g$ (for guesses) calibrations available to us. Suppose the set $C$ is the set of calibrations, which we’ll write as $C = \{c_{i} \hspace{.3em} \vert \hspace{.3em} i \in [1,g]\}$. $c_{g}$ will be the biggest one and they descend from there, so this equation is true:


$\displaystyle 0 < c_{1} < ... < c_{g-1} < c_{g} < 1$     (1)

Finally, add the two constants $c_{g+1} = 1$ and $c_{0} = 0$ to make our formulas cleaner. Each barrel can fall into any of the $g + 1$ ranges: less than the smallest calibration, bigger than the largest, or between any pair of consecutive calibrations.

To find the expected value of a set of calibrations, we can find the expected values of each of these gaps and multiply those values by their probabilities, then sum up the products. The average value of a barrel between $c_{i+1}$ and $c_{i}$ is $\frac{c_{i+1}+c_{i}}{2}$ and the only way you’ll end up with that as the amount of gold you get is if the largest barrel is in that range. Fortunately, that probability is easy to calculate: the chance of all the barrels being less than $c_{i+1}$ is $c_{i+1}^{b}$ and the chance of them all being smaller than $c_{i}$ is $c_{i}^{b}$, so we can simply subtract these two powers to get the probability that all the barrels are less than $c_{i+1}$, but not all are less than $c_{i}$.

Then the expected value is


$\displaystyle E(C)$ $\textstyle =$ $\displaystyle \sum_{j = 0}^{g}\frac{c_{j+1}+c_{j}}{2}(c_{j+1}^{b} - c_{j}^{b})$ (2)
  $\textstyle =$ $\displaystyle \frac{1}{2} \left[\sum_{j = 0}^{g}(c_{j+1}+c_{j})(c_{j+1}^{b} - c_{j}^{b}) \right]$  
  $\textstyle =$ $\displaystyle \frac{1}{2} \left[\sum_{j = 0}^{g}(c_{j+1}^{b+1} - c_{j+1}c_{j}^{b} +c_{j}c_{j+1}^{b} - c_{j}^{b+1}) \right]$  
  $\textstyle =$ $\displaystyle \frac{1}{2} \left[\sum_{j = 0}^{g}(c_{j}c_{j+1}^{b} - c_{j+1}c_{j}^{b}) +\sum_{j = 0}^{g}(c_{j+1}^{b+1}- c_{j}^{b+1}) \right]$  
  $\textstyle =$ $\displaystyle \frac{1}{2} \left[\sum_{j = 0}^{g}(c_{j}c_{j+1}^{b} - c_{j+1}c_{j}^{b}) + 1 \right]$  

The maximum value of $E(C)$ can be found by taking partial derivatives with respect to each $c_{i} \in C$, setting these expressions to zero, and solving them simultaneously. The constant 1 will not survive differentiation and the $\frac{1}{2}$ is superfluous. A variable $c_{i}$ appears in 4 terms, namely

\begin{eqnarray*}c_{i}c_{i+1}^{b}-c_{i}^{b}c_{i+1} + c_{i-1}c_{i}^{b}-c_{i-1}^{b}c_{i}\end{eqnarray*}

with derivative,

\begin{eqnarray*}c_{i+1}^{b}-bc_{i}^{b-1}c_{i+1} + bc_{i-1}c_{i}^{b-1}-c_{i-1}^{b}\end{eqnarray*}

Thus the solution can be found by solving the equations:


$\displaystyle c_{i+1}^{b}-bc_{i}^{b-1}c_{i+1} + bc_{i-1}c_{i}^{b-1}-c_{i-1}^{b} = 0, \forall i \in [1, g]$     (3)

Finally, If g = 1 and b = 3

Returning to our original problem, if there are 3 barrels and 1 calibration $C = \{c_{1}\}$, the Equations (3) require that we solve

\begin{eqnarray*}1 - 3c_{1}^{2} & = & 0\end{eqnarray*}

Therefore, the solution is $c_{1} = \frac{1}{\sqrt{3}} = 0.57735... $, meaning the best calibration is 577 lbs. This has a nice 42% chance of isolating the heaviest barrel and a mere 27% chance of not separating the barrels at all. You must be wondering what your payout is. By Equation 2 it is 748 pounds of Gold.

Another Example, g = 3 and b = 4

As another example, for 3 calibrations $C = \{c_{1}, c_{2}, c_{3}\}$ and 4 barrels, Equations (3) are

\begin{eqnarray*}c_{2}^{4}-4c_{1}^{3}c_{2} & = & 0 \\c_{3}^{4}-4c_{2}^{3}c_{3......{4} & = & 0 \\1-4c_{3}^{3} + 4c_{2}c_{3}^{3}-c_{2}^{4} & = & 0\end{eqnarray*}

This might be pretty tricky to solve by hand, but the mathematical software Sage gives the numerical solution:

\begin{eqnarray*}c_{3} & = & 0.83463... \\c_{2} & = & 0.64395... \\c_{1} & = & 0.40566...\end{eqnarray*}

In fact, Sage finds 57 solutions but only 5 are real. Of these 5, only 1 satisfies the ordering in Inequalities (1).

Leave a Comment

Follow

Get every new post delivered to your Inbox.