Tuesday, August 26, 2014

Day 2

Today in Puzzles and Logic, we shared a series of related mathematical games that involved sequentially taking coins from a pile. The “Don’t be greedy” game and the “Don’t be greedier” game are both known as games of “Nim”. Together, we discovered some strategies that are sure to succeed, as well as some winning and losing states. If you enjoyed playing the game of Nim, try this related problem given to me by my first competition math teacher:

Imagine you are playing a game against an opponent on a chessboard. A rook is placed on the bottom left square on the board, and both players attempt to move the rook to the upper right square on the board. The players take turns moving the rook. When a player moves the rook, they can move the rook any number of squares up or right, but they cannot move both up and right on the same turn. Whichever player places the rook on the upper right hand square wins.
-Mr. Holbrook

Does a winning strategy exist for the player that makes the first move? What about the player that makes the second move? What are some conditions that guarantee a win?

In our problem-solving unit, we discovered several different methods of deriving a general formula for the handshake problem proposed on the first day. We also started on a path counting problem, using the streets of New York City to think about the number of shortest paths between two points on a grid. Thinking about minimizing the amount of walking you need to do is very good for very tired people, and one of our mathematicians met a very tired ant that wanted to find the length of the shortest path between the circled corners on this 1m. x 1m. x 1m.  wire cube.


Image Credit: Jürgen Kornmeier and Michael Bach
Can you tell me the minimum distance the ant has to walk if the ant can only walk along the edges of the cube? How many “shortest paths” are there? How many “shortest paths” would there be if instead of a wire cube, we had a solid cube, and the ant could walk on the top of the faces of the cube instead of just on the edges?

Our computer scientists learned about variables today, and used them to help draw and color our own avatars on the Processing programming language. With our new tool, we figured out how to set or drawings to positions based on variables, so we could easily move our entire picture up, down, left, or right depending on how we set our variables in our code. Can you figure out how the variables in the following code will behave?

int cat = 18;
int dog = 36;

dog=dog/cat
cat=cat/5
dog=dog+dog+dog-cat

What is the value of dog?

During our Proofs and Investigations module, we took a trip in a time machine to the city of Königsberg, Prussia to explore Graph Theory as Leonhard Euler did in 1736. Using bridges and ghosts to help us think, we learned about Eulerian paths, which are paths on a graph that visit every edge once. If you enjoyed playing with Eulerian paths, you may want to take a look at Hamiltonian paths. A Hamiltonian Path is simply a path that visits every vertex exactly once.

Do you think I have to use every edge in a graph if I draw a Hamiltonian path? Do you think I can use an edge twice in a Hamiltonian Path? For a much tougher challenge, how many Hamiltonian paths can you find on a cube? I give you two examples of Hamiltonian paths on cubes below. The red line on the left cube makes the Hamiltonian path a Hamiltonian cycle, a special kind of Hamiltonian path that is a closed loop.
Image Credit: mathafou.free.fr
Finally, our mathematical artifact of the day was a triangle pattern that could be folded and glued to create an invertible three-dimensional figure. The mathematical artifact of today can be used to explore the path counting problems we talked about in our Problem Solving module, and the Eulerian paths we explored in Proofs and Investigations. Given two vertices, and assuming all edges are the same length, try figuring out how many shortest paths exist between different pairs of points on the figure. Alternatively, see if you can take a marker and draw out a Eulerian path using the vertices and edges of the figure as vertices and edges on a graph. Do these problems change now that we are using a distorted torus (A three dimensional solid that looks like a doughnut) instead of a flat plane?

Day 2 was packed with both tough problems and elegant solutions from our mathematicians. All of our mathematicians went home with lots to think about, and we await some more thinking and problem solving in the morning. Until tomorrow!


-Justin Shin