758 – algebretta
Immaginate di avere nove ragazzi seduti in cerchio come in figura, e di assegnare a ciascuno di loro un numero tra 1 e 9 senza che nessun numero sia usato più di una volta. A questo punto si dice ai ragazzi di alzarsi e spostarsi di tanti posti in senso antiorario quanto è il numero che hanno: quindi il numero 1 si sposta di un posto, il 2 di due posti e così via, fino al 9 che fa tutto il giro e ritorna a sedersi dov’era prima. È possibile assegnare i numeri in modo che alla fine dell’operazione non ci siano due ragazzi nello stesso posto?
(trovate un aiutino sul mio sito, alla pagina https://xmau.com/quizzini/p758.html; la risposta verrà postata lì il prossimo mercoledì. Problema ideato da James Tanton.)
Mi pare questo quizzino fosse già stato proposto qualche settimana fa.
Sei sicuro? Ho fatto una rapida ricerca e non ho trovato nulla. Ah, no! E’ quello che avevo postato per sbaglio un mese fa e poi cancellato quasi subito!
Non so se è l’unica soluzione, o meglio se la ricerca della soluzione è unica, ma trovo abbastanza intuitivo che:
– la posizione del [ragazzo] 9 è ininfluente per il resto del gruppo, mentre
– per mantenere un certo ordine conviene che se ad esempio il [ragazzo] 2 si sposta in senso orario di 2, allora va fatto in modo che il [ragazzo] 7, spostandosi contemporaneamente in senso orario di 7 (alla fine è come se si spostasse di 2 in senso antiorario) lasci il suo posto libero al [ragazzo] 2 andando ad occupare il posto lasciato libero da quest’ultimo,
– procedere analogamente anche per le altre coppie complementari a 9, cioè 1+8, 3+6 e 4+5, così non si complicano troppo le cose.
Non servono molti tentativi per trovare una soluzione soddisfacente, almeno per un singolo turno, ma non essendo specificato che i passaggi vadano ripetuti…
Prima (rappresentando in linea due giri, partendo in senso orario dal 9 e ritornandoci): 9 3 4 2 6 7 5 1 8 9 3 4 2 6 7 5 1 8 9
Dopo (allo stesso modo): 9 6 5 7 3 2 4 8 1 9 6 5 7 3 2 4 8 1 9
Ok :-)
Ho ri-provato perché rileggendo era indicato di fare spostare i ragazzi in senso antiorario e in quel momento il prefisso anti- m’era sfuggito, e va bene; poi effettivamente che “i ragazzi siano numerati in senso antiorario da 1 a 9” funziona bene ed è decisamente più semplice.
Come sospettavo non si va molto più avanti con i possibili passaggi successivi, perché 9 non è un numero primo e ad esempio, con la sequenza iniziale descritta, il [ragazzo] 3 capiterà sul posto occupato dal [ragazzo] 9 già nel passaggio seguente.
Ho provato con 7 posti per 7 ragazzi (7 è un numero primo) e riesce bene fino ad n-2 cioè fino al quinto passaggio, poi col passaggio successivo (il sesto) si entra in conflitto.
Suppongo sia così anche per n=11; anche con n=13 ma già qui potrebbero esserci dei problemi: l’essere designato come tredicesimo potrebbe non essere apprezzato e generare conflitti :-)
Nell’anello delle classi resto mod m, fissato un elemento k che non è divisore dello 0, la funzione
f(x) = kx
è iniettiva.
Infatti se kx = ky, allora k(x-y) = 0 ed essendo k non divisore dello 0, deve essere x = y.
Immaginiamo che i posti in cui sono seduti i ragazzi siano numerati in senso antiorario da 1 a 9.
Se a ciascun ragazzo si dà il numero corrispondente al posto in cui è già seduto (sia x), questi si dovrà spostare nel posto 2x (mod 9).
Ma, visto che 2 non è un divisore dello zero modulo 9, abbiamo mostrato che questa operazione è iniettiva, perciò non ci saranno due ragazzi che finiranno nel medesimo posto.
Il trucco funziona per tutti i circoli con un numero dispari di posti.
Il problema mi ha appassionato. Vediamo perché coi numeri pari non funziona mai.
Se sommiamo tutti i numeri da 0 a 2m-1 mod m, otteniamo m. Infatti, tolto m e tolto 0, tutti gli altri numeri si accoppiano in tante somme pari a 2m, cioè 0.
Ciò vuol dire che in una situazione come quella di partenza e in quella desiderata di arrivo la somma dei numeri di posto occupati dai ragazzi è m.
Ma se alla situazione di partenza sommiamo modulo m tutti i numeri pari a tutti gli spostamenti, stiamo aggiungendo a m una quantità pari ancora a m, ottenendo 0.
Perciò l’operazione descritta nel problema produrrà sempre una situazione incompatibile con la disposizione desiderata.
corretto