n-1 morti 1 sopravvissuto

[mattilgale]

n condannati vengono messi in cerchio e numerati da 1 a n
il boia comincia a sparare al #2 e ne ammazza uno sì e uno no... i cadaveri vengono tolti...

chi è l'ultimo vivente (che viene liberato...)?

[SkZ]

a regola "normale" (si ammazzano i pari):
se $ n=2m $ ne vengono uccisi la meta' e la regola per il turno dopo rimane invariata (si continua a uccidere i pari)
se $ n=2m+1 $ vengono uccisi m e ne rimangono m+1 ovvero se $ n=2m-1 $ vengono uccisi m-1 e ne rimagono m, ma la regola al turno dopo e' invertita (si uccidono i dispari)
dato $ n=2^m(2k+1) $ (con $ m\geq 0\; \land\; k\geq 1 $) dopo m+1 passaggi rimagono k+1 persone con i numeri $ 2^{m+1}i+1 $ con i da 0 a k e la regola per il turno successivo e' invertita.

a regola "invertita" (si ammazzano i dispari):
se $ n=2m $ come prima (ne vengono uccisi la meta' e la regola per il turno dopo rimane invertita)
se $ n=2m+1 $ vengono uccisi m+1 e ne rimangono m, ovvero se $ n=2m-1 $ vengono uccisi m e ne rimagono m-1, e la regola al turno dopo torna "normale"
dato $ n=2^m(2k+1) $ (con $ m\geq 0\; \land\; k\geq 1 $) dopo m+1 passaggi rimagono k persone con i numeri $ 2^{m+1}i $ con i da 1 a k e la regola per il turno successivo e' normale.



per $ n=2^m $ rimane in vita l'1 (vengono ammazzati sempre i pari)
per $ n=2^m-1 $ rimane in vita l'n-esimo (vengono ammazzati prima i pari poi ne rimangono $ 2^{m-1} $ e la regola cambia: vengono uccisi i dispari)
per $ n=2^m+1 $ rimane in vita il 3 (dopo il primo turno il 3 e' il secondo e rimagono in $ 2^{m-1}+1 $ con regola invertita, dopo il secondo turno il 3 e' il primo e rimangono in $ 2^{m-2} $ con regola normale, quindi primo caso)
quindi (mero colcolo algebrico)
per $ n=2^m(2^p-1) $ rimane in vita il numero $ 2^m(2^p-2)+1 $
per $ n=2^m(2^p+1) $ rimane in vita il numero $ 2^{m+1}+1 $

adesso devo tornare alle mie immagini
mandi
SkZ

[mattilgale]

tutto ok ma non capisco come finisci...

se $ n=2^m+k $ con $ 0\leq k < 2^m $ allora rimane in vita il
2k+1-esimo

[SkZ]

infatti non avevo finito.
Anche se il fatto che io completi un discorso non e' condizione sufficiente affinche' esso sia comprensibile

[mattilgale]

come non avevi finito...??

a me pare che manchi poco alla fie al punto in cui sei arrivato...

[SkZ]

ho una tesi da finire. Gia' trovo difficile scostarmi da questo forum (maledetto Bolzo e alessio che me l'hanno fatto conoscere).

[Simo_the_wolf]

Procediamo per induzione:

Osserviamo che se indichiamo con $ f(n) $ la nostra funzione che associa ad $ n $ il posto del salvo nel caso in cui ci siano $ n $ uomini allora si vede facilmente che:

$ f(2n+1)=2f(n)+1 $
$ f(2n)=2f(n)-1 $

A questo punto è facile concludere che $ f(2^n +k)=2k+1 $ dove $ 0\leq k < 2^n $. Si può vedere sia per induzione su $ n $ che guardando le due equazioni di prima in base 2.