Results
To answer questions about the game pegs, I wrote a program to simulate
every possible permutation of the game. This program gives the
following output:
Move number 0, 0 possible combinations.
Pegs remaining 0, 0 games exist.
There are 6816 ways to leave exactly one peg in slot 1
Move number 1, 0 possible combinations.
Pegs remaining 1, 29760 games exist.
There are 0 ways to leave exactly one peg in slot 2
Move number 2, 2 possible combinations.
Pegs remaining 2, 139614 games exist.
There are 0 ways to leave exactly one peg in slot 3
Move number 3, 8 possible combinations.
Pegs remaining 3, 259578 games exist.
There are 0 ways to leave exactly one peg in slot 4
Move number 4, 42 possible combinations.
Pegs remaining 4, 123664 games exist.
There are 0 ways to leave exactly one peg in slot 5
Move number 5, 222 possible combinations.
Pegs remaining 5, 14844 games exist.
There are 0 ways to leave exactly one peg in slot 6
Move number 6, 1074 possible combinations.
Pegs remaining 6, 844 games exist.
There are 3408 ways to leave exactly one peg in slot 7
Move number 7, 5072 possible combinations.
Pegs remaining 7, 324 games exist.
There are 0 ways to leave exactly one peg in slot 8
Move number 8, 21530 possible combinations.
Pegs remaining 8, 2 games exist.
There are 0 ways to leave exactly one peg in slot 9
Move number 9, 75758 possible combinations.
Pegs remaining 9, 0 games exist.
There are 3408 ways to leave exactly one peg in slot 10
Move number 10, 211696 possible combinations.
Pegs remaining 10, 0 games exist.
There are 0 ways to leave exactly one peg in slot 11
Move number 11, 398148 possible combinations.
Pegs remaining 11, 0 games exist.
There are 0 ways to leave exactly one peg in slot 12
Move number 12, 387308 possible combinations.
Pegs remaining 12, 0 games exist.
There are 16128 ways to leave exactly one peg in slot 13
Move number 13, 162558 possible combinations.
Pegs remaining 13, 0 games exist.
There are 0 ways to leave exactly one peg in slot 14
Move number 14, 29760 possible combinations.
Pegs remaining 14, 0 games exist.
There are 0 ways to leave exactly one peg in slot 15
This data means, for example, that there are 29,760 ways to win the
game, or in other words, to leave only one peg remaining. It also
means that for the first move, there are two possible moves, for the
first two moves there are 8 possible combinations, etc. With this data
I can now answer the following questions:
1.What is the least number of pegs that can be left on the board of a
completed game?
This I could figure out using my intuition. Obviously you have to have
at least one peg remaining at the end because there will be no more
pegs left to jump. It turns out there are 29,760 ways to do this.
2.What is the greatest number of pegs that can be left on the
board of a completed game?
This is a much more difficult question. I had no idea before writing
this program, but there are in fact two ways to leave eight pegs on
the board. If I wanted to, I could traverse my Jump tree to find out
how to do this, but this would make my program even longer to run.
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?
Yes there are, in fact there are countless games that will leave 1-7
pegs on the board and each number of pegs from 1 to 8 is accounted for.
4.How many different games can be played that leave exactly 1 peg
on the board?
29,760
5.Is there a game that leaves one peg in position p for every p
between 0 and 14?
No, as you can see above, games can only end with pegs in position 1,
7, 10, and 13. I counted from 1-15 to make it more understandable for
users not in the CS mentality of counting.
6.What is the greatest number of moves that can exist in a
complete game?
This can be answered without a simulation. Since each move removes a
peg, and you can remove at most 13 pegs in a game, the greatest number
of moves must be 13.
7.How many different moves can be made for the first move?
2
8.How many different combinations of moves exist for the first 2
moves?
8
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?
These numbers are in the output above.
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?
There are 568,630 total games, so the probability of a random game
being a winner is 29760/568630 = 0.05233
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?
n=2, .2455
n=3, .4565
n=4, .2175
n=5, .0261
n=6, .0015
n=7, .0006
n=8, .000004