Helmut Prodinger: Two Applications of the Kernel Method: A Simple Guessing Game and a Functional Equation

A trick by Don Knuth eventually evolved into the so-called Kernel method. It is used to solve a certain type of recursions. We report about some applications. One is like this:

A deck of cards consisting of $m$ red and $n$ black cards is given. A guess is made as to the colour of the top card, after which it is revealed and discarded. To maximise the number of correct guesses one chooses the colour corresponding to the majority of cards remaining in the deck. We determine the expected number of correct guesses with this strategy, as well as the probability of beating an opponent (a child) who uses the naive strategy of random guessing.

Back to the Index

Please send comments and corrections to Thomas Klausner.