Archive for July, 2008

The Monkey Problem

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…

Advertisements

Comments (1)

Thailand 2008

During my stay in Thailand last week, I took 1,040 pictures and video segments. A representative 112 are posted on flickr. All the pictures in this blog entry below are also on that set.

For the first half of the week, I was in Bangkok at Natalie’s apartment. After her work finished for a break, we flew to Krabi, far to the south, then took a ferry to the island of Phi Phi (pronounced Pee-Pee). We stayed there for two nights and went bushwhacking in the mountainside jungle. There were far more european tourists than americans, (but they all stayed in town).

For the next phase, we took a ferry to the peninsula of Railay. The end of this ferry trip involved climbing on open water from the ferry into a covered canoe with a motor on the back (called a longtail boat). Then after a short canoe trip, wading up the beach with all our stuff, because there was no dock. I think we were safe, but there were other tourists with children and some with small babies that had to be passed from boat to rocking, heavily-laden boat.

In Railay, we saw a wild monkey climbing on the walls of a Hotel. Railay is quite isolated and there are apparently no roads to access it. In order to make our 10AM flight the following morning, we chartered a private longtail boat (with wading on both ends of the trip). We specially requested that the boat leave at 7:30 and paid in advance for this, but I guess that information got lost in the shuffle somewhere. We left around 8:10 with a german family and made it to the flight in time.

The area around Railay and Phi Phi is open ocean punctuated by numerous islands with steep cliffs on several, and sometimes all, sides.

Apparently at least one James Bond film was shot in the area. More details can be found on the Wikipedia page for The Man with the Golden Gun.

Some observations about Bangkok:

There’s a 7-11 on almost every corner

It’s very hot and humid, but everybody wears pants and long sleeves

Street vendors sell fruit, grilled meat and various other dishes. For 10 bhat (about $0.30) you can get a 1/3 of a pineapple, carefully peeled and chopped up in a bag with a shish-kebab stick to eat it with.

Stoplights have a large timer next to the lights which counts down the seconds until the light will change. The timers, which are about 5 feet across, are red, yellow or green to match the lights. You can see one below:

Compared to Beijing, Bangkok residents are friendlier, seem to be slightly more wealthy, are more likely to speak English and have somewhat cleaner air.

Several times in Bangkok, we saw elephants being led on the street.

The Thai language is harsh sounding.

Soy Dogs (soy means street) sleep under cars and in doorways. The one I saw looked healthy and well-groomed. Apparently, Thai people have a strong sense of generosity.

In Tokyo, as the plane was leaving the gate, I saw 3 members of the airport ground crew who had been loading luggage, wave in unison to the plane, then bow together before they turned and went back to the terminal.

Comments (3)

Why do planes even have “No Smoking” signs anymore?

Is because it’s a neat place for a sign that is already wired into every plane and they might want to use it for something later? Or is it really stopping people from lighting up? Is there even an off switch for it in the cockpit?

Leave a Comment

Web 2.0 ideas that would probably not take off

Mr. Fuller asks for the most unworkable Web 2.0 idea.

How about the one where you enter the kinds of pollen you are allergic to and it matches you people with similar allergies so you can carpool to work through parts of town far away from those plants?

Or the historical-data-driven horoscope site, where people with your same birthday who are in time-zones ahead of you write what actually happened to them that day, which is then turned around to be your prediction for the next few hours.

Then there’s the one where you upload geo-locating data about what part of your world your dog’s breed is originally from, so you can find neighbors whose dogs speak the same dog-language (e.g., a peruvian dog speaks the Spanish form of dog).

Finally, there’s the site where you upload your Gmail contact information and for each a friend a movie you know he or she is excited to see, and it does nothing but spam them with mail appearing to be from you that reveals spoilers. The site propagates virally, on the premise that each friend will be angry enough about it to do the same to his or her own friends.

Comments (1)

Seeded Plants

There is one plant I bike next to every morning where the path is very narrow, just one plant, that produces all of these cute little seeds:

Comments (1)

Divisible by 7, Both Ways

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

Concrete Riddling

In trying to make a riddle for someone, I put a famous quote into Google translate in telephone-game style sequence of language translations. The idea was to see if it would come out puzzling but not completely impossible to determine the original saying.

It didn’t work. The first half of the quote is oddly untouched and the second half has collapsed into a single-word non-sequitur. If it only there were a way to compromise on these two extremes.

Here’s the sequence I used: English -> Arabic -> Finnish -> Croatian -> Czech -> Russian -> Japanese -> Dutch -> Chinese -> German -> French -> Greek -> Bulgarian -> Korean -> English.

And here’s the garbled quote:

“Be careful when you fight monsters and concrete.”

Leave a Comment

Older Posts »