Optimal stopping

,

Imagine a conveyor belt in front of you, on which are placed one hundred various-sized piles of money. You are allowed to stop the belt at any point and take the pile of money in front of you, but you cannot take any pile that has already passed you. Which pile should you take?

There is a mathematical solution to this problem, (sometimes called the Sultan’s Dowry Problem or the Fussy Suitor Problem) which is quite elegant.

  1. Wait until 37% of the piles have gone past you. (The figure of 37% is the reciprocal of e, the base of the natural logarithms.)
  2. Pick the next pile that is better than all the other piles so far.

Here are one hundred randomly-generated piles of money under £100:

£52.33, £80.83, £27.39, £84.75, £63.87, £1.66, £96.82, £76.51, £22.77, £90.94, £24.08, £60.41, £10.38, £95.59, £92.98, £46.80, £85.86, £21.96, £92.22, £29.19, £59.08, £72.22, £45.08, £63.39, £16.38, £71.49, £29.59, £78.62, £30.05, £97.98, £70.95, £3.79, £19.22, £77.52, £1.78, £48.74, £48.71, £35.95, £79.48, £11.50, £47.33, £32.83, £99.19, £3.23, £10.59, £58.22, £21.15, £61.37, £42.78, £25.27, £58.86, £32.82, £91.75, £13.04, £21.76, £72.29, £85.48, £58.81, £8.70, £91.63, £93.30, £23.00, £13.49, £11.67, £95.27, £21.37, £67.27, £90.99, £50.88, £77.22, £9.51, £10.63, £28.23, £63.94, £89.51, £90.12, £68.53, £76.98, £76.83, £92.04, £19.21, £73.82, £71.31, £99.94, £26.96, £86.92, £33.94, £8.25, £13.70, £74.44, £60.08, £11.54, £42.75, £78.67, £41.92, £92.36, £8.25, £92.89, £37.31 and £36.62.

The “best” value from the first thirty-seven piles is £97.98, so you should proceed through the remaining piles until you reach a value greater than this. This means stopping at the 43rd pile: £99.19.

Looking at the data, this strategy doesn’t actually yield the best value – waiting until the 84th pile would yield £99.94, which is slightly more. For large numbers of piles the 37% rule yields the perfect result in only 37% of cases, but this is a greater percentage than any other solution and it usually results in a very good result (i.e. one close to the perfect result).

Grains of sand in a breath

,

I recently saw this tweet:


This immediately didn’t sound right to me, so I decided to investigate.

The volume of the average human breath (the tidal volume) is about half a litre or 0.0005 cubic metres; one half-litre of air is about twenty-two millimoles. One mole contains 6.02×1023 particles, so 22 mmol contains 1.32×1022 particles.

Sand ranges in size, from 0.05 millimetres to one or two millimetres in diameter. Assuming a diameter of 0.5 millimetres, and that sand grains are spherical, gives each grain of sand a volume of 6.54×10?11 cubic metres. Twenty-two millimoles of sand would therefore have a volume of 867 billion cubic metres.

However, this ignores the gaps between the sand particles. The famous mathematician Carl Fredrich Gauss showed that the closest spheres can pack together is with a packing fraction of 74.0%, meaning that 26% of the space is wasted. Our sand would therefore occupy a volume of 1.17 trillion cubic metres rather than the value calculated earlier.

The surface area of the United States (all fifty states, including land and water) is 9.83 trillion square metres. This volume of sand would therefore cover the US to a depth of eleven centimetres, which is nowhere near the height of a eight-storey building. Even if we take “cover the US” to mean only the land and only the forty-eight contiguous states then we still only get to fifteen or sixteen centimetres; and even if we used the largest possible grains of sand we’d still be out by at least two orders of magnitude. The author of the article must be imagining sand grains the size of peas or something.

(Also, the article linked-to in the tweet refers to an average human breath containing 8×1022 particles, which is six times larger than the value I calculated; I think they may have confused inspiratory reserve volume with tidal volume.)

Resistor values

,

I am occasionally forced to teach some electronics. Looking recently at our resistor sets I was somewhat puzzled by the odd values involved.

resistor-values-E12-series

We have two sets of resistors: the E12 series and the E24 series. The E24 series has twice as many resistors for each scale (1-10, 100-1000, 1000-10000, etc.) as the E12, with the number after the ‘E’ telling you how many resistors are in the series.

For example, in the 10-100 Ω scale the values are as follows:

E12: 10 Ω, 12 Ω, 15 Ω, 18 Ω, 22 Ω, 27 Ω, 33 Ω, 39 Ω, 47 Ω, 56 Ω, 68 Ω and 82 Ω.
E24: 10 Ω, 11 Ω, 12 Ω, 13 Ω, 15 Ω, 16 Ω, 18 Ω, 20 Ω, 22 Ω, 24 Ω, 27 Ω, 30 Ω, 33 Ω, 36 Ω, 39 Ω, 43 Ω, 47 Ω, 51 Ω, 56 Ω, 62 Ω, 68 Ω, 75 Ω, 82 Ω and 91 Ω.

The reason for the choice of values is tolerance. The resistors in the E12 scale are guaranteed to be ±20% of the stated value, so with a starting value of 100 Ω it makes little sense to produce a 110 Ω resistor as this is already within the tolerance of the 100 Ω resistor; a 120 Ω resistor will be 144 Ω at most, so it makes sense for 150 Ω to be the next value.

The resistors in the E24 scale are guaranteed to be ±10% of the stated value, therefore twice as many values are needed within the scale when compared with the E12 scale. With a starting value of 100 Ω a 105 Ω resistor is unnecessary for the same reasons described above.

For use in schools it makes sense to use E12 and E24 series resistors, as we rarely require great precision in our resistors. But for other uses it’s necessary to use more accurate resistors: the E192 series contains 192 resistors and has a tolerance of just ±0.5% and resistors with even finer tolerances are produced for super high-accuracy applications, for example in defibrillators.

Thanks to PAS for help with this post.

An unexpected hazard of manned Mars exploration

, ,

mars-surface

There are many risks associated with a manned mission to Mars. The journey itself would last between 150 and 350 days, and beside the risks associated with prolonged isolation and cramped conditions there is also the lack of real-time communication caused by the time taken for radio signals to travel the very large distances involved. Once arriving on Mars there is the presence of high levels of cosmic rays and ionising radiation to content with, all to be dealt with without proper medical facilities.

But a new paper* identifies a risk I hadn’t considered: asteroid impacts. Mars is much closer to the asteroid belt than Earth, and thus asteroid impacts are more frequent. The authors analyse the rate of crater formation on Mars and come up with a model that predicts the number of craters of a given diameter likely to be formed over a given period of time.

crater-impact-graph

Their model predicts that a one megaton (≈1 km crater) impact will occur once every 3.3 years, which would make spending any significant length of time on Mars quite hazardous. Mars’ atmosphere is much thinner than Earth’s, with an atmospheric pressure only 0.6% of ours, and so damage on the Martian surface is likely to be much more severe than for a similar impact on Earth.

* William Bruckman, Abraham Ruiz and Elio Ramos, “Earth and Mars crater size frequency distribution and impact rates: Theoretical and observational analysis”, arXiv:1212.3273.