“In a problem, the great thing is the challenge….”

In childhood I was given a book on probability, a subject that fascinated me. It had a series of intriguing problems, with humorous illustrations scattered throughout, and detailed solutions at the end. I loved the book, opened it up many times, but did not get far in it. I remember poring over the first few problems and browsing through the others. Then, after a series of moves and life changes, the book got misplaced.

Years later, I remembered it and wanted to find it, but I couldn’t remember the title or author. I asked people, searched in bookstores, searched online, and racked my memory, all to no avail. Then one day I read an interview with a dear friend of the family, George Cobb, who died last spring and whom I had not seen in many years. He mentioned using Frederick Mosteller’s Fifty Challenging Problems in Probability with Solutions (1965) in a probability course that he taught. Something told me that this might be the book; I looked it up, and sure enough, it was. He must have given me a copy as a gift. I ordered a Dover paperback (the original book was hardcover); it arrived the other day.

I opened it up and read the preface, which I probably hadn’t read before, since in childhood I didn’t bother much with prefaces, preferring instead to get right into the matter. It brought back a dim and beloved world. Mosteller writes:

Much of what I have learned, as well as much of my intellectual enjoyment, has come through problem solving. Through the years, I’ve found it more and more difficult to tell when I was working and when playing, for it has so often turned out that what I have learned playing with problems has been useful in my serious work.

In a problem, the great thing is the challenge. A problem can be challenging for many reasons: because the subject matter is intriguing, because the answer defies unsophisticated intuition, because of its difficulty, because of a clever intuition, or even because of the simplicity or beauty of the answer.

I turned to the first problem, which I now remembered clearly.

1. The Sock Drawer

A drawer contains red socks and black socks. When two socks are drawn at random, the probability that both are red is 1/2. (a) How small can the number of socks in the drawer be? (b) How small if the number of black socks is even?

The first part I figured out just by experimenting in my mind. The total number of possibilities for choices of two socks would be (t)(t-1), where t is the total number of socks. I would need r(r-1), the total number of possibilities for choosing two red socks, to be 1/2(t)(t-1). If the total number of socks were 4, and the number of red socks 3, this would work out.

The second part is much trickier–and the solution in the book involves setting up an inequality, using it to express the relation of r to b, and then trying out increasing even values of b until one of them works.

Last night I started thinking of a different solution, which I would execute with Perl. My underlying principle was this: if I could have Perl generate two tables, one of which held particular values for the total number of socks (t, t-1, t(t-1), and t’s even/odd value) and the other for the total number of red socks, and if I could write a program that iterated through the tables until it found a match where t(t-1) was twice r(r-1), then I could narrow down the list to those where t and r had the same even/odd value, which would make b even (since b = t-r). I worked on that for quite a while but couldn’t get Perl to do the iterations that I had in mind.

Then, when biking to the supermarket for last-minute groceries for dinner, I had a different idea.

use POSIX;

for ($redtotal = 1; $redtotal <= 1000000; $redtotal++) {
$redsocks[$redtotal][0] = $redtotal;
$redsocks[$redtotal][1] = $redsocks[$redtotal][0] – 1;
$redsocks[$redtotal][2] = $redsocks[$redtotal][0] * $redsocks[$redtotal][1];
$redsocks[$redtotal][3] = 0;
if ($redsocks[$redtotal-1][3] == 0) {
$redsocks[$redtotal][3] = 1;
}
else {
$redsocks[$redtotal][3] = 0
}
$redsocks[$redtotal][4] = 2 * $redsocks[$redtotal][2];
$product = $redsocks[$redtotal][4];
$square = sqrt($product);
$roundup = ceil($square);
$rounddown = floor($square);
if ($roundup != $rounddown) {
if (($roundup * $rounddown) == ($product)) {
if ((($roundup % 2) + ($redtotal % 2)) != 1) {
print (“$roundup”, ” total socks, “, “$redtotal”, ” red socks\n”);
}
}
}
}

The POSIX call just brings in some extra functions. The whole program consists of a “for” loop that iterates through values of $redtotal, the total number of red socks. First it established the elements of the array @redsocks. Then it assigns a few more variables.

Basically, we are trying to find out whether, for any particular r, 2r(r-1) can be expressed as the product of two consecutive integers, t(t-1). To find this t and t-1, take the square root of $product, and, if it is not an even integer, identify the integers immediately above and below it ($roundup and $rounddown). Then test them out by multiplying them with each other. If they equal $product, then you have a match. In that case, add the even/odd values of $roundup and $redtotal. If the sum does not equal 1, then they are either both even or both odd, in which case b will be even. Those are the matches that will be printed out.

Now have the program print out all the matches as specified above. For the purposes of the problem, we only need the lowest value (15 red socks, 21 socks in total), but it’s fun to see what happens after that. Here are the results (where $redtotal goes up to one million):

21 total socks, 15 red socks
697 total socks, 493 red socks
23661 total socks, 16731 red socks
803761 total socks, 568345 red socks


You can test them out by multiplying each number of total socks by the number one less than that, doing the same for the red socks, and then verifying that your second result is one-half of your first one. Let’s do this for the highest number here.

803,761 x 803,760 = 646,030,941,360
568,345 x 568,344 = 323,015,470,680

323,015,470,680 x 2 = 646,030,941,360

So, you see, it works!

There are probably ways to make the script more elegant. Instead of nesting the ifs, I could have used a series of ands, but I couldn’t get that to work correctly. I haven’t used Perl in years, so I’m a little rusty with the syntax. I was proud to be able to get this working.

The book was written long before Perl and more sophisticated programming languages came into use, long before it became possible to program from home. But the problems do just what they did before. They incite you to think, play, tinker, and solve. And this book is not only rejoining my collection but opening up to me in a new way after all these years.

If you try out this code, be sure to change the minus sign (in line 5) to a plain hyphen and the quotes near the end to plain quotes.

Previous Post
Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s