Archive for September 2011

## Hiding Behind

Let’s call a projection of a body L onto a hyperplane a shadow. Here is a mathematical way to hide behind. An object K can hide behind an object L if in any direction the shadow of K can be moved by a translation to be inside the corresponding shadow of L. If K can hide inside L, then obviously K can hide behind L. Dan Klain drew my interest to the following questions. Is the converse true? If K can hide behind L can it hide inside L? If not, then if K can hide behind L, does it follow that the volume of K is smaller than that of L?

We can answer both questions for 2D bodies by using objects with constant width. Objects with constant width are ones that have the same segment as their shadow in every direction. The two most famous examples are a circle and a Reuleaux triangle:

Let’s consider a circle and a Reuleaux triangle of the same width. They can hide behind each other. Barbier’s Theorem states that all objects of the same constant width have the same perimeter. We all know that given a fixed perimeter, the circle has the largest area. Thus, the circle can hide behind the Reuleaux triangle which has smaller area and, consequently, the circle can’t hide inside the Reuleaux triangle. By the way, the Reuleaux triangle has the smallest area of all the objects with the given constant width.

To digress. You might have heard the most famous Microsoft interview question: Why are manhole covers round? Presumably because round manhole covers can’t fall into slightly smaller round holes. The same property is true for manhole covers of any shape of constant width. On the picture below (Flickr original) you can see Reuleaux-triangle-shaped covers.

Let’s move the dimensions up. Dan’s questions become both more difficult and more interesting, because the shadows are not as simple as segments any more.

Before continuing, I need to introduce the concept of “Minkowski sums.” Suppose we have two convex bodies in space. Let’s designate the origin. Then a body can be represented as a set of vectors from the origin to the points in the body. The Minkowski sum of two bodies are all possible sums of two vectors corresponding to the first body and the second body.

Another way to picture the Minkowski sum is like this: Choose a point in the second body. Then move the second body around by translations so that the chosen point covers the first body. Then the area swept by the second body is the Minkowski sum of both of them.

Suppose we have two convex bodies K and L. Their Minkowski interpolation is the body tK + (1-t)L, where 0 ≤ t ≤ 1 is a scaling coefficient. The picture below made by Christina Chen illustrates the Minkowski interpolation of a triangle and an inverted triangle.

If two bodies can hide behind L, then their Minkowski interpolation can hide behind L for any value of parameter t. In particular if K can hide behind L, then the Minkowski interpolation tK + (1-t)L can hide behind L, for any t.

In my paper co-authored with Christina Chen and Daniel Klain “Volume bounds for shadow covering”, we found the following connection between hiding inside and volumes. If L is a simplex, and K can hide behind it, but can’t hide inside L, then there exists t such that the Minkowski interpolation tK + (1-t)L has a larger volume than the volume of L.

In the paper we conjecture that the largest volume ratio V(K)/V(L) for a body K that can hide behind another body L is achieved if L is a simplex and K is a Minkowski interpolation of L and an inverted simplex. The 3D object that can hide behind a tetrahedron and has 16% more volume than the tetrahedron was found by Christina Chen. See her picture below.

The main result of the paper is a universal constant bound: if K can hide behind L, then V(K) ≤ 2.942 V(L), independent of the dimension of the ambient space.

## Star Trek TNG Science Quiz

Question 1. Holodeck. After a long and difficult assignment on an uninhabited planet, Commander Riker went to Holodeck III to unwind. While there he ate three cheeseburgers generated by the holodeck program. Is Commander Riker hungry after he ends the program?

Question 2. Relativity. We know that speed in space is relative, there is no absolute speed. What does Captain Picard mean when he orders a “full stop”?

Question 3. The Replicator. Captain Picard approached a replicator and requested: “Tea, Earl Grey. Hot.” The replicator immediately created a glass with hot Earl Grey tea. How much energy would the Enterprise have saved in seven years if they used a dish-washing machine, rather than creating glasses from atoms each time and dissolving them afterwards?

Question 4. Contractions. Commander Data hasn’t mastered contractions in English speech. In what year do you think the first program was written to convert formal English into English with contractions?

Question 5. Data. Commander Data is fully functional and absolutely superior to a vibrator. Given that there are more than a thousand people on board the Enterprise, estimate how many times a year on average Data will receive sexual requests.

The next two questions are related to particular episodes.

Question 6. “Up The Long Ladder”. Mariposans reproduce by cloning. Why do all the identical sets of clones appear to be the same age? Does it mean that upon the reproduction the clone is the age of the host? If so, they all should be 300 years old.

Mariposans steal sample DNA from Commander Riker and Dr. Pulaski. If Riker and Pulaski didn’t destroy their maturing clones what age would those clones be? Would they know how much two plus two is when they awaken? If clones awaken as adults, what is their life span?

Question 7. “Force of Nature”. Serova sacrifices herself to save her world from the effects of warp drive, but in doing so, she herself creates the rift that will destroy her world. Explain the logic.

## Time for Nerdy Humor

* * *

Logic: if an empty yogurt container is in the sink, a spoon is in the garbage can.

* * *

Logically, a wireless mouse should be called a hamster.

* * *

— I started a new life today.
— You quit smoking and drinking?
— No, I changed my email and Facebook accounts.

* * *

— The reviewer has rejected your paper submitted to our math journal because it doesn’t contain any theorems or fomulae or even numbers.
— Wait a minute. Your reviewer is mistaken. There are page numbers on every page.

* * *

A kyboard for sal: only on ky dosn’t work.

* * *

My computer always beats me in chess. In revenge, I always beat it in a boxing match.

* * *

— Were your parents married when you were born?
— 50%.
— 50%?
— Yes, my father was married and my mother was not.

* * *

Two programmers are talking:
— I can’t turn on my oven.
— What’s the error message?

## Too Good at Spider Solitaire

Have you ever been punished for being too good at spider solitaire? I mean, have you ever been stuck because you collected too many suits? Many versions of the game don’t allow you to deal from the deck if you have empty columns, nor do they allow you to get back a completed suit. If the number of cards left on the table in the middle of the game is less than ten — the number of columns — you are stuck. I always wondered what the probability is of being stuck. This probability is difficult to calculate because it depends on your strategy. So I invented a boring version of spider solitaire for the sake of creating a math problem. Here it goes:

You start with two full decks of 104 cards. Initially you take 54 cards. At each turn you take all full suits out of your hand. If you have less than ten cards left in your hand, you are stuck. If not, take ten more cards from the leftover deck and continue. What is the probability that you can be stuck during this game?

Let us simplify the game even more by playing the easy level of the boring spider solitaire in which you have only spades. So you have a total of eight full suits of spades. I leave it to my readers to calculate the total probability of being stuck. Here I would like to estimate the easiest case: the probability of being stuck before the last deal.

There are ten cards left in the deck. For you to be stuck, they all should have a different value. The total number of ways to choose ten cards is 104 choose 10. To calculate the number of ways in which these ten cards have different values we need to choose these ten values in 13 choose 10 ways, then multiply by the number of ways each card of a given value can be taken from the deck: 810. The probability is about 0.0117655.

I will leave it to my readers to calculate the probability of being stuck before the last deal at the medium level: when you play two suits, hearts and spades.

No, I will not tell you how many times I played spider solitaire.

## What Sequences Sound Like

Is there a way to put a sequence of numbers to music? The system that comes immediately to mind is to match a number to a particular pitch. The difference between any two neighboring integers is the same, so it is logical to assume that the same tone interval should correspond to the same difference in integers. After we decide which tone interval corresponds to the difference of 1, we need to find our starting point. That is, we need to choose the pitch that corresponds to the number 1. After that, all numbers can be automatically matched to pitches.

After we know the pitches for our numbers, to make it into music we need to decide on the time interval between the notes. The music should be uniquely defined by the sequence, hence the only logical way would be to have a fixed time interval between two consecutive notes.

We see that there are several parameters here: the starting point, the pitch difference corresponding to 1, and the time interval between notes. The Online Encyclopedia of Integer Sequences offers the conversion to music for any sequence. It gives you freedom to set the parameters yourself. The sequences do not sound melodic because mathematical sequences will not necessarily follow rules that comply with a nice melody. Moreover, there are no interesting rhythms because the time interval between the notes is always the same.

One day I received an email from a stranger named Michael Blake. He sent me a link to his video on YouTube called “What Pi Sounds Like.” He converted the digits of Pi to music. My stomach hurt while I was listening to his music. My stomach hurts now while I am writing this. He just numbered white keys on the piano from 1 to 9 starting from C. Then he played the digits of Pi. Clearly, Michael is not a mathematician, as he does not seem to know what to do with 0. Luckily for him the first 32 digits of Pi do not contain zero, so Michael played the first several digits over and over. My stomach hurts because he lost the basic math property of digits: the difference between the neighboring digits is the same. In his interpretation the digits that differ by one can have a tone interval of minor or major second in a random order corresponding to his random starting point.

I am not writing this to trash Michael. He is a free man in a free country and can do whatever he wants with the digits of Pi. Oops, I am sorry, he can’t do whatever he wants. Michael’s video was removed from YouTube due to an odd copyright infringement claim by Lars Erickson, who wrote a symphony using the digits of Pi.

Luckily for my readers Michael’s video appears in some other places, for example at the New Scientist channel. As Michael didn’t follow the symmetry of numbers and instead replaced the math rules with some music rules, his interpretation of Pi is one of the most melodic I’ve heard. The more randomly and non-mathematically you interpret digits, the more freedom you have to make a nice piece of music. I will say, however, that Michael’s video is nicely done, and I am glad that musicians are promoting Pi.

Other musicians do other strange things. For example, Steven Rochen composed a violin solo based on the digits of Pi. Unlike Michael, he used the same tone interval for progressing from one number to the next, like a mathematician would do. He started with A representing 1 and each subsequent number corresponded to an increase of half a tone. That is, A# is 2 and so on. Like Michael Blake he didn’t know what to do with 0 and used it for rest. In addition, when he encountered 10, 11, and 12 as part of the decimal expansion he didn’t use them as two digits, but combined them, and used them for F#, G, G# respectively. To him this was the way to cover all possible notes within one octave, but for me, it unfortunately caused another twinge in my stomach.

## Broom Bridge

In August I visited my son Alexey Radul, who currently works at the Hamilton Institute in Maynooth, Ireland. One of the greatest Irish attractions, Broom Bridge, is located there. It’s a bridge over the railroad that connects Maynooth and Dublin. One day in 1843, while walking over the bridge, Sir William Rowan Hamilton had a revelation. He understood how the formulae for quaternions should be written. He scratched them into a stone of the bridge. Now the bridge has a plaque commemorating this event. The plaque contains his formulae. I don’t remember ever seeing a plaque with math, so naturally I rushed off to make my pilgrimage to Broom Bridge.

Quaternions have very pronounced sentimental value for me, since my first research was related to them. Let’s consider a simple graph. We can construct an algebra associated with this graph in the following way. For each vertex we have a generator of the algebra. In addition we have some relations. Each generator squared is equal to −1. If two vertices are connected the corresponding generators anti-commute, and they commute otherwise. The simplest non-commutative algebra associated with a graph corresponds to a graph with two vertices and one edge. If we call the generators i and j, then the we get the relations: i2 = j2 = −1, and ij = −ji. I we denote ij as k, the algebra as a vector space has dimension 4 and a basis: 1, i, j, k. These are exactly the quaternions. In my undergraduate research I studied such algebras related to Dynkin diagrams. Thirty years later I came back to them in my paper Clifford Algebras and Graphs. But I digress.

I was walking on the bridge hoping that like Hamilton I would come up with a new formula. Instead, I was looking around wondering why the Broombridge Station didn’t have a ticket office. I already had my ticket, but I was curious how other people would get theirs. I asked a girl standing on the platform where to buy tickets. She said that there is no way to buy tickets there, so she sometimes rides without a ticket. The fine for not having tickets is very high in Ireland, so I expressed my surprised. She told me that she just says that she is from the town of Broombridge if she is asked to present her ticket.

Being a Russian I started scheming: obviously people can save money by buying tickets to Broombridge and continuing without a ticket wherever they need to go. If the tickets are checked, they can claim that they are traveling from Broombridge. Clearly Ireland hasn’t been blessed with very many Russians visitors.