One Million Hats

From the always-excellent Futility Closet, a problem by Paul J. Nahin:

Each of a million people puts his or her hat into a very large box. Each hat has its owner’s name on it. The box is given a good shaking, and then each person, one after another, randomly draws a hat out of the box. What is the probability that at least one person gets their own hat back?

Most people might think that the chance is very, very small, but it’s not. It’s actually more than 60%. How can this be true?

We can view this problem as having only two possible solutions (events): either nobody gets their hat back, or at least one person gets their hat back. The sum of the probabilities of these events must be equal to one and therefore if we can work out the probability that nobody gets their own hat back, then the probability that at least one person does is one minus that.

For each person, there is only a one-in-a-million chance that they have picked their own hat, and thus a 999999 in 1000000 chance that they have not got their own hat.

$\Pr \left( \textnormal{one incorrect hat} \right) = \frac{999999}{1000000}$

$\Pr \left( \textnormal{one million incorrect hats} \right) = \left( \frac{999999}{1000000} \right)^{1000000}$

$\Pr \left( \textnormal{one million incorrect hats} \right) = 0.368$

If the probability of all one million people picking the incorrect hat in 0.368, then via our previous reasoning, the probability of at least one person picking the correct hat is 1-0.368, or 63.2%.

This is a very counterintuitive result, but the wording of the question is key. If we changed the wording to exactly one person getting their hat back then our answer changes dramatically. Starting with our 63.2% chance, we would have to subtract the chance of two people getting their hats back, and of three people getting their hats back, and so on … until we reached the very small chance of one person, and one person only, getting their hat back.

Fixed Area, Infinite Perimeter

The Koch Snowflake (named after its inventor, the Swedish mathematician Helge von Koch) is a fractal with a number of interesting properties.

The first four generations of the Koch Snowflake

As the number of generations increases, the area of the snowflake increases, but it increases towards a limit: eight-fifths of the size of the first (triangular) generation. This is because each additional generation adds three triangles which are one-ninth the size of the triangle added in the previous generation (for a total increase of one-third), and the additional of increasingly small triangles has a lesser and lesser effect on the overall area as the number of generations increases.

But as the number of generations increases, the perimeter of the shape continues to grow, without approaching a limit: each generation of the Snowflake has a perimeter which is four-thirds of the previous generation’s perimeter. This is because the additional perimeter added each time is four times one-third of the length of each side, for a total increase of four-thirds, as opposed to the one-third increase in area. Because four-thirds is greater than one, the perimeter tends to infinity, whereas the area (which at one-third is less than one) does not.

As you can see from the graph above, the area approaches its limit very quickly, whereas the perimeter grows very quickly (which is why it has to be shown on a different axis).

Veblen and Giffen Goods

There is a fundamental law of economics that says that as the price of a good or service increases, the demand for that product decreases. This is the Law of Demand: if prices are high, people cannot buy as much. But there are some products for which this is not the case.

Veblen Goods do not obey the Law of Demand: as their price increases, so does demand for them. This is a case of conspicuous consumption, people show off and demonstrate their status by buying increasingly expensive products. A £10000 gold Rolex watch does not really tell time any better than a £10 Casio, but owning a £10000 gold Rolex demonstrates that you are so wealthy that you can afford to spend £10000 on a watch. People do not want to buy a £10 Rolex, but they do want to buy a £10000 Rolex, to show off how much money they have.

There are some goods to which the Law of Demand does not apply, and which are not Veblen Goods. These are called Giffen Goods, and on the face of it, they seem to disobey all rational economic rules: demand for them increases even when their price increases, despite the fact that they cannot be used to demonstrate status via conspicuous consumption.

But imagine this situation: You need to feed your family. You normally buy a mixture of expensive (tasty) and inexpensive (staple) products to provide enough nutrition, but also some variety. But one day the price of rice quadruples: now you can’t afford the more expensive products and the rice, and you still need the staple rice to provide basic nutrition. Thus you buy more rice, even though its price has increased, and the rice is a Giffen Good.

Types of Perpetual Motion Machines

Perpetual motion machines (which don’t exist) come in many forms.

Perpetual motion machines of the first kind violate the First Law of Thermodynamics. They produce mechanical work (i.e. movement) without any energy being input; this violates the principle of the conservation of energy.

Perpetual motion machines of the second kind violate the Second Law of Thermodynamics. They convert thermal energy directly into mechanical work, with no exhaust heat being emitted; this violates the rule of the production of entropy, that entropy in a system must always increase.

Perpetual motion machines of the third kind do not, as their name suggests, violate the Third Law of Thermodynamics. Rather they claim to maintain motion (once started) forever, and do so by assuming that frictional forces can be eliminated completely (often through operating in a perfect vacuum, which is also not possible).

Altitude and Flight Level

The term elevation refers to the position of a point or an object on the ground above a fixed reference point, usually mean sea level. The term altitude refers to the position of a point or object in the air above a fixed reference point.

But defining altitude can be difficult, and so when altitude is referred to, the reference point must always be explicitly defined. Altitude is normally measured above mean sea level (AMSL) or above ground level (AGL). For example, if an aeroplane flew over the peak of Mount Everest, its altitude could be referred to as either 38 000 ft AMSL or 9000 ft AGL, because the peak of Everest has an elevation of 29 000 ft.

For aircraft it is difficult to measure altitude. You might think that GPS could provide this information, but GPS is designed for positioning on the surface of the Earth and isn’t very good at measuring altitude.

Pilots have always used atmospheric pressure to measure altitude. As an aircraft moves further upwards into the air, there is less air above it pushing down on it and the pressure decreases. This decrease is predictable and easy to calculate:

$p_h = p_0 \left( 1- \frac{\gamma h}{T_0} \right)^{\frac{gM}{R\gamma}}$

where $p_h$ is the pressure at height $h$$p_0$ is the standard atmospheric pressure of 1013.25 hPa$\gamma$ is the rate at which temperature decreases with altitude (the temperature lapse rate); $T_0$ is the standard temperature; $g$ is the gravitational field strength; $M$ is the molar mass of dry air; and $R$ is the molar gas constant.

Aeroplanes do not fly at a set altitude. Rather they fly at a given flight level, which – although it sounds like a height – is actually a pressure. When a pilot flies at a flight level of 32 000 ft (FL320) they are actually flying at a constant pressure of 275 hPa, and may actually be far above or far below this altitude, depending on the local weather (and therefore pressure) conditions. If they enter an area of particularly high or low pressure they will have to ascend or descend correspondingly.

Using flight levels helps to prevent collisions between aircraft: in the UK aircraft flying on headings between 000° and 089° (north to east) they flight at odd numbered flight levels (FL310, FL330, etc); flying between 090° and 179° (east to south) at odd numbered flight levels plus 500 ft (FL315, FL335); flying between 180° and 269° (south to west) at even numbered flight levels (FL320, FL340); and flying between 270° and 359° (west to north) at even numbered flight levels plus 500 ft (FL325, FL 345). In other parts of the world different flight level rules are used.