From Newsgroup: rec.puzzles

A well-known puzzle apparently - I don't think I'd seen it before it
appeared on the National Cipher Challenge a couple of week's ago. I've
added the part b) question.

There is a plane with 100 seats and we have 100 passengers entering the
plane one after the other. The first passenger cannot find their boarding pass, so chooses a random (uniformly) seat. All the other passengers do
the following when entering the plane (they have their boarding passes).
If the seat written on the boarding pass is free, the passenger sits on
this seat, if not they chooses a other (free) seat at random (uniformly).

a) What is the probability the last passenger entering the plane gets
their allocated seat?
b) What is the average number of passengers seated in the incorrect seat
on each flight?
--
David Entwistle
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On 30/11/2025 08:31, David Entwistle wrote:

A well-known puzzle apparently - I don't think I'd seen it before it
appeared on the National Cipher Challenge a couple of week's ago. I've
added the part b) question.

There is a plane with 100 seats and we have 100 passengers entering the
plane one after the other. The first passenger cannot find their boarding pass, so chooses a random (uniformly) seat. All the other passengers do
the following when entering the plane (they have their boarding passes).
If the seat written on the boarding pass is free, the passenger sits on
this seat, if not they chooses a other (free) seat at random (uniformly).

a) What is the probability the last passenger entering the plane gets
their allocated seat?
b) What is the average number of passengers seated in the incorrect seat
on each flight?

I have answers. I'm reluctant to spoil (so I won't) because I
Monte Carlo'd it, but I have a question about the philosophy of
puzzles. What distinguishes this from a maths problem? That is,
what makes it a puzzle rather than an exercise?
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On 02/12/2025 00:44, Richard Heathfield wrote:

On 30/11/2025 08:31, David Entwistle wrote:

A well-known puzzle apparently - I don't think I'd seen it before it
appeared on the National Cipher Challenge a couple of week's ago. I've
added the part b) question.

There is a plane with 100 seats and we have 100 passengers entering the
plane one after the other. The first passenger cannot find their boarding
pass, so chooses a random (uniformly) seat. All the other passengers do
the following when entering the plane (they have their boarding passes).
If the seat written on the boarding pass is free, the passenger sits on
this seat, if not they chooses a other (free) seat at random (uniformly).

a) What is the probability the last passenger entering the plane gets
their allocated seat?
b) What is the average number of passengers seated in the incorrect seat
on each flight?

I have answers. I'm reluctant to spoil (so I won't) because I Monte Carlo'd it, but I have a
question about the philosophy of puzzles. What distinguishes this from a maths problem? That is,
what makes it a puzzle rather than an exercise?

I don't have a definition-style answer to the question. If the maths to be applied were obvious,
then it would just a maths problem. So there needs to be something beyond the routine maths.

Perhaps the maths could be "routine in principle, but excessively complicated" leading to the
expectation that the answer must be complicated, and pretty meaningless even if it were obtained.
Then the puzzle aspect is trying to look at the problem in the right way, and when this is achieved
the answer is seen to be both simple and obvious. That criterion seems to apply to the given
problem. (But also it would be fair to call it a maths problem, requiring some lateral thinking for
a clean solution.)

If someone employs complicated mathematics (say beyond high-school level) and comes up with the
correct answer, they can be said to have solved the maths problem, but if they can't explain the
answer in a few sentances to someone without advanced maths knowledge then they've not really
understood the "puzzle".


Mike.

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On Tue, 2 Dec 2025 00:44:23 +0000, Richard Heathfield wrote:

I have answers. I'm reluctant to spoil (so I won't) because I Monte
Carlo'd it, but I have a question about the philosophy of puzzles. What distinguishes this from a maths problem? That is, what makes it a puzzle rather than an exercise?

I'd say there may be an element of surprise (or disquiet) at the part a) answer too. I didn't find the first part answer 'obviously true' and as a result I may look a little harder and, possibly, gain deeper insight into
the problem. I'm getting old and tired now, but still wake up in the night thinking "that doesn't seem quite right, or at least not obvious". Part b) probably is more of an exercise, although considering fewer seats makes me think I could almost generate the solution from scratch.

I'm also using a Monte Carlos method, but wasn't happy with the first
version, which had the passengers boarding in order, so I wrote versions
where the passengers boarded in (pseudo) random order. The practice
writing code, especially if I try not to be too sloppy, is very welcome
for me. Looking, on paper, at the solution with a lot fewer seats helped provide insight.

A paper "Absent-minded passengers" by Norbert Henze and G|+nter Last goes
into some mathematical detail. I'd never normally read something like
that, but having tried to find my own solutions makes it all the more meaningful and readable.

When working, before I retired, I always found the training courses
covering a subject I was already working on, and to some extent struggling with, far more valuable than something that covered a completely new
subject.
--
David Entwistle
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

In article <10ggvc9$565j$1@dont-email.me>,
David Entwistle <qnivq.ragjvfgyr@ogvagrearg.pbz> wrote:

A well-known puzzle apparently - I don't think I'd seen it before it >appeared on the National Cipher Challenge a couple of week's ago. I've
added the part b) question.

A nice problem.

Solution to part (a).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Preliminary observations:

Let n be the number of seats (100, but we'll do it generally).
Label the passengers 1 .. n and their assigned seats similarly.

There's a 1/n probability that the first passenger will by chance take
their own seat. In that case, everyone else will be able to take
their own seat.

Otherwise they takes a wrong seat and the following are now true:

(1) Seat 1 is (wrongly) available.
(2) There is one unboarded passenger whose seat is (wrongly) already taken.

When a passenger boards the plane, one of the following happens:

(a) Their seat is available; (1) and (2) are unaffected, since their seat
is not seat 1 and they are not a passenger whose seat is wrongly taken.

(b) Their seat is wrongly taken, and they take a seat other than seat 1.
Now the number of unboarded passengers whose seat is wrongly taken
decreases by 1 (because this passenger is no longer unboarded), but
also increases by 1 (because they've taken the seat of an unboarded
passenger). Again (1) and (2) are unaffected.

(c) Their seat is wrongly taken, and they take seat 1. Now the number of
unboarded passengers with their seat wrongly taken decreases by 1,
and seat 1 is taken.

We see that there is always exactly one unboarded passenger whose seat
is wrongly taken until someone takes seat 1, at which point all the
remaining passengers will be able to take their own seat.

So the question is equivalent to asking what the probability is of someone taking seat 1 before the last passenger boards.

Solution:

Assuming that seat 1 has not yet been taken, the probability of
passenger i taking seat 1 is the chance of them being the unboarded
passenger whose seat is wrongly taken, times the chance of them
choosing seat 1 out of the available seats. There are n - (i-1)
unboarded passengers and n - (i-1) available seats, so this
probability is

1/(n - (i-1))^2

The probability of none of them before the last taking seat 1 is
therefore

(1 - 1/n) prod(i=2..n-1) (1 - 1/(n - (i-1))^2)

Writing j = n - (i-1) we get

(1 - 1/n) prod(j=2..n-1) (1 - 1/j^2)

= (n-1) / n prod(j=2..n-1) ((j-1)(j+1)/j^2)
= (n-1) / n prod(j=2..n-1) (j-1) prod(j=2..n-1) (j+1) / prod(j=2..n-1) j^2

The products cancel out except for their first and last terms, giving

(n-1) / n . 1/(n-1) . n/2

= 1/2

-- Richard


--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On 03/12/2025 16:06, Richard Tobin wrote:

In article <10ggvc9$565j$1@dont-email.me>,
David Entwistle <qnivq.ragjvfgyr@ogvagrearg.pbz> wrote:

A well-known puzzle apparently - I don't think I'd seen it before it
appeared on the National Cipher Challenge a couple of week's ago. I've
added the part b) question.

A nice problem.

Solution to part (a).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Preliminary observations:

Let n be the number of seats (100, but we'll do it generally).
Label the passengers 1 .. n and their assigned seats similarly.

There's a 1/n probability that the first passenger will by chance take
their own seat. In that case, everyone else will be able to take
their own seat.

Otherwise they takes a wrong seat and the following are now true:

(1) Seat 1 is (wrongly) available.
(2) There is one unboarded passenger whose seat is (wrongly) already taken.

When a passenger boards the plane, one of the following happens:

(a) Their seat is available; (1) and (2) are unaffected, since their seat
is not seat 1 and they are not a passenger whose seat is wrongly taken.

(b) Their seat is wrongly taken, and they take a seat other than seat 1.
Now the number of unboarded passengers whose seat is wrongly taken
decreases by 1 (because this passenger is no longer unboarded), but
also increases by 1 (because they've taken the seat of an unboarded
passenger). Again (1) and (2) are unaffected.

(c) Their seat is wrongly taken, and they take seat 1. Now the number of
unboarded passengers with their seat wrongly taken decreases by 1,
and seat 1 is taken.

We see that there is always exactly one unboarded passenger whose seat
is wrongly taken until someone takes seat 1, at which point all the
remaining passengers will be able to take their own seat.

So the question is equivalent to asking what the probability is of someone taking seat 1 before the last passenger boards.

Solution:

Assuming that seat 1 has not yet been taken, the probability of
passenger i taking seat 1 is the chance of them being the unboarded
passenger whose seat is wrongly taken, times the chance of them
choosing seat 1 out of the available seats. There are n - (i-1)
unboarded passengers and n - (i-1) available seats, so this
probability is

1/(n - (i-1))^2

The probability of none of them before the last taking seat 1 is
therefore

(1 - 1/n) prod(i=2..n-1) (1 - 1/(n - (i-1))^2)

Writing j = n - (i-1) we get

(1 - 1/n) prod(j=2..n-1) (1 - 1/j^2)

= (n-1) / n prod(j=2..n-1) ((j-1)(j+1)/j^2)
= (n-1) / n prod(j=2..n-1) (j-1) prod(j=2..n-1) (j+1) / prod(j=2..n-1) j^2

The products cancel out except for their first and last terms, giving

(n-1) / n . 1/(n-1) . n/2

= 1/2

-- Richard

To see this more simply (none of the formulas above required):
1. The first boarder starts a chain of displaced passengers, e.g.
- 1-->57-->24-->26-->94-->1
- 1-->41-->59-->28-->100-->...
Other passengers get to sit in their seat.
2. In the first example, the chain goes back to 1 before 100, so
the last passenger (100) gets to sit in his seat. :)
In the second example, the chain goes to 100 before getting
back to 1, so the last passenger (100) doesn't get to sit in his seat. :( 3. So whether the last passenger sits in his seat is determined by
whether the displacement chain reaches 1 or 100 first.
4. One of these must occur, and they are equally likely by symmetry,
so probability of both is 1/2.

Mike.


















--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

In article <10gq084$3imsj$1@dont-email.me>,
Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:

[much simpler solution]

Having found the answer I felt sure there must be a simple way to get
it, but I didn't find it.

-- Richard
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On 03/12/2025 19:44, Richard Tobin wrote:

In article <10gq084$3imsj$1@dont-email.me>,
Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:

[much simpler solution]

Having found the answer I felt sure there must be a simple way to get
it, but I didn't find it.

Having found a completely different answer I felt sure there must
be a simple way to get it, but I didn't find it.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On Wed, 3 Dec 2025 18:41:08 +0000, Mike Terry wrote:

4. One of these must occur, and they are equally likely by symmetry,

It's that statement that I struggled with. It is clearly true, but not
obvious to me, even when spelled out. Well done for being able to see
that. I got the right answer, but not that clarity.
--
David Entwistle
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On Wed, 3 Dec 2025 21:19:57 +0000, Richard Heathfield wrote:

Having found a completely different answer I felt sure there must be a
simple way to get it, but I didn't find it.

:)
--
David Entwistle
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles


David Entwistle <qnivq.ragjvfgyr@ogvagrearg.pbz> posted:

There is a plane with 100 seats and we have 100 passengers entering the plane one after the other. The first passenger cannot find their boarding pass...
...
b) What is the average number of passengers seated in the incorrect seat
on each flight?

I didn't see any solution to part (b) posted. I'll paste Hamlet's
soliloquy as spoiler space.

To be, or not to be- that is the question:
Whether 'tis nobler in the mind to suffer
The slings and arrows of outrageous fortune
Or to take arms against a sea of troubles,
And by opposing end them. To die- to sleep-
No more; and by a sleep to say we end
The heartache, and the thousand natural shocks
That flesh is heir to. 'Tis a consummation
Devoutly to be wish'd. To die- to sleep.
To sleep- perchance to dream: ay, there's the rub!
For in that sleep of death what dreams may come
When we have shuffled off this mortal coil,
Must give us pause. There's the respect
That makes calamity of so long life.
For who would bear the whips and scorns of time,
Th' oppressor's wrong, the proud man's contumely,
The pangs of despis'd love, the law's delay,
The insolence of office, and the spurns
That patient merit of th' unworthy takes,
When he himself might his quietus make
With a bare bodkin? Who would these fardels bear,
To grunt and sweat under a weary life,
But that the dread of something after death-
The undiscover'd country, from whose bourn
No traveller returns- puzzles the will,
And makes us rather bear those ills we have
Than fly to others that we know not of?
Thus conscience does make cowards of us all,
And thus the native hue of resolution
Is sicklied o'er with the pale cast of thought,
And enterprises of great pith and moment
With this regard their currents turn awry
And lose the name of action.- Soft you now!
The fair Ophelia!- Nymph, in thy orisons
Be all my sins rememb'red.
- - - - - - - - - - - - - - - -

The mapping between assigned seat and actual seat is a permutation
with all but one cycle singletons. What is the average length of the
cycle containing the confused passenger?

There is a 1/100 (or 1/N) chance the cycle-size is just 1; a
99/100 x 1/99 chance of size 2, 99/100 x 98/99 x 1/98 chance of 3,
and so on. Those complicated products each reduce to 1/100 (or 1/N).
So the average cycle length is (1/N) x (1 + 2 + 3 + ... + N) which is
(N+1)/2.

But the confused passenger gets their assigned seat when the cycle size
is 1, so that case must be subtracted for a final answer of
(N+1)/2 - 1/N
or 50.49

Cheers,
James
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles


Richard Heathfield <rjh@cpax.org.uk> posted:

... I have a question about the philosophy of
puzzles. What distinguishes this from a maths problem? That is,
what makes it a puzzle rather than an exercise?

One part of the answer is that a puzzle should short-circuit
tedious math.

As an example, after I posted a solution to the confused passenger problem
just moments ago, I realized that I'd made it much harder than necessary.
The answer is so simple that others had doubtless already mentioned it
but so briefly I didn't notice.

Others shown that each non-confused passenger has a 1/2 chance of failure,
for an average total of (N-1)/2. Add to this the confused passenger's failure rate of (N-1)/N and immediately get the same answer I gave.

- - - - - - - -

Following is a fun(?) puzzle. It's math no matter how you do it, but the choice is fun math vs tedious math. (This puzzle appeared on IBM's
Ponder This several years ago. IIRC it was first posed and solved
by the great 19th-century mathematician J.J. Sylvester.)

You are given a square with unit area. (In fact, you'll get the same
answer starting with any parallelogram of unit area.)
Pick three points uniform randomly inside the square.
What is the expected (average) area of the triangle those three points form?

Three approaches to solution are:
(1) Monte Carlo simulation
(2) Sextuple definite integration of Heron's formula
(3) Trimming away parts of the square one side at a time

I presented this puzzle to some math types. Both solvers wrote
the sextuple integral and fed that into a solver like Wolfram or Matlab.
UGH! Method (3) is much simpler, and more fun ... though still
much more mathy than puzzley.

Cheers,
James
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

In article <10gqiof$3plqj$1@dont-email.me>,
David Entwistle <qnivq.ragjvfgyr@ogvagrearg.pbz> wrote:

It's that statement that I struggled with. It is clearly true, but not obvious to me, even when spelled out. Well done for being able to see
that. I got the right answer, but not that clarity.

I like the phrasing of the solution in which we ask the first
passenger to move, which I think also makes that symmetry clearer.

The first passenger (let's call him Bob) gets on and sits in some random
seat. The other passengers get on and take their seats freely, until we
get the passenger (let's call her Susan) whose seat Bob has taken. At
this point, Susan asks Bob to move. Bob sighs, gets up, and chooses a
new seat at random.

This is equivalent to the original problem in terms of which seats are occupied. The only differences are that we now have Bob taking the new
seat rather than Susan, and that Susan gets her own seat rather than
also being displaced.

In this approach, as passengers 2 to 99 get on, they will all sit in
their own seat, and Bob will keep being asked to change seat whenever
he's in the seat of the next passenger, until at some point he ends up
either in seat 100 or his own seat 1.

In other words, whatever happens along the way, Bob will end up in
either seat 1 or seat 100, and each is equally likely. So, when the
last passenger gets on, they get seat 100 with probability 1/2.

Gareth
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On 05 Dec 2025 08:57:20 +0000 (GMT), Gareth Taylor wrote:

I like the phrasing of the solution in which we ask the first passenger
to move, which I think also makes that symmetry clearer.

Ah, yes. Very nice.
--
David Entwistle
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On 05/12/2025 05:34, James Dow Allen wrote:

David Entwistle <qnivq.ragjvfgyr@ogvagrearg.pbz> posted:

There is a plane with 100 seats and we have 100 passengers entering the
plane one after the other. The first passenger cannot find their boarding
pass...
...
b) What is the average number of passengers seated in the incorrect seat
on each flight?

I didn't see any solution to part (b) posted. I'll paste Hamlet's
soliloquy as spoiler space.

To be, or not to be- that is the question:
Whether 'tis nobler in the mind to suffer
The slings and arrows of outrageous fortune
Or to take arms against a sea of troubles,
And by opposing end them. To die- to sleep-
No more; and by a sleep to say we end
The heartache, and the thousand natural shocks
That flesh is heir to. 'Tis a consummation
Devoutly to be wish'd. To die- to sleep.
To sleep- perchance to dream: ay, there's the rub!
For in that sleep of death what dreams may come
When we have shuffled off this mortal coil,
Must give us pause. There's the respect
That makes calamity of so long life.
For who would bear the whips and scorns of time,
Th' oppressor's wrong, the proud man's contumely,
The pangs of despis'd love, the law's delay,
The insolence of office, and the spurns
That patient merit of th' unworthy takes,
When he himself might his quietus make
With a bare bodkin? Who would these fardels bear,
To grunt and sweat under a weary life,
But that the dread of something after death-
The undiscover'd country, from whose bourn
No traveller returns- puzzles the will,
And makes us rather bear those ills we have
Than fly to others that we know not of?
Thus conscience does make cowards of us all,
And thus the native hue of resolution
Is sicklied o'er with the pale cast of thought,
And enterprises of great pith and moment
With this regard their currents turn awry
And lose the name of action.- Soft you now!
The fair Ophelia!- Nymph, in thy orisons
Be all my sins rememb'red.
- - - - - - - - - - - - - - - -

The mapping between assigned seat and actual seat is a permutation
with all but one cycle singletons. What is the average length of the
cycle containing the confused passenger?

There is a 1/100 (or 1/N) chance the cycle-size is just 1; a
99/100 x 1/99 chance of size 2, 99/100 x 98/99 x 1/98 chance of 3,
and so on. Those complicated products each reduce to 1/100 (or 1/N).
So the average cycle length is (1/N) x (1 + 2 + 3 + ... + N) which is (N+1)/2.

But the confused passenger gets their assigned seat when the cycle size
is 1, so that case must be subtracted for a final answer of
(N+1)/2 - 1/N
or 50.49

Cheers,
James

I get the same.

Another approach, using Indicator RVs [random variables]... For each passenger k, define a RV:

I_k = 1 if passenger k is displaced (doesn't get to sit in his own seat)
= 0 otherwise (i.e. the passenger gets his own seat)

and D = number of displaced passengers

Then D = SUM(k=1 to 100) I_k

So E(D) = E(SUM(k=1 to 100) I_k) [E(X) meaning expectation of X]
= SUM(k=1 to 100) E(I_k)

and E(I_k) [expectation of I_k] is easy to work out for each k:

for k=1, I_1 = 1 if first passenger chooses a seat other than his own, so
p(I_1 = 1) = 99/100, and E(I_1) = 99/100.

for k = 2,3,..100, we worked out elsewhere the passenger is displaced with prob 1/2, so E(I_k) =
1/2. [Basically, the passenger is displaced if the cycle of displacements started by the first
passenger reaches the first passengers own seat before passenger k's seat. By symmetry either
possibility is equally likely.]

So E(D) = E(I_1) + 99*E(I_2)
= 0.99 + 99*0.5 = 0.99 + 49.5
= 50.49

[Since someone often asks this, I'll add that E(X+Y) = E(X)+E(Y) for RVs X and Y holds
/regardless of whether X and Y are independent/. It's true the indicator RVs I_k are not
independent, but that does not matter...]


Mike.

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

In article <1764912868-4353@newsgrouper.org>,
James Dow Allen <user4353@newsgrouper.org.invalid> wrote:

There is a 1/100 (or 1/N) chance the cycle-size is just 1;

- that is, the first passenger happens to take their own seat

a 99/100 x 1/99 chance of size 2

- no; the chance that the passenger displaced by the first passenger
takes the first seat is not 1/99 unless they happen to be the
second passenger.

Simulation gives an average number of displaced passengers of about 5.2.

-- Richard
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On Fri, 05 Dec 2025 06:34:25 GMT, James Dow Allen <user4353@newsgrouper.org.invalid> wrote:

Richard Heathfield <rjh@cpax.org.uk> posted:

... I have a question about the philosophy of
puzzles. What distinguishes this from a maths problem? That is,
what makes it a puzzle rather than an exercise?

Perhaps, some maths problems evolve into puzzles?

One part of the answer is that a puzzle should short-circuit
tedious math.

As an example, after I posted a solution to the confused passenger problem >just moments ago, I realized that I'd made it much harder than necessary.
The answer is so simple that others had doubtless already mentioned it
but so briefly I didn't notice.

Coming from a physics background, I have seen this often. One arrives
at a result after torturous maths (mind you, you do *know*,
beforehand, that a result exists when you doing real research) and
once you have it, it all seems so simple. A few hours/days later the proverbial "physical intution" (whatever that may be) kicks in and
suddenly it is "Its really quite obvious isn't it? Once you get the
physics behind it, you really do not need all the stuff ...", etc.

The next step is making the maths more economic, now that one
has the result. Which, in turn, leads to, "I don't know why did
all that before. It is so straightforward".


--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On 06/12/2025 16:22, Mike Terry wrote:

On 05/12/2025 05:34, James Dow Allen wrote:

David Entwistle <qnivq.ragjvfgyr@ogvagrearg.pbz> posted:

There is a plane with 100 seats and we have 100 passengers entering the
plane one after the other. The first passenger cannot find their boarding >>> pass...
...
b) What is the average number of passengers seated in the incorrect seat >>> on each flight?

I didn't see any solution to part (b) posted.a I'll paste Hamlet's
soliloquy as spoiler space.

aaaa To be, or not to be- that is the question:
aaaa Whether 'tis nobler in the mind to suffer
aaaa The slings and arrows of outrageous fortune
aaaa Or to take arms against a sea of troubles,
aaaa And by opposing end them. To die- to sleep-
aaaa No more; and by a sleep to say we end
aaaa The heartache, and the thousand natural shocks
aaaa That flesh is heir to. 'Tis a consummation
aaaa Devoutly to be wish'd. To die- to sleep.
aaaa To sleep- perchance to dream: ay, there's the rub!
aaaa For in that sleep of death what dreams may come
aaaa When we have shuffled off this mortal coil,
aaaa Must give us pause. There's the respect
aaaa That makes calamity of so long life.
aaaa For who would bear the whips and scorns of time,
aaaa Th' oppressor's wrong, the proud man's contumely,
aaaa The pangs of despis'd love, the law's delay,
aaaa The insolence of office, and the spurns
aaaa That patient merit of th' unworthy takes,
aaaa When he himself might his quietus make
aaaa With a bare bodkin? Who would these fardels bear,
aaaa To grunt and sweat under a weary life,
aaaa But that the dread of something after death-
aaaa The undiscover'd country, from whose bourn
aaaa No traveller returns- puzzles the will,
aaaa And makes us rather bear those ills we have
aaaa Than fly to others that we know not of?
aaaa Thus conscience does make cowards of us all,
aaaa And thus the native hue of resolution
aaaa Is sicklied o'er with the pale cast of thought,
aaaa And enterprises of great pith and moment
aaaa With this regard their currents turn awry
aaaa And lose the name of action.- Soft you now!
aaaa The fair Ophelia!- Nymph, in thy orisons
aaaa Be all my sins rememb'red.
a - - - - - - - - - - - - - - - -

The mapping between assigned seat and actual seat is a permutation
with all but one cycle singletons.a What is the average length of the
cycle containing the confused passenger?

There is a 1/100 (or 1/N) chance the cycle-size is just 1; a
99/100 x 1/99 chance of size 2, 99/100 x 98/99 x 1/98 chance of 3,
and so on.a Those complicated products each reduce to 1/100 (or 1/N).
So the average cycle length is (1/N) x (1 + 2 + 3 + ... + N) which is
(N+1)/2.

But the confused passenger gets their assigned seat when the cycle size
is 1, so that case must be subtracted for a final answer of
aaaa (N+1)/2 - 1/N
or 50.49

Cheers,
James

I get the same.

Oh dear. My previous answer was rubbish! :(

Richard is right - the answer should be just a handful of passengers. His 5.2 seems plausible.

Another approach, using Indicator RVs [random variables]...aa For each passenger k, define a RV:

a I_k = 1aaa if passenger k is displaced (doesn't get to sit in his own seat)
aaaaa = 0aaa otherwise (i.e. the passenger gets his own seat)

and D = number of displaced passengers

Then D = SUM(k=1 to 100) I_k

So E(D) =a E(SUM(k=1 to 100) I_k)aaaaaa [E(X) meaning expectation of X]
aaaaaaa =a SUM(k=1 to 100) E(I_k)

and E(I_k) [expectation of I_k] is easy to work out for each k:

<cough> um, not so much...

for k=1, I_1 = 1 if first passenger chooses a seat other than his own, so p(I_1 = 1) = 99/100, and E(I_1) = 99/100.

That bit's right :)

for k = 2,3,..100, we worked out elsewhere the passenger is displaced with prob 1/2, so E(I_k) =
1/2.a [Basically, the passenger is displaced if the cycle of displacements started by the first
passenger reaches the first passengers own seat before passenger k's seat.a By symmetry either
possibility is equally likely.]

But this is all wrong. E.g. obviously the second passenger to board has a 99% chance of getting his
seat, not 50%.

My argument would only work if the passengers boarding order was arranged by the cabin crew so that
all the displaced passengers are called for boarding as soon as their seat is occupied, before
allowing all the remaining passengers to board, which is complete nonsense. Doh!

The problem is more like some kind of discrete "random decay" problem, like there are 100 sweets,
and children come up sequentially, taking a random number of the remaining sweets until they're all
gone: how many children get sweets? (But not quite random decay, because each child takes at least
one sweet...)

Not as easy as I first thought...

Mike.

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: rec.puzzles

On 30/11/2025 08:31, David Entwistle wrote:

A well-known puzzle apparently - I don't think I'd seen it before it
appeared on the National Cipher Challenge a couple of week's ago. I've
added the part b) question.

There is a plane with 100 seats and we have 100 passengers entering the
plane one after the other. The first passenger cannot find their boarding pass, so chooses a random (uniformly) seat. All the other passengers do
the following when entering the plane (they have their boarding passes).
If the seat written on the boarding pass is free, the passenger sits on
this seat, if not they chooses a other (free) seat at random (uniformly).

a) What is the probability the last passenger entering the plane gets
their allocated seat?
b) What is the average number of passengers seated in the incorrect seat
on each flight?

Here's my second attempt at part (b), the average number of displaced passengers.


.s......
..p.....
..o.....
.i......
..l.....
...e....
....r...
.....s..
.....p..
....o...
.....i..
......l.
......r.
.....r..
....s...
...p....
..o.....
..i.....
...l....
..e.....
.r......
.s......
..p.....
..o.....
.i......
..l.....
...e....
....r...
.....s..
.....p..
....o...
.....i..
......l.
......r.
.....r..
....s...
...p....
..o.....
..i.....
...l....
..e.....
.r......


The average number of displaced passengers is

360968703235711654233892612988250163157207 / 69720375229712477164533808935312303556800

which is roughly 5.1773775176... !

I don't have a formula for n-seats, but my calculation is exact, and uses a recursion relation based
on the number of seats, which I'll try to explain.

The problem is /almost/ the same as the following "children grabbing sweets" problem, which I think
is easier to follow and to describe. In this new problem we have a pile of n sweets, and in turn
children remove a random number sweets from the pile, from 1 to n sweets. How many children get
sweets? The number of sweets goes down with each child, so the answer will be between 1 and n, and
we want the /average/ number of children. Let's solve this puzzle first!

E.g. starting with 5 sweets, the first child might take 2, leaving 3 sweets, and the second child
might take all 3 remaining sweets emptying the pile. I write that as

5 -> 3 -> 0

and in this case 2 children got sweets. For a pile of n sweets, define

C(n) = expected number of children who get sweets.

If a child takes sweets reducing the pile n -> m sweets, then that one child has got sweets, and the
remaining m sweets on average will feed C(m) more children. The first child is equally likely to
reduce the sweet pile to n-1, n-2, ...2, 1 or 0. So there is a recursion relation:

C(n) = 1/n * ( [1+C(0)] + [1+C(1)] + ... + [1+C(n-1] )
= 1 + 1/n * ( C(0) + C(1) + ... + C(n-1) )

Now we can [write a program to] calculate successively C(1), C(2), C(3),... as far as we need (e.g.
up to n=100), recording each result in an array for later use. Hmm, we need to start the recursion
somewhere, and we can do that at C(0) = 0: a pile of 0 sweets feeds 0 children on average!

So if we do this, we get:

n average # children
--- --------------------
0: 0
1: 1
2: 3/2
3: 11/6
4: 25/12
5: 137/60
...

[These entries may be low enough to check the arithmetic/logic by hand...]

So now we go back to the airline/displaced passengers problem! How does it relate to the sweets
problem?

The children are like the /displaced/ passengers in the airline problem, and the sweets are like the
seats. When the first passenger chooses a random seat, that's like the first child grabbing a
random number of sweets. E.g. assuming the passengers are queued in seat order to start with,
passenger 1 could randomly choose seat 73. That's like taking out seats 2-73, leaving 28 seats -
equivalent to the first child reducing the sweet pile to 28. Passengers 2-72 will all get their
seats, then passenger 73 will be displaced - he is like the second child who gets to pick sweets,
and he can only choose from the 28 remaining seats!

So continuing, passenger 73 chooses a random seat. If he chooses seat 99, there are now only 2
seats left: seat 1 and 100. (That's like the second child removing all but 2 sweats from the pile.)

And so on. If a displaced passenger chooses seat 1, that effectively means all seats are "removed"
from the game as everybody from now on gets their own seat. (So logically we should visualise seat
1 being the last sweet in the pile, not the first - one reason why the child/sweet game is simpler
to describe...)

And every displaced passenger to be counted corresponds to one of our children in the sweet game - EXCEPT... /Just for the first passenger/, if he randomly chooses seat 1 [i.e.
empties the sweet pile], he does not count as a displaced passenger! WHEREAS... in the sweet game,
if the first child takes all the sweets that counts as ONE child fed, not zero. This is the only
real difference between the airline game and the sweet game, where the correspondence breaks down.

That's a pain, but easy to adjust for. If we define

D(n) = expected number of displaced passengers.

Then we have

D(n) = 1/n * ( 0 + [1+C(1)] + ... + [1+C(n-1] )

[On the right, we have C(k)s appearing, not D(k)s, because after the first passenger has chosen, the
game becomes /exactly/ like the child/sweets game - if the 2nd displaced passenger "empties the
sweet pile" by choosing seat 1, he /does/ count as a displaced passenger...]


Comparing this with C(n) formula from above:

C(n) = 1/n * ( [1+C(0)] + [1+C(1)] + ... + [1+C(n-1] )

we see it's nearly the same, and only differs by one term. Since C(0) = 0 that term contributes an
extra 1/n to C(n), so

D(n) = C(n) - 1/n

That's basically it! Here's the start of the C(n) table from above, with D(n) appended:

n C(n) D(n)
--- ------------------
0: 0
1: 1 0 = 0.0000000000
2: 3/2 1 = 1.0000000000
3: 11/6 3/2 = 1.5000000000
4: 25/12 11/6 = 1.8333333333
5: 137/60 25/12 = 2.0833333333
...

(Remember: C(n) = fed children average in sweet game;
D(n) = displaced passengers average in airline boarding game)

My answer above for the 100 passengers problem (average = 5.1773775176...etc.) is D(100) in the
above table.

Given my recent record, that might well be nonsense too, but I've more confidence this time! :)
Maybe I'll still end up eating some humble pie, but it's nearly Christmas, so that's ok.

Mike.

--- Synchronet 3.21a-Linux NewsLink 1.2