Resumen de Yet more frogs

Paul Shutler

• 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.