Qualche quiz

[aspesi]

astromauh

Ma dovrei cercare di creare quante più regioni è possibile?

E' questo lo scopo del quiz?


E' sufficiente evitare di prendere punti opposti?

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"

[nino280]

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

Il triangolo di Mizarino:





Ciao

[aspesi]

nino280

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 , 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...

                                                         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

[nino280]

B b b buon hanno ha ttt tuttt sic sic!

[Erasmus]

aspesi

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 , 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...

                                                         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 + B·N + C·N^2 + D·N^3 + E·n^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 + 2·B + 4·C + 8·D + 16·E = 2
R(3) = A + 3·B + 9·C + 27·D + 81·E = 4
R(4) = A + 4·B + 16·C + 64·D + 256·E = 8
R(5) = A + 5·B + 25·C + 125·D + 625·E = 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è:

            24  – 18·N + 23·N^2 – 6·N^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.

aspesi

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 k–1 è "linearmente dipendente di ordine k" con polinomio caratteristico
P(x) = (x–1)^k.
Essendo questa sequenza polinomiale di 4° grado è "linearmente dipendente di ordine 5" con polinomio caratteristico
P(x) = (x – 1) ^5 = x^5 – 5·x^4 + 10·x^3 – 10·x^2 + 5·x – 1.
Il che significa proprio:
R(N+5) – 5·R(n+4) + 10·R(N+3) – 10·R(N+2) + 5·R(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.

Function FACTORIAL_1(n: integer): integer; {Algoritmo iterativo}
  var f: integer;
  begin
      f:=1;
      if n>0 then
      repeat
         f:=n*f; n:= n–1
      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(n–1)
  end;

Ciao a tutti.
BUON ANNO!

[aspesi]

Erasmus

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

Dovresti dirlo anche a Nino280 ...

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!

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...

BUON ANNO

[aspesi]

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

[Erasmus]

aspesi

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

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) = 7·T(n–1) – 7·T(n–2) + T(n–3).

Per esempio, T(3) risulta
7*[20, 21, 29] – 7*[3, 4, 5]+ [0, 1, 1] = (140–21+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!

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:

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

         |2 1 2|   |119|   |696|
C·T(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 lòe tyerne
A·T(n) = T(3n–1);
C·T(n)= T(3n);
B·T(n) = T(3n+1);

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

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

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

Ciao, ciao

[aspesi]

Erasmus

Dopo un hanno

Invece qualche hanno dopo,

Ciao, ciao

Mmmmmm....

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

Non conoscevo la tua soluzione "recursiva"

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

[aspesi]

Erasmus

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

        |2 1 2|   |119|   |696|
C·T(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 lòe tyerne
A·T(n) = T(3n–1);
C·T(n)= T(3n);
B·T(n) = T(3n+1);

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

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

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