Coelestis - Il Forum Italiano di Astronomia

Coelestis - Il Forum Italiano di Astronomia (http://www.trekportal.it/coelestis/index.php)
-   Rudi Mathematici (http://www.trekportal.it/coelestis/forumdisplay.php?f=11)
-   -   Qualche quiz (http://www.trekportal.it/coelestis/showthread.php?t=33691)

aspesi 31-12-11 10:25

Re: Qualche quiz
 
Quote:

astromauh (Scrivi 551580)
Ma dovrei cercare di creare quante pi regioni possibile?

E' questo lo scopo del quiz?


E' sufficiente evitare di prendere punti opposti?

:confused:

Lo scopo determinare per un numero qualsiasi N (es. se N=15, R=1471:)) di punti distinti della circonferenza, qual il numero massimo di regioni che si possono formare.

La rappresentazione grafica diventa sempre pi difficile, mano a mano che il numero dei punti aumenta.
Penso sia fondamentale ricordare quello che ha sottolineato Erasmus: " Ogni volta che pi di 2 corde si intersecano nello stesso punto, il numero di regioni viene di meno del massimo possibile"

:hello:

nino280 31-12-11 16:18

Re: Qualche quiz
 
Vecchissima discussione.
Mizarino l'aveva risolta col suo famoso "Triangolo di Mizarino".:D
http://trekportal.it/coelestis/showthread.php?t=15832

Il triangolo di Mizarino:





Ciao

aspesi 31-12-11 20:02

Re: Qualche quiz
 
Quote:

nino280 (Scrivi 551758)
Vecchissima discussione.

Ciao

Questo quiz un classico.
Dovevo immaginarlo che se ne fosse gi discusso.
Ricordo che a me fu proposto nel 2000, fra altri giochi matematici.

Mi scuso per la ripetizione :o, ma nel 2008 non frequentavo ancora questo forum.

Comunque, non c' bisogno di inventarsi un triangolo particolare ;); basta prendere quello arcinoto di Tartaglia e fermarsi alla somma dei primi cinque termini di ogni riga...

Codice:

                                                        1                                  1
                                                      1    1                                2
                                                  1    2    1                              4
                                                1    3    3    1                          8
                                            1    4    6    4    1                        16
                                          1    5  10  10  5    -                      31
                                      1    6  15  20  15  -    -                  57
                                    1    7  21  35  35  -    -    -                99

Oltre alla formula trovata da Erasmus nel link di Nino280, si pu usare anche questa formula ricorsiva:

a(n) = 5a(n-1) - 10a(n-2) + 10a(n-3) - 5a(n-4) + a(n-5)

dopo aver determinato:
a(1) = 1
a(2) = 2
a(3) = 4
a(4) = 8
a(5) = 16

:hello:

nino280 31-12-11 20:10

Re: Qualche quiz
 
B b b buon hanno ha ttt tuttt sic sic!

Erasmus 01-01-12 00:32

Re: Qualche quiz
 
Quote:

aspesi (Scrivi 551808)
Questo quiz un classico.
Dovevo immaginarlo che se ne fosse gi discusso.
Ricordo che a me fu proposto nel 2000, fra altri giochi matematici.

Mi scuso per la ripetizione :o, ma nel 2008 non frequentavo ancora questo forum.

Comunque, non c' bisogno di inventarsi un triangolo particolare ;); basta prendere quello arcinoto di Tartaglia e fermarsi alla somma dei primi cinque termini di ogni riga...

Codice:

                                                        1                                  1
                                                      1    1                                2
                                                  1    2    1                              4
                                                1    3    3    1                          8
                                            1    4    6    4    1                        16
                                          1    5  10  10  5    -                      31
                                      1    6  15  20  15  -    -                  57
                                    1    7  21  35  35  -    -    -                99


Potevi aspettare un po', no?
Ho appena finito di risolvere il quiz (anche 'sta volta per via "euristica").

A naso mi parso che dovesse essere una funzione polinomiale.
Sono andato a contare le regioni per n = 7, trovando R(7) = 57.
Ecco qua:
=> R(7) = 57, PNG

La "formula" deve dare:
R(0) = 1;
R(1) = 1;
R(2) = 2;
R(3) = 4;
R(5) = 8;
R(5) = 16;

R(6) = 31;
R(7) = 57.
Dovendo imbroccare quei 5 termini [che sembrano i primi di una progressione geometrica di ragione 2, ma questo non ha importanza, i valori potrebbero essere qualsiasi altri], ho fatto l'ipotesi che la "formula" fosse polinomiale di 4 grado, cio del tipo:
R(N) = A + BN + CN^2 + DN^3 + En^4.
Ho calcolato le costanti A, B, C, D e E come incognite del sistema lineare:
R(1) = A + B + C + D + E = 1
R(2) = A + 2B + 4C + 8D + 16E = 2
R(3) = A + 3B + 9C + 27D + 81E = 4
R(4) = A + 4B + 16C + 64D + 256E = 8
R(5) = A + 5B + 25C + 125D + 625E = 16

Si trova cos:
A = 1 = 24/24;
B = 3/4= 18/24;
C = 23/24;
D = 1/4; = 6/24;
E = 1/24.

La "formula" trovata cio:
Codice:


            24  18N + 23N^2 6N^3 + N^4
R(N) =
                                24                             

Siccome funziona per N = 0, N = 6 e N = 7, la "formula" senz'altro quella giusta! ;)
-------------
Non mi ricordo di avere gi risolto il quiz, anche se vagamente mi pare di ricordare un quiz posto dal superlatitante Piotr(ora; allora frequentatore) in cui c'era una successione che pareva una progressione di ragione 2, ossia
1, 2, 4, 8, 16
ma poi invece che 32 il termine successivo era 31.
Andr poi a vedere cosa avevo scritto l dove dice Nino I.
-------
P.S.
Controllare che la mia "formula" d R(15) = 1471, come diceva Nno II.
Quote:

aspesi (Scrivi 551808)
Oltre alla formula trovata da Erasmus nel link di Nino280, si pu usare anche questa formula ricorsiva:

a(n) = 5a(n-1) - 10a(n-2) + 10a(n-3) - 5a(n-4) + a(n-5)

Lo credo bene!
Infatti, come ho spiegato (ormai per ben 3 volte), ogni sequenza polinomiale di grado k1 "linearmente dipendente di ordine k" con polinomio caratteristico
P(x) = (x1)^k.
Essendo questa sequenza polinomiale di 4 grado "linearmente dipendente di ordine 5" con polinomio caratteristico
P(x) = (x 1) ^5 = x^5 5x^4 + 10x^3 10x^2 + 5x 1.
Il che significa proprio:
R(N+5) 5R(n+4) + 10R(N+3) 10R(N+2) + 5R(N+1) R(N) = 0 per ogni N.
Questa formula (di dipendenza lineare di ordine 5) vale non solo per il particolare problema in questione, ma per qualsiasi sequenza polinomiale di 4 grado (ossia con coefficienti del polinomio A, B, C, D e E qualsiasi purch sia E ≠ 0, altrimenti non di 4 grado ;) ).
--------------------
Occhio: meglio dire "ricorrente" (anizich "ricorsiva")
L'aggettivo "ricorsivo" nell'italiano comune vuol dire la stessa cosa di "ricorrente"; ma in informatica ha una accezione specifica che ben diversa da questa!

Una formula definita per "ricorrenza" si pu programmare con algoritmo iterativo o, invece "ricorsivo" (o "recursivo" come si sempre detto in telecomunicazioni per procedimenti analoghi agli algoritmi "recursivi" dell'informatica).

Una procedura ("routine") ricorsiva dipende da (almeno) un parametro variabile. Se la si fa "girare", richiama s stessa con parametro un passo soltanto diverso da quello con cui "gira" tranne il caso in cui il parametro ha un determinato valore. Si scrive magari in qualche riga soltanto: ma quando "gira" richiama s stessa, gira perci una seconda volta con parametro scalato di un passo e girando si richiama ancora, ecc. fino ad arrivare al valore di scappatoia del parametro. Allora i richiami si richiudono in cascata rovescia di quella in cui si erano aperti permettendo di chiudersi infine anche al primo richiamo (quello fatto esternamente alla "routine").
Faccio l'esempio pi facile che c' per capire la differenza tra "iterativo" e "ricorsivo"
Ovviamente, scrivo in Pascal, cos capisce chiunque.
Codice:

Function FACTORIAL_1(n: integer): integer; {Algoritmo iterativo}
  var f: integer;
  begin
      f:=1;
      if n>0 then
      repeat
        f:=n*f; n:= n1
      until n = 0;
      FACTORIAL_1:=f
  end;
Function FACTORIAL_2(n: integer): integer; {Algoritmo recursivo}
  begin
      if n=0 then FACTORIAL_2:=1
      else FACTORIAL_2:=n*FACTORIAL_2(n1)
  end;

Ciao a tutti.
BUON ANNO!

aspesi 01-01-12 09:27

Re: Qualche quiz
 
Quote:

Erasmus (Scrivi 551825)
Potevi aspettare un po', no?
Ho appena finito di risolvere il quiz (anche 'sta volta per via "euristica").

Dovresti dirlo anche a Nino280 ...:)

Quote:

A naso mi parso che dovesse essere una funzione polinomiale.
Sono andato a contare le regioni per n = 7, trovando R(7) = 57.
Ecco qua:
=> R(7) = 57, PNG
Bello! :ok:

Quote:

Occhio: meglio dire "ricorrente" (anizich "ricorsiva")
L'aggettivo "ricorsivo" nell'italiano comune vuol dire la stessa cosa di "ricorrente"; ma in informatica ha una accezione specifica che ben diversa da questa!

Ciao a tutti.
BUON ANNO!
Cominci gi al primo dell'anno...:D

BUON ANNO
:hello:

aspesi 14-01-12 12:37

Re: Qualche quiz
 
Definiamo triangoli pitagorici quasi-isosceli i triangoli rettangoli con lati interi nei quali la differenza tra la lunghezza dei cateti, oppure la differenza fra la lunghezza dell'ipotenusa e di un cateto uguale a 1.

Esempio: 3-4-5; oppure 7-24-25; oppure 20-21-29; ecc....

Una famiglia quasi isoscele con ipotenusa - cateto = 1 facile da ottenere.
Basta generare le Terne Pitagoriche Primitive:
Cateto 1 = m^2 - n^2
Cateto 2 = 2*m*n
Ipotenusa = m^2 + n^2
scegliendo m e n interi consecutivi (2 e 1; 3 e 2; ecc...)

Ma come si pu procedere se devono essere i cateti a differire di 1 (qual ad esempio il quinto triangolo con queste caratteristiche)?

:hello:

Erasmus 15-01-12 03:42

Re: Qualche quiz
 
Quote:

aspesi (Scrivi 556362)
Definiamo triangoli pitagorici quasi-isosceli i triangoli rettangoli con lati interi nei quali la differenza tra la lunghezza dei cateti, oppure la differenza fra la lunghezza dell'ipotenusa e di un cateto uguale a 1.

Esempio: 3-4-5; oppure 7-24-25; oppure 20-21-29; ecc....

Una famiglia quasi isoscele con ipotenusa - cateto = 1 facile da ottenere.
Basta generare le Terne Pitagoriche Primitive:
Cateto 1 = m^2 - n^2
Cateto 2 = 2*m*n
Ipotenusa = m^2 + n^2
scegliendo m e n interi consecutivi (2 e 1; 3 e 2; ecc...)

Ma come si pu procedere se devono essere i cateti a differire di 1 (qual ad esempio il quinto triangolo con queste caratteristiche)?

:hello:

Si vede che non hai letto i precedenti miei interventi sulle terne pitagoriche.
------------------------------
Le terne con differenza 1 tra ipotenusa e cateto maggiore sono attribuite allo stesso Pitagora.
Procloo Diadoco (5 secolo d. C.) dice che Pitagora ha dimostrato che i triangoli rettangoli con lati interi sono infiniti dicendo come si pu continuare all'infinito a fabbricarne di nuovi.
Infatti il metodo di Pitagora comporta un triangolo rettangolo di forma diversa per ogni numero dispari.
Proclo dice che il metodo di Pitagora ... il seguente (detto con parole moderne):
Prendi per cateto minore a un dispari arbitrario (maggiore di 1), diciamo 2k+1, con k = 1, 2, 3, ...
Fa' il quadrato di a, togli 1 e dividi per 2: e poni il risultato che 2k(k+1) come cateto maggiore b.
Aggiungi 1 a b: quel che risulta, cio 2k(k+1)+1 l'ipotenusa c.

(Controllare che allora a^2+b^2 = c^2).

-------------------
Una volta ho trovato l'albero ternario delle terne pitagoriche primitive (quelle con massimo comune divisore dei lati che vale 1).
Era (mi pare) il 1987, non avevo ancora il computer (comperato nel 1989).
Pensa: ero partito proprio dal cercare le terne pitagotriche primitive con differenza 1 tra i cateti.
Come primo risultato ho trovato la successione delle TPP con differenza costante tra i cateti.
Se T(n) la terna pitagorica di indice n con la differenza 1 tra i cateti, allora vale questa legge di ricorrenza (lineare di 3 ordine):
T(0) = [0, 1, 1]; T(1) = [3, 4, 5]; T(2) = [20, 21, 29];
Per ogni n > di 2 risulta T(n) = 7T(n1) 7T(n2) + T(n3).

Per esempio, T(3) risulta
7*[20, 21, 29] 7*[3, 4, 5]+ [0, 1, 1] = (14021+0, 147 28 +1, 203 35+1] = [119, 120, 169].

Questa legge che mantiene costante lo scarto tra i cateti funziona con qualsiasi terna pitagorica iniziale: per occorre [e basta] sapere tre terne consecutive tra quelle con lo stesso scarto tra i cateti.
========================
Poi ho trovato ... atre cose che qui lungo dire: ma la cosa pi bella l'albero ternario.
Allora non c'era internet.
Ho spedito all'UMI un "paper" e quelli m'hanno risposto di averlo ricevuto.
Dopo un anno ho riscritto e quelli m'hanno risposto che non lo pubblicano e che non di loro interesse!
Qualche anno dopo ho scritto alla Mathesis. Per qualche altro anno ... nessuna risposta. Nel '96 c' stato il Congresso di Mathesis a Verona e allora ... ho potuto protestare di persona col Presidente.
Finalmente il mio papaer stato preso in considerazione e superato il vaglio d'un profe di Storia della Matematica (un. La Sapienza - Roma) secondo il quale l'albero delle TPP era originale, non mai pubblicato prima stato pubblicato sul "Periodico di matenatiche, organo della Mathesis": ma ... "massacrato" con una caterva di errori paurosa!

Anch'io, dopo la conferma del profe di Storia della Matematica, mi illudevo di aver scoperto per primo quella chicca! Invece qualche anno dopo, quando Internet era gi abituale, ho scoperto che un tal profe del MIT ha [i]pubblicato il mio albero delle TPP nel 1977, una decina d'anni prima della mia scoperta! :o

Ma quelli dell'UMi non lo sapevano: loro sono molto pi "avanti" dei profe del MIT!
Loro l'albero delle terne pitagoriche non lo reputano degno di interesse.
======================
Comunque: le Terne Pitagoriche con differenza 1 tra i cateti sono quelle che si ottengono moltiplicando la terna "fondamentale " [3, 4, 5] per una potenza della matrice simmetrica che segue:
Codice:

      | 2  1  2 |
C = | 1  2  2 |
      | 2  2  3 |

Per esempio: chi viene dopo la [119, 120, 169]?
Si pu fare con la combinazione lineare deelle tre terne precedenti di pesi 7, 7, e 1, cio:
a = 7*119 7* 20 + 3 = 696
b = 7*120 7*21 + 4 = 697
c = 7*169 7*29 + 5 = 985.
Oppure fare il prodotto di matrice per vettore:
T(n+1) = C*T(n).
Infatti:
Codice:


        |2 1 2|  |119|  |696|
CT(3) = |1 2 2| |120| = |697|
        |2 2 3|  |169|  |985|

Il "mio" albero ternario funziona cos
C' una rterna capostipite (o "radice"). Questa la terna T(1) = [3, 4, 5].
Ci sono tre matrici quadrate, diciamole A come "alto", C come "centrale" e B come "basso".
Si moltiplica la Terna T(n) per A, per C e per B ottenendo rispettivamente le tyerne
AT(n) = T(3n1);
CT(n)= T(3n);
BT(n) = T(3n+1);

La matrice C l'ho gi scritta. Ecco le matrici A e B:
Codice:

      | 1  2  2 |
A = | 2  1  2 |
      | 2  2  3 |

      | 2  1  2 |
B = | 1  2  2 |
      | 2  2  3 !

Ciao, ciao

aspesi 15-01-12 10:14

Re: Qualche quiz
 
Quote:

Erasmus (Scrivi 556571)
Dopo un hanno

Invece qualche hanno dopo,

Ciao, ciao

Mmmmmm....:D

-------------

Non conoscevo la tua soluzione "recursiva" :ok:

Il problema pu essere affrontato anche in questo modo.

Le formule per generare tutte le TPP che ho riportato prima possono essere adattate per il caso in cui sono i cateti a differire di 1.
Allora deve essere:
m^2 - n^2 + 1 = 2*m*n
oppure
m^2 - n^2 - 1 = 2*m*n

Cio:
(m - n)^2 - 2n^2 = +-1
(che non ho idea di come si possa risolvere)

Per, bastano alcune prove per vedere che i valori di n per i quali 2n^2+-1 un quadrato sono:
1 - 2 - 5 - 12 - 29 - 70 - .....
con -1 e +1 alternati.

La successione :
a(0) = 0 ; a(1) = 1
e per n>1
a(n) = 2a(n-1) + a(n-2)
che, guardando su Internet:), ho trovato essere una trasformazione della Fibonacci:
a(n) = Sum[Fibonacci[k]*a(n-k),(k,1,n)]

A questo punto, le terne si possono trovare facilmente:
n = 1 .... (m-1)^2 = 2*1^2 - 1 = 1 .......... m =2 ..... A = 3 .... . B = 4 ...... C = 5
n = 2 .... (m-2)^2 = 2*2^2 + 1 = 9 ......... m =5 ..... A =21 ..... B = 20 .... C = 29
n = 5 .... (m-5)^2 = 2*5^2 - 1 = 49 ..... ... m =12 ... A = 119 .. B = 120 .. C = 169
n = 12 .. (m-12)^2 = 2*12^2 + 1 = 289 ... m =29 .... A = 697 ..B = 696 ..C = 985
...............

Una cosa che mi pare interessante che la successione
a(n) = 2a(n-1) + a(n-2)
costituisce i denominatori delle frazioni continue che convergono a radice quadrata di 2:
1/1 ; 3/2 ; 7/5 ; 17/12 ; 41/29 ; 99/70 ; 239/169 ; .....
i cui numeratori sono determinati da:
a(0) = 1 ; a(1) = 3
e per n>1
a(n) = 2a(n-1) + a(n-2)
come la precedente.
O anche:
a(n) = ((1-RADQ(2))^n + (1+RADQ(2))^n)/2

:hello:

aspesi 15-01-12 11:12

Re: Qualche quiz
 
Quote:

Erasmus (Scrivi 556571)
Oppure fare il prodotto di matrice per vettore:
T(n+1) = C*T(n).
Infatti:
Codice:

        |2 1 2|  |119|  |696|
CT(3) = |1 2 2| |120| = |697|
        |2 2 3|  |169|  |985|

Il "mio" albero ternario funziona cos
C' una rterna capostipite (o "radice"). Questa la terna T(1) = [3, 4, 5].
Ci sono tre matrici quadrate, diciamole A come "alto", C come "centrale" e B come "basso".
Si moltiplica la Terna T(n) per A, per C e per B ottenendo rispettivamente le tyerne
AT(n) = T(3n1);
CT(n)= T(3n);
BT(n) = T(3n+1);

La matrice C l'ho gi scritta. Ecco le matrici A e B:
Codice:

      | 1  2  2 |
A = | 2  1  2 |
      | 2  2  3 |
 
      | 2  1  2 |
B = | 1  2  2 |
      | 2  2  3 !

Ciao, ciao

Ho visto qui:
http://oeis.org/search?q=3%2C21%2C119%2C697&sort=&language=english &go=Search
che un certo Vim Wenders ti ha ciulato nel 2004 questa tua scoperta::D

Values of x obtained by repeatedly multiplying the triple (x, y, z)=(3, 4, 5) by the matrix A = ([1 2 2] [2 1 2] [2 2 3]), the Across matrix of "The Trinary Tree(s) underlying Primitive Pythagorean Triples" generating matrices. - Vim Wenders (vim(AT)gmx.li), Jan 14 2004


:hello:


Tutti gli orari sono GMT. Attualmente sono le 22:43.

Powered by vBulletin versione 3.6.7
Copyright ©: 2000 - 2022, Jelsoft Enterprises Ltd.
Traduzione italiana a cura di: vBulletinItalia.it