dai giochi matematici del 2012

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

MB.enigmi
Nuovo utente
Nuovo utente
Messaggi: 18
Iscritto il: dom gen 15, 2017 9:02 am

dai giochi matematici del 2012

Messaggio 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)?

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: dai giochi matematici del 2012

Messaggio 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?
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

MB.enigmi
Nuovo utente
Nuovo utente
Messaggi: 18
Iscritto il: dom gen 15, 2017 9:02 am

Re: dai giochi matematici del 2012

Messaggio 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

Bruno
Livello 10
Livello 10
Messaggi: 2020
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Re: dai giochi matematici del 2012

Messaggio 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.
(Bruno)

...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: dai giochi matematici del 2012

Messaggio 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?
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

MB.enigmi
Nuovo utente
Nuovo utente
Messaggi: 18
Iscritto il: dom gen 15, 2017 9:02 am

Re: dai giochi matematici del 2012

Messaggio 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
:)

Info
Livello 5
Livello 5
Messaggi: 377
Iscritto il: lun nov 21, 2005 1:11 pm
Contatta:

Re: dai giochi matematici del 2012

Messaggio 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

vittorio
Livello 3
Livello 3
Messaggi: 63
Iscritto il: lun ago 20, 2007 9:29 am
Località: Ravenna

Re: dai giochi matematici del 2012

Messaggio 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
Vittorio

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: dai giochi matematici del 2012

Messaggio 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. ?
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: dai giochi matematici del 2012

Messaggio 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
Pace e bene a tutti.
Gianfranco

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: dai giochi matematici del 2012

Messaggio 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.
Ultima modifica di Pasquale il mer mar 22, 2017 12:37 am, modificato 3 volte in totale.
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

vittorio
Livello 3
Livello 3
Messaggi: 63
Iscritto il: lun ago 20, 2007 9:29 am
Località: Ravenna

Re: dai giochi matematici del 2012

Messaggio 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
Vittorio

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: dai giochi matematici del 2012

Messaggio 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.
Pace e bene a tutti.
Gianfranco

Bruno
Livello 10
Livello 10
Messaggi: 2020
Iscritto il: lun nov 21, 2005 6:07 pm
Località: Bologna

Re: dai giochi matematici del 2012

Messaggio da Bruno »

Quando dite "Tino" state riferendovi a Info, giusto?
(Bruno)

...........................
Invisibile un vento
l'ha apena sfioragia
sospension d'un momento;
e la bola iridessente gera 'ndagia.
{Biagio Marin}
................................................................
Meglio soluzioni sbagliate che risposte esatte.
{Rudi Mathematici}

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: dai giochi matematici del 2012

Messaggio 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".
Pace e bene a tutti.
Gianfranco

Rispondi