Sunday, October 26, 2008

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.

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.

No comments: