Problem of the Week 872

Random Tic-Tac-Toe

In early November the regional ACM Programming Competition will take place at Macalester College. Here is a problem that budding programmers can use for practice (though I believe it can be done by hand).

Alice: Let's play random tic-tac-toe. We'll each make our moves randomly. I'll go first, of course.

Bob: That's not much of an offer. You'd have a big advantage. But I'll play if you give me two-to-one odds.

Should Alice acccept?

NOTES: A random game is played with each player making a random choice among the legal moves at his or her turn. The question is whether p/q is larger than, equal to, or smaller than 2, where p (respectively q) is the probability that Alice (respectively Bob) wins. Tic-tac-toe is the standard game of X's and O's on a 3x3 board.

Source: The classic problem book: "The Surprise Attack in Mathematical Problems" by L A Graham (Dover).

Web Notes

There have been many movies on turning the sphere inside-out, but POW subscriber John Sullivan (Univ of Illinois) figured out a new physics-based way of doing it, and the method is now on video-tape. The idea is based on minimizing Willmore's elastic bending energy for surfaces. He is happy to send a copy to individuals who send him $15. Check out the web page or contact John.

Stanley Rabinowitz's problem indexing efforts are now on the web in searchable form. Thus about 20000 problems from various journals can be looked at efficiently.

© Copyright 1998 Stan Wagon. Reproduced with permission.

The Math Forum

10 November 1998