CPS 108 : Pegs

Fall 2000

Do you remember playing the peg game when you were a child? Have you visited restaurants that have triangularly shaped boards lying out on the tables? The boards have 15 holes drilled into them: 5 rows of 1, 2, 3, 4 and 5 holes respectively, as shown below.

All of the holes are initially filled with pegs (golf tees) except one (hole zero).

A move in the peg game is a jump of one peg over an adjacent peg into an open hole. The peg over which you jump is removed from the board. Using the board shown above, peg 3 could jump over peg 1 and into hole number 0. Peg 1 would be removed. The board shown below illustrates the result of jump 3 => 0.

The object of the game is to continue jumping until only one peg remains on the board. Of course, if no adjacent pegs remain, or if adjacent pegs have no open holes to which they can jump, no more moves can be made. In either case, when no more moves can be made, the game is considered to be complete. Often, the game ends with more than one peg remaining as shown below.

Questions

Ultimately, you are to answer the following questions with the correct answers or with your best guesses, given what you know about the peg game at this time. Type your reasoning describing how you arrived at your answers as a justification for your answers in your README file.

1. What is the least number of pegs that can be left on the board of a completed game?
2. What is the greatest number of pegs that can be left on the board of a completed game?
3. Do games exist that will leave n pegs on the board for every value n between the minimum and maximum number of pegs that can be left on the board?
4. How many different games can be played that leave exactly 1 peg on the board?
5. Is there a game that leaves one peg in position p for every p between 0 and 14?
6. What is the greatest number of moves that can exist in a complete game?
7. How many different moves can be made for the first move?
8. How many different combinations of moves exist for the first 2 moves?
9. How many different combinations exist for the first m moves, where m is any value between 3 and the greatest possible number of moves, inclusive?
10. If each move in a game is chosen randomly from all of the possible moves that exist at any time during the game, how often should such a random game result in 1 peg remaining?
11. If each move in a game is chosen randomly from all of the possible moves that exist at any time during the game, how often should such a random game result in n pegs remaining, where n is between 2 and the maximum number of pegs that can remain on the board for a complete game, inclusive?

Examples of a set of winning moves and a set of losing moves are provided at the end of the handout.

Simulation

If you have correctly answered all of questions above by now, without using a computer, you have analytical skills well beyond my own and I congratulate your on possessing such wonderful abilities. If you have not arrived at all the solutions, you should search for additional information and revise your initial guesses and confirm that the answers you believe are correct truly are correct. To confirm your answers, you may logically justify the answers using techniques of logic and proof, you may play the peg game on a board and verify the answers by hand, or you may simulate the peg game on the computer, confirm that the simulation is equivalent to the actual peg game, and allow the simulation to gather information that enables you to better answer the questions.

If you choose to simulate the game, you must document each of the following on your project web page:

• What data structures did you consider for modeling the board?
• What data structure did you actually use to model the board?
• Why did you pick the data structure that you did?
• What functionality did you implement in order to simulate the game?
• How did the choice of your data structure effect the functionality implementations?
• Are your functions as efficient as they can be? Justify your answer.
• What did you do to confirm that your simulation is modeling the peg game?
• Provide sample output from the simulation runs that were used to answer the original questions.

Examples

A Winning Sequence

Peg Game Soution #1		Begin =>	Read Left to Right, Top to Bottom	=>
3 => 0		8 => 1		10 => 3, 11 => 4
1 => 6, 2 => 7		9 => 2		0 => 5, 6 => 8
13 => 11		5 => 12		11 => 13, 14 => 12		Winner!

A Losing Sequence

Peg Game Loss #1		Begin =>	Read Left to Right, Top to Bottom	=>
3 => 0		8 => 1		0 => 3
5 => 0		6 => 8		13 => 4, 14 => 5
11 => 13		You Lose :-(