Algorithmic Problem Solving

Solutions to Exercises

Solution 2.1  1233 games must be played. Let k be the number of players who have been knocked out, and let g be the number of games that have been played. Initially, k and g are both equal to 0. Every time a game is played, one more player is knocked out. So, k and g are always equal. To decide the tournament, 1234−1 players must be knocked out. Hence, this number of games must be played.

In general, if there are p players, the tournament consists of p−1 games.

Solution 2.4  Introducing variables b and e as before, filling boxes is modelled by the assignment

b,e := b+k,e+k−1.

The value of (k−1)×b−k×e is invariant. Its initial value is −m. So, when the process of filling boxes is complete,

(k–1)×b–k×n=−m.                                                                      (S.1)

Assuming and simplifying, we get that . For the problem to be well formulated, we require this to be a natural number. That is, we require that n is at least m, k is at least 2 and n−m is a multiple of k−1.

When k is 1, (S.1) simplifies to n=m. That is, the number of empty boxes remains the same. However, the number of boxes cannot be determined.

Solution 2.5  The ball problem is modelled by the choice

b,w := b+1,w−2 b, w := (b−2)+1,w b, w := b−1,w.

In order, the assignments model what ...