Number of Increases within a Random Permutation, and an Unexpected Link to a Familiar Series – Elliott Line

Consider a deck of n numbered cards. You play the following game: you turn over the first card and retain it. Then you turn the next one: if it ranks less than the first one, discard it; if it ranks greater then keep it and make it the new benchmark. Repeat this step for each subsequent card. At the end of the deck, count the number of cards you have retained. For a given ‘n’, what is the expected number of cards? If there were 11 cards? If there were 12,367 cards?

We’ll start with a few small values of n: trivially when n=0, the number of cards retained, x, will also be 0. For n=1, x will also be 1. For n=2, the two cards will either be in descending or ascending order, so x could be either 1 or 2, with equal probability, so X (big x, the average value of x) will be 1.5.

Since no cards will be retained after the maximum card has been seen, it is useful to consider where in the deck the maximum card might be and what the consequences are:

Consider the case with three cards. If the 3 card comes up first, which it will do in 1/3 of cases, x will be 1. If the 3 card comes up second, x will be 2. If the 3 card comes up last, x may be 2 or 3, depending on the order of the 1 and 2 cards.

In other words, when the maximum 3 card is first, there are 0 cards before it so the average number of cards retained before reaching the maximum card is 0, so the count will be 1 more than that, 1.

If the maximum card is second, there is 1 card before it so the average number of cards retained before reaching the maximum card is 1, so the count will be 1 more than that, 2.

If the maximum card is third, there are 2 cards before it so the average number of cards retained before reaching the maximum card is 1.5, so the count will be 1 more than that, 2.5.

Those three cases are equally likely, so we can express X3 in terms of previous X values:

X3 = ((X0) + 1 + (X1) +1 + (X2) +1)/3

We can generalise this so that any Xn can be expressed as an equation involving previous X values by extending the idea of considering where the maximum card is and how many cards are retained prior to reaching it:

Xn = ((X0) + (X1) + … + (Xn-1) + n)/n

Now a very interesting thing happens if you compare the equation for Xn with that of Xn-1

Xn-1 = ((X0) + (X1) + … + (Xn-2) + n-1)/(n-1)

In the first equation you multiply both sides by n, and in the second equation by (n-1) to get the following two equations:

n(Xn) = (X0) + (X1) + … + (Xn-1) + n

(n-1)(Xn-1) = (X0) + (X1) + … + (Xn-2) + n-1

Now if you take the difference between those two equations almost all the terms cancel out:

n(Xn) - (n-1)(Xn-1) = (Xn-1) + 1

Which then simplifies to:

(Xn) – (Xn-1) = 1/n

This is great as it means that since X0 = 0, the sequence of Xn is merely the partial sum of the harmonic series:

1 + 1/2 + 1/3 + 1/4 +1/5 …

… a series about which we know a great deal.

We know for instance that the sequence does not converge but tends to infinity. This rings true when we consider the numbered cards, as we would expect Xn to keep creeping up as the number of cards increased and it would seem very odd for it to converge to an upper bound.

What is surprising I feel, when considering it in terms of the cards, is just how slowly Xn does increase.

It seems quite reasonable that Xn first exceeds 3 when n is 11, that is when there are 11 numbered cards, the average number of cards retained is around 3.

However, when we calculate when the expected number of retained cards first exceeds 10, the number of cards would be 12367 (!).

Puzzle of the Week #189 - Three Palindromes

I recently stumbled upon an intriguing theorem that stated that every positive whole number can be expressed as the sum of three palindromic numbers, although it is often far from straightforward to find them.

Can you express the number 6878592 as the sum of three palindromes?

It is the sum of three numbers of 7, 6 and 5 digits respectively, and no digit is repeated except where being a palindrome dictates it:

ABCDCBA + EFGGFE + HJKJH = 6878592

Puzzle of the Week #188 - Triple Indivisibility

We have a whole number, let’s call it ‘b’.

 

We also have a number of statements:

1 divides exactly into ‘b’

2 divides exactly into ‘b’

3 divides exactly into ‘b’

4 divides exactly into ‘b’

… continuing all the way to …

 ‘a’ divides exactly into ‘b’

 

We are told that three consecutive statements in the list are NOT true, while all of the others are true.

 

Question a: what is the MAXIMUM value that ‘a’ could possibly be?

Question b: given that value for ‘a’, what is the MINIMUM value that ‘b’ could possibly be?

 

Puzzle of the Week #186 - Prime of my Life

I celebrated my birthday this week. Right now, my age, and those of my wife, my daughter and my son, are all prime numbers. After my daughter celebrates her next birthday in a few months we will not all be prime ages until 30 years from now. And after that (if we are all still around) it would be another 30 years.

My daughter is about four and a half years older than my son, and I am about one and a half years older than my wife. How old are we all?

 

Puzzle of the Week #185 - How Long is a Piece of String?

I have a loop of string N centimetres long. I can form this loop into a square with n cm along each side (n being exactly a quarter of N). Not surprisingly I find that if I draw diagonals from opposite corners of this square, they cross at right angles. I also find that I can tilt the square into a rhombus shape, while still having n cm along each side, the diagonals still cross at right angles. Still not surprising.

However, I discover that if I move some of the corners so that instead of all being n cm long, the four edges of the quadrilateral are n, n-5, n+1 and n+4, then the diagonals STILL cross at right angles.

How long in my loop of string?

piece of string.JPG

Puzzle of the Week #182 - The Rickety Carousel

There is a rickety old carousel, with 24 horses equally spaced around the edge of a disc. There are at least two things wrong with it: one is that the horses in positions A, B, C, D, E, F and G are broken and not safe to ride; another is that the carousel needs to be perfectly balanced around the centre of the disc, otherwise it won’t go round. This means that when there are two children wishing to ride, they would have to be positioned in diametrically opposite positions, eg, A and M, in order that the centre of gravity is at the centre of the disc. If there were three children they could be at positions A, I and Q.

On this particular day, nine children wish to ride the carousel. Where do they need to be positioned such that the centre of gravity is at the centre of the disc, and that positions A to G are unoccupied?

Puzzle of the Week #178 - Tangent Curve

The line begins in a vertical downward direction, transitions into an arc of radius 60, then into another arc with a tighter radius, which just touches the horizontal dashed line. Then there is an arc of radius 50 in a clockwise direction, then a horizontal line. At each transition between line and arc or arc and arc the tangents are continuous.

What is the missing radius?


Puzzle of the Week #177 - Skyscrapers and Empty Lots

Each of the 25 squares contains either a building of height 1, 2, 3 or 4, or an empty lot. Each row and each column contains exactly one of each of those.

The numbers in the twenty ‘vantage points’ around the edge denote how many buildings you can see looking along that particular row or column, so for instance if the 2 building was closest, followed by 1, 4 and 3 in that order, the vantage point would say 2, as you can see the 2-building and the 4-building, whereas the 1-building and 3-building are hidden behind taller buildings.

Here’s an example (with only 1, 2 and 3 height buildings) which might make it clearer, followed by the puzzle itself:

skyscrapers.JPG

Puzzle of the Week #176 - Nine Point Circle

You might be familiar with the famous ‘Nine Point Circle’ theorem, which says that for ANY triangle the 3 midpoints (shown below in red), the 3 perpendicular feet (shown in green), and the 3 points midway between the each of the vertices and the orthocentre (shown in blue), will all lie on a circle. (Of course for an equilateral or isosceles triangle some of these points will coincide). But I have discovered there is something quite special about the 9 points of a triangle with angles 45, 60 and 75.

What is so special?

9 point circle.JPG

The figure is to scale so you may be able to guess the answer.