Finale 2008 Cesenatico
Il direttore della centrale nucleare, il signor Bourbaks, si sta annoiando e allora decide di licenziare un dipendente. Prende i suoi 6642 dipendenti e li mette tutti in cerchio, numerandoli da 1 a 6642 in ordine crescente in senso orario. A questo punto si mette al centro e, andando in senso orario a partire dal numero 1, alternativamente salva un dipendente - che esce dal cerchio - oppure passa al successivo (il primo che salva è il dipendente con il numero 2). Alla fine, dopo un certo numero di giri, rimarrà un solo dipendente e Bourbaks licenzierà quello. Che numero deve evitare Numer se non vuole essere licenziato?
Risposte
risultato
calcolo
calcolo
Scusate, ma non ho capito la risposta, mi interessano i problemi tipo olimpiadi della matematica
Personalmente l'avevo risolto in una maniera un po' più "brutale", cioè usando i moduli. Provo a spiegarmi il più chiaramente che riesco a fare, ma mi interessava sapere la logica dietro la soluzione proposta perché molto più veloce e meno dispendiosa in termini di tempo e fatica.
Vado per esclusione, cioè se si salvano tutti quelli dal 2 in poi alternandosi a 1 a 1, allora rimangono i numeri 1,3,5 ecc, perciò chiamato x il numero corrispondente all'impiegato licenziato abbiamo che
$x=1 mod2$
Consideriamo che l'ultimo numero è 6642, ed essendo esso pari viene salvato. Al secondo giro dunque rimangono1,5,9, ecc, abbiamo
$x=1 mod4$
consideriamo l'ultimo numero rimasto, cioè 6641. Abbiamo che $6641=1 mod4$ ,allora rimane, perciò è il primo numero del secondo giro a essere salvato, cioè 1, mentre il successivo (che rimarrà per almeno un altro giro) sarà quindi 1+4=5.
Da qui è facile capire che $x=5 mod8$, e se l'ultimo numero che abbiamo, cioè 6641, verifica la congruenza allora rimane, altrimenti viene salvato. Per verificare se $6641=5 mod8$ osserviamo se $6641-5=0 mod8$.
Non essendo questo il caso (infatti $6641=1 mod8$) il dipendente a cui corrisponde tale numero si salva, per cui l'ultimo rimasto sarà il dipendente dal numero 6641-4=6637. Inoltre l'impiegato dal numero minore (cioè 5) rimane ancora per almeno un altro giro, essendo stato il suo precedente salvato.
Mi azzardo a definire un algoritmo per la soluzione di questo problema.
Abbiamo n impiegati, in circolo, numerati da 1 a n. Seguendo le istruzioni del problema e salvando gli impiegati a 1 a 1 partendo dal secondo, e chiamando x il numero dell'impiegato licenziato, abbiamo
$x=1 mod2$ dopodiché consideriamo l'ultimo numero n, e vi sono 2 possibilità:
$n=1 mod2$, ovvero $n-1=0 mod2$, cioè l'impiegato rimane per un altro giro e viene scartato l'impiegato dal numero minore, facendo si che ora l'impiegato dal numero minore non sia più 1, ma 1+2=3.
n=\=1 mod2 (non so come scrivere sul computer il simbolo per "diverso"), perciò viene salvato, il primo impiegato rimane almeno per un altro giro e l'ultimo numero non sarà più n, ma n-1 (cioè n meno la metà del modulo considerato)
Continuando in questo modo per tutte le potenze di 2 otteniamo infine che
$x=997 mod 4096$, per cui x=4096+997=5093
Non so se ho spiegato bene il mio ragionamento, non sono molto patico con questo tipo di problemi e ancor meno a spiegarli, ma sono abbastanza sicuro che funzioni. Il fatto è che mi sembra molto dispendioso in termini di tempo, e vedendo come si poteva giungere al risultato così rapidamente mi chiedevo quale fosse la strategia seguita.
Personalmente l'avevo risolto in una maniera un po' più "brutale", cioè usando i moduli. Provo a spiegarmi il più chiaramente che riesco a fare, ma mi interessava sapere la logica dietro la soluzione proposta perché molto più veloce e meno dispendiosa in termini di tempo e fatica.
Vado per esclusione, cioè se si salvano tutti quelli dal 2 in poi alternandosi a 1 a 1, allora rimangono i numeri 1,3,5 ecc, perciò chiamato x il numero corrispondente all'impiegato licenziato abbiamo che
$x=1 mod2$
Consideriamo che l'ultimo numero è 6642, ed essendo esso pari viene salvato. Al secondo giro dunque rimangono1,5,9, ecc, abbiamo
$x=1 mod4$
consideriamo l'ultimo numero rimasto, cioè 6641. Abbiamo che $6641=1 mod4$ ,allora rimane, perciò è il primo numero del secondo giro a essere salvato, cioè 1, mentre il successivo (che rimarrà per almeno un altro giro) sarà quindi 1+4=5.
Da qui è facile capire che $x=5 mod8$, e se l'ultimo numero che abbiamo, cioè 6641, verifica la congruenza allora rimane, altrimenti viene salvato. Per verificare se $6641=5 mod8$ osserviamo se $6641-5=0 mod8$.
Non essendo questo il caso (infatti $6641=1 mod8$) il dipendente a cui corrisponde tale numero si salva, per cui l'ultimo rimasto sarà il dipendente dal numero 6641-4=6637. Inoltre l'impiegato dal numero minore (cioè 5) rimane ancora per almeno un altro giro, essendo stato il suo precedente salvato.
Mi azzardo a definire un algoritmo per la soluzione di questo problema.
Abbiamo n impiegati, in circolo, numerati da 1 a n. Seguendo le istruzioni del problema e salvando gli impiegati a 1 a 1 partendo dal secondo, e chiamando x il numero dell'impiegato licenziato, abbiamo
$x=1 mod2$ dopodiché consideriamo l'ultimo numero n, e vi sono 2 possibilità:
$n=1 mod2$, ovvero $n-1=0 mod2$, cioè l'impiegato rimane per un altro giro e viene scartato l'impiegato dal numero minore, facendo si che ora l'impiegato dal numero minore non sia più 1, ma 1+2=3.
n=\=1 mod2 (non so come scrivere sul computer il simbolo per "diverso"), perciò viene salvato, il primo impiegato rimane almeno per un altro giro e l'ultimo numero non sarà più n, ma n-1 (cioè n meno la metà del modulo considerato)
Continuando in questo modo per tutte le potenze di 2 otteniamo infine che
$x=997 mod 4096$, per cui x=4096+997=5093
Non so se ho spiegato bene il mio ragionamento, non sono molto patico con questo tipo di problemi e ancor meno a spiegarli, ma sono abbastanza sicuro che funzioni. Il fatto è che mi sembra molto dispendioso in termini di tempo, e vedendo come si poteva giungere al risultato così rapidamente mi chiedevo quale fosse la strategia seguita.
Al primo giro salva i pari, ossia i numeri che hanno 0 nel bit di destra.
Restano i dispari tra cui il licenziando che quindi ha sempre 1 in quel bit, indipendentemente dal numero di partenza.
Al secondo giro salva 3 7 11 15 etc..; restano 5 9 13 17 etc.. ossia i numeri con 0 nel secondo bit: questo dipende dal valore 0 del primo bit di 6642 che in binario vale 1 1001 1111 0010.
Ai giri successivi restano quei numeri che hanno il bit $(n+1)^{esimo}$ uguale al bit $n^{esimo}$ di 6642.
Quindi il licenziando ha il numero 1 0011 1110 0101 che si ottiene ruotando di un bit a sinistra i 13 bit suddetti e scartando il bit quattordicesimo irrilevante perché il procedimento è terminato. Si può verificare con la calcolatrice programmabile di Windows.
L'operazione decimale è $5093=1+2*6642-2^14$ (oops, correggo la mia risposta precedente: avevo scritto $2^13$).
Restano i dispari tra cui il licenziando che quindi ha sempre 1 in quel bit, indipendentemente dal numero di partenza.
Al secondo giro salva 3 7 11 15 etc..; restano 5 9 13 17 etc.. ossia i numeri con 0 nel secondo bit: questo dipende dal valore 0 del primo bit di 6642 che in binario vale 1 1001 1111 0010.
Ai giri successivi restano quei numeri che hanno il bit $(n+1)^{esimo}$ uguale al bit $n^{esimo}$ di 6642.
Quindi il licenziando ha il numero 1 0011 1110 0101 che si ottiene ruotando di un bit a sinistra i 13 bit suddetti e scartando il bit quattordicesimo irrilevante perché il procedimento è terminato. Si può verificare con la calcolatrice programmabile di Windows.
L'operazione decimale è $5093=1+2*6642-2^14$ (oops, correggo la mia risposta precedente: avevo scritto $2^13$).
Grazie mille, è la prima volta che vedo un problema risolto così e devo dire che è molto molto interessante
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo