Math Trivia: Triangular Billiards

Imagine you are playing billiards on a triangular table. The ball  travels in a straight line with no friction, and when it hits an edge, it reflects in the standard way. One might ask whether or not there exists a way to hit the ball so that it follows a closed periodic path. (i.e. the ball eventually returns to where it started moving in the same direction that it started.)

One way to achieve this is by drawing the three altitudes of the triangle. For each edge, draw a line perpendicular to that edge, passing through the third vertex not on that edge. Then, take the three points where the altitudes intersect the edges perpendicularly, and connect them up. You can check that this simple triangular path, bouncing off of each once, is a closed periodic path for the ball.

There is one problem. In order for the altitudes to intersect the edges, the triangle must be acute. What happens when the triangle is not acute? This is actually a 200 year old open problem!

It can be shown that a different method works for all right triangles. This paper gave a computer assisted, but still rigorous, proof in 2006 that there is a closed periodic path for all triangles where all of the angles are less than 100 degrees. However, if one of the angles is can be greater than 100 degrees, this question is shockingly still open!

Math Trivia: Auctions

Here are two common mechanisms for auctions:

1) Everyone privately bids, and whoever bids the highest wins and pays what they bid.

2) Everyone privately bids, and whoever bids the highest wins and pays the bid of whoever bids the second highest.

In the second mechanism, the optimal strategy for each bidder is to bid however much they actually value what they are bidding for. In the first mechanism, the optimal strategy is more complicated, and players should bid less than their true value.

Lets assume that there is a fixed number of bidders. The value each bidder assigns to the object being auctioned is generated independently at random from a fixed continuous probability distribution that everyone knows. If everyone follows an optimal strategy, then the amount that the object sells for will follow some probability distribution.

Not surprisingly, the distribution that the auction house sells the object for is dependent on which auction mechanism they use. and the two different mechanism actually do produce different distributions.

Which mechanism do you think will produce a better expected value for the auction house. In the first, people will bid less, but in the second, the highest bid is ignored. Amazingly, in spite of producing different distributions, these two auction mechanisms produce the same expected value for the auction house!

This is actually part of a more general revenue equivalence theorem, which shows that the auction house expects the same revenue for any of a large class of auction mechanisms. This class even includes the auction where all players have to pay whatever they bid, even though only only the highest bidder wins.

Math Trivia: Interlocked Cubes

Here is a math fact that may surprise you:

There exists a configuration in three dimensional space of a finite number of unit cubes such that no cube can be removed without moving the others. That is to say it is not possible to hold all but one of the cubes fixed in space and move the last cube arbitrarily far away from the others.

This should surprise you. Your intuition is probably saying “Why don’t you just take the highest cube and move it straight up?” That intuition would be correct if we were talking about spheres, but not with cubes. A cube that is on average below another cube can still be partially above that cube.

The configuration is actually not all that difficult to imagine. First notice that if you balance a cube on one of its corners and take a horizontal cross section right in the middle, that cross section is a regular hexagon. You can take a tiling of the infinite plane by hexagons, and extend that tiling to cubes. If we tile the xy plane with these hexagons, and extend it to cubes, all of those cubes will have the same z coordinate. Each cube will be touching 6 other cubes, and even though they have have the same height, 3 of those are positioned “above” the cube to stop it from going  up, while 3 of them will be positioned “below” the cube to stop it from going down. If this is hard for you to imagine, or you want to see a proof, you can see it in this paper. (Look at figure 6)

Now that you believe that you can tile a plane, instead tile a very large square with cubes, so that no cube can be moved up or down. Make all the cubes very slightly smaller, so that you have some freedom to bend this large square. Wrap it around to make a large cylinder, then wrap it around in the other direction to make a large torus. When you wrap it around, you will glue edges of the square to other edges of the square, by interlocking the cubes on the boundaries.

The final configuration is a large torus, which locally looks like a plane tiled by the hexagonal cross sections of the cubes, but with the cubes slightly shrunken.

Math Trivia: Concentration

You probably know about the game of Concentration.

Some number of pairs of matching cards (often 27 pairs, but well just assume it is an odd number and at least 5) are placed face down on a table. Players take turns flipping over two cards, and checking whether they match. The cards are chosen and flipped one at a time. If the cards match, they are removed and the player who flipped them gets a point and gets another turn. When all the cards are removed, the player who has the most points wins.

What you probably don’t know is that if the first player plays optimally, he will lose with probability at most 45%. What you probably won’t believe is that if the second player plays optimally, he will lose with probability at most 45%.

What about the other 10% of the games? They never end! Both players just continue picking up cards that they already know about, to avoid giving any information to the other player. I will now give a sub-optimal, but simple strategy that is similar to the optimal strategy. It will win most games you play if the person you are playing against is naively flipping over cards and giving away information.

If there are two or more completely hidden pairs, flip a new card. If it matches a card you’ve seen before, take the match, if not, flip a card you already know (If possible).

If there is only one completely hidden pairs, never flip any new cards.

If there are no completely hidden pairs, flip a new card, then flip the card that matches it.

I haven’t checked that this particular strategy works for small numbers of cards, but a strategy that loses only 45% of the time exists as long as there are at least 5 pairs. For large n, notice that you win rough half the points won before the second to last pair is revealed. After the second to last pair is revealed, if your opponent wants the game to end. He has to keep flipping new cards. He will win all the pairs until he flips the first card in the last pair. Then, assuming he cannot successfully match it, you win all the remaining pairs. You therefore on average about 2/3 of the pairs after the second to last pair is revealed.

Notice that if both players play this strategy (or the optimal one), games with lots of pairs often do not finish. The actual optimal strategy is complicated, because you are trying to maximize probability of winning and not just the expected number of points, and because this is a discrete problem with lots of special cases, but hopefully this gives you a rough idea.

If you want to rigorously check my claim, you can easily write a program to recursively compute the probability of winning in different states of the game. There aren’t that many equivalence classes of states.