Pagina 1 di 2

dai giochi matematici del 2012

Inviato: dom feb 26, 2017 3:05 pm
da MB.enigmi
Un’epidemia di una strana malattia che fa
crescere dei bernoccoli ha colpito il paese della
matematica. Il numero dei malati al primo
giorno era M(1)=1, quello al secondo giorno
M(2)=14, quello al terzo giorno M(3)=43. Poi
per J maggiore o uguale a 4, M(J) si ottiene per
ricorrenza calcolando il resto della divisione per
2012 (tra 0 e 2011):
4[M(J-1)]-5[M(J-2]+[M(J-3)].
Si avrà quindi M(4)=104; M(5)=229;
M(6)=482; M(7)=991; M(8)=0; M(9)=33; etc.
Se, per disgrazia, l’epidemia dovesse durare
più di 5 anni e mezzo, quale sarebbe il
numero dei malati al 2012° giorno, ovvero
M(2012)?

Re: dai giochi matematici del 2012

Inviato: lun feb 27, 2017 12:58 am
da Pasquale
Scusa, non mi è chiaro il quesito. Cosa va diviso per 2012? M(j)? Perché m(4)=104, m(5)=229, ecc.?
Infine, solo per la precisione, trascorsi 5 anni e mezzo esatti, al 2012° giorno non ci si giunge.
Puoi controllare il testo del quesito o comunque chiarire?

Re: dai giochi matematici del 2012

Inviato: lun feb 27, 2017 7:12 am
da MB.enigmi
In effetti Pasquale hai ragione, ho postato il problema proprio perché non riuscivo a capire queste cose, il testo invece mi sembra sia corretto, ecco la fonte
http://matematica.unibocconi.it/sites/d ... arigi2.pdf

Re: dai giochi matematici del 2012

Inviato: lun feb 27, 2017 2:22 pm
da Bruno
C'è un errore di battitura nel testo, la ricorrenza corretta è:
4 · M(J-1) - 5 · M(J-2) + 2 · M(J-3).
Infatti:
4·43 - 5·14 + 2·1 = 104 = 2012·0 + 104,
4·104 - 5·43 + 2·14 = 229 = 2012·0 + 229,
4·229 - 5·104 + 2·43 = 482 = 2012·0 + 482,
4·482 - 5·229 + 2·104 = 991 = 2012·0 + 991,
4·991 - 5·482 + 2·229 = 2012 = 2012·1 + 0,
4·0 - 5·991 + 2·482 = -3991 = -2012·2 + 33, etc.

Re: dai giochi matematici del 2012

Inviato: lun feb 27, 2017 4:40 pm
da Pasquale
.............mi pareva: bravo Bruno, come sempre!

Con il Decimal Basic si potrebbe fare così:

DIM M(2012)
LET M(1)=1
LET M(2)=14
LET M(3)=43
FOR j=4 TO 2012
LET a=4*M(j-1)-5*M(j-2)+2*M(j-3)
LET M(j)=MOD(a,2012)
NEXT j
PRINT M(2012)
END

Risultato: 116

Ove ci interessasse M(10000000) ed ammesso che fossimo disposti ad attendere il tempo necessario per l'elaborazione, occorrerebbe apportare alla routine le opportune modifiche e quindi:

DIM M(10000000)
LET M(1)=1
LET M(2)=14
LET M(3)=43
FOR j=4 TO 10000000
LET a=4*M(j-1)-5*M(j-2)+2*M(j-3)
LET M(j)=MOD(a,2012)
NEXT j
PRINT M(10000000)
END

Risultato: 48

Se però ci interessasse ad esempio M(12000000), decimal Basic si rifiuterebbe di dimensionare una matrice di tale grandezza ed allora occorrerebbe pensare a qualcosa di diverso.
Ad esempio si potrebbe procedere come segue, sempre che si accettino attese sempre più impegnative:

LET a=1
LET b=14
LET c=43
LET j=3
DO
LET j=j+1
LET x=4*c-5*b+2*a
LET d=MOD(x,2012)
IF j=12000000 THEN
PRINT "M(";STR$(j);") =";d
EXIT DO
END IF
LET a=b
LET b=c
LET c=d
loop
END

Comunque, ne vien fuori M(12000000)=8 in circa 92" ed M(36000000)=1528 in circa 490"; vale a dire che triplicato il valore di j, si è più che quintuplicato il tempo di attesa (almeno sul mio p.c.), perché evidentemente una stessa operazione richiede tempi più lunghi di elaborazione, se effettuata su numeri maggiori dei precedenti.
Dunque, come soleva dire qualcuno di nostra conoscenza: "è la somma che fa il totale".

E allora? Si può fare qualcosa di meglio?

Re: dai giochi matematici del 2012

Inviato: lun feb 27, 2017 5:16 pm
da MB.enigmi
Si viene 116. Il programmino però era ciò che volevo evitare...
comunque bravo buon tentativo.
Se qualcuno avesse un metodo senza l'uso di un calcolatore si faccia avanti
:)

Re: dai giochi matematici del 2012

Inviato: lun feb 27, 2017 7:37 pm
da Info
per migliorare il programmino l'unico e`rimuovere un po' di assegnazioni penso, scriverlo cosi`:

Codice: Seleziona tutto

LET a=1
LET b=14
LET c=43
LET j=3
DO
	LET j=j+1
	LET x=4*c-5*b+2*a
	LET a=MOD(x,2012)
	IF j=12000000 THEN
		PRINT "M(";STR$(j);") =";a
		EXIT DO
	END IF
	
	LET j=j+1
	LET x=4*a-5*c+2*b
	LET b=MOD(x,2012)
	IF j=12000000 THEN
		PRINT "M(";STR$(j);") =";b
		EXIT DO
	END IF
	
	LET j=j+1
	LET x=4*b-5*a+2*c
	LET c=MOD(x,2012)
	IF j=12000000 THEN
		PRINT "M(";STR$(j);") =";c
		EXIT DO
	END IF
loop
END

cosa ne dite? Vorrebbe dire fare solo 3 assegnazioni ogni 3 numeri.... non so se sia possibile eliminare anche la x, tipo

Codice: Seleziona tutto

LET c=MOD(4*b-5*a+2*c,2012)
per l'ultima assegnazione
diventa solo un po' meno leggibile ma a volte bisogna scegliere se la velocita`o la comprensibilita`del codice

Re: dai giochi matematici del 2012

Inviato: lun feb 27, 2017 7:47 pm
da vittorio
Si può usare la formuletta
$M(t)=(2^{t+2}-3t-12) mod 2012$
valida per ogni t>0.
Per t=2012 si ottiene M(2012)=116.

Per ottenere la formula si consideri la successione ricorrente
$M(t+3)=4M(t+2)-5M(t+1)+2M(t)$ con M(1)=1 M(2)=14 M(3)=43
e la si risolva con i metodi tradizionali.
Ponendo $M(t)=x^2$ si ha $x^{t+3}-4x^{t+2}+5x^{t+1}-2x^{t}=0$ da cui, dividendo per $x^t$ si ottiene l'equazione di terzo grado $x^3-4x^2+5x-2=0$ che ha le soluzioni x=2 semplice e x=1 doppia.
La formula risolutiva sarà allora del tipo $M(t)=a2^t+(bt+c)1^t$ con a,b e c da determinarsi in base ai termini iniziali M(1), M(2), M(3).
Sostituendo si ottiene il sistema 2a+b+c=0 4a+2b+c=14 8a+3b+c=43 da cui a=8, b=-3 e c=-12, quindi la formula proposta.

Occorre ora considerare la questione dei residui modulo 2012 che fin qui ho trascurato. Si ha comunque che il residuo di una somma di più numeri modulo un qualsiasi numero P non è altro che la somma dei residui dei singoli addendi sempre modulo P.
Si può quindi considerare il residuo modulo 2012 alla fine del processo di iterazione e non ad ogni singolo passo.
Spero di essere stato utile.
Ciao
Vittorio

Re: dai giochi matematici del 2012

Inviato: mar feb 28, 2017 12:07 am
da Pasquale
Bene, l'appello è stato raccolto :shock: :idea: :wink:

Tuttavia è' possibile un controllo sui risultati a partire da j=4 e procedendo con 5, 6, ecc. ?

Re: dai giochi matematici del 2012

Inviato: mar feb 28, 2017 8:43 am
da Gianfranco
Pasquale chiede:
Tuttavia è' possibile un controllo sui risultati a partire da j=4 e procedendo con 5, 6, ecc. ?
In effetti c'è un piccolo errore di scrittura nella formula di Vittorio.
La formula corretta è:
$\large M(t)=(2^{t+3}-3t-12) \text{ mod } 2012$
I risultati di questa formula coincidono con i risultati del programma per computer.
WOW! Problema risolto.
---
Piccola nota aggiuntiva.
Anch'io ho scritto un programmino ispirandomi ai programmi di Pasquale e Info. Cos'ha di speciale? Usa un vettore di soli 4 elementi ed è brevissimo ma nello stesso tempo è leggibile nel senso che rispecchia chiaramente la struttura del problema.
Ho iniziato a programmare con la calcolatrice HP-25 (ringrazio il professor Pietro Arduini) e successivamente con il Vic-20 e il Commodore-64.
I programmi con la HP avevano al massimo 49 passi di programmazione e si disponeva di 8 memorie, ciascuna delle quali poteva contenere un numero.
I programmi in BASIC col Vic-20 dovevano stare in 3,5 Kb di memoria.
E' stata per me una scuola di concisione!
Comunque, il program-minimo è questo:

Codice: Seleziona tutto

DIM M(4)
LET M(1)=1
LET M(2)=14
LET M(3)=43
LET j=3

DO UNTIL j=2012
   LET j=j+1
   LET M(4)=MOD(4*M(3)-5*M(2)+2*M(1),2012)    
   LET M(1)=M(2)
   LET M(2)=M(3)
   LET M(3)=M(4)
LOOP

PRINT M(3)
END

Re: dai giochi matematici del 2012

Inviato: mar feb 28, 2017 7:15 pm
da Pasquale
Bene, bene: bellissima, più matematica, interessante ed immediata la formula di Vittorio, che per sola uniformità e praticità riepilogo come segue:

$\text M_j= (2^{j+3}-3j-12) MOD 2012$

Il programmino invece, che punta solo al calcolo, resta un divertimento come nello spirito di Base5 e la sintesi di Gianfranco dona più eleganza al suo sviluppo nel linguaggio utilizzato.

Ora, a parte il quesito posto così come è stato posto, volendolo estendere a valori più alti di j e lasciando inalterato il modulo 2012, a puro titolo di curiosità, divertimento e approfondimento, ho notato che:

la formula immediata contiene una potenza e che se ci procuriamo un calcolatore a basso costo, tipo Decimal Basic, possiamo scrivere, solo dopo aver selezionato la doppia precisione:

LET j=2012
LET Mj=MOD(2^(j+3)-3*j-12,2012)
PRINT Mj

ottenendo l'ormai noto risultato di 116.

Proviamo adesso con j=3345, sempre in doppia precisione, e poi con j=3346: cosa notiamo?

Abbiamo poi visto più su che il programmino in formato brutto anatroccolo è riuscito a tirar fuori un risultato con j=36.000.000 in circa 490 secondi, così come vi riesce l'elegante routine di Gianfranco in ........... 626 secondi. Come mai? Accade perché la routine invece che su semplici variabili opera su matrici, anche se di piccole dimensioni, caratteristica questa cui riconosco pregio ed ingegno, perché evita che si blocchi l'elaborazione per un valore ad esempio di j=12.000.000, come avevo fatto rilevare in precedenza.
In realtà il ciclo Do-Loop che opera tutto su matrici, con immissioni ed estrazioni di dati reiterati per 36 milioni di volte, a causa della struttura stessa del linguaggio, comporta un aumento dei tempi di elaborazione.
Conclusione: non sempre conta la quantità di righe scritte, ma il contenuto; per cui, alla luce di quanto si è evidenziato nella discussione, per j=36.000.000, la geniale routine di calcolo, pur se con più righe di scrittura, cioè quella di Tino, sforna il risultato 1528 in circa 282 secondi, a fronte dei precedenti 490 e 626 secondi (tutti tempi relativi al mio vecchio p.c., al linguaggio utilizzato, al sistema operativo).
La risposta per Tino sull'uso di un solo comando nel calcolo del modulo 2012 è positiva: i due comandi avevano solo uno scopo di una più agevole leggibilità.
Sarà mai possibile fare di meglio?
Appare comunque evidente che da un punto di vista pratico ogni soluzione avrà il proprio limite relativamente alla grandezza di j.

Riporto per intero il programma scritto da Tino con l'aggiunta del calcolo dei tempi di elaborazione:
LET a=1
LET b=14
LET c=43
LET j=3

LET t1=TIME
DO

LET j=j+1
LET a=MOD(4*c-5*b+2*a,2012)
IF j=36000000 THEN
PRINT "M(";STR${$}$(j);") =";a
EXIT DO
END IF

LET j=j+1
LET b=MOD(4*a-5*c+2*b,2012)
IF j=36000000 THEN
PRINT "M(";STR${$}$(j);") =";b
EXIT DO
END IF

LET j=j+1
LET c=MOD(4*b-5*a+2*c,2012)
IF j=36000000 THEN
PRINT "M(";STR${$}$(j);") =";c
EXIT DO
END IF

LOOP

LET t2=TIME
PRINT "tempo di elaborazione espresso in minuti secondi:";t2-t1

END

Aggiungo un benvenuto ed un ringraziamento per Mr.enigmi, che con la sua recente iscrizione a Base5 e le sue proposte ha risvegliato un pochino il can dormiente.

Re: dai giochi matematici del 2012

Inviato: mar feb 28, 2017 8:01 pm
da vittorio
Come prima cosa desidero scusarmi per lo stupido errore commesso.
Ho poi visto che Pasquale ha calcolato M(12000000) e M(36000000) ed ho pensato di calcolarli a mia volta a mano utilizzando la formula (ed eventualmente una buona calcolatrice). In primo luogo ho determinato che $2^{251k+h}$ e $2^h$ hanno lo stesso residuo modulo 2012 quindi ho proceduto come segue:
1) ho calcolato h = mod(t+3,251)
2) ho calcolato $r=mod(2^h,2012)$
3) ho calcolato s=mod(3t,2012)
4) ho calcolato M(t)=mod(r-s-12,2012) ottenendo il risultato.
Per t=12000000 si ottiene h=295, r=1316, s=1296 M=1316-1296-12=8 (che è già il residuo modulo 2012).
per t=36000000 si ottiene h=77, r=1404, s=1876 r-s-12=-484 da cui M=2012-484=1528.
I risultati corrispondono ai valori dati da Pasquale
Ciao e spero di non aver fatto errori
Vittorio

Re: dai giochi matematici del 2012

Inviato: mar feb 28, 2017 10:33 pm
da Gianfranco
Vittorio, NON devi scusarti. La tua soluzione è perfetta, anche nei valori di a, b, c. C'è stato soltanto un refuso nella trascrizione di un esponente nella formula finale.
Pasquale, la lentezza del mio programmino è proprio dovut all'uso di variabili indicizzate. Usando variabili "normali" i tempi sono paragonabili a quelli di Tino.

Codice: Seleziona tutto

LET a=1
LET b=14
LET c=43
LET t1=TIME

FOR j=4 TO 36000000
   LET d=MOD(4*c-5*b+2*a,2012) 
   LET a=b
   LET b=c
   LET c=d
NEXT j

PRINT c
LET t2=TIME
PRINT "Tempo sec.:";t2-t1

END
Il programma di Tino, intelligentemente, evita le istruzioni di shift delle variabili ad ogni ciclo ma introduce altre istruzioni per incrementare il contatore j e per testare se il ciclo è finito. Credo che sotto questo aspetto possa essere migliorato.

Re: dai giochi matematici del 2012

Inviato: mer mar 01, 2017 8:38 am
da Bruno
Quando dite "Tino" state riferendovi a Info, giusto?

Re: dai giochi matematici del 2012

Inviato: mer mar 01, 2017 9:00 am
da Gianfranco
Bruno, da parte mia sì.
In realtà pensavo "Info" ma ho scritto "Tino" perché i miei pochi neuroni rimasti ancora vivi erano concentrati sul post di Pasquale che lo citava come "Tino".