All posts by gibson

Parity NIM

Parity NIM consists of a pile containing an odd number of objects from which players take turns removing one or more objects, with at most \(k\) objects removed by each player during his or her turn. The player who has removed an odd number of objects at the end of the game wins.  If \(n\) is the number of objects in the initial pile, a specific solution for the pair \((n,k)\) can be found.   However, no general solution is known.

Partizen Graph Coloring

Partizen Graph Coloring Game has two players: Alice and Bob. The players alternate coloring the uncolored vertices of a finite graph G from a fixed finite set of colors. At each step of the game, the players must choose to color an uncolored vertex with a legal color. In the basic formation of the game, a color is legal for an uncolored vertex if the vertex has no neighbors already colored with that color. Alice wins the game if all vertices of the graph are colored; otherwise, Bob wins. The least  such that Alice has a winning strategy for this game on \(G\) is called the game chromatic number of G. If the definition of legal color is altered so that at each step in the game, each color class must have maximum degree at most \(d\), for some fixed integer \(dge{0}\), then the least such that Alice has a winning strategy is called the \(d\)-relaxed game chromatic number of \(G\). These parameters have been studied extensively for many classes of graphs. The classes for which the most is known are trees and forests. While upper bounds on the game chromatic number (and \(d\)-relaxed game chromatic number) are known for these classes, and the bounds are known to be achievable, it is not known what structural properties the graphs must have in order to achieve the bounds. This project will attempt to find these properties, thereby classifying these classes completely with respect to the Partizen Graph Coloring Game. We will then attempt to classify trees and forests relative to the d-relaxed game chromatic number for small values of \(d\). Finally, we may consider other variations of the game in which the definition of legal color is altered in other ways.

Hexagonal Chess

Hexagonal Chess is a modification of the traditional game of chess, played on a hexagonal board. A board is defined as an n-board if the board has n hexagons on the bottom row of the board.  All boards we used for this game are regular hexagonal boards. This means that the board has the same number of hexagons on every side.  At right is an example of a 5-board.

What is the minimum number of bishops (knights, kings, queen, etc) can be placed on the board so that all sites are challenged (the board is dominated)?  What is the maximum number of bishops (knights, kings, queen, etc) that can be placed on the board so that no bishop is able to capture another (all are independent).

graph1

Envelopes

There are 13 envelopes, and each one is either red or blue.  There are 5 of one color, each containing $100, and 8 of the other color that are empty.  You don’t know which color is the winning color other than it is the one with the smaller number of envelopes.

At the start of the game, one of the thirteen envelopes appears on your computer screen and stays there for 15 seconds.  During that time interval, you have two options.

(1)   You can pick the envelope and see what’s inside, which ends the game, or

(2)   You can pass on the envelope.  If you pass, the envelope disappears forever and brings up one of the remaining envelopes for you to choose or let pass.

  • How should you play the game to maximize your chance of getting the $100?
  • How would the winning strategy change if the amount of money in each winning envelope decreases by $5 each time you pass on an envelope?

Suppose there are  winning envelopes and  empty envelopes.  How should you adjust your strategy given different numbers of winning and empty envelopes?

Chutes and Ladders

To play Chutes and Ladders, you begin with your marker off the board.  Roll a die and move to the position on the board given by the die.  If you land at the bottom of a ladder, you exit the top.  If you land at the top of a Chute, you slide to the bottom.  To win the game of Chutes and Ladders, you must land exactly on cell 100.   Try 9 and 16 cell games to develop a theory of Chutes and Ladders related to the number of moves required to play the game.   How does the length of the game depend upon the number of sides to the die that is used?  How is a game with no chutes or ladders affected by the number of faces on the die?   How does adding a ladder or a chute affect the length of a game.  Does it depend upon where the ladder is added?

graph1

Foxes and Hares

In the game of Foxes and Hares, we begin with \(k\) foxes, \(F_1, F_2, …, F_k\) and one hare \(H\).  Given a finite undirected graph \(G\), the foxes are first placed at \(k\) vertices of the graph, then the Hare is placed on a vertex.  The foxes and the hare alternate turns.  On the foxes’ turn, each fox may move to an adjacent vertex or remain in place, and multiple foxes may occupy the same vertex.  The hare has the same choices of moves on its turn.

graph1

The foxes win if they catch the hare, meaning there is some time at which a fox occupies the same vertex as the hare; otherwise the hare wins.  For a given graph, the minimum number of foxes required to catch the hare (regardless of the hare’s strategy) is called the graph’s fox number.

How can you find the fox number of a given graph?  What are all of the one-fox graphs?  What characteristic(s) of a graph determine(s) whether or not more than one fox is needed?  What are all of the two-fox graphs?

Pass the Stone

In the game of passing stones, each vertex on a graph begins with a certain number of stones.   On each move, if a vertex has at least as many stones as its degree, it passes one stone to each adjacent vertex.  All vertices pass stones simultaneously.   Initially, we consider only cycle graphs, but you will want to branch out into other kinds of graphs later.

graph1

Reversible Cellular Automata

One-dimensional cellular automata are closely associated with dynamical systems and modern chaos theory. While the results are complex and intriguing, the basic principle of cellular automata is simple:  Given an infinite row of cells with each cell colored either black (on or 1) or white (off or 0).  With each iteration, the cells are recolored based upon the colors of their neighbors.

A simple example of a transition rule is the following:  If the sum of  values of the two adjacent squares is even (equal to 0 (mod 2)), color the cell white in the next iteration, otherwise color it black. Under this rule, the initial row becomes:

graph1

 The simplest way to see the effects of a transition rule is to show the evolution of the row over time.  Thus, each row represents one iteration of the transition rule.  Below we see the first 4 iterations of the transition rule described above.

graph2

Which translates into the following diagram using white and black instead of 0’s and 1’s.

graph3

When describing the cellular automata with a sequence of successive rows, it is helpful to describe the transition rule locally.  The new value of a cell in the \(n^{th}\) row is determined by the values lying directly above it in the \((n-1)^{th}\) row.  Thus:

\(frac{111}{0}  frac{110}{1}  frac{101}{0}  frac{100}{1}  frac{011}{1} frac{010}{0}  frac{001}{1}  frac{000}{0} \)

describes the transition rule given above.  The upper part shows one of the eight possible states that three adjacent cells can have at iteration \(n\), where the lower part shows the state of the central cell of the trio time \(n+1\).  Since \(01011010 = 90\) in base two, the rule above is called the rule of 90.

For which Rules and which size neighborhoods is the cellular automata reversible (that is, you can determine the \((n-1)^{th}\) row from the \(n^{th}\) row?  Does each Rule have an inverse Rule?  Can Rules be composed and if so, does order matter?  Suppose the next state depends on the previous two states, does this create any new structures?

The Leaves are Gold

Each vertex in a tree is assigned a positive integer value.  Two players take turns deleting a leaf of the remaining tree and adding the value of the leaf to their collection.  The player with the largest value at the end of the game wins.  For what trees and values is this game solvable and what strategies should the first and second players use?

Three Player Nim

In the game of Nim, several piles of sticks are placed on a table.  Two players take turns removing sticks from the piles. On each turn, a player must remove at least one stick, and may remove any number of sticks provided they all come from the same piles.  The first player without a stick to remove loses.  We will consider 3-player Nim.  Three players, A, B, and C, rotate turns in playing Nim.  The first player without a move loses. The goal for each player is, naturally, to avoid losing and each would prefer to make the last move, if possible.  Develop a theory of 3-person Nim and generalize your results.