Exploring Discrete Mathematics Summary

Monday - Friday, July 4 - 8, 2011

This week we worked on classical problems from discrete mathematics. We started out with variations of Nim. Such variations included

  • the total number of tokens,
  • the number of tokens you are allowed to take during a single turn,
  • if taking the last token meant you were the winner or the loser, and
  • if the number of tokens you are allowed to take in your turn depended on how many tokens the previous person took (specifically we said it was up to double the previous number).

The problems lead us to interesting explorations of modular arithmetic, Fibonacci numbers (yes they really are everywhere in some form or another), problem solving by simplification and then systematic complexification, and Brian's overall satisfaction at the utter torment of his pure and innocent lemmings (us) who are doing everything he has asked us to do without complaint or reservation. Just to clarify the type of person Brian is, he tried to get us to believe there was some guy named Zeckendorf (possibly a teacher at Hogwarts?) who proved that any natural number can be written as the sum of nonconsecutive Fibonacci numbers. [Note: We really do love Brian.]

Wednesday we spent some time doing other problems including pan balance problems and non-transitive outcome games. For example we talked about Rock-Paper-Scissors-Lizard-Spock. (And why does a paper disprove Spock? That doesn't sound logical at all.) This game is preferred to simply Rock-Paper-Scissors because in this variant of the game a tie will only occur one-fifth of the time while in the original it would be one-third. However, every outcome still has an equal chance of winning and losing.

Finally, we split into project groups. We decided to do two projects from the categories

(1) combinations/permutations,
(2) Nim problems,
(3) Euclidean algorithm, and
(4) Graph Theory problems.

As a group we selected (1) and (4). The combination/permutation group consists of Trevor, Marcelle, Mahen, and Todd and is exploring activities based on the game Mastermind. The Graph Theory group consists of Timon, Gabe, Olimpia, and Dan and is playing around with the ideas of map colorings, paths and circuits, Eulerean and Hamiltonian paths, and shortest path algorithms.

Back to Journal Index

PCMI@MathForum Home || IAS/PCMI Home

© 2001 - 2018 Park City Mathematics Institute
IAS/Park City Mathematics Institute is an outreach program of the Institute for Advanced Study, 1 Einstein Drive, Princeton, NJ 08540
Send questions or comments to: Suzanne Alejandre and Jim King

With program support provided by Math for America

This material is based upon work supported by the National Science Foundation under DMS-0940733 and DMS-1441467. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.