Past exam of the computer science course of the University of Oxford / 2023 / Artificial intelligence / 2 / f / Solution

Partition the items into successive groups of size two, with a singleton final group if $n$ is odd. For a pair $(x,y)$ on the east bank, executeFor a singleton $x$, executeReturn the empty boat east between groups. Each group starts and ends with marker $q_0$, and its items finish west, proving all preconditions and the final goal by mathematical induction over the groups. For $n\ge 1$ there are $\lceil n/2\rceil$ outward journeys and $2\lceil n/2\rceil -1$ crossings in total; $\lceil \cdot \rceil$ is the ceiling function. Again $n=0$ needs no actions.