aez-notes

(a) Suppose King Arthur holds a jousting tournament where the jousts are in pairs as in a tennis tournament. See Problem 16 for tournament ladder. The \(8\) knights in the tournament are evenly matched, and they include the twin knights Balin and Balan. What is the chance that the twins meet in a match during the tournament?

(b) Replace \(8\) by \(2^n\) in the above problem. Now what is the chance that they meet?

We are asked the probability that they meet given they have 0.5 probability of winning any matches and they are uniformly distributed across the initial runs of the tournament ladder. We will use the law of total probability to solve this, partitioning on how many matches until they could possibly meet.

If there are \(2^n\) jousters, then the probability that they could meed after \(i\) matches is \(2^{i-1} / (2^n - 1)\). The probability that they survive the \(i\) matches in order to meet up is \((1/2^{i-1})^2\).

The probability is then just a simple evaluation of a sum to find that the probabilit y is \(2^{1-n}\).

load(simplify_sum);

f(n) := sum(2 ^ (1-i) / (2^n - 1), i, 1, n);

assume(n > 1);
declare(n, integer);
facts();
is(equal(simplify_sum(f(n)), 2 ^ (1-n)));

Note the use of assume and declare allows the simplify_sum function to confirm that the expressions are equal.