Puzzle Pt.2 Pokemon Stamp Rally
In 1996, the Pokemon stamp rally started on the Yamanote train line in Tokyo, Japan. What is “stamp rally”? For the stamp rally, people collect a series of rubber stamps in a passport type booklet at railway stops on the Yamanote line. In Japan, this style of entertainment has become really popular. Anyway, today’s puzzle is related to the stamp rally.
Problem
Yamanote line, which is a loop line, has 29 stations. (In 2020, a new station will be completed and opened between Shinagawa and Osaki stations.)
How many different stop variations are there for collecting Pokemon stamps when participants must enter at station No.1 and exit at station No.14?
Note: The participants in this stamp rally don’t necessarily have to collect stamps at each station.
[1]: the station No.1. Participants must start at this station.
[14]: the station No.14. Participants must exit at this station. [27][28][29][01][02][03][04]
[26] [05]
[25] [06]
[24] [07]
[23] [08]
[22] [09]
[21] [10]
[20] [11]
[19][18][17][16][15][14][13][12]
How to think of this puzzle
When participants get to a train stop, they have 2 options: 0 or 1.
- 0: not getting off the stop and going to the next stop.
- 1: getting off the stop, getting the Pokemon stamp and going to the next stop.
You need to think of the inner track (counter clockwise) and the outer track (clockwise) in the loop train.
Participants must get on the start station and get off the end one. Then, they think of wether or not they get off the stop and get the Pokemon stamp “the number of stations between the start and the end” times.
This is a loop line. Even if they use the inner track and the outer track, when they only stamp Pokemons at the start and end, they will get the same 2 kinds of stamps. That’s why we have to subtract one from the sum in order to prevent overlap.
In order to make the problem more simple, let’s think about the loop line which consists of 5 stations.
[1]-[2]-[3]
| /
[5]-[4]In this simple case, the answer is bellow:
The inner track (1->5): counter clockwise
1-5The outer track (1->2->…->5): clockwise
1-2-3-4-5
1-2-3-5
1-2-4-5
1-3-4-5
1-2-5
1-3-5
1-4-5
1-52³ + 2⁰ - 1 = 8 ways
2³:3is the number of stations between the start and the end in the outer track (1->2->…->5). At each train stop (No. 2, No. 3 and No. 4), we have 2 options about whether or not we will get off the stop and get the Pokemon stamp of the station. That’s why there are 2*2*2 ways.2⁰:0is the number of stations between the start and the end in the inner track (1->5). Like the above, there is only 1 way (1->5).-1: the inner track and the outer track have the same way (1->5) so we subtract one way to avoid overlap.
Answer
const stampRally = (numberOfStaions, start, end) => {
return 2 ** (Math.abs(start - end) - 1) + 2 ** (numberOfstaions - Math.abs(start - end) - 1) - 1;
}The answer is 36863 ways.
