Në vitin 1996, mitingu i pullave Pokemon filloi në linjën e trenit Yamanote në Tokio, Japoni. Çfarë është "mitingu i pullave"? Për tubimin e pullave, njerëzit mbledhin një seri pullash gome në një broshurë të llojit të pasaportës në stacionet hekurudhore në linjën Yamanote. Në Japoni, ky stil argëtimi është bërë me të vërtetë popullor. Gjithsesi, enigma e sotme lidhet me mitingun e pullave.

Problem

Linja Yamanote, e cila është një linjë loop, ka 29 stacione. (Në vitin 2020, një stacion i ri do të përfundojë dhe do të hapet midis stacioneve Shinagawa dhe Osaki.)

Sa variacione të ndryshme ndalimi ka për mbledhjen e stampave të Pokemonit kur pjesëmarrësit duhet të hyjnë në stacioninNr.1 dhe të dalin në stacioninNr.14?

Shënim: Pjesëmarrësit në këtë tubim pullash nuk duhet domosdoshmërisht të mbledhin pulla në çdo stacion.

[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]

Si të mendoni për këtë enigmë

Kur pjesëmarrësit arrijnë në një stacion treni, ata kanë 2 opsione: 0 ose 1.

  • 0: të mos zbrisni nga ndalesa dhe të mos shkoni në ndalesën tjetër.
  • 1: zbritja nga ndalesa, marrja e vulës së Pokemonit dhe shkuarja në stacionin tjetër.

Ju duhet të mendoni për binarët e brendshëm (në drejtim të kundërt të akrepave të orës) dhe atë të jashtëm (në drejtim të akrepave të orës) në trenin e qarkut.

Pjesëmarrësit duhet të hipin në stacionin e fillimit dhe të zbresin nga ai i fundit. Më pas, ata mendojnë nëse do të zbresin apo jo nga ndalesa dhe do të marrin vulën Pokemon "numri i stacioneve midis fillimit dhe fundit".

Kjo është një linjë loop. Edhe nëse përdorin pistën e brendshme dhe atë të jashtme, kur vulosin vetëm Pokemonët në fillim dhe në fund, ata do të marrin të njëjtat 2 lloje pullash. Kjo është arsyeja pse ne duhet të zbresim një nga shuma për të parandaluar mbivendosjen.

Për ta bërë problemin më të thjeshtë, le të mendojmë për linjën e lakut e cila përbëhet nga 5 stacione.

 [1]-[2]-[3]
  |      /
 [5]-[4]

Në këtë rast të thjeshtë, përgjigja është më poshtë:

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
  • 2³: 3 është numri i stacioneve ndërmjet fillimit dhe mbarimit në pistën e jashtme (1_8->9_…->5). Në çdo ndalesë treni (Nr. 2, Nr. 3 dhe Nr. 4), ne kemi 2 opsione nëse do të zbresim apo jo nga stacioni dhe do të marrim vulën Pokemon të stacionit. Kjo është arsyeja pse ka mënyra 2*2*2.
  • 2⁰: 0 është numri i stacioneve midis fillimit dhe fundit në pistën e brendshme (1->5). Ashtu si më sipër, ka vetëm 1 rrugë (1->5).
  • -1: gjurma e brendshme dhe ajo e jashtme kanë të njëjtën mënyrë (1->5) kështu që ne zbresim një mënyrë për të shmangur mbivendosjen.

Përgjigju

const stampRally = (numberOfStaions, start, end) => {
  return 2 ** (Math.abs(start - end) - 1) + 2 ** (numberOfstaions - Math.abs(start - end) - 1) - 1;
}

Përgjigja është 36863 mënyra.