Mathematical induction games

Contributors

• Zerui Qian, Department of Physics, Student partner from October 2021
• Kelly Chang, Department of Medical Biosciences, Student partner from October 2021
• Max Bingham, Department of Physics, Student partner from October 2021
• Deniz Aydin, Department of Mathematics, Student partner from October 2021

• Mark Wheelhouse, Department of Computing. Staff partner from October 2021.

Staff Partner's Brief

1. Visualising "The Game of Frogs"

This is a thought experiment to get students thinking about Mathematical Induction. We would like to have a visualisation for this little game that will allow the students to experiment with the idea (number of frogs, starting speeds, etc).

The core learning outcome here is that a student should be able to provide an inductive argument to answer why all of the frogs will eventually fall off of the plank.

2. Visualising "The beetle and the cactus".

This is a thought experiment to get students thinking about Mathematical Induction. We would like to have a visualisation for this scenario that will allow the students to experiment with the idea (e.g. initial cactus set-up and beetle's rules). The core learning outcome here is that a student should be able to provide an inductive argument to show why the beetle can (and will) eventually consume the whole cactus. This thought experiment has also been referred to as "Hercules and the Hydra" and has an existing online visualisation.

I'd be happy with the students only tackling one of these two visualisations (not that I would be unhappy if they did both!) - Mark

Aims & Learning Outcomes

These two game visualisations will be shown during a lecture of COMP400018 - Discrete Mathematics, Logic and Reasoning. They will also be available for self-study so that students can validate what we have discussed in the lecture.

The two thought experiments are intended as playgrounds for developing an intuition for mathematical induction. Mathematical Induction is a technique for proving statements about a class of mathematical objects. The core idea is that if a statement is true for the first object in a sequence, and it being true for one object means that it is true for the next, then the statement must be true for all objects in the sequence. This can later be generalised to "structural induction", where the objects need not form a linear sequence but instead can be a part of any recursively defined structure, such as a tree.

The first thought experiment is "The Game of Frogs", where n frogs slide back and forth on a 1-dimensional frictionless log. If two frogs collide, they bounce off eachother, and if they reach the end of the log they fall into the water and are removed from the game. It seems obvious that each frog must eventually fall into the water, but how can one prove this? After the lecture, the students should be able to provide such an inductive argument.

The second is "The Beetle and the Cactus" (also known as the Kirby-Paris Hydra). A beetle is attempting to eat a cactus which has a tree structure, where every segment can have other segments branching off of it. When it eats one of the outermost "leaf" segments the segment immedietly before it gets duplicated, along with every one of it's descendents. The question is whether or not the beetle can finish off the whole cactus. At first the cactus appears to grow exponentially making the task seem impossible, but the surprising fact is that not only can the beetle eat the whole cactus regardless of the starting configuration, it cannot be avoided so long as it keeps eating. The inductive argument here is more complicated, as the cactus can get bigger before it gets smaller. Because of this a a complete proof is not expected from the students, but it would be nice for them to be able to describe a rough overview of how such an argument would work.

For our visualisation, Mark has stated that it is not strictly necessary for the inductive arguments to be explained within the visualisation for them to be of use in his lecture. The main intent is for the visualisation to make the abstract thought experiments more real for the students to play with and the teaching will be done around them. Our designs will at least have self contained instructions for use, but we may consider including an overview of the inductive arguments.

Design Overview

By our staff partner's reccomendation we focused on fleshing out one of the visualisation designs while viewing the other as a bonus task.

We provide:

• A blueprint for a visualisation of "The Game of Frogs", suitable for use in lectures or as a self-contained learning tool. Educational, Graphical, and Interaction design factors have been considered.
• A javascript prototype for "The Beetle and the Cactus" tackling some of the technical problems involved in visualising this thought experiment.

The Game of Frogs

In The Game of Frogs, you swim or you die.

Page 1 is an introduction explaining the motiviation of induction in the context of computer science

Page 2 introduces the setup, explaining the rules. Note: The completed visualisation should display the water the log is floating on

Clicking the start button begins the animation, which runs until all frogs fall off. The user is then asked to consider whether this happens in general before moving on to the next page.

Page 3 is the main visualisation. Users can change the number of frogs, the speed and direction of each individual frog and then observe the results.

Screenshot of the inital configuration.

The Beetle and the Cactus

Link to prototype

(Note: this link is live so functionality may break or change as I work on it. Reported not to work on some (Kelly's) browsers, should be fine on mobile now though)

Click on the leaf (pink) segments and watch the magic! Code can be seen by clicking the button in the top right.

Design Justification

Education Design

Though this was not a requirement in the brief, I felt as though it was necessary to provide context for why this topic matters in computer science. The explanation here would have been totally different if this was for a mathematics course, but I thought computing students would like to have the direct connection to computer programs explained. The decisions on what variables the user should control and what should be emphasized was also based on the educational context.

I would not say our visualisation alone fits the learning outcome specified in the brief as we did not get on to explaining the inductive argument, but I think this isn't so bad as it is intended to be a tool used alongside lectures to get the students thinking about how they would construct such an argument themselves. If we straight up told them the answer there wouldn't be much point in the interactive visualisation. However, an extra page detailing the argument is listed in potential future work.

Graphical Design

A key goal of the design process was to have the abstract mathematical problem appear more familiar to the user, in order to keep them actively engaged. We chose to implement the conventional icons like the start/stop/pause buttons one would expect in any interactive animation; the user does not need to be reminded what the purpose of these are and so we save clutter on the display by using them. Given the theme of animals we also thought a nice touch would be to include hare/snail symbols to indicate the speeds of the frogs.

We chose also to implement the conventional start/stop/pause buttons one would expect in any interactive animation

The red (wood), green (frog), and blue (water) colour scheme is vibrant and complements Imperial's own colour scheme which we use in our UI. We felt this choice would look engaging and clear in its simplicity, as well as be consistent as an ImpVis visualisation.

We wanted the configuration of the game to be highly interactive for the user; enabling them to customise the speeds of the frogs individually with sliders allows them to get their hands on the problem at hand in an engaging way. By implementing vertical sliders we simultaneously provide this option to the user, and take up dead space caused by the one-dimensional horizontal aspect of the game.

To keep from the visualisation feeling plain, one possible feature of an implementation of this design could be a page transition in which the log, frogs, etc. are dropped onto the screen (featuring water) at the start of a new page, and drift offscreen at the end of one.

In keeping with mathematical conventions, the velocities of the frogs are indicated by vectors to provide feedback for when the user changes them. In an extreme case of many frogs being hard to keep track of, we can employ a colour scheme to indicate the parity (direction) of their motion.

Interaction Design

In the main visualisation, buttons that start, pause, and reset the game are located at the upper left corner of the visualisation section. All buttons have icons, and in many cases these are so universal and familiar that text labels are not necessary. Buttons that cannot be interacted with at the current moment are "grayed out". Otherwise all buttons are colour-coded: yellow for pause, red for reset, green and red for adding and removing frogs.

We had much discussion about what parameters the user need to change as being able to control every detail could get overwhelming. We decided on these:

Number of Frogs

A frog counter is located at the upper left corner of the visualisation section. The number of frogs on the log, and number of frogs fallen off the log are shown, though the latter is greyed out while the simulation is not running as it conveys no useful information at that point. Even though you can infer the number of frogs remaining by looking at the image we still believe it is key information that needs to be emphasized as it is the core of the inductive argument. Users can control the number of frogs by clicking add and remove frog buttons, or typing in a number directly into the box if they wish to save time. A limit on the number of frogs will likely be needed but the exact number will be constrained by technical limitations.

Frog Velocities

The velocity of each individual frog can be changed by varying the slider above it. Sliders are ideal for this task as they are good for variables where full precision is not necessary. To make the purpose of these sliders intuitive, snail and hare icons are shown and the slider body gets thicker towards the top, indicating a rise in intensity as the slider goes up. With many frogs changing the velocities one by one is annoying so a button is provided to randomize all of them to get a varied spread of speeds without taking too long. In response to feedback we have added the option to select all frogs at once and allow the user to toggle any single slider to change the speeds of all the frogs together.

In addition, clicking on the frog will flip its direction. Hovering over a frog will show a blue circular arrow in order to make this obvious before the user does it.

Animation Speed

With differing frog numbers, the run time for the game will differ and it may be more ideal if the user can change the animation speed to improve engagement with the game. For example, a simulation with a high frog count would take relatively longer for the game to conclude, so allowing the user to speed up the animation while it is running with a slider will help sustain focus.

Beetle and Cactus

The Beetle and Cactus prototype is intended more as a technical demonstration than a full design but there are still some design decisions that go into it. The cactus itself is based on the prickly pear plant, as it has the desired node-tree structure. This also makes the colour scheme very contrasting with the green body nodes and the pink clickable edge nodes.

The main thing the prototype does is provide a solution to the problem of displaying the full cactus and animating it's growth. Each of the descendants of a node are evenly spread out (by angle) around it, and when a node is removed the duplication of it's parent is smoothly animated with transparency so the user can clearly see what is being changed. An animation speed slider is provided so they can speed it up if they wish to click through the cactus faster.

The starting cactus is chosen to be large enough for it to grow a fair amount as it gets eaten, but still be relatively quick to beat as slightly larger cacti get out of hand very fast! When there is no more cactus the following message is displayed:

The cactus is defeated! But now the beetle will starve - could it have sustained itself forever?

This poses an extra (impossible) challenge to the user and attempting it will force them to think about why the cactus will run out rather than just mindlessly clicking through it.

Progress and Future Work

We are happy to say we have succeeded in our goal of a complete design for The Game of Frogs. Nevertheless there are opportunities for future work to consider:

• Of course, actually constructing the visualisation in Javascript.
• Creating vector sprites for the components involved.
• Designing slides that go after the visualisation to explain the inductive argument in detail, as well as the broader concept of mathematical induction it is an example of. This would ordinarily be done in the lecture it is shown in, but having this built in to the visualisation would allow it to be used as a learning tool for people outside the course as well.

The prototype Beetle and Cactus game functions and could be used in lectures but is not a complete visualisation design. As such there is a lot of future work that could be done here:

• Making a new wiki page for it, as it will likely be a seperate visualisation entirely from The Game of Frogs.
• Figuring out why it doesn't work on some people's browsers.
• Supplementing the prototype with an educational preamble and an animated explanation of the rules.
• Designing an explanation of the inductive argument which this time is more complicated as it typically uses ordinals, at least in the general case.
• Adding the choice of mutltiple starting cacti, or even custom user-defined ones.
• An "auto-play" feature that just eats away at the cactus without user input.
• Improving visuals, eg making the cactus look more realistic.

Useful links

• The Imperial Brand colours
• Googology Wiki article on the Kirby-Paris Hydra. In the version we implemented, n is always 1.