Fuji 2dsan 2fChallengeTwo

Find an upper limit for the length of optimal solutions.

The lowest upper limit found so far is 20474. This was found on 15 Jun 2005 by DonKirkby. This is a lot longer than the longest solution found so far, so there's plenty of room to improve on challenge one or two.

One upper limit can be found by realizing that the same position of priests cannot be repeated in an optimal solution. If a position were repeated, then all the moves between the two occurrences could be removed to make a shorter solution, but an optimal solution is the shortest solution possible.

If a position cannot be repeated, then the longest optimal solution cannot be longer than one that contains every possible position. The number of possible positions can be calculated as follows:

• There are 28 positions possible for a single priest: 24 coins plus 4 starting positions.
• The priests are identical, so swapping two priests recreates the same position.
• The number of possible positions is therefore the number of combinations of 4 items (the position of each priest) from a set of 28 (the number of positions possible for a priest. There is a standard formula for this: 28! / 4!(28 - 4)! = 20475.

Therefore, the longest optimal solution cannot be longer than 20474 moves. (Each move goes from one state to the next, so the number of moves is one less than the number of states.)

Refinements

We can improve on DonKirkby's longest optimal solution upper bound by recognizing that within each game it is impossible for all of those (28 C 4) = 20,475 states to be reached due to the fact that once a "priest" leaves their starting space they cannot return.

1. There are (4 C 3)(24 C 1) = 96 possible states with exactly three priests in their starting spaces but within a single game there can only be at most (24 C 1) = 24 possible states with exactly three priests still in their starting space. So this allows us to subtract 96-24=72 states.
2. Similarly there are (4 C 2)(24 C 2) = 1,656 possible states with exactly two priests in their starting spaces but within a single game there can only be at most (24 C 2) = 276 possible states with exactly two priests still in their starting space. So this allows us to subtract 1,656-276 = 1,380 states.
3. Similarly there are (4 c 1)(24 c 3) = 8,096 possible states with exactly one priest in their starting spaces but within a single game there can only be at most (24 c 3) = 2,024 possible states with exactly one priest still in their starting space. So this allows us to subtract 8,096-2,024=6,072 states.

So within a single game there can be at most 20,475 - 6,072 - 1,380 - 72 = 12,951 states. Therefore, the longest optimal solution cannot be longer than 12,950 moves.

-- TrevorLDavis

Related pages: Fuji-san