Seznam "padlih za svobodo": 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 1, 5, 10, 14, 19, 23, 28, 32, 37, 41, 7, 13, 20, 26, 34, 40, 8, 17, 29, 38, 11, 25, 2, 22, 4, 35, 16. Številka \(31\) pa je preživela.
Oreh:
Naj bo zdaj vseh \(n=100\), umrl pa naj bi vsak drugi (\(k=2\)).
Rešitev: 73. oseba bo ostala na koncu živa.
Razlaga:
Oblikujmo tabelo od 1 do 100
- Št. 1 ima meč, ubije naslednjo (št. 2) in meč poda naslednjemu (št.3) (element 2 umaknemo iz tabele)
- V prvem krogu tako vsak z mečem ubije svojega naslednika, kar pomeni, da iz tabele odstranimo vse sode elementem ostanejo preživeli lihi:
Krog 1: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99
Krog 2: 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97
Krog 3: 1, 9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97
Krog 4: 9, 25, 41, 57, 73, 89,
Krog 5: 9, 41, 73
Krog 6: 9, 73
Krog 7: 73
Seveda za dano rešitev obstajajo razne formule, vendar me je presenetila ugotovitev, kako je ta problem močno povezan z dvojiškim zapisom (če je \(k=2\)):
če število \(n=100\) zapišemo v dvojiškem sestavu, temu številu prvo enico prestavimo na konec števila, novo število \(f(n)\) pa zapišemo v desetiškem sestavu, dobimo mesto "zadnjega preživelega":\[n=100={1}100100, f(n)=100100{1}=73.\]
Ta metoda deluje za poljubni \(n,\) če je le \(k=2.\)
Ostaja še vprašanje, kako najlažje izračunati za poljubni \(k.\)