# More math for six-year-olds: Win at Nim!

The latest installment of math for six-year-olds

Win at Nim!
Fold up the bottom flap to prevent parents from learning the super-secret strategy.

This morning once again I went into my daughter’s first-grade classroom, full of inquisitive six-and-seven-year-old girls, and made a mathematical presentation on the game of Nim.

Win at Nim!

The game of Nim, I explained, begins with one player setting up a number of stacks of blocks,while the opponent chooses whether to go first or second.  Taking turns, each player removes one or more blocks from a stack of their choosing. (It is fine to take a whole stack on your turn.) The player who takes the last block wins.

We demonstrated the game by playing a number of exhibition rounds, and then the girls divided into pairs to play each other and also me.  They were surprised that I was able to win against them every single time.  In explanation, I told them that this was because in the game of Nim, there is a super-secret mathematical strategy!  Did they want to learn?  Yes!  I took as my goal that they would all learn the Nim strategy, so that they could go home and confound their parents by beating them again and again at the game.

Since this was a first-grade class, we concentrated at first on games with stacks of heights 1, 2 and 3 only, a special case of the game which can still challenge adults, but for which six-year-olds can easily learn the winning strategy.

Two balanced stacks

After gaining some familiarity with the game by playing several rounds amongst each other, we gathered again for the secret strategy session. We began by thinking about the case of a game of Nim with only two stacks. They had noticed that sometimes when I played them, I had made copying moves; and indeed I had purposely said, “I copy you,” each time this had occurred.  The copying idea is surely appealing when there are only two stacks.  After some discussion, the girls realized that with just two stacks, if one played so as to equalize them, then one would always be able to copy the opponent’s move.  In particular, this copying strategy would ensure that one had a move to make whenever the opponent did, and so one would win the game.

A balanced position

In short order, the girls also realized that if one had any number of pairs of such balanced stacks—so that every stack had a partner—then the whole position was also winning (for one to give to the other player), since one could copy a move on any stack by making the corresponding move on the partner stack.  Thus, we deduced that if we could match up stacks of equal height in pairs, then we had a winning strategy, the strategy to copy any move on a partner stack.

In particular, this balancing idea provides a complete winning strategy in the case of Nim games for which all stacks have height one or two.  One should play so as to give a balanced position to one’s opponent, namely, a position with an even number of stacks of height one and an even number of stacks of height two.  Any unbalanced position can always be balanced in this way, and any move on a balanced position will unbalance it.

1+2+3 counts as balanced

To handle positions with stacks of height three, the super-secret trick is that one can balance a stack of height three either with another stack of height three, of course, but also with two stacks:  one of height one and one of height two.   Thus, one should regard a stack of height three as consisting of two sub-stacks, one of height one and one of height two, for the purposes of balancing. Thus, the Nim position 1+2+3 counts as balanced, since the 3 counts as 2+1, which balances the other stacks.  The 1+2+3 position has two stacks of height two and two of height one, when one regards the stack of height three as having a substack of height two and a substack of height one.

In this way, one arrives at a complete winning strategy for Nim positions involving stacks of height at most three, and furthermore, this is a strategy that can be mastered by first-graders. The strategy is to strive to balance the position.  If you always give your opponent a balanced position, then  you will win!  Faced with an unbalanced position, you can always find a balancing move, and any move on an balanced position will unbalance it.  If the game is just starting, and you are deciding whether to go first or second, you should determine whether it is balanced yet or not.  If it unbalanced, then you should go first and make the balancing move; if it is already balanced, then you should go second and adopt the copying strategy, in which you re-balance the position with each move.

More advanced players will want to consider Nim positions with taller stacks than three, and we talked about this a little in the classroom.  Some of the girls realized that the copying strategy and the idea of balanced positions still worked with taller stacks.  One can balanced stacks of height four against other stacks of height four, and so one, but the trick for these taller stacks is that one may balance 5 with 4+1; balance 6 with 4+2; and 7 with 4+2+1. Mathematicians will recognize here the powers of two.

To teach the strategy to children, it is a great opportunity to talk about the powers of two. Any child knows how to count 1, 2, 3, 4 and so on, and most can count by twos 2, 4, 6, 8, 10, …; by fives 5, 10, 15, 20, …; by tens, by threes; by sevens; and so on.  , The powers of two are the numbers 1, 2, 4, 8, 16, 32, 64, 128, and so on, doubling each time.  Climbing this exponential growth, children are often amazed at how quickly one reaches very large numbers:

One plus one is two;

two plus two is four;

four plus four is eight;

eight plus eight is sixteen;

sixteen plus sixteen is thirty-two;

thirty-two plus thirty-two is sixty-four;

sixty-four plus sixty-four is one hundred twenty-eight.

For Nim, we don’t in practice need such big powers of two, since one doesn’t usually encounter stacks of height eight or larger, and usually just 1s, 2s and 4s suffice. The relevant fact for us here is that every natural number is uniquely expressible as a sum of distinct powers of two, which of course is just another way of talking about binary representation of a number in base two.  We regard a Nim stack as consisting of its power-of-two substacks.  Thus, a stack of height 3 counts as 2+1; a stack of height 5 counts as 4+1; a stack of height 6 counts as 4+2; and a stack of height 7 counts as 4+2+1.

Ultimately, the winning general strategy for Nim is always to play so as to balance the position, where one regards every stack as being composed of its power-of-two sub-stacks, and a position counts as balanced when these stacks and sub-stacks can be matched up in pairs. This is a winning strategy, since every unbalanced position can be balanced, and any move on a balanced position will unbalance it.  To balance an unbalanced stack, play on any stack containing the largest size unbalanced power of two substack, and reduce it so as to balance the parity of all the stacks.  If one thinks about it, at bottom what we are doing is ensuring that if we represent the stack heights in their binary representation, then we should play so as to ensure that the position has a even number of one digits in each place.

# Universality, saturation and the surreal number line, Shanghai, June 2013

This will be a short lecture series given at the conclusion of the graduate logic class in the Mathematical Logic group at Fudan University in Shanghai, June 13, 18 (or 20), 2013.

I will present an elementary introduction to the theory of universal orders and relations and saturated structures.  We’ll start with the classical fact, proved by Cantor, that the rational line is the universal countable linear order.  But what about universal partial orders, universal graphs and other mathematical structures?  Is there a computable universal partial order?  What is the countable random graph? Which orders embed into  the power set of the natural numbers under the subset relation $\langle P(\mathbb{N}),\subset\rangle$? Proceeding to larger and larger universal orders, we’ll eventually arrive at the surreal numbers and the hypnagogic digraph.

# Playful paradox with large numbers, infinity and logic, Shanghai, June 2013

This will be a talk at Fudan University in Shanghai, China, June 11, 2013, sponsored by the group in Mathematical Logic at Fudan, for a large audience of students.

Abstract: For success in mathematics and science, I recommend an attitude of playful curiosity about one’s subject. We shall accordingly explore a number of puzzling conundrums at the foundations of mathematics concerning issues with large numbers, infinity and logic. These are serious issues—and we’ll have serious things to say—while still having fun. Can one complete a task involving infinitely many steps? Are there some real numbers that in principle cannot be described? Is every true statement provable? Does every mathematical problem ultimately reduce to computational procedure? What is the largest natural number that can be written or described in ordinary type on an index card? Which is bigger, a googol-bang-plex or a googol-plex-bang? Is every natural number interesting? Is every sentence either true or false or neither true nor false? We will explore these and many other puzzles and paradoxes involving large numbers, logic and infinity, and along the way, learn some interesting mathematics and philosophy.

# In memory, Clark John Hamkins (1930- 2013)

Clark John Hamkins at            Hoyerswort, 2005

My father, Clark John Hamkins (1930 – 2013) passed away May 11, 2013 at his home in Brunswick, Maine. He was a good man, witty, kind, intelligent, honest, hard-working, caring, curious, patient, philosophical, mathematical, practical, fair.  The world has just lost a great human being. He was a loving family man, married to my mother, Monica, for 55 years (their wedding anniversary was yesterday), with six children and thirteen grandchildren.

US Patent 3756058

He was an engineer’s engineer, one who could take apart any machine and put it back together and tell you all about the ways in which the design was flawed or how it was clever.  I think of his work as a kind of meta-engineering, for he designed the machines for manufacturing a product, bending pipes and twisting wire, rather than the product itself.   He held a number of patents for his inventions, including some for his design of a manufacturing apparatus for winding semi-toroidal transformers. When I was a kid, he designed and built in his wood shop a hand-crank centrifugal honey-extractor, which we used to harvest the crop from our bee hives.  He taught all his kids their way around a wood shop, how to cut, saw, nail, drill, screw, sand, bore, file, buff, solder, join, plane, dowel, glue, measure, how to use all manner of hand tools and the jig saw, the band saw, the table saw, the mitre saw, the drill press, the belt sander. He was beyond serious, with a lathe in his shop.  “Use the right tool for the job,” I can still hear him say, and “measure twice, cut once; measure once, cut twice,” a warning to those who would rush their work.  He made all manner of toys for his children and then for his grandchildren.  He made cabinets, tools, furniture, items of all kinds, large and small, fine and plain.  He kept and used a wood shop his entire adult life, insisting even in his final days that he go down into it.  One of his final projects was to design and build a beautiful, melodious whale-motif dulcimer.

He was an artist, and as a young man produced oil paintings, which move me to this day.  Long ago, before having kids, he made architectural drawings for the family home he had planned, and it is clear in retrospect that he hadn’t planned at that time on having such a large family.  (The joke in our family is that Dad wanted four kids and Mom wanted two, and they both got their wish!)  Later, he would inevitably win our family games of pictionary, where one is given the task to draw the meaning of a word selected randomly from the dictionary. His drawings always started with a clear simple line, capturing the essence of the concept, which was then fleshed out in fuller artistic flair until his partner said the word.  I found an old math book of his, from his own school days, with a chapter on Polar Coordinates in which he had drawn a wonderful Eskimo, carrying a harpoon and fish, and an igloo.

He was a teacher at heart.  He explained the slide rule to me when I was young, and gave a lesson on logarithms and log tables and the accompanying explanation of linear interpolation.  He explained to me as a child what $x^2$ and $x^3$ meant, and then, with a twinkle in his eye, as I listened wide-eyed and dumbstruck, about what $x^{2.3}$ meant.  Some of my fondest young memories with him include viewings of the moon and planets through a telescope, as I shivered in my pajamas in the cool night air, pondering the craters and drinking hot cocoa. He would discuss the various historical astronomical theories, comparing Copernicus with Ptolemy and the role of Tycho Brahe.  He loved a good scientific controversy, and liked even more to figure things out himself.  He liked to put a scientific explanation in a historical context.

He was a programmer, programming computers in the earliest days. I brought his cast-off computer cards, punched paper tapes and so on into my third-grade classroom for show-and-tell.  I remember him poring over expansive flowcharts spread across the kitchen table in the evenings. He made sure that his kids were learning how to program.

He was a voracious reader, consuming books in science, philosophy, literature, history, archeology, biology, physics, mathematics. You name it; he read it.

He was a skeptic.

He was a rebel physicist, refusing to accept the conclusion of the Michelson-Morley experiment on relativistic length foreshortening and time contraction.  And he backed up his beliefs by writing an account of this part of physics, re-developing the theory from an alternative perspective of his own invention, involving a notion of time translation, which avoided the need for those paradoxical conclusions, but ended up deriving the same fundamental equations.

I will miss him.

# Algebraicity and implicit definability in set theory, CUNY, May 2013

This is a talk May 10, 2013 for the CUNY Set Theory Seminar.

Abstract.  An element a is definable in a model M if it is the unique object in M satisfying some first-order property. It is algebraic, in contrast, if it is amongst at most finitely many objects satisfying some first-order property φ, that is, if { b | M satisfies φ[b] } is a finite set containing a. In this talk, I aim to consider the situation that arises when one replaces the use of definability in several parts of set theory with the weaker concept of algebraicity. For example, in place of the class HOD of all hereditarily ordinal-definable sets, I should like to consider the class HOA of all hereditarily ordinal algebraic sets. How do these two classes relate? In place of the study of pointwise definable models of set theory, I should like to consider the pointwise algebraic models of set theory. Are these the same? In place of the constructible universe L, I should like to consider the inner model arising from iterating the algebraic (or implicit) power set operation rather than the definable power set operation. The result is a highly interesting new inner model of ZFC, denoted Imp, whose properties are only now coming to light. Is Imp the same as L? Is it absolute? I shall answer all these questions at the talk, but many others remain open.

This is joint work with Cole Leahy (MIT).

# The theory of infinite games, with examples, including infinite chess

This will be a talk on April 30, 2013 for a joint meeting of the Yeshiva University Mathematics Club and the  Yeshiva University Philosophy Club.  The event will take place in 5:45 pm in Furst Hall, on the corner of Amsterdam Ave. and 185th St.

Abstract. I will give a general introduction to the theory of infinite games, suitable for mathematicians and philosophers.  What does it mean to play an infinitely long game? What does it mean to have a winning strategy for such a game?  Is there any reason to think that every game should have a winning strategy for one player or another?  Could there be a game, such that neither player has a way to force a win?  Must every computable game have a computable winning strategy?  I will present several game paradoxes and example infinitary games, including an infinitary version of the game of Nim, and several examples from infinite chess.

# Norman Lewis Perlmutter

Norman Lewis Perlmutter successfully defended his dissertation under my supervision and will earn his Ph.D. at the CUNY Graduate Center in May, 2013.  His dissertation consists of two parts.  The first chapter arose from the observation that while direct limits of large cardinal embeddings and other embeddings between models of set theory are pervasive in the subject, there is comparatively little study of inverse limits of systems of such embeddings.  After such an inverse system had arisen in Norman’s joint work on Generalizations of the Kunen inconsistency, he mounted a thorough investigation of the fundamental theory of these inverse limits. In chapter two, he investigated the large cardinal hierarchy in the vicinity of the high-jump cardinals.  During this investigation, he ended up refuting the existence of what are now called the excessively hypercompact cardinals, which had appeared in several published articles.  Previous applications of that notion can be made with a weaker notion, what is now called a hypercompact cardinal.

web page | math geneology | MathSciNet | ar$\chi$iv | related posts

Norman Lewis Perlmutter, “Inverse limits of models of set theory and the large cardinal hierarchy near a high-jump cardinal”  Ph.D. dissertation for The Graduate Center of the City University of New York, May, 2013.

Abstract.  This dissertation consists of two chapters, each of which investigates a topic in set theory, more specifically in the research area of forcing and large cardinals. The two chapters are independent of each other.

The first chapter analyzes the existence, structure, and preservation by forcing of inverse limits of inverse-directed systems in the category of elementary embeddings and models of set theory. Although direct limits of directed systems in this category are pervasive in the set-theoretic literature, the inverse limits in this same category have seen less study. I have made progress towards fully characterizing the existence and structure of these inverse limits. Some of the most important results are as follows. If the inverse limit exists, then it is given by either the entire thread class or a rank-initial segment of the thread class. Given sufficient large cardinal hypotheses, there are systems with no inverse limit, systems with inverse limit given by the entire thread class, and systems with inverse limit given by a proper subset of the thread class. Inverse limits are preserved in both directions by forcing under fairly general assumptions. Prikry forcing and iterated Prikry forcing are important techniques for constructing some of the examples in this chapter.

The second chapter analyzes the hierarchy of the large cardinals between a supercompact cardinal and an almost-huge cardinal, including in particular high-jump cardinals. I organize the large cardinals in this region by consistency strength and implicational strength. I also prove some results relating high-jump cardinals to forcing.  A high-jump cardinal is the critical point of an elementary embedding $j: V \to M$ such that $M$ is closed under sequences of length $\sup\{\ j(f)(\kappa) \mid f: \kappa \to \kappa\ \}$.  Two of the most important results in the chapter are as follows. A Vopenka cardinal is equivalent to an Woodin-for-supercompactness cardinal. The existence of an excessively hypercompact cardinal is inconsistent.

# Joining the Doctoral Faculty in Philosophy

I am recently informed that I shall be joining the Doctoral Faculty of the Philosophy Program at the CUNY Graduate Center, in addition to my current appointments in Mathematics and in Computer Science.  This means I shall now be able to teach graduate courses in philosophy at the Graduate Center and also to supervise Ph.D. dissertations in philosophy there.  I am pleased to become a part of the GC Philosophy Program, which is so highly ranked in the area of mathematical logic, and I look forward to making a positive contribution to the program.

# Interviewed by Richard Marshall at 3:AM Magazine

I was recently interviewed by Richard Marshall at 3:AM Magazine, which was a lot of fun. You can see that his piece starts out, however, rather over-the-top…

# playing infinite chess

Joel David Hamkins interviewed by Richard Marshall.

Joel David Hamkins is a maths/logic hipster, melting the logic/maths hive mind with ideas that stalk the same wild territory as Frege, Tarski, Godel, Turing and Cantor. He thinks we all can go there and that we all should. He gives tips about the Moebius strip to six year olds and plays around with his sons homework. He has discovered all sorts of wonders involving supertasks, infinite-time Turing machines, black-hole computations, the mathematics of the uncountable, the lost melody phenomenon of infintary computability (which really should be the name of a band), set theory and multiverses, infinite utilitarianism, and infinite chess. He’s also thinking about whether we really have an absolute notion of the finite and doubts if any of this is brain melting, which is just a testimony to his modesty. He also thinks that although maths is open to all he thinks mathematicians could use more metaphors and silly terminology to get their ideas across better than they do. All in all, this is the grooviest of the hard core maths/logic groovsters. Bodacious!

→ continue to the rest of the interview