Mathematical induction games

This is a template which you can use to help get you started on the wiki submission. It is just intended as a guide and you may modify the structure to suit your project.

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

Explain the motivation for your visualisation.

Introduce the subject of your visualisation.
Which module and year is it intended for and which setting (lecture or self study)?
List learning outcomes. E.g.: "After using this visualisation, students should be able to explain that..."

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". 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 may consider including at least an overview of the inductive arguments.

Design Overview

We provide:

....

Design Justification

Assessment Criteria

List your cohort's assessment criteria. You may want to number the assessment criteria so you can refer to them easily later.

Education Design

What Methods were considered to convey concepts?
Design progression, key choices with justifications.
How has feedback been incorporated.

Graphical Design

How were accessibility issues considered?
How was space used effectively?
Design progression, key choices with justifications.
How has feedback been incorporated.

How is the design intuitive?

Interaction Design

Choice of interactive element(s) that fit in organically with the visualisation [inspiration of choice might be from lecture/in-class activity or other sources] - Sliders/Buttons/Cursor (hover/click).
Keeping accessibility of interactive elements in mind during design phase.
Design progression, key choices with justifications.
How has feedback been incorporated.

Progress and Future Work

Is the design finalised?
Which pages have been uploaded to website?
Any ideas for future improvements.

Links

Link to GitHub repository for code in development:
Link to visualisation on ImpVis website (when uploaded):
Link to Collection on ImpVis website (when created):
Any other links to resources (Miro boards / notes pages / Google Docs etc):