Archive for June 2016

Your Deal is Better than my Deal

Do you know how to cut a cake? I mean, mathematically. There is a whole area of mathematics that studies cake cutting.

Mathematicians usually assume that each person has their own idea of what is the best part of the cake. Suppose three sisters are celebrating the New Year by having a cake. Anna likes only icing, Bella likes only chocolate chips, and Carol likes only pieces of walnuts mixed into the cake. Mathematicians want to cut cakes fairly. But what is fair? Fair is fair, right? Wrong. There are several different notions of fair cake division.

There is a proportionate division. In such a division every sister gets at least one-third of her value of the cake. This seems fair. Let’s see an example. Anna gets one third of the icing, Bella gets one third of the chocolate chips, and Carol gets everything else. This is a fair proportionate division. Each of the sisters believes that she got at least one-third of the cake, in their own value. But it doesn’t seem quite fair.

There is a stronger notion of fairness. It is called envy-free. In this division each sister gets at least one-third of the cake and, in addition, none of the three sisters would improve their value by swapping pieces. That means, if Anna wants only icing, not only does she get at least one-third of the icing, but also no one else gets more icing than Anna. The previous example of the proportionate division is not envy-free. Carol got two-thirds of the icing, so Anna would want to switch with her.

Let’s try a different division. Anna gets one third of the icing, Bella gets the chocolate chips and another third of the icing, and Carol gets all the walnuts and another third of the icing. Formally, this is envy-free cake cutting. But poor Anna. What do you think Anna feels when she sees the smiles of contentment on the faces of her sisters? Whoever invented the name doesn’t understand envy. Anna got one-third of the cake by her value, but the other sisters got the whole cake!

Luckily mathematicians understand this conundrum. So they invented another name for a cake division. They call a division equitable if everyone values all the pieces the same. So the division above is envy-free but not equitable. Let’s try again. Let’s give each sister one-third of all the components of the cake. This division is very good mathematically: it is proportionate, envy free, and equitable. By the way, envy-free division is always proportionate. This division seems fair. But is it a good division?

There is another term here: Pareto-efficient division means that it is impossible to make one person feel better, without making another person feel worse. All divisions above are not Pareto-efficient. Moving some icing from Carol to Anna, doesn’t decrease the value for Carol, but increases the value for Anna.

There is an even better way to divide the cake. We can give the icing to Anna, the walnuts to Bella, and the chocolate chips to Carol. This division is envy-free, equitable, and Pareto-efficient. It is perfect. Mathematicians even have a word for it. They call it a perfect division.

Mathematically this division is perfect. Unfortunately, sisters are not. I know an Anna who would still envy Bella.

Share:Facebooktwitterredditpinterestlinkedinmail

The Reuleaux Tetrahedron

Why are manhole covers round? The manhole covers are round because the manholes are round. Duh! But the cute mathematical answer is that the round shapes are better than many other shapes because a round cover can’t fall into a round hole. If we assume that the hole is the same shape as the cover but slightly smaller, then it is true that circular covers can’t fall into their holes. But there are many other shapes with this property. They are called the shapes of constant width.

A circle and a Reuleaux triangle

Given the width, the shape with the largest area is not surprisingly a circle. The shape with the smallest area and a given constant width is a Reuleaux Triangle. Here is how to draw a Reuleaux triangle. Draw three points that are equidistant from each other at distance d. Then draw three circles of radius d with the centers at given points. The Reuleaux triangle is the intersection of these three circles.

Can we generalize this to 3d? What would be an analogue of a Reuleaux Triangle in 3d? Of course, it is a Reuleaux Tetrahedron: Take four points at the vertices of a regular tetrahedron; take a sphere at each vertex with the radius equal to the edge of the tetrahedron; intersect the four spheres.

Is this a shape of the constant width? Many people mistakenly think that this is the case. Indeed, if you squeeze the Reuleaux tetrahedron between two planes, one of which touches a vertex and another touches the opposite face of the curvy tetrahedron, then the distance between them is equal to d: the radius of the circle. This might give you the impression that this distance is always d. Not so. If you squeeze the Reuleaux tetrahedron between two planes that touch the opposite curvy edges, the distance between these planes will be slightly more than d. To create a shape of constant width you need to shave off the edges a bit.

Meissner Bodies

Theoretically you can shave the same amount off every edge to get to a surface of constant width. But this is not the cool way to do it. The cool way is to shave a bit more but only from one edge of the pair of opposite edges. You can get two different figures this way: one that has three shaved edges forming a triangle, and the other, where three shaved edges share a vertex. These two bodies are called Meissner bodies and they are conjectured to be shapes of the constant width with the smallest volume.

On the picture I have two copies of a pair of Meissner bodies. The two left ones have three edges that share a vertex shaved off. The very left shape gives a top view of this vertex and the solid next to it has its bottom with holes looking forward. The two shapes on the right show the second Meissner body in two different positions.

I recently discovered a TED-Ed video about manhole covers. It falsely claims that the Reuleaux tetrahedron has constant width. I wrote to TED-Ed, to the author, and posted a comment on the discussion page. There was no reaction. They either should remove the video or have an errata page for it. Knowingly keeping a video with an error that is being viewed by thousands of people is irresponsible.

Share:Facebooktwitterredditpinterestlinkedinmail

Who is Guilty?

I am running a PRIMES-STEP program for middle school students, where we try to do research in mathematics. In the fall of 2015 we decided to study the following topic in logic.

Suppose there is an island where the following four types of people live:

  • Absolute truth-tellers always tell the truth.
  • Partial truth-tellers tell the truth with one exception: if they are guilty, they will say that they are innocent.
  • Absolute liars always lie.
  • Responsible liars lie with one exception: if they are guilty, they will say that they are guilty.

See if you can solve this simple logic puzzle about people on this island.

It is known that exactly one person stole an expensive painting from an apartment. It is also known that only Alice or Bob could have done it. Here are their statements:
Alice: I am guilty. Bob is a truth-teller.
Bob: I am guilty. Alice stole it. Alice is the same type as me.
Who stole the painting and what types are Alice and Bob?

My students and I discovered a lot of interesting things about these four types of people and wrote a paper: Who Is Guilty?. This paper contains 11 cute logic puzzles designed by each of my 11 students.

I envied my students and decided to create two puzzles of my own. You have already solved the one above, so here is another, more difficult, puzzle:

A bank was robbed and a witness said that there was exactly one person who committed the robbery. Three suspects were apprehended. No one else could have participated in the robbery.
Alice: I am innocent. Bob committed the crime. Bob is a truth-teller.
Bob: I am innocent. Alice is guilty. Carol is a different type than me.
Carol: I am innocent. Alice is guilty.
Who robbed the bank and what types are the suspects?

Share:Facebooktwitterredditpinterestlinkedinmail