Reflecting on Convexity

Last Friday, I was told of a puzzle by my colleague that was given to him on an interview. The puzzle goes like this: You and an opponent sit opposite a round table. You are to place coins (of the same size) on the table, one at a time. No coin should sit on top of another coin, even partially. No part of any coin should go beyond the table’s boundaries. You take turns putting coins on the table until you can no longer find any space to fit a coin. The last person to put a coin wins. If you had the first turn, what would be your strategy? This is a puzzle i’m not be able to answer on an interview and over 2 bottles of beer. So I told my colleague i’ll work on it on the weekend.

My first impulse was to treat this as a packing of circles inside a bigger circle. To start, let us have the circle small enough to fit only a 1 layer of circles along the circumference of the middle circle, as shown below.

In this configuration, the circles in dark blue are mine while the lighter ones are of the opponents. In this game, I win because I was the last one to put the coin. However, since my opponent is also rational, he will not allow me to win. He will put his lighter colored coin in a position shown below. This game started with me putting my coin in the middle. He then put his coin on top of the middle coin. Next I put my coin next to his coin, touching each other. But my opponent now puts his second coin in such a way that it has a space between my 2nd coin and his 2nd coin for which no coin can fit. Then I put my 3rd coin next to his 2nd coin. When he put his third coin, there was no more space for me to insert another coin. So I lost.

There must be a way for me to influence his next move. Looking at the geometry of circles, there must be something that can be made use of the circular symmetry. For one thing, all points on a circle have the same distance from the center. Another thing is if you pass a line through the center it will intersect the circle in 2 points. These points are antipodes of each other. This gives a very good way to control the outcome of the game. We let our opponent select a spot to put the coin, then we get the antipod of that location and put our coin there. We do this until no more coins can be put on the table.

Let us walkthrough the sequence of steps as shown above. After I put my coin in the middle, my opponent puts his coin above it. Then what I do is to put my 2nd coin on the opposite side (antipode). My opponent then employs his usual strategy which is to put his next coin so that it will have a small space in between. However, i put my 3rd coin opposite his 2nd coin. When he puts his 3rd coin, he will realize that there is no more space for him to squeeze it in, as shown by the red coin which already goes beyond the bounder of the table. So I win!

The good news is that this is not a coincidence. We will always be the last person to put a coin on the table. To see this, assume the contrary: our opponent was able to put a coin C_o on the table but for which the antipode has no more space to accommodate the coin. This means that if we put our coin, it will intersect at least one coin C\prime. Let p\prime be a point inside this intersection. By the way this was constructed, there is another coin C which contains the antipode p of point p\prime. This means that p \in C_o \cap C, that is, C_o intersects C, which is a contradiction.

Convex Regions and Point Reflections

Will this work only with circular tables? Will it work also with rectangular tables? Will it work only with coins? Will any other shape also work? Consider a table of some arbitrary shape but with the property that for any two points p and q on this table, we can draw a line connecting them in such a way that the line is contained with in the table. We call this region a convex region. The property of a convex region is that the centroid of this region is contained within it. Shown below is an example of a convex region and a non-convex region.

A table shaped like a horseshoe is not convex and its centroid is outside of the table.

Suppose we have found the centroid of our convex region. Instead of using a coin, let’s use a star to put into the table. If our opponent puts his star anywhere on the table at a position r_1 from the centroid, then the antipode of this position must also be inside the region, by virtue of its being convex. Let us put our star in such a way that it is the reflection through the centroid of our opponent’s star. If we set up a coordinate system on the table centered at the centroid (surprise!), then point reflection through the origin transforms in the following manner:

\displaystyle (x_1,y_1) \mapsto (-x_1, -y_1)

Since this mapping is isometric, i.e, preserves distances, any two points p_1 and p_2 will retain the same distance after reflection. This means that if two stars don’t intersect, they will not suddenly intersect under this mapping.

The figure below shows a star S_1 defined by the following coordinates.

           x         y
1  0.8754257 0.4100271
2  0.8292804 0.4380167
3  0.8248856 0.4700049
4  0.7941220 0.4360175
5  0.7501740 0.4400160
6  0.7809376 0.3980315
7  0.7567662 0.3620448
8  0.8029116 0.3680426
9  0.8226882 0.3380536
10 0.8358726 0.3780389
11 0.8732283 0.4080278

This star is the one shown in blue in the first quadrant. Another star S_2 was defined by translating S_1 by 0.1 in both directions. This is the star shown in red in the first quadrant.

Applying the point reflection through the origin, we get the two stars shown in the third quadrant. The blue colored star is the reflection of the blue colored star in the first quadrant. The same thing applies to the red star. What we have just shown is that you can modify the problem to tables like squares or polygons by virtue of being convex regions. Also, by the isometry of the point reflection through the origin, we can use other shapes and not just circles.


Published by

Bobby Corpus

Loves to Compute!

Leave a Reply

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

You are commenting using your 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