Newsgroup: it.hobby.enigmi
Titolo: Catasta di triangoli

Contare quanti triangoli si possono vedere in questa figura :
       /\
      /__\
     /\  /\
    /__\/__\
   /\  /\  /\
  /__\/__\/__\
 /\  /\  /\  /\
/__\/__\/__\/__\
Vanno contati tutti, dai piu' piccoli al piu' grande, e anche capovolti
E' troppo facile ?
Allora trovare la formula generica in funzione di n, l'ordine della figura.

Allora trovare la formula generica in funzione di n, l'ordine della figura.
Spoiler
n^2 +3(n-2) +1
n essenso il numero con la base sulla base, cioe` nel tuo caso n=4
-- 
Ci sentiamo  |  Remigio Zedda  || Attenzione! campo "From:" alterato
ciao Remigio |                 ||==> E-mail: 
remi...@tiscalinet.it
-------------|      ..si` d'accordo.. ma con la Deb e` un'altra cosa!
/* Linux 2.2.17 su Debian GNU/Linux 2.2 Potato */

 n^2 +3(n-2) +1
funziona solo per n=2 e n=3
Silv:o)

funziona solo per n=2 e n=3
E lo credo, l'ho fatto brute force con 2 e 3 :-))))


funziona solo per n=2 e n=3
Adesso ha ripreso a funziare anche con 4 (quello postato) e con 5  8-]
Guarda, che forse c'e` equivoco:
Alla base del triangolo di figura, ci stanno 4 triangoli ("con la base
nella base", dicevo).
Ebbene, i singoli triangoli interni sono n*n=somma primi n dispari.
Da aggiungere sono: il generale, piu` uno per ogni parallela a ciascun
lato (tranne la prima e l'ultima, infatti "meno due").
Con n=5 si ha: 25+9+1=35. Quelli dati 23.
Sbaglio a cantarli a mano?


rez dice


 Sbaglio a cantarli a mano?
Mancano tutti quelli non unitari che non hanno vertici nei vertici del
triangolone.
Sono 10 da 2 (A,B,C per 3 lati + 1 centrale), e 3 da 3, per un totale
di 48
         /\
        /__\
       /\  /\
      /__\/__\
     /\      /\
    /  \ B  /  \
   / A  \  / C  \
  /__  __\/__  __\
 /\  /\  /\  /\  /\
/__\/__\/__\/__\/__\
Ciao, Silv:o)

Si diceva:
Contare quanti triangoli si possono vedere in questa figura :
.               linea    dist
       /\
      /__\        1       n-1
     /\  /\
    /__\/__\      2       n-2
   /\  /\  /\
  /__\/__\/__\    ...
 /\  /\  /\  /\
/__\/__\/__\/__\  n         0
Numero le linee orizzontali, a partire dall'alto, da 1 a n, come in figura;
per ogni linea ho indicato anche la distanza
 n-1 dalla base del triangolone.
I triangoli *dritti*, con base sulla linea k_ma sono:
1 con base k; 2 con base k-1; ... k con base 1, cioč
1+2+...+k = k*(k+1)/2
da sommare per tutti i valori di k da 1 a n.
Ad ogni triangolo dritto ne corrisponde uno *rovesciato* con la stessa base,
se e solo se
base<=dist.
Mo' si tratterebbe di mettere il tutto in una formula compatta.
:-(
Oppure scrivere un programmino facile facile che li conta.
:-)
ciao
paolo

 :-)
Hint: differenze finite. C'è una sorpresa.
Silv:o)

 Hint: differenze finite. C'č una sorpresa.
Per i SOLI triangoli *dritti* la formula semplicissima č
N*(N+1)*(N+2)/6
Ecco la dimostrazione:
.                C
.                /\
.               /__\
.              /\  /\
.             /__\/__\
.            /\  /\  /\
.           /__\/__\/__\
.          /\  /\  /\  /\
.         /__P/__\/__\/__\
.        /\  /\  /\  /\  /\
.       /__\/__\/__\/__\/__\
.      /\  /\  /\  /\  /\  /\
.     /__\/__\/__\/__\/__\/__\
.    /\  /\  /\  /\  /\  /\  /\
.   /__\/__\/__\/__\/__\/__\/__\
.  /\  /\  /\  /\  /\  /\  /\  /\
. /__\/__\/__\/__\/__\/__\/__\/__\
 A                                B
Consideriamo un triangolo ABC di ordine N, e consideriamo come unitaria
l'altezza del triangolino elementare.
Contiamo tutti i PUNTI, vertici dei triangolini: essi sono (N+1)*(N+2)/2
Il generico punto P č vertice di a triangoli con base parallela a BC, b
triangoli con base parallela ad AC e c triangoli con base parallela ad AB,
dove a,b,c, sono rispettivamente le distanze di P dai tre lati del triangolo
grande.
Per un noto teorema, in un triangolo rettangolo la somma delle distanze di
ciascun punto P dai lati AB, BC e CA č costante, uguale all'altezza N.
Esistono quindi (a+b+c)=N triangoli con vertice in P, e ciň vale per
qualsiasi P.
Abbiamo cosě contato N*[(N+1)*(N+2)/2] triangoli dritti, ma, dal momento che
ciascun triangolo č stato contato tre volte, a partire da ciascuno dei suoi
vertici, il totale va diviso ancora per tre:
N*(N+1)*(N+2)/6
cvd
ciao
paolo
PS
Questa formula mi ricorda qualcosa di deja vu, ma ora non mi viene in mente
a che proposito.

/__\/__\/__\/__\/__\
!!Ahhhhhhh allora mi arrendo:-((
Dunque era difficile anche contarli a mano 8-]


 N*(N+1)*(N+2)/6
Proviamo a contare i triangoli rovesciati
linea         numero triangoli
0                      0
1                    0   0
2                  0   1   0
3                0   1   1   0
4              0   1   2   1   0
5            0   1   2   2   1   0
6          0   1   2   3   2   1   0
7        0   1   2   3   3   2   1   0
8      0   1   2   3   4   3   2   1   0
9    0   1   2   3   4   4   3   2   1   0
Lo schema rappresenta il triangolo grande.
Per ogni punto č indicato il numero di triangoli rovesciati che hanno il
vertice basso in quel punto.
Esaminando lo schema, considerando ciascun numero separatamente, osserviamo
che:
se N č pari (mi fermo per esempio alla linea 8) il numero (N*/2)
(nell'esempio N/2=4) compare una volta, ciascun altro numero compare quattro
volte in piů del precedente
se N č dispari (arrivo alla linea 9) il numero [(N-1)/2] (nell'esempio
ancora 4) compare tre volte, ciascun altro numero ancora quattro volte in
meno del precedente
oppure, considerando le linee verticali:
per N pari:
sommatoria [1+2+3...+(N/2)]  una volta
ciascuna altra sommatoria (1) (1+2) (1+2+3)... quattro volte
per N dispari:
sommatoria [1+2+...((N/2)-1)] tre volte
ciascuna altra sommatoria .... quattro volte
Non so ancora se quanto sopra possa essere utile per arrivare alla formula
compatta.
ciao
paolo

 N*(N+1)*(N+2)/6
Bellissima dimostrazione. Ce ne sono altre abbastanza semplice (per
induzione, per esempio) ma questa è davvero elegante.
Nel dimostrare la formula per induzione, mi sono accorto che nel
passare da un livello n-1 al successivo n, i triangoli aggiunti sono
Tn=1+2+..+n. Quindi il numero che hai trovato è equivalente a
1+(1+2)+..+(1+2+..+n) cioè la somma dei primi n triangolari, ma anche,
raccogliendo gli 1, i 2 ecc., 1*n + 2*(n-1) + .. + n*1, cioè il
prodotto scalare (1,2,..n)*(n,n-1,..,1).
Però devi ancora contare i capovolti ;)
Silv:o)

 Perň devi ancora contare i capovolti ;)
Per N pari
(2*N^3 + 3*N^2 - 2*N) / 24
per N dispari ... ne parliamo domani
ciao
paolo

 (2*N^3 + 3*N^2 - 2*N) / 24
che sommato al risultato ottenuto per i triangoli dritti porta a
Tr(n) = n*(n+2)*(2n+1)/8
Come ho già detto, la formula per il caso dispari è simile (non voglio
toglierti il piacere di trovarla, Paolo), al punto che, prendendo la
parte intera, la formula precedente va bene in tutti i casi.
Silv:o)

 Hint: differenze finite. C'è una sorpresa.
Vediamo di dare un senso al suggerimento.
Se ci calcoliamo un po' di valori a mano o con un qualche programma,
otteniamo la sequenza
1, 5, 13, 27, 48, 78, 118, 170, 235, 315, ..
Calcoliamo le successive differenze
1     5     13    27    48    78    118   170 ..
   4     8     14    21    30    40    52
      4     6     7     9     10    12
         2     1     2     1     2
Le differenze terze sono alternativamente 1 e 2, quindi ci sono due
formule di terzo grado distinte per i dispari ed i pari, e questa è la
sorpresa di cui parlavo. Per chi conosce il metodo delle differenze
finite è anche semplice riscrivere le tabelle con i soli dispari o
pari e ricavare i coefficienti dei polinomi che generano le sequenze.
Silv:o)

parte intera, la formula precedente va bene in tutti i casi.
Ma qualcosa del genere contare li conta, ma non so se puo` andare
perche' non e` un polinomio:
n(n+1)/2+(n-1)n+(n-2)(n-1)/2+(n-3)(n-2)+(n-4)(n-3)/2+(n-5)(n-4)+..
Per n=8 --> 36+56+21+30+10+12+3+2=170
n=5 --> 15+20+6+6+1=48, dovrebbe andare perche' i triangoli li avevi
contati tu per n=5:-))
Ps. Quasi brute force del tutto:-))))))


 toglierti il piacere di trovarla, Paolo),
A questo punto è solo lavoro di manovalanza.
Se n è dispari, p=n+1 è pari (principio di La Palisse)
:-)
Allora calcolo i triangoli totali in p, e poi sottraggo quelli generati
dall'ultima fila, che sono
p*(p+1)/2 dritti, e
(p/2-1)*(p/2)+p/2 rovesciati.
Con qualche passaggio, esprimendo poi il tutto in funzione di n, trovo
Tr(n) = (2*n^3+5*n^2+2*n-1)/8
Verifico:
n    Tr(n)
1      1
3     13
5     48
7    118
...
Funziona.
ciao
paolo

 prodotto scalare (1,2,..n)*(n,n-1,..,1).
Aha. Da Silvio non mi aspettavo niente di meno :-)
Questa sommatoria : Sum_1^n {Tn} = n*(n+1)*(n+2)/3! = Bin(n+2,3)
e' la formula dei numeri tetraedrici, che ricorre non a caso nel
metodo di Newton per le differenze finite.
Ma forse questa e' sfuggita anche a Silvio :
il numero dei triangoli capovolti si puo' trovare come
Tr_capovolti = Tr(n-1) + Tr(n-3) + Tr(n-5) + Tr(n-7) + ...
ove la somma va fermata agli indici positivi.

"Crios" propose:

Visto che il thread ha avuto un buon sucesso (io avevo gia la soluzione e
quindi non ho partecipato) propongo di passare a:
Quanti parallelogrammi si vedono nella stessa figura?
Di questa non posseggo soluzione e quindi parto da zero anche io, non so se
esista una formula generale, se esiste sono sicuro che siete in grado di
trovarla.
GaS

Tr(n) = (2*n^3+5*n^2+2*n-1)/8
Cosa ne dite di questa, testata ok, che vale per n qualsiasi:
Tr(n) = (1/2)S[p_i + q_i]
S[]=somme per i da 0 a (n-1)
p_i=(n-i)(n-i+1)
q_i=[p_i + delta*p_i]/2
delta=(-1)^(i+1)
E` la stessa che ho postato avantieri, ma con le somme fino a n-1.
Eccola senza somme:
Tr(n)=[nm+2(n-1)(m-1)+(n-2)(m-2)+2(n-3)(m-3)+..]/2
con m=n+1.
Siccome l'ho testata facendo un brevissimo sorgente in C, ecco ad
esempio i valori seguenti:
[~] rez_1$: ./triangoli.out
Introdurre il numero n:
1000
Il numero di triangoli e`: 250625250
Introdurre il numero n: 
10001
Il numero di triangoli e`: 250137522501
Uhm.. un po' lentina, vediamo con n=20.000 di calcolare il tempo.
[~] rez_1$: time ./triangoli.out
Introdurre il numero n: 
20001
Il numero di triangoli e`: 2000550045001
real	0m16.539s
user	0m3.570s
sys	0m0.000s
Be', 16 secondi e mezzo. Non oso introdurre 100.000, troppo tempo..


 quindi non ho partecipato).
Mi sono astenuto per la stessa ragione. Per alcune verianti
di "Conta i triangoli" si puo' vedere nelle pagine del
solito Sillke:
http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles
con molti riferimenti bibliografici.
Per contare i parallelogrammi.....
SPOILER
Riprendo una bella intuizione di Paolo Licheri.
L'unione di due qualunque punti dell'array triangolare,
costituisce la diagonale PIU' LUNGA di un parallelepippedo.
Ciascun punto puo' essere unito a tutti gli altri, escluso
tutti quelli giacenti sulle stesse linee che passano per il
punto considerato.
         x
        /\
       /__\
      /\  /\
     /__\/__\
    /\  /\  /\
   /__\/__\/__\
  /\  /\  /\  /\
 /__\/__\/__\/__\
Il punto al vertice x, ad esempio,  genera una diagonale se
unito agli altri punti, escluso gli 8 che stanno sui 2 lati
concorrenti in x.
Per un triangolo di lato n, il totale dei punti e'
(n+1)(n+2)/2 e possono essere uniti ai restanti n(n-1)/2.
Moltiplicando queste due quantita', dividendo per due
(perche' la stessa diagonale e' contata due volte) e
semplificando ricavo
n(n-1)(n+1)(n+2)/8.
La serie comincia con 0,3,15,45,105,210,378,630,990,1485....
ciao :) dario

 ciao :) dario
ciao
paolo

 contare *solo* le diagonali più lunghe.
Avevi postato questo metodo delle diagonali,  per contare
quanti subrettangoli ci sono in un rettangolo m*n. Il metodo
mi era piaciuto, anche se poteva essere considerato
equivalente se non meno immediato, di ques'altro:
Ciascun subrettangolo e' individuato univocalmente da due
linee orizzontali e da due verticali, cosi' se nel
rettangolo originale ci sono m linee orizzontali e n
verticali, il totale dei subrettangoli e' dato da
C(m,2)*C(n,2).
Ora, alla luce del problema appena trattato, il tuo metodo
si e' rivelato piu' generale, surclassando l'altro di molte
lunghezze.
Complimenti.
:) dario

 quindi non ho partecipato)
Conoscevo la soluzione(orientativa, mi ricordavo il passaggio alle diff.
finite e che la soluzione fosse diversa per n pari o dispari) e cosi non mi
ci sono ricimentato.  Legendo pero' le vostre soluzioni mi sono accorto di
capire veramente poco(e non certo per colpa vostra), ho provato a ritirare
fuori la soluzione per conto mio ma niente :o(
Mi sono allora messo a cercare una soluzione indipendente e ve la propongo,
non e' completa ma fa a meno del metodo alle differenze e mette in luce il
perche' la sol. sia distinta per n pari o impari(principalmemnte mi sembra
piu facile). Forse sara' inutile questa mia sol. ma trovarla mi ha impegnato
un po' e cosi ve la propongo
m
e
z
z
o
s
p
o
i
l
e
r
!
!
Denotiamo con m-vert il vertice di ogni triangolo che si trovi in alto(per
triangolo *dritti*)o in basso(per triangoli capovolti), per come e' definito
ogni triangolo possiede un unico m-vert ma ogni punto della griglia puo'
essere m-vert per piu' di un triangolo.
Ho cominciato a numerare ogni punto della griglia con il totale dei
triangoli di cui e' m-vert.
per es.
      1
      /\
     /__\
    0    0
        3
       /\
    2 /__\2
     /\  /\
  1 /__2/__\1
   /\  /\  /\
  /__\/__\/__\
 0   1    1   0
        4
        /\
      3/__\3
       /\  /\
    2/__\3__\2
    /\  /\  /\
  1/__\2__\2__\1
  /\  /\  /\  /\
 /__\/__\/__\/__\
0    1   2   1   0
         5
         /\
       4/__\4
       /\  /\
     3/__4/__\3
     /\  /\  /\
   2/__3/__\3__\2
   /\  /\  /\  /\
 1/__2/__3/__\2__\1
 /\  /\  /\  /\  /\
/__\/__\/__\/__\/__\
0  1    2   2   1   0
E' facile capire, intuitivamente, come funziona per ogni n.
Si noti che la somma di tutti i vertici da proprio il numero totale di
triangoli.
Data una configurazione con un dato n si vede come, per ottenere la config.
n+1 basta aggiungere 1 a tutti i vertici ed aggiungere la fila in basso.
Si avra', detta T(n) il tot. di triangoli per la config. n:
T(n)=T(n-1)+n(n+1)/2+ultima fila
in quanto i vertici di n-1 sono proprio n e abbiamo detto che aggiungiamo 1
ad ogni vertice della vecchia config..
L'ultima fila sara' del tipo
0_1_2_...._2_1_0
Per n dispari la base ha n+1 vertici e si avra'
0_1_2_..._(n-1)/2_(n-1)/2_...2_1_0
in tot. si avra', per l'ultima fila un totale di
2*(n-1)/2*[(n-1)/2+1]=(n^2-1)/2
triangoli.
Per n pari si avra'
0_1_2_..._n/2_...2_1_0
e, analogamente a prima, si ottiene, sempre per l'ultima fila,
2*[(n-1)/2][(n-1)/2+1]+n/2=n^2/2 triangoli
A questo punto c'e' *solo* da risolvere la *facile* eq. alle differenze ed
ottenere il risultato (cosa che, sinceramente non ho assolutamente il tempo
di fare :o) che spero sia quello giusto.
Sperando di non avere annoiato con questa sol. alternativa vi saluto a
tutti.
GaS
P.S.: Ora che ci penso se si parla di eq. alle diff. si parla di metodo alle
diff. finite e quindi forse il metodo non e' completamente diverso.....
P.P.S.:Mi e' sembrata semplice da capire ma abbastanza ostica a descrivere.

P.P.S.:Mi e' sembrata semplice da capire ma abbastanza ostica a descrivere.
E` un caso di TIMTOWTDI gigante.. se ti interessa *il modo*, guardali
allora anche sotto quest'aspetto, che IMHO mostra l'essenza:-))
	 1	 2	 3	 4	 5
n	d r	d r	d r	d r	d r
1	1
2	2 1	1
3	3 2	2	1
4	4 3	3 1	2	1
5	5 4	4 2	3	2	1
6	6 5	5 3	4 1	3	2
7	7 6	6 4	5 2	4	3
8	8 7	7 5	6 3	5 1	4
Ovviamente:
colonne d=dritti, r=rovesciati, il numero sopra indica il tipo di
triangolini.
E cosi` non c'e` bisogno di considerare i tre lati: e` tutto compreso.
Esempio:
quanti triangolini da due (= di lato 2) ci sono in un
triangolo di n=7 ?
Risposta:
dritti la somma dei primi 6 interi, a testa in giu`
invece la somma dei primi 4.
Si vede facilmente che i rovesciati saltano i dispari..
Le semplicissime formole le avevo gia` postate:-))
