The Critical Line – Volume 1: Hello, World!

What’s in a name?

Maintaining the tradition, a new puzzle column deserves a new name and today we get two for the price of one. The Critical Line is an allusion to the line of thought required to solve each monthly puzzle. In a more literal sense it also refers to the actual line $$\Re(z) = \frac{1}{2}$$

You may recognise this as being relevant to the formulation of the Riemann Hypothesis – that all non-trivial zeros of the Riemann zeta function lie on the critical line. It’s arguably one of the most important open problems in mathematics, but don’t worry, the problems considered in this column will be marginally more tractable.

Warming Up

Here’s a problem that I heard from a friend recently:

There exist two cities, A and B, separated by a very long road. N cars have set off from A travelling towards B. Initially, they all drive at a constant speed that has been chosen at random from a continuous (and non-negative) probability distribution X. This road, however, only has one lane so overtaking is impossible. If a fast car comes up behind a slower car then the faster car will slow down and these cars will form a group. What is the expected number of groups of cars that arrive at B?

(Note: a “very long road” means long enough that a faster car will always have time to catch up to a slower car before arriving at B)

[reveal heading=”

%image% Click to reveal solution

” id=”id1″]SOLUTION: Let P(n) be the expected number of groups of cars arriving at B given n cars embark from A. When there is only one car we get one group, $$P(1) = 1$$.Now let’s assume we have k-1 cars embarking from A and we are going to add a k^th car. We can assume without loss of generality that we are adding the fastest car.

• If this car is the first to leave A then no other car will catch it and we will have an additional group arriving at B. This occurs with probability $$\frac{1}{k}$$.
• If the car is in any other position then it will eventually run into a car in front and the number of group arriving at B will be unchanged. This occurs with probability $$\frac{k-1}{k}$$.

This means that $$P(k) = P(k-1) + 1 \cdot \frac{1}{k} + 0 \cdot \frac{k-1}{k}$$ and therefore $$P(n) = \sum_{m=1}^{n} \frac{1}{m}$$.So the expected number of groups of cars arriving at B is $$H_{n}$$ (the n^th Harmonic number). Neat![reveal]

And now for the main event…

The Magic Teller Machine

You have several coins. Each of these coins has a front and a back, and on each side of the coin is a non-negative integer. We can represent a coin as the ordered paid $$\langle x, y \rangle$$ and the value of each coin is the sum of the integers on the front and back, x + y. In front of you is a magic teller machine, it knows the contents of your coin purse. If you have a coin $$\langle x, y \rangle$$, but you have neither the coin $$\langle x + 1, y \rangle$$ or $$\langle x, y + 1 \rangle$$  , then the MTM will allow you to exchange your coin $$\langle x, y \rangle$$ for two new coins $$\langle x + 1, y \rangle$$ and $$\langle x, y +1 \rangle$$. You are allowed to make any (finite) number of transactions with the MTM. The aim of the game is to make a sequence of transactions with the MTM so that all of your coins have a value greater than 2. Is this possible in either of the following scenarios:

1. You start with the 6 unique coins with a value at most 2: $$\langle 0, 0\rangle$$, $$\langle 1, 0\rangle$$, $$\langle 0, 1\rangle$$, $$\langle 2, 0\rangle$$, $$\langle 1, 1\rangle$$, $$\langle 0, 2\rangle$$
2. You start with a single coin of value zero: $$\langle 0, 0\rangle$$

Demonstrate that you can exchange your coins until they all have a value greater than 2, or prove that it’s impossible.

For your chance to win $1,000,000! Send your proof of the Riemann Hypothesis to:

Clay Mathematics Institute
70 Main St
Suite 300
Peterborough, NH 03458
USA

Alternatively, for your chance to win $50! Send your solution to the Magic Teller Machine puzzle to ActuariesMag@actuaries.asn.au

CPD: Actuaries Institute Members can claim two CPD points for every hour of reading articles on Actuaries Digital.