Yet more frogs

Abstract

Extending a recent paper by Derek Holton, we show how to represent the algorithm for the Frog Problem diagrammatically. This diagrammatic representation suggests a simpler proof of the symmetrical case (equal numbers of frogs of each colour) by allowing the even and odd cases to be treated together. It also provides a proof in the asymmetrical case (unequal numbers of frogs) as an extension of the symmetrical case. The issue of whether frogs of a given colour should be allowed to move in either direction is discussed. While it is possible to restrict to the case of movement in a single direction, results for bi-directional movement can be obtained by making the correspondence between the algorithm and its diagrammatic representation more concrete. The Frog Problem then becomes a form of constrained shortest path problem around the diagram, and from this point of view optimality of the algorithm becomes much clearer.

Keywords:

• the Frog Problem
• induction
• combinatorics

Acknowledgements

The author would like to thank Prof. Holton for his introduction to the Frog Problem as well as several helpful discussions which contributed towards the writing of this article.