Wednesday, August 12, 2015

Three Puzzles Adapted from Lewis Carroll

1. In a certain junkyard, 60% of the cars have lost their wheels, 70% of the cars have lost their doors, and 80% of the cars have lost their seats. What is the least possible fraction of the cars that has lost all three?

2. A bag contains one counter, known to be either white or black. A white counter is put in, the bag shaken, and a counter drawn out, which proves to be white. What is now the chance of drawing a white counter?

3. Consider that:

  • 3 divides evenly into 9. 
  • 37 divides evenly into 999.
  • 7 divides evenly into 999999. 

Show that any odd number not divisible by 5 divides evenly into 99...9, if you include enough 9's.

All three puzzles can be solved using K–12 mathematics. I have provided some hints here.

Thursday, August 6, 2015

Minimizing Length to a Segment, Cont'd

Place a segment of length 1/2 in such a way as to minimize the sum of its distances to three vertices of a unit square.


In the example shown, the three lengths to be added are shown as dashed lines. (The example shown is not optimal.)

I didn't know how to solve this puzzle when I posted it, but since then I have thought about it some, and I think I have the answer.

Here goes; if I have it wrong, someone will let me know.

To begin with, replace the dashed lines in the figure with solid lines. The result is a network that connects the three vertices of the square. Obviously, this network cannot be shorter than the shortest possible network connecting the three vertices. But what is the shortest possible network connecting three points?

As I learned from this historical study, Pierre de Fermat first posed a similar problem in 1643:
datis tribus punctis, quartum reperire, a quo si ducantur tres rectae ad data puncta, summa trium harum rectarum sit minima quantitatis.

Apparently this is Latin for
given three given points, a fourth is to be found, from which if three straight lines are drawn to the given points, the sum of the three lengths is minimum.
Fermat himself could probably solve this problem, but the first known solution is due to Torricelli (1608–1647). Then, it seems, the problem was forgotten until it was posed again in 1810 by the French mathematician Joseph Gergonne. He posed a number of extensions of the problem, including some that resemble our segment problem. 

Gergenne was the first to pose what has become known in modern times as the Steiner tree problem: Given a collection of points in the plane, find the shortest network that connects them. This is the problem we are interested in today. The Steiner problem differs from Fermat's problem because Gergenne isn't assuming from the outset that the network will meet in a single point (though that turns out to be the case for three boundary points).

Gergenne solved the problem in some specific cases and made impressive progress toward general conclusions. Later, Gauss toyed with the problem, and a mathematician/schoolteacher named Bopp did further work on it, including deriving the first results for a collection of boundary points in three-dimensional space. 

In the 1930's, a couple of Czech mathematicians gave the first modern treatment of the Steiner problem, and in the 1960's interest in the problem exploded. The reason seems to have been twofold. First, problem was presented to a wide readership in the popular 1941 book What Is Mathematics? (still popular!); and second, the problem proved to be directly related to emerging industrial problems such as optimizing integrated circuits and communication networks.

Today, it is known that length-minimizing networks in the Euclidean plane always consist of straight segments that meet in threes at angles of 120 degrees. Like other optimal forms, these minimal networks are often handsome to look at.

(By the way, I first learned about all this when I was an undergraduate and part of the group that proved the planar double-bubble conjecture.)

So much for the history. How does this knowledge help us in the segment problem? Recall that we were interested in the shortest possible network connecting three vertices of the unit square. Based on the summary above, you can probably devise this network yourself; it looks like this:




This length-minimizing network provides a way to solve our segment problem: namely, we lay down our segment along one of the edges of the minimal network:




If we denote the length of the minimal network by L, then we see that the dashed segments in this solution have total length L - 1/2. There is no way to give the dashed lines a smaller total length. For if you could somehow connect the three vertices to the segment using total length D < L - 1/2, then there would exist a network of length D + 1/2 <  L. Since no network exists with length less than L, no better solution to the segment problem exists either.

By the way, our solution has a total dashed length of about 1.43. By comparison, laying the segment vertically down the left-hand edge of the square (touching the upper-left vertex) gives a total dashed length equal to 1.5.

Tuesday, August 4, 2015

Minimizing the Total Distance to a Segment

Place a segment of length 1/2 in such a way as to minimize the sum of its distances to three vertices of a unit square.


In the example shown, the three lengths to be added are shown as dashed lines. (The example shown is not optimal.)

Monday, July 20, 2015

List of animal names sorted by syllable count

The list I said I would make is now available at www.tinyurl.com/animalsyllable.

(Click to read the name of a 15-syllable animal!)

The document is open for comments. Perhaps it will grow over time.


Sunday, July 19, 2015

Animal/Syllable

My kids enjoyed this puzzle—I thought my readers & their kids might enjoy it too:
  • A one-syllable animal: _________________
  • A two-syllable animal: _________________
  • A three-syllable animal: _________________
  • Etc.
The Internet can be helpful for some of the higher syllable counts. But on a quick search, I actually didn't find a super-convenient list of animal names sorted by syllable count. For my next post, I'll make a start at one.

Animal names don't have to be single words; lake trout is an animal name for the purposes of this puzzle. Also, it is not the intention here to use scientific Latin names, although that version of the puzzle would be fun too.

Wednesday, July 8, 2015

Bad Johnny and the Fractions, Cont'd

As punishment for misbehaving, Johnny's teacher made him compute \(\frac{6446266}{9669399} - \frac{6666442}{9999663}\). "That's easy," said Johnny, as he sauntered out of the classroom. "It's the same thing as \(\frac{2446666}{3669999} - \frac{2446666}{3669999}\), which is zero."

Reader jeff solved this puzzle in brief. Here's a more leisurely walkthrough, in case interesting.

If you see a fraction like \(\frac{24}{48}\), it's pretty easy to realize that it equals \(\frac{1}{2}\). How about a fraction like \(\frac{1234332}{2468664}\)? This is also \(\frac{1}{2}\). How can you tell? One way is to compare the numerator and the denominator one place value at a time. If you do that, you'll see that each digit in the denominator is twice as large as its corresponding digit in the numerator. Therefore the denominator itself is twice as large as the numerator.

The reasoning behind this "twice as large" example works for other ratios as well. For example, in the fraction \(\frac{123}{369}\), each digit in the denominator is three times as large as the corresponding digit in the numerator. That makes the denominator itself three times as large as the numerator—so the fraction equals \(\frac{1}{3}\).

In the cases above, we "sized" the denominator relative to the numerator, but you could just as well reverse the comparison. Thus, in \(\frac{123}{369}\), we can notice (along the lines of the reader's comment) that each digit in the numerator is one-third as large as the corresponding digit in the denominator. That makes the numerator itself one-third of the denominator—so the fraction equals \(\frac{1}{3}\).

Those two ways of looking at \(\frac{123}{369}\) could be expressed respectively as

\(\frac{123}{369}=\frac{123}{300+60+9} = \frac{123}{3\cdot100+3\cdot20+3\cdot3} = \frac{123}{3\cdot(100+20+3)} = \frac{123}{3\cdot123} = \frac{1}{3}\)

and

\(\frac{123}{369} = \frac{100+20+3}{369} = \frac{\frac{1}{3}300 + \frac{1}{3}{60}+\frac{1}{3}{9}}{369} = \frac{\frac{1}{3}(300+60+9)}{369} = \frac{\frac{1}{3}\cdot369}{369} = \frac{1}{3}\).

One last example: In \(\frac{462}{693}\), each digit in the numerator is two-thirds of the corresponding digit in the denominator. That makes the numerator itself two-thirds of the denominator—so the fraction equals \(\frac{2}{3}\).

When every digit in the numerator is a constant multiple of its corresponding digit in the denominator, that remains true even if the digits are permuted, as long as the digits in the numerator and the digits in the denominator are permuted in the same way. Thus \(\frac{462}{693} = \frac{426}{639} = \frac{246}{369}\), etc. One way to understand Johnny's cheeky response is to observe that he has permuted digits in the two given fractions in such a way as to make them manifestly identical.

Exercise: \(\frac{66336363}{88448484} - \frac{12221}{48884}\) = ?

***

The principles at work in this puzzle might merit a little more discussion. If so, consider this scenario about a hypothetical hotel that has one guest room, one boardroom, and one ballroom. In each of the three rooms there is a party going on.

  • In the guest room there are 3 people, 2 of whom are crashing the party. Clearly, in this room \(\frac{2}{3}\) of the people are crashers.
  • In the boardroom, there are 60 people, 40 of whom are crashing that party. So in this room, \(\frac{40}{60} = \frac{2}{3}\) of the people are crashers too. 
  • In the ballroom, there are 900 people, 600 of whom are crashing that party. So in this room as well, \(\frac{600}{900} = \frac{2}{3}\) of the people are crashers.

What fraction of people in the entire hotel are crashers? One way to find out is to add up all of the crashers and then divide by the total number of guests: \(\frac{600 + 40 + 2}{900 + 60 + 3}=\frac{642}{963}\). But another way is to realize that since \(\frac{2}{3}\) of every room is crashers, \(\frac{2}{3}\) of the entire hotel is crashers. The two methods must agree, so \(\frac{642}{963}=\frac{2}{3}\).

***

More abstractly, we can say that if \(\frac{a}{b}=\frac{c}{d}\), then for any \(k\), \(\frac{ka+c}{kb+d} = \frac{c}{d}\). (One can verify this by cross-multiplying. For simplicity I'm taking all of the variables to be positive.) Applying this principle with \(\frac{a}{b}=\frac{4}{6}\), \(\frac{c}{d}=\frac{2}{3}\), and \(k=10\), we have \(\frac{10\cdot4+2}{10\cdot6+3} = \frac{2}{3}\). Applying the principle once more with \(\frac{a}{b}=\frac{600}{900}\), \(\frac{c}{d}=\frac{40 + 2}{60 + 3}\), and \(k=100\), we have \(\frac{100\cdot6+40 + 2}{100\cdot9+60 + 3} = \frac{40 + 2}{60 + 3} = \frac{2}{3}\). And we could keep going to create larger and larger fractions, all equal to \(\frac{2}{3}\). Choosing the \(k\)'s to be powers of 10 creates a series of equivalences that can be read off directly from the digit strings of the multi-digit numbers in the numerator and denominator.

Solution to Fourth of July Puzzle: Out of Many, One

Challenge: Form 1 out of the following fractions:
3/5, 1/3, 2/3, 2/3, 2/3, 2/3, 2/3, 3/4.
In other words, create an expression, the value of which is 1, using all of the above fractions together with any or all of the symbols \(+\), \(-\), \(\times\), \(\div\), and parentheses.

My solution was

\(\frac{3}{5}\times\left(\frac{3}{4}-\frac{1}{3}\right)\times\left(\frac{2}{3}+\frac{2}{3}+\frac{2}{3}+\frac{2}{3}\right)\div\frac{2}{3} = 1\).

This uses 7 binary operation symbols and two sets of parentheses. Reader jeff's solution was

\( (\frac{2}{3}\div\frac{3}{5})+(\frac{2}{3}\div\frac{3}{4})-(\frac{2}{3}\div\frac{1}{3})+(\frac{2}{3}\div\frac{2}{3}) = 1\).

This solution also uses 7 binary operation symbols, but it's better than mine in the sense since that it requires no parentheses. (The parentheses here add clarity but could be removed leaving a well formed expression equaling 1.)