Triangoli con i lati di lunghezze [tex]1,2,\ldots,n[/tex]

Problemi enumerativi, teoria dei grafi ...

Moderatore: Moderatori

Triangoli con i lati di lunghezze [tex]1,2,\ldots,n[/tex]

Messaggioda fry il mer 13 feb 2013, 11:49

Si hanno a disposizione n segmenti di lunghezze 1,2,\ldots,n rispettivamente. In quanti modi si può costruire un triangolo usando tre di tali segmenti?
"Hey. They laughed at Louis Armstrong when he said he was gonna go to the moon. Now he's up there, laughing at them."
Avatar utente
fry
 
Messaggi: 1122
Iscritto il: ven 20 giu 2008, 19:06

Re: Triangoli con i lati di lunghezze [tex]1,2,\ldots,n[/tex]

Messaggioda Gottinger95 il lun 21 lug 2014, 22:32

Assumo che i triangoli degeneri siano validi. Se non lo fossero, la dimostrazione rimarrebbe sostanzialmente invariata.
1. La condizione necessaria e sufficiente affinchè si possa costruire un triangolo di lati \(a > b > c\) è che \( a \le b+c\); le altre due disuguaglianze triangolari si possono facilmente derivare da questa.
2. Notiamo che deve valere \( a < 2b\), altrimenti si avrebbe \( a \ge 2b > b+c\) contro (1). Inoltre, fissati \(a,b\) "papabili", ossia tali che \(b < a < 2b\), di certo \(c\) deve appartenere all'intervallo \( [a-b, b[ \) (l'estremo sinistro per soddisfare (1), l'estremo destro per l'assunzione sull'ordine).
3. Poniamo per comodità \(s:= \left \lfloor (n+1)/2 \right \rfloor\). Dunque la quantità cercata è
\[ S_n = \sum_{b<a < 2b, \ \ a,b \le n} 2b-a = \sum_{b=1}^{n-1} \sum_{a=b+1}^{\min \{n,2b-1\} } 2b-a = \sum_{b=1}^{ s} \sum_{a=b+1}^{2b} 2b-a + \sum_{b=s+1}^{n-1} \sum_{a=b+1}^{n} 2b-a =\]
Notiamo che per \(n \ge 3\), per cui ha senso il testo, nessuna sommatoria è vuota.
4. Adesso sono solo contacci:
\[ S_n = \sum_{b=1}^{s} 2b^2 - \frac{2b (2b+1)}{2}+ \frac{b(b+1)}{2} + \sum_{b=s+1}^{n-1} 2b(n-b)- \frac{n(n+1)}{2} + \frac{b(b+1)}{2} =\]
Spezziamo le sommatorie in sommatorie semplici, ossia dove appaiono solo potenze di \(b\):
\[ \frac{1}{2} \left ( \sum_{b=1}^{ s} b^2 \right ) - \frac{1}{2} \left ( \sum_{b=1}^{ s}b\right ) + (2n+ 1/2 ) \left ( \sum_{b=s+1}^{n-1} b \right ) - \frac{3}{2} \left ( \sum_{b=s+1}^{n-1} b^2\right ) - \left ( n- s-1 \right ) n \frac{(n+1)}{2} = \]
\[ =\frac{ s ( s+1) ( 2 s+1)}{12} - \frac{ s (s+1) }{4} + \frac{4n+1}{2} \left ( \frac{(n-1)n}{2} - \frac{s(s+1)}{2} \right ) + \frac{3}{2} \left ( \frac{s(s+1)(2s+1)}{6} -\frac{(n-1)n(2n-1)}{6} \right ) + \frac{n (s+1-n)(n+1)}{2} = \]
\[ = \frac{5s^3}{12}- \frac{s^2}{2} (2n-1) + \frac{s}{6} (3n^2-3n-1) - \frac{3n^2}{4} \]
I più coraggiosi potranno, a onor dell'estetica, distinguere i casi \(n\) pari, dispari per trovare l'effettivo polinomio cubico che descrive la quantità richiesta (sempre a patto che, auspicabilmente, non abbia sbagliato i conti). Io, dovendo partire tra meno di cinque ore, non mi avventuro.
Nota 1. Anche senza conti, notando che \( \lim_{n \to \infty} \frac{s}{n/2} = 1 \), si può dedurre che
\[ \lim_{n \to \infty} \frac{S_n}{ \binom{n}{3} } = \frac{5}{16} \]
Ossia che la probabilità che, presa una terna, essia sia triangolare, è asintoticamente \(5/16\).
Nota 2. Propongo tre vie di generalizzazione:
a) Continuo. Stessa domanda, ma nell'intervallo dei reali \( ]0, n]\) invece che in quello dei naturali \( \{1, \ldots, n\}\);
b) Poligoni. Stessa domanda, ma con i poligoni invece che con i triangoli;
c) Funzioni. Invece di considerare \( \{1, \ldots, n\}\), consideriamo la sua immagine attraverso \(f\), i.e. \(\{f(1), \ldots, f(n)\}\). Credo che una \(f\) polinomiale, oppure della forma \( f(n) = \sqrt[n]{ \frac{ x_1^n + \ldots + x_k^n }{k} } \) per certi \( x_1, \ldots, x_k\) fissati.
L'approccio che ho seguito non mi piace molto, perchè non è simmetrico e non ci sono idee. Di fatto non può essere facilmente esteso a nessuno dei tre casi.
Volendo, le tre generalizzazioni possono coesistere.
Gottinger95
 
Messaggi: 16
Iscritto il: lun 12 mag 2014, 21:32


Torna a Combinatoria

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron