Online World Math Contest - quesito 17

Giochi di Archimede, Gara provinciale, Gara Nazionale, Gara a squadre, Giochi della Bocconi, Kangourou della Matematica, Corsi di preparazione, Simulazioni...
Rispondi
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Online World Math Contest - quesito 17

Messaggio da ronny »

Ciao a tutti, qualcuno ha partecipato all' Online World Math Contest organizzato dalla federazione svizzera?
In pratica erano le finalissime dei Campionati di Giochi Matematici della Bocconi, che non sono stati svolti in presenza,
ma in modalitò online ed apeta a tutti.
Sono giochi che rientrano nel loro stile matematico ma anche un po0 logico-enigmistico. Però questo testo mi è piaciuto
abbastanza e mi mi ha messo molto in difficoltà.
Sto cercando di risolvere tutti gli esercizi con calma piano piano. Però il 17 non sono sicuro di averlo capito.

17. BALBETTII (coefficiente 17)
Fibo gioca con una serie di cui il primo
termine è 1, il secondo termine è 1 e
successivamente ciascun termine è la
somma dei due precedenti: 1, 1, 2, 3, 5, 8, 13, ... Inizia dal primo termine, lo moltiplica per
10 e gli aggiunge il secondo, moltiplica il
risultato per 10 e aggiunge il terzo, e così
via. Fibo ottiene così 1, 11, 112, 1123, 11235, 112358,
1123593 (= 112358 x 10 + 13), ...
Dopo un po’, ottiene dei blocchi di numeri
che si ripetono uno dopo l’altro
all’infinito.
Quante cifre contengono questi
blocchi, come minimo?


Cosa si intende per blocchi di numeri (o di cifre?) che si ripetono?
Cioè se metto uno accando all'altro i numeri della sequenza di Fibo dopo un po' ottengo che ha un gruppetto di n cifre che si ripete di continuo?
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Online World Math Contest - quesito 17

Messaggio da afullo »

Ciao! Io avevo pensato di farli, poi però sabato ero preso e non sono riuscito ad essere della partita; mi rifarò sabato 11 in presenza a Milano. Ho visto che nella categoria "regina" G c'è stata una bella doppietta italiana, dovrebbero uscire anche i ranking per nazione ma le premesse sono buonissime! :D

Sì, penso che intenda quello. Bisognerebbe provare a scrivere un certo numero di elementi con un software (probabilmente serve un CAS o un ACE, altrimenti si esauriscono in fretta le cifre dei 64 bit sia degli interi che dei numeri a virgola mobile), e vedere quello che effettivamente succede... ;)
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Re: Online World Math Contest - quesito 17

Messaggio da ronny »

Ho provato ieri a scrivere un programmino c++ (ho usato la libreria gmp se ti interessa). Ti riporto di seguito le prime iterazioni:
i: numero di iterazione (si parte dal terzo numero di fibonacci per comodità)
fn: numero di fibonacci
bn: numero della serie di Fibo

Al passo 54 si vede che è presente il blocco:

11235955056179775280898876404494382022471910

e che la cifra successiva è un "1" cioè l'inizio di un nuovo blocco uguale.

Da qui ho capito cosa chiede l'esercizio. Ma non per ora la minima idea di come analizzare il problema.

i: 0 fn: 2 bn: 112
i: 1 fn: 3 bn: 1123
i: 2 fn: 5 bn: 11235
i: 3 fn: 8 bn: 112358
i: 4 fn: 13 bn: 1123593
i: 5 fn: 21 bn: 11235951
i: 6 fn: 34 bn: 112359544
i: 7 fn: 55 bn: 1123595495
i: 8 fn: 89 bn: 11235955039
i: 9 fn: 144 bn: 112359550534
i: 10 fn: 233 bn: 1123595505573
i: 11 fn: 377 bn: 11235955056107
i: 12 fn: 610 bn: 112359550561680
i: 13 fn: 987 bn: 1123595505617787
i: 14 fn: 1597 bn: 11235955056179467
i: 15 fn: 2584 bn: 112359550561797254
i: 16 fn: 4181 bn: 1123595505617976721
i: 17 fn: 6765 bn: 11235955056179773975
i: 18 fn: 10946 bn: 112359550561797750696
i: 19 fn: 17711 bn: 1123595505617977524671
i: 20 fn: 28657 bn: 11235955056179775275367
i: 21 fn: 46368 bn: 112359550561797752800038
i: 22 fn: 75025 bn: 1123595505617977528075405
i: 23 fn: 121393 bn: 11235955056179775280875443
i: 24 fn: 196418 bn: 112359550561797752808950848
i: 25 fn: 317811 bn: 1123595505617977528089826291
i: 26 fn: 514229 bn: 11235955056179775280898777139
i: 27 fn: 832040 bn: 112359550561797752808988603430
i: 28 fn: 1346269 bn: 1123595505617977528089887380569
i: 29 fn: 2178309 bn: 11235955056179775280898875983999
i: 30 fn: 3524578 bn: 112359550561797752808988763364568
i: 31 fn: 5702887 bn: 1123595505617977528089887639348567
i: 32 fn: 9227465 bn: 11235955056179775280898876402713135
i: 33 fn: 14930352 bn: 112359550561797752808988764042061702
i: 34 fn: 24157817 bn: 1123595505617977528089887640444774837
i: 35 fn: 39088169 bn: 11235955056179775280898876404486836539
i: 36 fn: 63245986 bn: 112359550561797752808988764044931611376
i: 37 fn: 102334155 bn: 1123595505617977528089887640449418447915
i: 38 fn: 165580141 bn: 11235955056179775280898876404494350059291
i: 39 fn: 267914296 bn: 112359550561797752808988764044943768507206
i: 40 fn: 433494437 bn: 1123595505617977528089887640449438118566497
i: 41 fn: 701408733 bn: 11235955056179775280898876404494381887073703
i: 42 fn: 1134903170 bn: 112359550561797752808988764044943820005640200
i: 43 fn: 1836311903 bn: 1123595505617977528089887640449438201892713903
i: 44 fn: 2971215073 bn: 11235955056179775280898876404494382021898354103
i: 45 fn: 4807526976 bn: 112359550561797752808988764044943820223791068006
i: 46 fn: 7778742049 bn: 1123595505617977528089887640449438202245689422109
i: 47 fn: 12586269025 bn: 11235955056179775280898876404494382022469480490115
i: 48 fn: 20365011074 bn: 112359550561797752808988764044943820224715169912224
i: 49 fn: 32951280099 bn: 1123595505617977528089887640449438202247184650402339
i: 50 fn: 53316291173 bn: 11235955056179775280898876404494382022471899820314563
i: 51 fn: 86267571272 bn: 112359550561797752808988764044943820224719084470716902
i: 52 fn: 139583862445 bn: 1123595505617977528089887640449438202247190984291031465
i: 53 fn: 225851433717 bn: 11235955056179775280898876404494382022471910068761748367
i: 54 fn: 365435296162 bn: 112359550561797752808988764044943820224719101053052779832
i: 55 fn: 591286729879 bn: 1123595505617977528089887640449438202247191011121814528199
i: 56 fn: 956722026041 bn: 11235955056179775280898876404494382022471910112174867308031
i: 57 fn: 1548008755920 bn: 112359550561797752808988764044943820224719101123296681836230
i: 58 fn: 2504730781961 bn: 1123595505617977528089887640449438202247191011235471549144261
i: 59 fn: 4052739537881 bn: 11235955056179775280898876404494382022471910112358768230980491
i: 60 fn: 6557470319842 bn: 112359550561797752808988764044943820224719101123594239780124752
i: 61 fn: 10610209857723 bn: 1123595505617977528089887640449438202247191011235953008011105243
i: 62 fn: 17167680177565 bn: 11235955056179775280898876404494382022471910112359547247791229995
i: 63 fn: 27777890035288 bn: 112359550561797752808988764044943820224719101123595500255802335238
i: 64 fn: 44945570212853 bn: 1123595505617977528089887640449438202247191011235955047503593565233
i: 65 fn: 72723460248141 bn: 11235955056179775280898876404494382022471910112359550547759395900471
i: 66 fn: 117669030460994 bn: 112359550561797752808988764044943820224719101123595505595262989465704
i: 67 fn: 190392490709135 bn: 1123595505617977528089887640449438202247191011235955056143022385366175
i: 68 fn: 308061521170129 bn: 11235955056179775280898876404494382022471910112359550561738285374831879
i: 69 fn: 498454011879264 bn: 112359550561797752808988764044943820224719101123595505617881307760198054
i: 70 fn: 806515533049393 bn: 1123595505617977528089887640449438202247191011235955056179619593135029933
i: 71 fn: 1304969544928657 bn: 11235955056179775280898876404494382022471910112359550561797500900895227987
i: 72 fn: 2111485077978050 bn: 112359550561797752808988764044943820224719101123595505617977120494030257920
i: 73 fn: 3416454622906707 bn: 1123595505617977528089887640449438202247191011235955056179774621394925485907
i: 74 fn: 5527939700884757 bn: 11235955056179775280898876404494382022471910112359550561797751741888955743827
i: 75 fn: 8944394323791464 bn: 112359550561797752808988764044943820224719101123595505617977526363283881229734
i: 76 fn: 14472334024676221 bn: 1123595505617977528089887640449438202247191011235955056179775278105172836973561
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Online World Math Contest - quesito 17

Messaggio da afullo »

Ok, si direbbe quindi che la risposta sia 45, ma in effetti nemmeno a me vengono in mente idee su come affrontarlo...
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Re: Online World Math Contest - quesito 17

Messaggio da ronny »

Il blocco che si ripete è "11235955056179775280898876404494382022471910" che mi sembra lungo 44 cifre. Che infatti è la soluzione ufficiale.

Immagino che il fatto che si formi un blocco che si ripete sia legato all'utilizzo della successione di fibonacci. Ma non so come sfruttarlo.
In pratica i vari Bn sono dati dalla somma di:

[tex]B_n = 10^{n-1}F_1 + 10^{n-2}F_2 + ... + F_n[/tex]

Espandendo qualche [tex]F_i[/tex] si possono ottenere dei coefficienti 11... ma non capisco da cosa di deduce che il blocco di 44 cifre si ripete.
Nella sequenza di fibonacci non ci vedo un modello del genere.

Forse la furmula non ricorsiva dei numeri di Fibonacci può aiutarci? (non me la ricordo, ma mi sembra di averla vista in passato).
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Re: Online World Math Contest - quesito 17

Messaggio da ronny »

Peccato non ci riesca. Volevo scrivere le soluzioni commentate e mi manca solo questo.

Provo a chidere nel forum delle olimpiadi di matematica.

Afullo, conosci qualche altro forum dove provare a chiedere?
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Online World Math Contest - quesito 17

Messaggio da afullo »

Ok, ho contato una cifra in più. Io pensavo ai B_n divisi per 10^n, che formano una successione che converge quindi ad un razionale; forse era stato affrontato qualcosa del genere in un Campigotto passato. Oltre all'oliforum, potresti provare su Matematicamente e su Art of Problem Solving...
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Re: Online World Math Contest - quesito 17

Messaggio da ronny »

Ho avuto una risposta su art of problemsolving. Avevi visto giusto con la successione dei Bn divisi per 10^N. Questa successione è fatta da numeri i cui decimali sono le stesse cifre dei Bn. Il valore a cui converge è quindi un numero con una parte decimale caratterizzata dal blocco che si ripete, cioè ha una parte periodica di cui vogliamo sapere il periodo.

Questa è soluzione che mi hanno inviato:

The digits are the same of [tex]S=\sum_{k=0}^\infty F_k10^{-k}[/tex]. It is well known that [tex]\sum_{k=0}^{\infty}F_kx^k=\frac{x}{1-x-x^2}[/tex]
So [tex]S=\frac{10}{89}[/tex] so the period of this number is [tex]ord_{89}(10)=44[/tex]

E' un po' tecnica, ma tu la capirai al volo.

Ho approfondito i vari passaggi ed ho visto che non ci sarei arrivato. Non mi ricordavo la funzione generatrice della serie di Fibonacci.
Trovare il periodo di una frazione, che si rivela essere 44, può essere un calcolo molto lungo. Non avevo pensato che si potesse vedere
come ordine moltiplicativo di 10 modulo 89. Comunque anche calcolare questo ordine moltiplicativo non è velocissimo.
Vanno provati solo i divisori di 88, ma fare 10 elevato 44 modulo 89 richiede molto tempo. O c'è un modo più veloce?
ronny
Messaggi: 125
Iscritto il: 20/04/2019, 23:28

Re: Online World Math Contest - quesito 17

Messaggio da ronny »

Inoltre hanno scritto che l'ordine moltiplicativo deve essere un divisore di 44 perché:

$$10^{44}=10^\frac{89-1}{2}\equiv\left(\frac{10}{89}\right)=1\pmod{89}$$

non capisco questo passaggio:

$$10^\frac{89-1}{2}\equiv\left(\frac{10}{89}\right)\pmod{89}$$

e questo:

$$\left(\frac{10}{89}\right)=1\pmod{89}$$

Forse mi sfugge la nostazione di quelle parentesi sulla frazione.
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Online World Math Contest - quesito 17

Messaggio da afullo »

ronny ha scritto: 07/09/2021, 10:52 Ho avuto una risposta su art of problemsolving. Avevi visto giusto con la successione dei Bn divisi per 10^N. Questa successione è fatta da numeri i cui decimali sono le stesse cifre dei Bn. Il valore a cui converge è quindi un numero con una parte decimale caratterizzata dal blocco che si ripete, cioè ha una parte periodica di cui vogliamo sapere il periodo.

Questa è soluzione che mi hanno inviato:

The digits are the same of [tex]S=\sum_{k=0}^\infty F_k10^{-k}[/tex]. It is well known that [tex]\sum_{k=0}^{\infty}F_kx^k=\frac{x}{1-x-x^2}[/tex]
So [tex]S=\frac{10}{89}[/tex] so the period of this number is [tex]ord_{89}(10)=44[/tex]

E' un po' tecnica, ma tu la capirai al volo.

Ho approfondito i vari passaggi ed ho visto che non ci sarei arrivato. Non mi ricordavo la funzione generatrice della serie di Fibonacci.
Trovare il periodo di una frazione, che si rivela essere 44, può essere un calcolo molto lungo. Non avevo pensato che si potesse vedere
come ordine moltiplicativo di 10 modulo 89. Comunque anche calcolare questo ordine moltiplicativo non è velocissimo.
Vanno provati solo i divisori di 88, ma fare 10 elevato 44 modulo 89 richiede molto tempo. O c'è un modo più veloce?
Sì, oltre che tecnica direi anche molto "cannone", nel senso che se conosci la funzione generatrice allora ti basta sostituire x=1/10 per arrivare già a metà del problema (resta poi l'ordine moltiplicativo), mentre se non la sai non puoi proprio approcciare il problema così, in quanto non ti viene data alcuna informazione per ricostruirla a parte il suo valore.

Ci sono tecniche per calcolare rapidamente determinati ordini moltiplicativi, bisognerebbe approfondire con letteratura specifica sul tema che non conosco appieno. Anche l'uso delle parentesi del post successivo mi sfugge, e non l'ho nemmeno trovato sul Gobbino.

Io avrei osservato sperimentalmente che la successione dei 10 elevato n modulo 89 segue la regola di Fibonacci della somma dei due elementi precedenti, poi a seconda del tempo a disposizione avrei provato a dimostrarlo per usare il risultato con sicurezza, altrimenti penso che avrei corso il rischio "fidandomi" (ecco la famosa differenza tra i numerici della Bocconi e i dimostrativi delle Olimpiadi di cui si parla spesso :mrgreen:); se si è veloci di conto calcolare addizioni ripetute (con i "meno 89" del caso) non richiede tantissimo tempo, certo più conti si fanno e più si rischia di commettere almeno un errore, ma di solito non è nella fase computazionale che sbaglio i problemi... :lol:
Rispondi