Problema 21 Cesenatico

[RobStam]

Buongiorno.

È da qualche giorno che un problema proposto nelle recenti gare a squadre di Cesenatico mi tormenta.
Sto ancora cercando la strada giusta da percorrere per poter arrivare alla soluzione.
Ecco il testo

I Goldbachtrotters sono famosi per la loro abilità nel manipolare numeri di altezza crescente. Nel loro numero più famoso, 2n di loro si mettono in fila, indossando maglie su cui sono scritti, da sinistra a destra, i numeri +1,+2,+3... + (n − 1),+n,−n,−(n − 1)... − 2,−1. Il primo di loro, quello con il numero +1, lancia la palla al suo compagno di squadra immediatamente alla sua destra. Allo stesso modo, quando riceve la palla, ogni giocatore la passa al giocatore che ha distanza da lui pari al suo numero di maglia, a destra se il numero è positivo e a sinistra se è negativo. Quindi per esempio il giocatore con il numero −4 passa la palla al giocatore che sta quattro posti a sinistra rispetto a lui. Per quanti interi n ≥ 1 la palla sarà di nuovo in possesso del giocatore iniziale dopo 24 passaggi?

Ho provato a calcolare dopo quanti passaggi la palla ritorna al giocatore iniziale per i primi valori interi:
dopo un passaggio 0 possibilità:
dopo due passaggi una possibilità: n=1
dopo tre passaggi una possibilità: n= 3
dopo quattro passaggi due possibilità: n= 2 ed n=7 (più il caso di due passaggi)
dopo cinque passaggi : una possibilità: n=15
dopo sei passaggi: tre possibilità: n=4, n=10, n=31 (oltre ai casi con due e tre passaggi)
dopo sette passaggi: una possibilità: n= 63
dopo otto passaggi: quattro possibilità: n= 8, n= 25, n=42, n=127 (oltre ai casi con due e quattro passaggi)

Mi sono poi fermato per cercare una ricorrenza per arrivare ai 24 passaggi.
Continuando così, ad ogni numero pari successivo di passaggi, le possibilità sembrano aumentare di uno ma se fosse corretto, dopo 24 passaggi ci dovrebbero essere 12 casi per 24 passaggi più 6 casi per 12 passaggi, più 4 casi per 8 passaggi, più 3 casi per sei passaggi, più 2 casi per quattro passaggi, più 1 caso per tre passaggi e 1 caso per due passaggi, in totale 29.
La risposta è però 95.

E’ impossibile proseguire cercando di controllare manualmente cosa accade in seguito,bisognerebbe controllare tra 2^23-1 numeri…

Ringrazio in anticipo coloro i quali vogliono provare a risolvere il dilemma proponendo qualche suggerimento.

[giammaria]

Sto cercando una soluzione, e noto che scrivi

... dopo otto passaggi: quattro possibilità: n= 8, n= 25, n=42, n=127...

Numeri di questo genere non sono certo stati ottenuti per tentativi; il tuo ragionamento potrebbe forse essermi di aiuto. Ti spiace indicarlo, magari in spoiler?

[RobStam]

Seguendo le indicazioni del testo, ho cercato una ricorrenza.
a) Sono partito da n=1
Persone in fila +1 -1; Se la palla parte dalla persona con il numero +1, dopo un passaggio la palla arriva a quello con la maglia -1 e dopo un altro passaggio la palla ritorna al giocatore che l'aveva lanciata per prima. Per n = 1 servono due passaggi;
b) n=2
Persone in fila: +1 +2 -2 -1; la palla parte dalla persona con +1, dopo un passaggio arriva alla persona con il +2; da lì la palla passa al giocatore con il numero -1 (due passi a destra rispetto a lui); il giocatore con il numero -1 la passa al giocatore con il -2 ed infine quello con il numero -2 la passa a quello con il numero +1. In totale per n=2 servono 4 passaggi per far sì che la palla ritorni al giocatore di partenza.
E così ho continuato per n= 3, n=4....
Procedendo in questo modo speravo di trovare delle sequenze ripetute o altre regolarità ma non ne ho riscontrate.
Ad esempio se si vuole che in 8 passaggi la palla ritorni al punto di partenza, ho trovato validi solo i casi in cui ci sono 8 persone:
1 2 3 4 5 6 7 8 -8 -7 -6 -5 -4 -3 -2 -1 (da 1 a 2 da 2 a 4 da 4 a 8 da 8 a -1 da -1 a -2 da -2 a -4 da -4 a -8 da -8 a 1)
25 persone:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 -25 -24 -23 -22 -21 -20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 - 8 -7 -6 -5 -4 -3 -2 -1 (da 1 a 2 da 2 a 4 da 4 a 8 da 8 a 16, da 16 a -19, da -19 a 13, da -13 a -25 e da -25 a 1)
42 persone: da 1 a 2 da 2 a 4 da 4 a 8 da 8 a 16 da 16 a 32 da 32 a -21 da -21 a -42 e da -42 a +1.
127 persone: da 1 a 2 da 2 a 4 da 4 a 8 da 8 a 16 da 16 a 32 da 32 a 64 da 64 a -127 da -127 a 1.
Non ho trovato alcun numero tra 64 e 127 che permetta di riportare la palla al numero 1 in 8 passaggi. Oltre 127 (2^7-1)non è possibile che la palla torni indietro con soli 8 passaggi.

Ho notato che (chiamando con 2n il numero delle persone presenti) se la persona che in un certo istante ha la palla riporta sulla maglietta il numero "a", la persona che riceve la palla avrà il numero "2a" se "a" è minore o uguale della metà di n oppure avrà il numero -((n-a)*2+1) se "a" è maggiore della metà di n. Inoltre colui che alla fine passa la palla al numero +1 deve possedere sulla maglia il numero -n.

Ad esempio: 2n= 34, n= 17
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1
Da 1 a 2, da 2 a 4 da 4 a 8 da 8 a 16 da 16 a -3 da -3 a -6 da -6 a -12 da -12 a 11 da 11 a -13 da -13 a 9 da 9 a -17 da -17 a 1.
[Da 16 a -3: -3 = -((17-16)*2+1); da 11 a -13: -13 =-((17-11)*2+1)]

Cerco una ricorrenza, ma finora non l'ho trovata, o altri metodi risolutivi.
Ringrazio,
Saluti.

[axpgn]

Non trovando "appigli" (a parte le potenze di due), ho provato con quattro righe di basic per vedere se ne usciva qualcosa ma niente ... epperò se l'hanno messo trai quesiti dei giochi deve esserci una "scorciatoia"

Riporto qui il pezzo di codice per i "movimenti"

Codice:

    if p>n then

        s=2*n-p+1
        p=p-s


    else

        s=p
        p=p+s

    end if



dove $p$ è la posizione della palla (da $1$ a $2n$) e $s$ il "salto" che fa la palla.

Cordialmente, Alex

[giammaria]

Ho fatto lo stesso ragionamento di RobStam, con le sue stesse conclusioni; il fatto che nella risposta desse $n$ in funzione del numero dei passaggi (e non viceversa) mi aveva fatto sperare in qualcosa di diverso. Comunque insistiamo; magari a qualcuno verrà l'idea buona.
Non sarebbe male se chi ha esaminato molti valori di $n$ (io mi limito ad $n<=9$) indicasse il relativo numero di passaggi; di solito, vedendo molti numeri è più facile individuarne le regolarità e risalire alla loro origine.

[axpgn]

Se vuoi fino a diecimila ...

[giammaria]

Non esageriamo: direi che ne bastano una cinquantina e forse meno.
Ma la tua frase voleva essere uno scherzo, o davvero intendi che hai provato fino a $n=10000$ senza mai trovare 24 passaggi?

Già che scrivo, indico anche i miei ultimi parziali: ho notato che ogni numero può essere raggiunto in un solo modo, che certo non si entra in un ciclo senza fine e che al massimo si possono fare $2n$ passaggi; in alcuni casi li si fa tutti, in altri no.

[axpgn]

Certo che sono arrivato a $n=10000$ ma ne ho trovati con $24$ passaggi (mi pare poco più di una trentina); cinquanta numeri sono pochi, tra l'altro non ci sarebbero quelli con $24$ passaggi, il primo è il $59$

Comunque, se ti può essere utile, pubblico i primi cento ...

Testo nascosto, fai click qui per vederlo

Ordinati per $n$


E ordinati per $p$

Cordialmente, Alex

[giammaria]

Ho trovato il modo di limitare il numero di tentativi, che restano però ancora numerosi; mando comunque la mia soluzione perché potrebbe essere lo spunto per una migliore.

Se la palla è lanciata dal numero positivo $k$, essa arriva a
${(2k if k<=n/2),(2k-(2n+1) if k>n/2):}$
ed i due numeri differiscono di $2n+1$. Se la palla è lanciata da un numero negativo c'è qualche cambiamento di segno ma la conclusione è invariata.
Possiamo quindi dire che, modulo $2n+1$, ogni lancio raddoppia il valore; le operazioni di modulo possono essere fatte alla fine dei raddoppi. Affinché il tutto termini dopo 24 passaggi è quindi necessario che sia
$2^24=1 (mod 2n+1)$
Si ha
$2^24-1=(2^12+1)(2^6+1)(2^3+1)(2^3-1)= 4097*65*9*7=17*241*5*13*3^2*7$
e quindi i possibili valori di $2n+1$ devono essere formati dai fattori indicati.
Questo ragionamento garantisce che dopo 24 passaggi si arriva ad 1, ma potremmo esserci arrivati anche dopo un sottomultiplo di 24 (allora $p$ sarebbe quel sottomultiplo), quindi occorre ancora fare molti tentativi. I dati di axpgn danno $n=59$ e ne consegue $2n+1=119=7*17$, rientrante in quanto detto.

[axpgn]

Quindi basta contare i divisori di $2^p-1$ che nel caso di $p=24$ sarebbero $96$ (la risposta ufficiale fornita da RobStam è $95$, probabilmente va tolto $1$ per qualche motivo).

Gli interi minori di mille che hanno un ciclo di $24$ passaggi sono $16$ e tutti sono composti da (alcuni) fattori di $2^24-1$

Direi che hai risolto ...

Cordialmente, Alex