Dodgson and Loyd
Introduction
Zoubin kicked off his tea talk on the 'Dutch book' with the following problem that can be solved by applying Bayes' theorem:
A bag contains a counter, known to be either white or black. A white counter is
put in, the bag is shaken, and a counter is drawn out, which proves to be white. What
is now the chance of drawing a white counter?
This problem occurs in the Pillow Book of Rev. Charles Lutwidge Dodgson.
This was written under the claim that the numerous puzzles it contained would cure the reader's insomnia.
Dodgson's pseudonym
This was not the author's best known work:
He Latinized his real name, reversed and Anglicised to generate the pseudonym Lewis Carroll
under which he wrote Alice in wonderland and Alice through the looking glass.
Dodgson the man
1832-1898
- Mathematician who lived on a fellowship of £25 a year at Oxford.
- He had a bad stammer.
- He invented the word 'chortle' - combination of 'chuckle' and 'snort'.
- He married his cousin and was deeply unhappy in the relationship.
Dodgson the mathematician
- He worked on understanding logic as if it were a game - 50 yrs before von Neumann invented game theory.
- He invented truth tables and matrices.
- He used trees to solve logic problems.
He wrote 3 pamphlets on elections and committees, which it is argued;
"...anticipates a stochastic model proposed by Thompson and Remage in 1964
and includes ideas that are basic to maximum likelihood estimation and game theory."
Dodgson's elections
Dodgson considered pairwise voting preferences in elections involving more than one person
he noted as the Marquis de Condorcet had before him that:
"Collective preferences can be cyclic even though the preferences of individuals are not - majority wishes can be in conflict with each other."
He fixed the system by choosing the winner as the candidate who with the fewest changes in voters' preferences becomes a Condorcet winner-a candidate who beats all other candidates in pairwise majority-rule elections.
| pref | pairs | no. voters |
|---|
| | 1>2 | 1>3 | 2>3 | Ex. 1 | Ex. 2 | Ex. 3 |
| 123 | 1 | 1 | 1 | 0 | 1 | 2 |
| 231 | 0 | 0 | 1 | 0 | 1 | 1 |
| 312 | 1 | 0 | 0 | 1 | 1 | 1 |
| 132 | 1 | 1 | 0 | 1 | 0 | 0 |
| 213 | 0 | 1 | 1 | 1 | 0 | 0 |
| 321 | 0 | 0 | 0 | 0 | 0 | 0 |
Example 1.
First past the post: 3 way tie
Condorcet: 1 wins (1>2 2/3rds, 1>3 2/3rds 2>3 1/3rd)
Example 2.
First past the post: 3 way tie
Condorcet: confusion (1>2 2/3rds, 2>3 2/3rds 3>1 2/3rds)
Example 3.
First past the post: 1 wins
Condorcet: confusion (1>2 3/4, 1>3 1/2 2>3 3/4)
Dodgson: 1 wins (1 has score 1, 2 score 2, and 3 score 3 )
However, generally it is NP hard to determine the winner under this scheme
- enter Arrow, Mackay etc.
Another problem from the Pillow Book
A cable hangs over a frictionless pulley. Now a weight which exactly balances
the monkey hanging on the other side is attached to a massless cable.
What happens to the weight if the monkey tries to climb up the cable?
This problem perplexed Dodgson and he never solved it despite help from the most famous puzzle inventor of the time; Sam Loyd.
Sam Loyd
Loyd was a;
- mathematician
- plumbing contractor
- music store chain owner
- wood engraver
- a skilled cartoonist (he drew the previous illustration for Dodgson)
- He was also a puzzle inventor (10,000 in his life time).
A typical Loyd puzzle
"Move the blocks about to bring them back to the present position in every respect except that the error in the 14 and 15 was corrected."
A prize of $1000, offered for the first correct solution to the problem, has never been claimed, although there are thousands of persons who say they have performed the required feat.
People became infatuated with the puzzle and there are stories of:
- the New York Times reports twice on the craze in 1880
- A famous Baltimore editor tells how he went for his noon lunch and was discovered by frantic staff long past midnight pushing little pieces of pie around on a plate
- Employers put up notices prohibiting playing the puzzle during office hours
- In France it was described as a "greater scourge than alcohol or tobacco"
Loyd knew his $1000 was safe: the puzzle cannot be solved - only pairs of numbers can be transposed without cheating.
A second puzzle from Loyd
Count the people, wait for the pieces to move, and count the people again;
An explanation of the vanishing puzzle
The basic trick:
But how do we place the people when we have vertical cuts too?
A final quote and his obituary in the Times
"Ideas came to [Loyd] with great fecundity, often too rapidly for him to analyse them completely. Yet his powers for rapid analysis were almost unrivalled. He could see an idea from many sides at once; first always from the point of view of a puzzle, then from the humorous standpoint, finally from the artistic aspect."
Richard Turner
Gatsby Computational Neuroscience Unit
Alexandra House
17 Queen Square
LONDON
WC1N 3AR
|
