11
$\begingroup$

This answer describes an analogy between finite state machines and mazes. This allows for some playful exercises, like

Draw a representation of a word accepted by the following automaton...

which sums up to "solve this maze" in more "respectable" terms. Many kids like solving mazes and such a special content might be desirable on some occasions (e.g. special exam on April 1st).

Do you know any other examples of this kind? In other words, are there any other puzzles that are likable which we can formulate using serious theories?

Improve this question
$\endgroup$
11
  • $\begingroup$ @BenjaminDickman I'm looking for exercises which look like kids' play (e.g. indeed are kids' play, like the one with the maze), but formulated in a serious manner which does not seem unnatural, isn't forced. For example, finding a word accepted by an automaton is a task that is sometimes given to students (e.g. prove that the following language is non-empty). On the other hand, "give an example of 1-dimensional manifold in $\mathbb{R}^2$" for "draw a doodle" would be forced. $\endgroup$
    – dtldarek
    Apr 23, 2014 at 9:43
  • 1
    $\begingroup$ Many entertaining puzzles (with thorough explanations, and rigurous mathematicals development as far as I'm able to judge) are given in Cut the knot. $\endgroup$
    – vonbrand
    Apr 23, 2014 at 14:44
  • $\begingroup$ Rubik's cube and group theory? $\endgroup$
    – mbork
    Apr 23, 2014 at 20:39
  • 1
    $\begingroup$ "Here are four crayons, color this map so that no adjacent regions have the same color." $\endgroup$
    – Alexander Gruber
    Apr 25, 2014 at 14:06
  • 1
    $\begingroup$ @mbork You have said it yourself: "one of her pupils". A question like "find an inverse element of <rubik's cube position>" might be too hard, while "formulate a theory of Rubik's cube" is a way deeper than "solve this maze". $\endgroup$
    – dtldarek
    Apr 30, 2014 at 9:00

3 Answers 3

Reset to default
5
$\begingroup$

There are many examples of games that children play (in the same way that kids might enjoy mazes) which have deep mathematics underlying them. An oft-cited example of this is the game of Hex:

enter image description here

In the board above, the red and blue players take turns putting down hexagons of their own color. Whoever first traces a connected path between his or her two sides (always opposite one another) wins.

For example: blue has won the game above because there is a connected blue path going from one blue side to the other.

Question: Can the game of Hex ever end in a tie?

The answer is no, but if you have never seen this game before, then you might wish to pause and see if you can prove why it cannot end in a tie.

Here is an image of a game board without any tiles placed; more on the question can be found below.

enter image description here

If you have just tried for the first time to prove that the game of Hex cannot end in a draw, then you have probably realized that it is not so straightforward. A couple of independent proofs of this fact were found, one of which is due to John Nash (of A Beautiful Mind fame).

An interesting fact, familiar perhaps only to those who know of this game, is that one can use Hex to prove the Brouwer fixed-point theorem! The citation for this proof can be found here:

Gale, D. (1979). The game of Hex and the Brouwer fixed-point theorem. American Mathematical Monthly, 818-827. Link.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ I'd like to plug the work of Stephen DeBacker, Professor at Michigan, who has for several years run a summer math program for high school students in which they prove the Brouwer fixed-point theorem via this method. The course takes high school students who have never written a proof before, and uses this as a way to introduce abstract mathematics. See math.lsa.umich.edu/mmss/courses/courses.php to see if he is still running it. $\endgroup$
    – Chris Cunningham
    Apr 29, 2014 at 16:03
  • 2
    $\begingroup$ @ChrisCunningham Very interesting; I have seen a similar course run by Daniel Goroff (previously a professor of mathematics at Harvard) who has taught an undergraduate course using the Kuratowski Closure Axioms and the game of Hex with the goal of introducing proof-writing and getting to the BFPT. Though the curricular materials for this course are not publicly available, I wrote up a bit more about the class here: matheducators.stackexchange.com/a/910/262 $\endgroup$
    – Benjamin Dickman
    Apr 29, 2014 at 16:10
  • $\begingroup$ And what kind of questions would you ask? "Can the game of Hex ever end in a tie?" is a fine problem, not a kid's play. $\endgroup$
    – dtldarek
    Apr 29, 2014 at 20:19
  • $\begingroup$ @dtldarek I put the most difficult question in bold. Assuming one knows that the answer is draws are impossible, you can ask: Which of Player 1 and Player 2 has a winning strategy? $\endgroup$
    – Benjamin Dickman
    Apr 29, 2014 at 20:22
  • 1
    $\begingroup$ See also mathoverflow.net/a/13652/12898 $\endgroup$
    – András Bátkai
    Apr 29, 2014 at 22:51
2
$\begingroup$

The game of Nim is often used as introduction to binary numbers and $\mathbf{Z}\ /\ 2\mathbf{Z}$.

It uses the curious addition on $\mathbf{N}$ defined by $a+b=c$ iff $a_i+b_i=c_i \pmod 2$ for all $i$, where $a_i$ is the $i^\text{th}$ digit in the base 2 expansion of $a$.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ CE Shannon's "Prime Nim" is an interesting variation, wherein players can only remove a non-composite number of objects at a time (i.e., the number removed must be 1 or prime). Analyzing game-play is not too tough under these conditions; however, if you don't allow the removal of 1 object, then afaik a characterization of the game (only removing prime numbers of objects) leads to an open problem. For more: math.stackexchange.com/q/226230/37122 $\endgroup$
    – Benjamin Dickman
    Apr 29, 2014 at 18:28
  • $\begingroup$ Could you give a question example? $\endgroup$
    – dtldarek
    Apr 29, 2014 at 20:11
  • $\begingroup$ @BenjaminDickman It is curious how Prime Nim is much more complex than Nim, yet they are essentially equivalent. $\endgroup$
    – dtldarek
    Apr 29, 2014 at 20:14
2
$\begingroup$

Try this special variation on the game of Nim:

Put a pile of 42 stones on the table (although if you don't have 42, any multiple of six will do). Explain to your student that each turn, each of you will remove either 1, 3, or 5 stones, and the person who removes the last stone from a pile wins. Then, explain that the person who moves second has a winning strategy, and offer them a choice of who goes first. Most likely, they'll make you go first.

Then, challenge one of your students to win exactly six of seven games of this type (perhaps offering some sort of prize as a reward). You could also do four out of five, two out of three, as long as they have to try to lose at least one game. They'll probably figure out some time during the first six games that they can force a win by taking 6 stones minus however many you took, especially if they've seen this sort of thing before.

But when they try to lose the seventh game, they'll find it's impossible. Can you guess why?

Every turn when you take stones, you'll leave an odd number, and every turn when they take stones, they'll leave an even number. There's no way to break this pattern within the defined rules, and a consequence of this is that the person who moves second always wins (since 0 is an even number), no matter whether he follows any sort of strategy.

This introduces them to the idea of invariants. It's hard to know the exact level of theory you're looking for, but I think this is a good example purely from a discovery point of view, and doing something counterintuitive (being unable to lose a game even when you want to).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Related problem: Place 100 coins in a row; you and an opponent alternate turns picking either the right-most or left-most coin available; whoever has the most money at the end wins. Number the coins $c_1, \ldots, c_{100}$ and observe player 1 can choose all $c_{2n}$ (even numbered coins) or all $c_{2n+1}$ (odd numbered coins). Thus, player 1 has a winning strategy: figure out which of (the even numbered coins) and (the odd numbered coins) has a greater sum, then take them all. $\endgroup$
    – Benjamin Dickman
    May 6, 2014 at 0:41
  • $\begingroup$ That is actually really clever. $\endgroup$
    – Joe Z.
    May 6, 2014 at 0:42
  • $\begingroup$ Problem creator is: Daniel J. Velleman (cs.amherst.edu/~djv) $\endgroup$
    – Benjamin Dickman
    May 6, 2014 at 0:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.