Puzzle Pt.2 Pokemon Stamp Rally

Shingo Konnai
Aug 31, 2018 · 3 min read

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-5
The 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-5
2³ + 2⁰ - 1 = 8 ways
  • : 3 is 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⁰: 0 is 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.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade