Tuesday, December 23, 2008

Th Seven Bridges of Q'w'nis

The most recent US presidential election has left Rotary High Command in something of a quandary. The window on many of our most of our important higher governmental connections is now closing. No longer will we be able to send captured Kiwanians to secret sites in Eastern Europe to be enlightened on new, aggressive interrogation techniques. But Noon Rotary is not so easily discouraged, and it has occurred to some in High Command that the current political situation might give that pitiful minority of the club who are democrats added value added value, if only as hostages.

It was in this spirit that I, a mere Replacement Cog in the group’s organizational structure, was approached with the request of a favor requiring something of my mathematical training. The following story was related to me in regard to some black operations that are being carried out deep in enemy territory on behalf of Noon Rotary High Command by a group known simply as “the Agency.”

This region is known as Q’w’nis. It is occupied by a simple, though sinister, people who are famed for creating a special wheat cake covered with a sugary tree derivative in the month of December. There is a huge gorge that divides the region of Q’w’nis and in the middle of that gorge are two tall rock formations, much like what you see in monument valley. One of the formations is called B’tar and the other S’ryp.

The gorge itself is too wide to be spanned directly by a bridge of any type; nevertheless, the pieces of the region are bound together for purposes of transportation by great swinging bridges that make use of B’tar and S’ryp. On the south side of the gorge there are a total of three bridges. Two of these connect to B’tar and one to S’ryp. On the north side, there are also three which connect to B’tar and S’ryp in the same way. There is also a single bridge between B’tar and S’ryp. This means there are five bridges connecting to B’tar, three to S’ryp, and a total of seven bridges all together.

The Agency plans to destroy these bridges in order to disrupt trade in the region and have concocted the following plan. Land a helicopter secretly on B’tar and begin tracing a path across the bridges, destroying each one as they go. Then, having closed the path, get back into the helicopter and return home.They discovered a problem, however. Normally the Agency just comes up with these plans and does them, but this time one of the agents drew a map of the region and began tracing out the route ahead of time. He discovered that, no matter how he traversed the bridges, when all the bridges were destroyed, he was somewhere besides on B’tar with the helicopter.

This was a pretty green agent or he never would’ve planned it out ahead. He would’ve done his job and dealt with the consequences as they happened. However, it occurred to the Agency that they might be able to save the helicopter if they called in a consultant. That’s where I came in.

As is so often the case, they did not get the answer they wanted. It turns out that, regardless of the path their agent might take, he will wind up stranded away from the helicopter. Each of the bodies of land has an odd number of bridges attaching it to the rest. If you use up the bridges as you cross them, you will always wind up away from where you started.

“This is actually exactly like the old Seven Bridges of Konigsberg problem,” I said. “It was solved by Leonhard Euler centuries ago.”

“Konigsberg?” the contact said. “I’ve never heard of Konigsberg.”

“It’s called Kalingrad now,” I said. “It’s in Russia.”He said nothing but eyed me suspiciously. Getting no further feedback, I still proceeded.

“You know,” I said, “it occurs to me that if your purpose is just to disrupt travel you could leave the single bridge between B’tar and S’ryp intact, and take out the remaining six bridges from the B’tar-S’ryp end of it.”

On hearing that, he answered.“The Agency does not require you to tell us how to do our business.” And with that, he left.I wonder if this will get me any points with High Command.

Friday, December 12, 2008

Hyperbolic History

An Introductory Fable
The McCoys were a family who lived in the hills and had a passel of kids. Passel is one of those imprecise words, but when I say it here, I mean more than one, but beyond that the actual number is not important. The hills that the family lived in and the hollows that they farmed were, in spite of their verdant fecundity, relatively bereft of people.

The McCoys were full of life and laughter and stories. These stories were about people the parents had known in old country during the days before they came to the hills. The children, though they'd heard the stories many times, loved to listen to them again and again.

When each of the McCoy children came of age, a trip was made to the city, which was many miles away, and a suitable spouse was found and brought back.

Each time the new couple lived with the original family until they were on their feet and had a desire for independence and at such a time they--quite tearfully because the family was close--removed themselves from the original family in order to take up occupation in one of the adjacent valleys.

As travel was difficult and by foot, there weren't many opportunities to travel back and forth, and eventually they fell out of touch, busy with their own lives.

As the years progressed, the McCoy grandchildren came of age and were married to suitable spouses, had families, and moved them into adjacent hills and hollows , but, and, for similar reasons, fell out of touch with their parents.

In the fullness of time, the family filled up the land, and, it came to pass, that distant cousins were residing in adjacent valleys far from the original McCoy home. They met and feasted because of coming upon kinfolks, however distant, in such a way. They passed the tradition moonshine jug and shared stories. In doing this they made the discovery they could understand the stories from those original McCoys so much better than each other's more recent stories.

Though they were neighbors in the sense of geography, they were much closer to those first McCoy's culturally than they were to each other.

Hyperbolic Geometry

Tenth grade geometry was the first course in mathematics I actually liked. My teacher, Hoyt Sloan, was of the old-fashioned sort who insisted that we learn how to do proofs. (With a name like Hoyt, you are going to be old-fashioned.) As I read more about mathematics and learned more about geometry, I kept running into something called hyperbolic geometry. It was rather a mysterious area of knowledge. None of my sources described what it was other than an alternative to Euclidean geometry. Euclidean geometry is what is taught in a typical high school geometry class.

It is named for Euclid, the ancient Greek mathematician, because he wrote a book about it in which he had a set of rules (axioms and postulates) that described the ways points, lines, and planes behave. The postulates were "obvious" statements from which other less obvious statements were deduced.

One of these postulates stated that given a line and a point not on the that line there is exactly one line through the point that is parallel to the original line. This is called the parallel postulate. Whereas postulates are meant to stand without proof, it seemed to a lot of folks that they should be able to prove the parallel postulate, so over the years a lot of ink was spent in the process of trying to do just that, but no one ever succeeded.

That's because you can't. It turned out there are other geometries besides Euclidean and the geometry in which there is more than one line through a point that is parallel to the original line is called hyperbolic geometry.

It's presented this way because that is how it was stumbled upon historically, but I find this regrettable because it leaves the impression that there is something wrong with hyperbolic geometry.

A Better Approach

A better way to understand the hyperbolic plane is through the concept of curvature. First, think about a sphere, which is the idealized version of a ball. (That is to say a basketball or a billiard ball, not a costume ball.) If you put a spherical object on a table, you can see that points on the ball curve away from the table. This is called positive curvature.

The table upon which the ball is sitting it perfectly flat and doesn't curve. This is called zero curvature.

Now consider another familiar object: the saddle. (If you are not from a rural culture, think of a Pringle's Potato Chip.) If you put a saddle on a table, you will note that some of the saddle curves away from the table and some curves toward it.

It's impossible to actually do this, but you can imagine the saddle to sink into the table so the the point of the saddle that normally meets your posterior is flush with the table top itself. Doing this, you can see in your head that part of the saddle is below the table and part is above. This is called negative curvature.

Now imagine yourself taking a walk. When you are walking on the plains around Wichita, you are most likely standing at a point of zero curvature. When you are at the peak of a mountain in Colorado, you are at a point of positive curvature.

But when you are standing at the top of a mountain pass in Utah with canyon walls curving up away from you on either side and the road curving down and away in front and behind you, you are at a point of negative curvature.

Geometrically speaking, in Euclidean Geometry, every point is a point of zero curvature and in Hyperbolic Geometry every point is a point of negative curvature.

How Big is your Circle?

One of the first formulas that anyone learns is C=2πr, that is the circumference of a circle is 2 times pi times the radius of the circle. This formula only works in Euclidean geometry, however. On the surface of a sphere, the circumference of a circle is somewhat less than it would be for a circle of the same radius on a plane.

You can see this by imagining a basketball cut in half along its equator. The equator is a circle because every point on it is the same distance from the north pole. (Not that a Santa Claus lives on a basketball, but I think you know what I mean.) Making the half basketball flat requires stretching out the equator, which makes it larger. In other words, it was originally smaller.

In hyperbolic geometry, the case is the opposite. The circumferences of circles are much larger with respect to their radii that is the case in Euclidean geometry. To be technical--and you knew I'd get here eventually--there is an exponential relationship between the radius and the circumference of the circle in hyperbolic geometry.

What does this have to do with a bunch of danged ol' hillbillies?

This is the connection, at least in a metaphorical way, to my original example. Your usual intuition for distances does not work in hyperbolic geometry. If you were taken by a spaceship to a hyperbolic world (a world inhabited a race of shapely warrior princesses...er forget that), it would be dangerous to go walking around.

As you got farther from your spaceship, the circumference of a circle around your spaceship would become increasingly large, and before you had gotten very far, it would be too far for you to walk around in a reasonable amount of time. Indeed if you walked to any place on the planet, but then decided you wanted to go to all most any other place, you would be well-advised to walk back to your spaceship first.

There are mathematicians who've noted this sort of behavior in the geometry of graphs. I don't mean the sort of graphs that you run into in College Algebra or Calculus. You might know them better by the name networks. These are geometrical/combinatorial objects constructed with vertices and edges, as you may have seen in the Seven Bridges of Konigsburg Problem.

It has occurred to me that if you have a growing system in which there is memory of the beginning state and the gaining of memories in subsequent states, after several generations there will be a great informational distance been the product states. That is to say, the McCoy cousins are not going to have much in common to talk about beyond stories about their great-great-etc grandparents--if they have managed to keep that tradition alive.

A practical application

This is the section in which the usually mild-mannered mathematician rants. Seeing a culture come unravelled is not pleasant. (I am convinced he end of civilization will be viewed on YouTube.) There are so many venues in which we take in culture, so many channels on the television, so many blogs on the 'Net, our common core of information is becoming very small relative to the mass of data that we are buried under. In order to understand someone who is outside of our own circle, we have to refer back to that common core of culture.

In my opinion, this makes it much more important to actually HAVE a common core of culture, a set of stories that everyone knows. As religious-nut/Bible-thumper being one of my avocations, I would tout holy scripture to an important part of our common cultural core. (I'd also put the old Warner Brothers cartoons there, but I am widely considered strange.)

Monday, November 3, 2008

Pick a number

Pick a number

Odd coincidences happen all the time. The other day I was on my way to Tulsa and had stopped at the so-called “World’s Largest McDonalds” that is on I-44 down around Vinita. I was in the mood to put another coat of cholesterol on my arteries and my family wasn’t along to perform an intervention. As a consequence I was in line to get a Quarter-Pounder combo with Fries, when I looked up an saw Bitty Bubba in the next line over.

Bitty Bubba, as you may recall, is one of my old friend Bubba’s nephews. He is the great hope of the family, so, as a consequence, the sum total of the family’s desires and fears are resting on his frail shoulders.

He was alone there too, so we sat down to eat together and began to talk. As it turns out, he’s taking a class in elementary probability and had learned a game he wanted to show me,
“Guess a number between one and three,” he directed.

“Inclusive or exclusive?” I asked. Whatever other interests I might have, I will be a mathematician until I die, so I make sure I know the rules before I get involved in a game. Bitty Bubba was a little confused by my question, however.

“What?” he asked.

“Inclusive means you include the endpoints—one and three in this case—and exclusive means you exclude them.”

“Uh...inclusive I guess,” he said.

“Two?” I replied.

“No,” he laughed. “I was thinking of 2.5.”

He had me. I’d been careful to ask about the endpoints, but I’d neglected to ask what he’d meant when he said “number,” assuming that he meant integer. You know what they say, if you assume you make an ass of you and me.

“That’s pretty funny,” I said. I appreciated his humor, but I didn’t want to waste a teaching opportunity. “Suppose, though, we’d stuck to the integers. What would’ve been my probability of getting a correct answer then?”

“Well,” he said, drawling it out to give himself time to think, “it would be one-third because there were three numbers to choose from—one, two, and three—but only one right number.”

“You are correct,” I said. I wasn’t surprised. In my experience as a math teacher, most students just know this. “Now, I’ve got a harder question to ask. You increase the numbers to those with a decimal representation. What is the probability of my choosing correctly then?”

His eyebrows nit for a moment like he was thinking very intently.

"I want to say zero," he finally answered, "but I don't know why."

"You are correct," I answered him. "The probability is zero. You can think about it like this. If you had ten numbers, the probabilty would be one tenth and if you had 100 numbers, it would be one one-thousandth, but there are infinitely many decimal numbers between one and three. When you say there are infinitely many numbers, that means whatever number you name there are more decimal numbers than that. That means the probability is smaller than one tenth or one one-thousandth or one one-millionth and so on. The probability is smaller than any number you can think of, so it's zero."

Bitty Bubba got that look in his eyes that so many of my students get when they are really fascinated with what I am saying. Oddly enough, it reminds a lot of people of a deer caught in headlights.

"Well, that's really interesting, but..."

"Do you know what is more interesting?" I asked. I hated to waste this teaching opportunity.
"But I really..."

"The probability of choosing a decimal number at random and getting a repeating decimal is zero as well," I said.

"Repeating decimals?" Bitty Bubba asked.

"Yes, repeating decimals are those like 1.222222... where the 2s go on forever or 2.31234343434...where the 34s repeat forever. There are infinitely many repeating decimals, there are even more that don't repeat. In fact, the number that are repeating is somehow insignificant to the the number that doesn't."

I was waxing eloquent now and look on Bitty Bubba's face was more mesmerized than ever.
"Indeed, we need new concepts to make sense of this. Instead of cardinality that we use when we count the members of a set, we need to use the concept of measure..."

"Oh!" Bitty Bubba cried out. "My bus is leaving."

With that he rushed from the dining area.

I thought this was strange because I hadn't even seen any buses. I thought it was even stranger when I saw someone that looked a lot like Bitty Bubba riding down the interstate below me on a motor cycle.

Back Log

I am currently in the process of rolling out a back log of articles I'd been amassing for a few years. The dear reader needn't feel obligated to following everything, of course.

An odd breed of termites



Introduction

Merle Bunyan, who is a good ole boy from the same neck of the woods where I grew up, still thinks that going out to the section line roads and spotlighting deer is a legitimate means of entertaining himself, or he did, I should say. A few years back he was out late at night doing just that and mysteriously disappeared for five days. This experience, whatever it was, changed him.
When he turned up, everyone who knew him, myself included, simply assumed he had been out on a drunk. This is what we call Ockham’s Razor where I come from, which is to say it’s simplest to assume they were drunk.

This assumption didn’t hold up over the long haul because after a while Merle started exhibiting what his wife interpreted as psychiatric symptoms. Last year during the Super Bowl he turned off the TV and started tidying up the house. His wife took him into the free clinic the very next morning.

His problems turned out to be deep seated. He started showing up for work on time and attending PTA meetings. It was then his psychiatrist started having sessions with him under hypnosis. During these sessions, it became apparent that his change in behavior stemmed back to the time he’d disappeared for five days.

I became involved when his wife, who I knew from back home, brought a tape of some of his sessions.

“Why are you bringing this to me,” I asked. “I’m not a psychiatrist. I am just a mathematics professor.”

“I know that,” she said, “and that is exactly why Merle and I need you. He would have been here himself, but he’s cleaning out the oven for me, poor man.” A little tear trickled down her cheek.

“Why do you need a mathematician?” I asked.

“Because of what’s on this tape,” she said. It was at that point she pulled out a cassette recorder and pressed the play button. What follows is my interpretation of what I heard on that tape and, as such, is necessarily incomplete.

Alien abduction

During the early part of the tape, it became clear that Merle was describing being taken aboard a spaceship. I am a skeptic about such things. The alien abduction has entered our modern mythology, so I believed Merle was just describing what he’d seen in some movie. And, in fact, the details that he recounted of his abduction matched the prevailing mythology to an astonishing—or perhaps not so astonishing—degree.

In spite of this, I came to believe his case might be an authentic alien abduction because of what I heard on the tape. The reason I changed my mind was the same reason Merle’s wife had brought me the tape, the mathematics on it.

You need to understand Merle was never any good at the mathematics he learned in school or what he had to use in life. He once bought cigarettes on special: One pack for 3 dollars, two for seven. On the tape, however, he said some things that required a precise knowledge of higher-level mathematics—at least a higher level than we would ever expect from him.

The termites

The first of these things was his description of a breed of alien creature that I will refer to as “termites” for reasons that will become apparent later in the story. From his description, I believe the termites were what followers of science fiction might refer to as nanites. These are little self-replicating robots.

The termites were creatures that reproduced by something very much like binary fission, which is to say they divided in half like bacteria. Each of the daughter termites was no more than half as large as the mother termite. Merle said that the daughter termites didn’t grow before they reproduced and they were twice as fast as the mother. The original birth he witnessed took about a minute, the second generation only took about thirty seconds to reproduce, the third generation only took about 15 seconds to reproduce, and so forth.

The psychiatrist who was conducting the interview asked how he could follow them after the first few divisions because they would be getting quite small by that time, and Merle said the aliens were displaying it on the screen of a fancy microscope for him.

The first point at which I began to become suspicious that what I was hearing might be true was a place in the interview when Merle said something that surprised me.

“They divided infinitely many times, and it was over in two minutes.”

The first thing that caught my attention was Merle using the word “infinitely,” and, in fact, pronouncing it correctly. His English is not much better than his math, and I’ve already explain how bad that was. The second was saying that it was over in two minutes, which would be true for the situation he described. The difficulty of understanding this was illustrated by the confusion in the psychiatrist’s next question.

“If there were infinitely many divisions, wouldn’t that take an infinite amount of time?”

The answer to that is no. The reason for this is that each generation of termites only took half as long to produce as the preceding generation. This produces what mathematicians call a geometric series. Geometric series of the type Merle described are known to sum to finite quantities. In this particular case it’s not difficult to see. Take a piece of paper and draw a line segment on it. Mark the endpoints and the center point. Label one endpoint with a zero, the other with “2,” and the center point with a “1.” We will use this line segment to keep a running total of the time it takes for all of the generations of termites to reproduce.

The first generation reproduced in one minute, and we can denote that one minute by the “1” in the center. The next generation reproduces in a half a minute. Adding this half minute to the half minute already noted splits the difference between 1 and 2 taking us to three quarters. The next generation takes one quarter of a minute which splits the difference again, and so on. At the end of each generation the total time expired splits the difference between the previous total and 2. Consequently, after infinitely many generations only two minutes would have expired.

There were details about this that bothered me one of which was the following. If the termites divided exactly in two at each stage, then, after an infinite number of divisions, they would have been of zero volume. However, for the sake of argument, I decided perhaps the termites might only be intrusions into our space of creatures that existed in higher dimensions.

Tiny toothpicks

Before I could explore this thought, the psychiatrist asked a very intelligent question.
“Reproduction requires energy,” he began. “Typically creatures which divide by binary fission spend time between each generation taking in energy so they can reproduce. How did the creatures you describe do this?”

It was then that Merle told about the “toothpicks.” The aliens who had abducted Merle laid out toothpicks—or some edible substance that looked like toothpicks—for the termites to eat. That’s why I’ve take to calling them termites.

The termites consumed the toothpicks in the following strange way. The first termite was at the center of the toothpick and consumed the middle one-third in a very precise fashion. This left two pieces. Each of the daughter termites then consumed the middle third of those two pieces making for a total of four pieces of the original toothpick. After the next generation, there were eight pieces and so forth.

“So,” the psychiatrist asked, “was the toothpick entirely consumed after the two minutes?”

It was Merle’s answer to this that convinced me something strange had happened.

He laughed.

“Did I say something funny?” I psychiatrist asked.

“All of it was gone, but there was an infinite amount left,” was all Merle said. The psychiatrist didn’t understand, but I did.

The process that Merle described was very similar to the construction of what mathematicians call the Cantor set. The construction of the Cantor set begins with a line segment. At each stage the middle third of each remaining segment is removed leaving twice as many segments that are one-third as long as the segments in the previous stage of the construction. The net affect is the total length of the remaining segments is two-thirds of the previous total length.

When one takes two-thirds of the previous length at each stage of an infinite process, the amount remaining will tend to zero. However, at no stage are the endpoints of any interval removed, so even after all of the length of the interval is removed, there are an infinite number of points remaining. Indeed, the Cantor set is said by mathematicians to be uncountable which is more intensely infinite than the set of natural numbers.

Return to earth

At that point in the interview, Merle told how the aliens communicated with him telepathically. Having read his mind, and sensing certain deficiencies in him as a sapient being, they implanted the termites into his brain in order that they might improve his character. Then they let him go.
Since his return, he has exhibited a remarkable change in character, so I am convinced his strange tale must be true. Certainly his is not the Merle I remember.

Saturday, November 1, 2008

A redneck math test

Here is another funny.

A new way to do arithmetic

I found this out on the net. It could change your life.

Thursday, October 30, 2008

The Tars of Ole Roy

The other day I ran back home in order to visit my family, and, while I was there, I made arrangements to visit my old friend Bubba. Bubba has acquired a lot of land due to the fact he comes from a large family and has managed to outlive a lot of them. He told me he wanted me to meet him at a particular spot and gave me directions to find him. One catch was that last leg of the journey required that I walk a mile or two.

I drove back into the boonies quite a ways following his directions as best as I could. There was one point where I could have chosen to go this way or that and I went that. Then I got to a place where I thought I was to begin walking and walked way more than two miles. I was remote enough that my cell phone wouldn’t work, of course, and I was about to retrace my steps when I saw what appeared to be an abandoned old church.

Drawing closer to it out of curiosity, I saw that I was mistaken, not about it being an old church, but about it being abandoned. On the front of it there was a sign that read, “The First Church of the Prophet Roy,” and off to the side there was a man who was staring inexplicably at a stack of old tires while scratching his head as if involved in some sort of a huge mental calculation.

“Hello,” I said from a distance so as not to startle him.

“Howdy,” he said in reply, continuing to stare at the stack of tire and scratch his head.

“That’s quite a stack of tires there,” I said as a way of trying to engage him in conversation.

It was indeed an interesting stack of tires. There were at least a dozen tires in the stack. They were stacked in a conical pile with each tire smaller than the one beneath it. The bottom one was a tractor tire, the top one was a tire from a wheel barrow, and each was mounted on a wheel. They were stacked with a fence post as their central axis that kept them from sliding to one side or the other.

“Yup,” he answered. “Quite a stack o’ tars.”

That not being terribly informative, I thought I’d try a direct question.

“What are you staring at them for?”

“I’m trying to figure out how to move them,” he said.

There were only about a dozen, so I thought I’d do my good deed for the day.

“I’ll help you,” I said and begin removing the smallest tire from the top of the pile, but, much to my surprise, he stopped me.

“No, you cain’t just do that,” he said with his hand gently on my elbow. “They’s rules.”

It was then I noticed in his had a book with a black leather cover. I initially took it to be a Bible but closer inspection revealed a title emblazoned in gold on its cover: The Prophecies of Roy.

He pointed to a passage with contained directions. It was written in archaic English much like the language of the King James Bible. After a bit of deciphering, I discerned the rules. There were two other posts besides the one the tires were stacked around. I hadn’t even noticed them until then. The passage directed the reader to move the tires from their current post to one of the other posts—it didn’t matter which one. What did matter was they had to be moved one tire at a time and at no time could a larger tire be stacked upon a smaller one.

The rules were simple, but the problem was how to carry the process out systematically. After little figuring myself, I explained it to my new friend, Daryl, who I learned was a new follower of the Prophet Roy.

In order to explain it to Daryl, I named the three posts John, Jack, and Jick with John as the name of the post holding all the tires originally.

“Daryl,” I began, “the idea is to first move a stack of one, then move a stack of two, then move a stack of three, and so on until you are done.”

He nodded his head as if he understood.

“First move the top tire to the post I named Jack,” I said. “If there was only one tire you’d be done. Now move the second tire to Jick and then move the tire from Jack over to Jick. If there were only two tires, you’d be done. Now, it gets harder.”

He looked at me with kind of a sad look.

“...but not that hard,” I said, trying to soften it. “Take the third tire and put it on Jack. Now, take the smallest tire and put it over on John. Then move the second tire to Jick and cap it off with the smallest tire you that’s been back on John.

“Notice,” I said, “that all of the piles with an odd number of tires are over on Jick but when it’s an even number, it’s over on Jack.”

He nodded again. Encouraged by this, I decided to expand a little more.
“You see,” I said, “this is an example of what is called a recursive process. When I build a pile of size n on Jick, for example, I then pull the new big tire off of John on to Jack. Then I proceed to build a new pile of size n on top of the new tire so as to make a tower of height n+1.”

Daryl was beginning to look uncertain, but I was undeterred.

“You see each time I move all of the tires I did before, then introduce the bigger tire, and then move all of the tires again. The number of moves adds up quickly: 1 move for 1 tire, 3 moves for 2, 7 for three, and so on. This is because each time we double what came before and add one.”

I looked up at him and he had the look my cat gets when she watches me program the DVD.

Whether he understood the mathematics or not, Daryl understood the procedure, and he was following it when I left. It turns out he knows Bubba and he explained to me how to get to Bubba’s place in a much clearer fashion than Bubba had.

As I walked back to my car, I recalled the story about a similar problem call the Towers of Hanoi. According to this story, there are monks in a temple in Hanoi who are moving disks from peg to peg using the same rules as the Prophet Roy insisted upon, i.e. never put a larger disk on a smaller one. Legend says that the world will end when they are done. They began with 64 disks, however, and it will take them more than the life of the universe to finish.

When I finally found Bubba, I told him the story and gave him The Prophecies of Roy that had described the puzzle. I’d put it in my pocket and had forgotten about it.

“Yes,” he said, “Daryl is a member of the Church of the Prophet Roy. They believe they are going to make the world come to an end, but none of them ever understood how to work the puzzle before. How many moves will it take Daryl to be done?”

“With a dozen tires,” I said, “that would be 4095 moves. Assuming that he moves one tire a minute, it would take 68 hours or so.”

Bubba was now reading The Prophecies of Roy.

“Then, according to this,” he said indicating the book, “the world has about 68 more hours to exist.” He closed the book and said, “I think I’ll have a beer. Better yet, I think I’ll take a few over to Daryl it might slow down the work.”

And so we did.

Monday, October 27, 2008

Handedness

Sometimes seeing mathematical truth is as easy a seeing your hand in front of your face, but sometimes the language of mathematics can even make that hard. Mathematicians use their own language which is often off-putting and frequently disguises everyday truth. This has occurred in the case of handedness.

Mathematicians recognize a phenomenon, give it a name, and then we can study it. This is how we operate. If we give it a Greek name we can attempt to leave the impression that we know Greek and are more educated than is actually the case. The name we give handedness is chirality. If we called it handedness, which is what it is, you might not think it was very important, but we are hoping to hook into your native pomposity by using the Greek word.

Are you hooked?

If not, then you don’t know what this sentence is saying. Or this one.
But I digress.

Chirality, that is to say handedness, is a mathematical phenomenon not a physical one, though it does manifest itself in physics because of the geometrical nature of the universe. But we needn’t get fancy, as this isn’t a truth that college professors alone own. I grew up hearing stories from the oilfield. A new, inexperienced member of the crew would be sent on an errand to bring back a left-handed monkey wrench. Hours of amusement would be gained as the neophyte went around asking for a left-handed money wrench.

As you’ve no doubt figured out (and if you haven’t let me tell you about a little bird called the snipe...) there is no such thing as a left-handed monkey wrench. Monkey wrenches work exactly the same way in either hand. They are not affected by handedness. The pompous way we denote this is to say they are achiral.

The reason the practical joke works is there are objects which are affected by handedness. A baseball glove would be a good example of this. You will not be able to get a catcher’s mitt which had been designed to go on the left hand to fit properly on the right. It simply will not happen. The geometry of the universe prevents it. (For latex surgical gloves, this is not an issue because latex is a lot more flexible than leather, so it doesn’t have to be fitted to a particular hand.)

You don’t have to actually worry about gloves to see this. Consider the following experiment. Put your hands out in front of you in the manner of traditional prayer. You will notice one is a reflection of the other. Now put one atop of other so as the middle fingers line up and the nails of each hand face you. Notice that the pinkie of one hand is aligned with the thumb of the other and vice versa. You cannot line arrange your hands so that thumbs align with thumbs and pinkies with pinkies. Not even if you try real hard, not even if you hack one off them off with a machete like they did in the “Blood Diamond” episode of Law and Order.

Chirality, handedness, is related to the mathematical concept of orientation. This is a technical mathematical term that does correspond to its usual English meaning. If I tell you that I am newly arrived in town and have yet to become oriented, you will discern that I am trying to figure out where the important places in the area are located so that I can get around more easily.

The root word in orientation is orient which originally meant east. When this becomes the verb “to orient,” I have to wonder whether it comes from the fact that at one time most European maps had the east at the top. (Jerusalem, the origin of the Christian religion was in the east.) They realized that by settling on particular direction, i.e. east, all of the other directions were determined. If you know east, you can find west pretty easily. If you know east, you can figure out north. If you know north, you can find south.

Orientation is a phenomenon that occurs in all dimensions. I would like to take a little time in order to discuss dimensions one, two, and three.

When I speak of dimension one, I am talking about a line, or objects that are line-like such as circles and curves. To illustrate dimension one, consider the plight of a man who has awoken in a tube underground, having been placed there by an evil genius. (Bwah-hah-hah.) On one end of the tube there is a beautiful woman with all of the assets that are traditionally considered the due of a hero-type, but, of course, on the other end is painful, embarrassing death, something too hideous for a gentle person like me to describe in detail, but rest assured it’s bad.

You might say, wait a minute, that’s a three-dimensional example because you’ve got a person in your example and people are three-dimensional. Well, you are correct, of course, but from the mathematical perspective it’s one dimensional because the map, which the hero has secreted in one of the orifices of his body, is a line. At one end of the line there is the hero’s reward (think Jessica Alba) and the other a picture (shudder) of the hideous form of death that awaits him there.

On that map, there is an arrow at the middle of the line segment that points from one end toward the other. The tunnel that our hero is in has also been marked with arrows inside at points spaced at regular intervals all aimed in the same direction. The arrows establish an orientation on the tunnel, and it is left to our hero to determine whether they match the orientation on his map. One might suggest that he say “Hey, baby, is that you Jessica?” at various points just to be sure.

Another example of orientation would be the use of Uptown and Downtown in New York City, being up the river and downtown down the river. It sort of makes sense, eh?
We have a lot more experience navigating two dimensions than one, and, in this case, there is more structure so it makes for a richer phenomenon.

We live on the surface of Planet Earth. In spite of the fact that we are three dimensional creatures, because of gravity, much of our navigation is done in two dimensions. Every map is based on a two-dimensional plane; every globe is based on a two-dimensional sphere. (In case you are confused about a globe being two-dimensional, I would suggest a trip to Wichita for you.)

In order to aid our comings and goings on Planet Earth, our forebears coordinatized it, and, in doing so, used a particular orientation. The coordinate system consists of latitude and longitude lines. In order to assign numbers to latitude and longitude, orientation was required.

From a practical aspect, the whole enterprise was helped by the fact that the earth is spinning on an axis. This gives us not only a direction that the sun comes up in each and every day, but poles where the axis of rotation meets the surface of the planet.

Though it sort of breaks the flow, I feel I need to make the point that those of us on planet earth have competing systems. I’m not talking about the metric system versus the British system—which the British no longer use by the way—but something more basic. In giving directions, one can either deal with cardinal directions, i.e. north, south, east, and west, or with relative directions, i.e. forward, backward, right, and left.

I’ve spent most of my life on the plains. Our here on the flat, we’ve a large number of section-line roads to coordinatize the world. As a consequence, we like our cardinal directions, thank you very much. Others, of a weaker, quiche-eating breed, are forced to deal with the matter in a power way, giving directions in terms of right and left, forward and backward.

To return to my original line of thought, everyone knows how to determine north from east, but I will describe it anyway. Face directly east and north is on your left hand. A subtle point here is that making this determination requires each of us to have our own personal orientation, i.e. you have to know right from left.

Another subtle point is that you don’t need hands to do this, a clock will do. (I know that a clock has hands but push on.) Though our beloved forebears did not realize it at the time I am sure, when they decided which direction clocks would turn they also gave us a device for determining orientation. As I understand it, this was taken from the direction shadows move on a sundial in the northern hemisphere. I don’t know whether the meaning of “clockwise” was set in this fashion or not, but I do know for a fact that’s how shadows from the sun move in the northern hemisphere. If you don’t believe me, go outside and watch the shadow of the flagpole move. If you are working in a government office, a flagpole is easy to find. In fact, I think this is what government employees do most of the time; there might even be a job which is described that way.

If determining an orientation seems too easy, we shouldn’t take it for granted. There are certain surfaces where, by taking the wrong path (or the right path depending upon you intentions), you could make a clock go counter-clockwise. One such surface is the Mobius strip. I am required by the Ancient and Hollowed Guild of Mathematicians to mention it as a price of them not assassinating me for circulating this article.

Having talked about clocks allows us to move to orienting three dimensions. In three dimensions, we have not only left and right and forward and backward, we also have up and down. Adding up and down doesn’t seem like much of a challenge to us because we’ve an old enemy, gravity, to make the determination. (Those of you who are over forty know why I classify gravity as an enemy.)

But if you ever escape the confines of Planet Earth—perhaps only in your imagination—gravity is not necessarily there to help us. However, you can use a clock to help. Take your left hand and allow the palm to close in the direction that the hands on the clock are moving; this would be the natural way. Your thumb is pointing up.
I now have brought hands back into the picture. Think now about your right hand. If you point your fingers out in front of you and close them across your palm, the thumb on that hand is pointing upward as well. This is called the right hand rule. You can use it to take the lids off of mayonnaise jars and to unscrew screws.
It is a very handy thing to know.

Remainder Tires

Sunday, October 26, 2008

Counting dots

In a small town like where I live, you get to know everyone. One of the people I’ve gotten to know is the local homicide detective Suzanna Doughcoup. Sue, as she is universally known, is only a part-time homicide detective as there are so few homicides in these parts to detect. In order to pull her weight, she spends a lot of her time finding lost dogs and running skateboarders away from the library steps.
I was headed into the library and met her just as she was doing the latter.

“You kids scram,” she told them, and then she turned to me. “Hello, do you have a minute?”

“Hello, Sue,” I replied, “is there something I can do for you?” I am always eager to help our local law enforcement folks as I never know when I might need a parking ticket fixed.

“I’ve got a potential homicide with no body and no budget to do much investigation.”
This is a sleepy little town, so hearing that got my complete attention as she explained the situation. It seems that a huge red stain was discovered on morning on the tiles in front of city hall. The stain was blood red which caused much alarm among the municipal workers as they came to their jobs that morning.

Since it was in front of city hall, the police arrived on the scene quickly and taped off the putative pool of blood with police tape. Officer Harley Jones was in charge of this part of the operation, and he is very fastidious. He carefully applied the tape so as to go from corner to corner on the tile. The shape of the stain was so regular that it fit within those straight lines almost exactly, as shown below.



When Harley arrived, the stain was still wet enough that he could measure its depth to be about one-eighth of an inch.

“I know you teach math at the university,” she said. “Is there anyway you could measure the volume of this to give us an idea of how much blood this would be?”

I said I would try. I went back to my office to work it out.

In general, calculating the volume of a liquid spilled uniformly over an area is not difficult. All one has to do is multiply the area of the spilled liquid by its height. When the area is irregular, however, that adds difficulty to the problem. In this case, since the liquid was spilled over a tiled area, it would be easy to get a lower bound for the estimate by counting the number of tiles in the stain and multiplying by the area of a single tile. This was made even simpler by the fact each of the tiles was exactly one foot by one foot.

As an initial estimate, I counted the tiles that were completely covered by the stain and found there to be 19 of them. However, in the act of counting, I notice that a large number of the tiles stained with blood were only partially stained, my under-estimate might be serious. I began to wonder whether the fact the stain had such straight sides might make the area easier to estimate when I remembered Pick’s Theorem.

Pick’s Theorem is due to German mathematician Georg Pick and has to do with calculating the area of polygons in the Cartesian plane whose corners have integer coordinates. The formula is simple. The area of the polygon can be calculated as follows. Count the number of points with integer coordinates that fall completely inside the polygon, add to this half the number that call exactly on the boundary, and then subtract one. This can be represented as

A=I+(1/2) B-1,

where A is area, I is the number of points with integer coordinates inside, and B is the number of points with integer coordinates on the boundary.

Having remembered this, I counted the number of corner points of the tiles that were completely inside the stain and found there to be 29. I counted the points that were on the police tape and there were 9. Applying Pick’s Theorem to this gave me a total area of 32.5 feet. A depth of one-eighth of an inch made the volume of the unknown liquid work out to be 0.34 of a cubic foot or 588 cubic inches. There are 231 cubic inches in a gallon, so this works out to be two-and-a-half gallons.

Since the human body has about a gallon and a half of blood, on the average, this was alarming. I phoned Sue right away and informed her of my findings.
“It might be a double homicide,” I said.

“I don’t think so,” Sue said. “I took closer look at the so-called blood. It turns out Harley got a little too excited. At that time of the morning, red paint passes for blood. The guys at the Sigma Alpha Pi Frat house got a little inebriated and tried to paint their Greek letters in front of city hall. They used up all their paint on the Sigma, but got it a little blotchy in the process.”
I looked and the red blotch and squinted.

“I suppose that accounts for the straight sides,” I said.

“I suppose so,” Sue replied. She sounded a little disappointed. “I went down to the Frat house and found two empty paint cans and a half empty one. Your estimate pretty well nails down their convictions. Somebody’s dad is going to have to lay out some cash for this one.”

“Good detective work,” I said.

“They can’t all be murders, I suppose,” she replied.

“Better luck next time.”

Dividing the spoils

A while back I was making my way through the “hills and hollers” of one of the nearby states on my way to a meeting of mathematics teachers. It is a beautiful state full of friendly people and great scenic beauty, but I will keep its identity a secret for reasons that will become clear in the sequel.

I’d gone to this particular annual meeting a number of times, but this time in order to break the routine I’d decided to take a new route, the road less traveled as it were. As so often happens when you take the road less traveled, at some point I became lost. I don’t know how. I might have been adjusting my radio and missed a turn off or, more likely, I might have just had my mind on something besides driving. This is one of the hazards of being a mathematician.

Regardless, the road I was on gradually deteriorated from paved to gravel and from gravel to dirt. I thought about turning around, but, by the time that notion made its way into my head amongst the theorems I’d been thinking about, the road was too narrow for me to do this.

Eventually, I came to a house and pulled onto its lawn. I put it this way because it had no formal driveway just a lawn with various types of broken-down pieces of equipment scattered across it. The house itself was unpainted and ramshackle, but there was a friendly looking, elderly man on the front porch, with and old hound dog by his side and another at his feet. Instead of just turning around, I decided to stop and ask him directions, thinking maybe there was a way to where I was going that didn’t require a lot of backtracking.

I had gotten out of my car and was walking up to the porch in order to ask directions when an ancient pickup truck pulled into the yard behind me effectively blocking me in.

There were three men in the pickup each of whom looked scarier than the others. They were dressed in overalls without shirts underneath and wore worn out cowboy hats. I swallowed hard when I saw them and became acutely aware there was no means of escape. Having seen the movie Deliverance, I had no desire to live it. I fought to keep the sound of banjo music out of my head.

However, my worries were groundless. Except for a sideward glance from the driver as he approached the porch to talk to the old man, they ignored my presence entirely.

“There was a dog food truck wreck up by the interstate,” the driver said. “We managed to get five hundred-pound sacks off before the highway patrol arrived.”
He went on to explain how, because of certain familial obligations, the dog food had to be divided among a total of seven brothers in the family.

“We got a bunch of sacks,” he said to the old man, “and we come to you because we know you can divide it up amongst us fair.”

The old man was about to speak, but my desire to be helpful came out as I saw an opportunity to put my mathematics to work, and I spoke.

“I am a math teacher,” I said. “What you need to do is this. With five bags to be divided among seven brothers, each brother should get a five-seventh share. Take two-sevenths of out of the top of each bag. This will leave five-sevenths in five bags. Give those bags to five of the brothers and divide the portion taken out between the other two.”

It was at this point, the old man who’d been silent so far began to speak. His voice was kindly and ancient.

“Well,” he said, “I can tell you know your cipherin’ but there are some problems with that. Let me show you one of them.”

He reached into one of the chest pockets of his overalls and removed two new plugs of chewing tobacco.

“Come over here boys,” he said to the other two. “I am going to divide this tobacco amongst you three.”

He proceeded to carefully cut the bottom third from each of the tobacco plugs. He gave two-thirds of a plug to each of the pickup’s passengers and gave the two remaining one-third size pieces to the driver.

“Hey,” said the driver, not seeming happy at all, “you gave them bigger pieces.” He began to snarl and turned toward the other two.

“You gave him more pieces,” said one of the others as he turned to face his brother.

“All right,” said the old man as he spat from his own chaw. “Give me back the t‘backy.”

They did as he said, and he cut the big pieces in half so that everyone had a pair of one-third size pieces.

I saw his problem immediately, and it wasn’t mathematical. It was political. The men with whom he was dealing hadn’t had the arithmetical experience to recognize that quantities that looked different could be the same. On the other hand, they had a highly developed sense of justice, especially when they perceived they were not being treated fairly.

I decided to keep my mouth shut and let them proceed. What I saw was fascinating.
He rocked back and forth in his rocking chair with his eyes closed. His lips were moving and by leaning close I could make out what he said.

“Five among seven. That will be a part of two, a part of seven, and a part of fourteen.”

I wasn’t quite sure what he said, but apparently the men from the pickup did. They went to the back of their pickup and cleared the sacks of dog food and other debris from the bed. They then began dividing the dog food. They divided the contents of four of the five sacks in half and put seven of the eight resulting halves into separate sacks. The eighth half they divided into seven equal piles and put each of those into a separate sack. The remaining hundred-pound sack of dog food was divided into seven equal piles and each of those piles was transferred into a bag.

There were then seven sets of three bags, one containing half a bag, one containing one-seventh of a bag, and one containing a fourteenth of a bag. Everyone would have the same number of bags and each of the brothers would have one bag of a particular size.

They thanked the old man and left, but before they did, I got directions from them to where I was going.

Since I didn’t want to get lost again, I waited until I got to my destination to think about how the old man solved the problem.

He’d used Egyptian Fractions, which are also known as unit fractions because if they are written in standard notation there is a one in the numerator.
Having the advantage of modern measuring devices, we could approach the problem of dividing up that dog food by noting there were five-hundred pounds of dog food altogether and giving each brother one-seventh. This could be done by weighing out approximately 71.4 pounds.

The ancient Egyptians didn’t have the advantage of this technology and had to solve the problem in a different way. One example this can be found is in the Rhind Papyrus which dates from about 3500 years ago.

In modern notation, the old man had used the fact that . Writing it this way is misleading, because it presumes a modern way of thinking. The Egyptians weren’t thinking about writing a fraction as a sum of unit fractions; they were thinking about dividing up quantities equally. While their problems and methods of solving them eventually lead into algebra and the modern way, they were living in a different milieu.

It is interesting to note there may be several ways to resolve a modern fraction into an Egyptian fraction. For instance we can also write . However, the other way is better than this in the sense of having fewer terms and smaller denominators. Having fewer terms and smaller denominators would result in an easier division of the quantities as described in the story. The author of the Rhind Mathematical Papyrus usually had the best way to do it.

No one knows how he did it.



Uncountable candy

Uncountable candy


The ladies of the United Methodist Women are a formidable lot anywhere in the world you encounter them, but in one particular small Kansas town—which I will refer to as Kimberly in order to preserve its anonymity—this is doubly true.

The Kimberly United Methodist Women engage in good works, but they don’t brook a lot of nonsense. They are led by a lady named Wilma B. Even, who is the most formidable member of this formidable group.

Recently they engaged in a project wherein they gave candy to children. The candy they distributed came in a variety of colors. This candy was to be distributed into sacks that were of the same range of colors as the candy.

Wilma is nothing if not—well—methodical. She established the rule that no sack of candy would contain two pieces of the same color. The contents of the sacks didn’t have to be identical, however. Indeed, no two sacks were to be the same. It was her logic that the kids are different, so the bags should be different, but the rule that no sack contain two pieces of the same color was to be adhered to strictly.

The day came the group was to fill the sacks prior to distribution. As so frequently happens when busy people are involved in a project, the members of the group were called one by one to other commitments. This happens particularly often when Wilma enforces her rules strictly, as she did on this occasion. At the end of the evening only Wilma was left.

I know what happened next because I am friend of Wilma’s. She phoned me at one point late that evening after her help had left with a desperate tone in her voice. I will summarize our conversation.

Wilma likes patterns and order. When everyone else left and there was not one remaining to rein her in, she decided she would indulge in a bit of whimsy and fill the sacks with all possible different combinations of colors without using any color for a sack twice. As I said, this began as a bit of whimsy, but it quickly became frustrating. Wilma is not the sort of person to give up simply because she is frustrated. Indeed, she believes persistence to be her chief virtue, so she continued with the task several hours before giving me a call.

It was quite late when she finally did, and I could tell it didn’t come easily. However, we are friends, she knew I was a mathematician, and she was desperate for an answer. She explained her problem to me.

“How do you do it?” her voice was frantic yet hard, and I didn’t like saying what I had to.

“Wilma, it is 3 o’clock in the morning,” I croaked as I blearily looked at the alarm clock behind by bed. “Could I work it out tomorrow and tell you about it later?”

She apologized—not having realized how late it was—and agreed that we could talk after I worked it out. At that time, what I didn’t realize was what some of you have probably already noticed. It couldn’t be worked out.

There are at least two different ways of seeing this. One of them requires formulas and numbers and the other doesn’t. Since most people don’t like formulas—and Wilma is no exception to this—I tried explaining it to her using the other one.

Suppose that she had succeeded in distributing candy into the sacks by the rules she had set for herself. For some colors there might have been sacks where a piece of the candy matched a color of the sack, but others might not have matched. Think of the colors where the sack of that color didn’t match any of the candy it contained as being “bad” colors.

Now bring together all of the pieces of candy that have a bad color and put them in a sack. By assumption, the task of distributing the candy according to her rules has been accomplished, so there must be a sack among the ones she has created matching this one both in contents and color.

This sack is a particular color. For the sake of argument, suppose the sack is red. Let us now ask a question. Does this sack contain a piece of red candy? This is easy to check, and it either does or it doesn’t.

Suppose that it does contain red candy. Then since the color of the candy and the color of the sack are the same, the color red isn’t a bad color, so the candy couldn’t have been in the sack to begin with. This situation can’t occur.

On the other hand, suppose that the sack contains no red candy. Then red is a bad color. Since the sack is supposed to contain all of the bad colors, it must contain the red candy. This situation can’t occur either.

Even though there are only two possibilities, neither of them can happen. As a consequence, we are forced to conclude that Wilma cannot do what she is trying to do.
I explained this to Wilma exactly the way I did above, and she was confused.
“Huh?”

I started explaining the same way, and she stopped me again.

“I was listening the first time,” she said. “Is there another way you can say it?”

“Okay,” I said as I took a deep breath. “There are more ways that you can choose colored candies than there are colors.”

“Why didn’t you just say that in the first place?” she asked. I could tell she was a bit miffed.

“Well the particular argument I gave you is from set theory and it extends to sets infinite sets,” I said. And I then began to explain it to her. About half way through my explanation, she remembered she had volunteered to give sponge baths at her local nursing home and had to leave, so I will share it with you.

By the very nature of infinite sets, we cannot assign a number as being the set’s size. If we could, the set would be finite, right? However, we can say that two infinite sets have the same size if they can be put into one-to-one correspondence with each other. I argued above that the ways of choosing colored candy can’t be put into one-to-one correspondence with the colors. Similarly, the ways of forming subsets of a set cannot be put into a one-to-one correspondence with elements of the set, even if that set is infinite.

For example, the set of counting numbers 1,2,3, etc is infinite and the sets of subsets of the counting numbers is infinite, but the set of subsets of the counting numbers is larger. It is infinitely big, but bigger than infinity of the natural numbers. This sort of thing was first discovered by Georg Cantor at the turn of the last century.