ThatsMaths

Alice and Bob, are enjoying a drink together. Sitting in a bar-room, they take turns placing beer mats on the table. The only rules of the game are that the mats must not overlap or overhang the edge of the table. The winner is the player who puts down the final mat. Is there a winning strategy for Alice or for Bob?

Image from Flickr. 

We start with the simple case of a circular table and circular mats. In this case, there is a winning strategy for the first player. Before reading on, can you see what it is?

* * *

Circular Table

The solution depends crucially on the symmetry of the problem. The circular table has symmetry about the centre. In fact, it has an infinity of symmetry transformations, but we need consider only one: reflection about the centre, or rotation through 180 degrees (these transformations are equivalent).

Alice, who goes first, can preserve the symmetry by placing a beer mat at the centre. Wherever Bob puts his mat, he must destroy the symmetry. However, Alice can restore it by placing a mat diametrically opposite the point chosen by Bob. This is a winning strategy for Alice. She always has a spot available to place a mat whereas, sooner or later, Bob runs out of space.

We see the strategy in the figure below. The mats are numbered in order of placement. The yellow mat is placed first by Alice. Bob’s mats are blue and Alice’s responses are shown in white.

It is clear that the winning strategy holds also for any table with symmetry under a rotation of 180 degrees. Thus, it is valid for square, rectangular and elliptic tables, as well as for tables of numerous other shapes.

Polygonal Tables

Now let us consider a triangular table. For simplicity, we assume an equilateral triangle, with an unambiguous centre. Obviously, it has symmetries for rotations through 120 and 240 degrees, but not for 180 degrees. Let us assume the table is just big enough to hold four mats (if the side of the table is of unit length, the radius of a mat must be 1/4√3). If Alice places a mat at the centre, she leaves three slots, one at each corner, so Bob can place the final mat and win (see figure, left panel).

Alice is smarter, so she places the first mat slightly above the centre (see figure, right panel). This cuts off one of the slots, leaving only two places where Bob can put his mat, so that the other is free for Alice to win.

A similar argument applies for a pentagonal table. If there is initially room for at most 6 mats, then if Alice chooses the centre, she leaves 5 isolated slots free and will lose. By judicious off-centering of her mat slightly towards a vertex, she can cut off three slots, leaving two, and winning.

What about a polygonal table with an odd number (2N + 1) of sides? If there is room for at most 2N + 2 mats, then if Alice chooses the centre, she leaves 2N + 1 isolated slots free and will lose. Can she ensure a win by judicious off-centering of her mat slightly towards a vertex?

Convexity and Symmetry

So far, we have chosen only convex shapes. In the figure below we have three non-convex tables with reflexive angles. The L-shaped table on the left has a reflective symmetry about the central diagonal. The T-shaped one in the centre is symmetric under reflection in the central vertical. The table on the right has no apparent symmetry. However, in all three cases, there is a winning strategy for Alice, shown by the white beer mat. The idea is to place the mat so as to leave two isolated regions, each with space for only one more mat. This ensures victory for Alice.

Victory for Bob

However, things are not completely hopeless for Bob. If he chooses a table smartly, he can win. The table below is guaranteed to give Bob a win if he “plays his mats right”.

It turns out that, no matter where Alice places her Number 1 mat, Bob can choose a spot that leaves two isolated regions, each with room for only one mat (making four mats in total) so that he places the final mat and triumphs. Two examples of Alice’s first move and Bob’s response are shown below. It is easy to show that Bob can always win by leaving two slots.

Generalizations

The Beer Mat Game can be developed in numerous directions. There is an infinite variety of table shapes and mat shapes and sizes. In the most general case, all that is assumed is that the table is homeomorphic to a disk, and likewise the mats. Clearly, there can be no winning strategy with such generality. It would be interesting to investigate the category of shapes for which a win is guaranteed for either Alice or Bob.

Good luck with your research into winning strategies for other shapes and sizes, and have fun playing the game.

* * *

This post leaves many questions unanswered. Comments and correspondence on the beer mat game are welcome by email to thatsmaths@gmail.com. Please specify Subject: Beer Mat Game.