In most two-person games, players take turns, proceeding from turn to turn in an orderly manner. If, instead of alternating turns, the players use a coin toss to decide who makes each move, a deterministic pastime becomes a random-turn game.
Interestingly, random-turn games can be easier to analyze than their deterministic counterparts, Yuval Peres, Oded Schramm, Scott Sheffield, and David B. Wilson report in the May American Mathematical Monthly. Such games also "exhibit surprising structure and symmetry," the researchers say.
The game of Hex, for example, is played on a diamond-shaped board made up of hexagons. Each player has pieces (or stones) of a particular color. The two players alternately place stones of their respective colors on unoccupied hexagons. A player wins by completing an unbroken chain of stones, creating a path that connects the two opposite sides of his or her color.
The game can't end in a tie. One player can block the other only by completing his or her own chain. It's possible to prove that there exists a winning strategy for the first player on a board of any size, but there is no known optimal strategy for the standard 11 by 11 board (or for larger boards).
In random-turn Hex, the players toss a coin to decide who places the next stone. Peres and his colleagues show that the probability that the first player wins when both players play optimally is the same as the probability that the first player wins when both players play randomly.
So, winning the game is akin to creating a path that crosses from one side of the board to the other after filling in empty hexagons at random—a process known as independent Bernoulli percolation.
"In this and other games, the set of moves played during an entire game (when both players play optimally) has an intriguing fractal structure," Peres and his colleagues observe.
The researchers also prove that, in a random-turn selection game such as Hex, any optimal strategy for one of the players is also an optimal strategy for the other player.
It turns out that the best first move in random-turn Hex is the site that is most likely to be crucial for a percolation crossing. For the standard board, the best first move is near the center.
The authors note that "random-turn games are natural models for real-world conflicts, where opposing agents (political parties, lobbyists, businesses, militaries, etc.) do not alternate turns. Instead, they continually seek to improve their positions incrementally."
References:
Browne, C. 2000. Hex Strategy: Making the Right Connections. A K Peters.
Gardner, M. 1959. The game of Hex. In Hexaflexagons and Other Mathematical Diversions: The First Scientific American Book of Mathematical Puzzles and Games. University of Chicago Press.
Peres, Y., O. Schramm, S. Sheffield, and D.B. Wilson. 2007. Random-turn hex and other selection games. American Mathematical Monthly 114(May):373-387.
May 29, 2007
May 10, 2007
Closet Doors
As anyone who lives in a tiny apartment or cluttered room has experienced, opening or closing a closet door requires a certain amount of floor space.
Suppose, for example, that a closet has a standard door, which can swing open so that it's at right angles to the closet interior. As it opens (or closes), the door covers a quarter of a circle, which represents the area that must be kept clear of obstacles. If the closet (or door) has width r, the door requires πr2/4 square feet of floor space.
To save floor space, some closets have so-called bifold doors. In this case, the door has hinges at one side and in the middle so that it folds as it opens. The unhinged side typically runs along a track that keeps it aligned with the closet opening. Note that "bifold" is a misnomer. There is only one fold (but two panels).
When Derek Seiple was a high school student, he wondered how much floor space is needed to accommodate the opening and closing of a bifold door. How big is the saving over a standard door? When he got to college (Penn State University at DuBois), Seiple was encouraged to investigate the problem, and the results appear in the April Mathematics Magazine.
"If you have a closet (or any doorway) covered with a bifold door there is an astroid lurking just inside and the only way you can get to it is to coax it carefully with a little bit of calculus," Seiple and his coauthors note. "If your door has more than one fold there are even more interesting objects waiting to be discovered."
Seiple's analysis shows that a bifold door traces out a path that consists of two curves. Given that each panel has a width r/2, a closing bifold door first sweeps out a circular arc of radius r/2. At 45 degrees, however, its path changes. Whereas the first part of the path was convex, the second part is concave. It now traces out part of a type of curve known as an astroid.
In this case, the area swept out by the door is 5πr2/64. That's a saving of nearly 70 percent, compared with a standard door.
"It is clear that adding 2, 3, 4, or n folds will reduce the floor space required even further," Seiple says.
At the same time, "adding more hinges has no effect on the astroidal portion of the curve," he adds. "The very same astroid appears regardless of the number of folds in the door as long as all of the panels are hinged so that they make the same angle with the front of the closet."
Interestingly, the entire path would be an astroid if you happened to have a "door" with no hinges. As one side of the door moved along a track across the closet opening, the other side would move along a track at right angles to the closet opening.
As the door closes (above), points A and B move toward points B and C respectively.
You'd see the same path traced by an initially vertical ladder that slips down and away from a wall.
References:
Seiple, D., E. Boman, and R. Brazier. 2007. Mom! There's an astroid in my closet! Mathematics Magazine 80(April):104-111.
Suppose, for example, that a closet has a standard door, which can swing open so that it's at right angles to the closet interior. As it opens (or closes), the door covers a quarter of a circle, which represents the area that must be kept clear of obstacles. If the closet (or door) has width r, the door requires πr2/4 square feet of floor space.
To save floor space, some closets have so-called bifold doors. In this case, the door has hinges at one side and in the middle so that it folds as it opens. The unhinged side typically runs along a track that keeps it aligned with the closet opening. Note that "bifold" is a misnomer. There is only one fold (but two panels).
When Derek Seiple was a high school student, he wondered how much floor space is needed to accommodate the opening and closing of a bifold door. How big is the saving over a standard door? When he got to college (Penn State University at DuBois), Seiple was encouraged to investigate the problem, and the results appear in the April Mathematics Magazine.
"If you have a closet (or any doorway) covered with a bifold door there is an astroid lurking just inside and the only way you can get to it is to coax it carefully with a little bit of calculus," Seiple and his coauthors note. "If your door has more than one fold there are even more interesting objects waiting to be discovered."
Seiple's analysis shows that a bifold door traces out a path that consists of two curves. Given that each panel has a width r/2, a closing bifold door first sweeps out a circular arc of radius r/2. At 45 degrees, however, its path changes. Whereas the first part of the path was convex, the second part is concave. It now traces out part of a type of curve known as an astroid.
In this case, the area swept out by the door is 5πr2/64. That's a saving of nearly 70 percent, compared with a standard door.
"It is clear that adding 2, 3, 4, or n folds will reduce the floor space required even further," Seiple says.
At the same time, "adding more hinges has no effect on the astroidal portion of the curve," he adds. "The very same astroid appears regardless of the number of folds in the door as long as all of the panels are hinged so that they make the same angle with the front of the closet."
Interestingly, the entire path would be an astroid if you happened to have a "door" with no hinges. As one side of the door moved along a track across the closet opening, the other side would move along a track at right angles to the closet opening.
As the door closes (above), points A and B move toward points B and C respectively.
You'd see the same path traced by an initially vertical ladder that slips down and away from a wall.
References:
Seiple, D., E. Boman, and R. Brazier. 2007. Mom! There's an astroid in my closet! Mathematics Magazine 80(April):104-111.
May 4, 2007
Integral Heptagons
It isn't hard to find three points such that the distance between each pair of points is an integer. Three points defining a right triangle with sides 3, 4, and 5 represent one such example. Triangles characterized by Pythagorean triples and many other triangles exhibit such integral relationships.
It's not so clear that there are sets of four points in which the distance between each pair is an integer, but there are. It's even less clear for five, six, seven, or more points.
The problem of finding sets of points with all mutual distances integers has intrigued many mathematicians, including Abram Besicovitch (1891–1970) and Paul Erdős (1913–1996). Erdős originally asked for five points in the plane, no three on a line, no four on a circle with the distance between each pair of points an integer.
When that problem was solved, six points became the target. There proved to be infinite families of such point sets.
Now, the seven-point case has been solved. Using an exhaustive computer search, Tobias Kreisel and Sascha Kurz of the University of Bayreuth found a integral heptagon, in which no three points lie on a line and no four points lie on a circle. In fact, they came up with two examples.
The following table gives the distances between the pairs of points in the smallest possible integral heptagon.
For a diagram of this heptagon, see Ed Pegg's current Math Games column.
In each case, you can also look the smallest possible diameter, d, where the diameter is the largest occurring distance in a point set. For four points, d = 8; for five points, d = 73, and for six points, d = 174. The new results show that, for seven points, d = 22,270.
The new target? Are there eight points in the plane, no three on a line, no four on a circle with pairwise integral distances?
References:
Brass, P., W. Moser, and J. Pach. 2005. Research Problems in Discrete Geometry. New York: Springer.
Guy, R.K. 1994. Unsolved Problems in Number Theory, 2nd. ed. New York: Springer.
Kreisel, T., and S. Kurz. Preprint. There are integral heptagons, no three points on a line, no four on a circle.
It's not so clear that there are sets of four points in which the distance between each pair is an integer, but there are. It's even less clear for five, six, seven, or more points.
The problem of finding sets of points with all mutual distances integers has intrigued many mathematicians, including Abram Besicovitch (1891–1970) and Paul Erdős (1913–1996). Erdős originally asked for five points in the plane, no three on a line, no four on a circle with the distance between each pair of points an integer.
When that problem was solved, six points became the target. There proved to be infinite families of such point sets.
Now, the seven-point case has been solved. Using an exhaustive computer search, Tobias Kreisel and Sascha Kurz of the University of Bayreuth found a integral heptagon, in which no three points lie on a line and no four points lie on a circle. In fact, they came up with two examples.
The following table gives the distances between the pairs of points in the smallest possible integral heptagon.
For a diagram of this heptagon, see Ed Pegg's current Math Games column.
In each case, you can also look the smallest possible diameter, d, where the diameter is the largest occurring distance in a point set. For four points, d = 8; for five points, d = 73, and for six points, d = 174. The new results show that, for seven points, d = 22,270.
The new target? Are there eight points in the plane, no three on a line, no four on a circle with pairwise integral distances?
References:
Brass, P., W. Moser, and J. Pach. 2005. Research Problems in Discrete Geometry. New York: Springer.
Guy, R.K. 1994. Unsolved Problems in Number Theory, 2nd. ed. New York: Springer.
Kreisel, T., and S. Kurz. Preprint. There are integral heptagons, no three points on a line, no four on a circle.
Subscribe to:
Posts (Atom)
