Quanti triangoli?

[axpgn]

Fissato il perimetro $n$, quanti differenti triangoli esistono che non siano congruenti fra loro, non siano degeneri e abbiano tutti e tre i lati di misura intera?


Cordialmente, Alex

[jas1231]

Il problema può essere trasformato in uno analogo:
Quante sono le terna (non ordinate) di numeri naturali tali che la somma di tali numeri sia uguale ad \(n\).

ho immaginato di disegnare una stringa composta da \(n\) quadratini (ci saranno quindi \(n-1\) spazi tra i quadratini), procedo allora a dividere la stringa in 3 parti con l'ausilio di due rette, che vado a posizionare in due spazi tra i quadratini (in maniera casuale).




Allora ho \(n-1\) modi di posizionare la prima retta e \(n-2\) modi di posizionare la seconda, tuttavia non importa in che ordine le due rette vengano posizionate.
Posso quindi concludere che le terne ordinate sono \(\dfrac{(n-1)(n-2)}{2}\).
Ora vanno distinti vari casi:

-se \(n\) è divisibile per 3 allora ci sarà una terna che viene contata una sola volta cioè \(\Large(\normalsize\dfrac{n}{3},\dfrac{n}{3},\dfrac{n}{3}\Large)\)

-se \(n\) è dispari scrivo \(n=2k+1\) allora il numero di numeri dispari che lo precedono è \(k\), allora ci saranno \(k\) terne che si ripetono 3 volte. Saranno terne del tipo \(\Large(\normalsize j,\dfrac{n-j}{2},\dfrac{n-j}{2}\Large)\) con \(j\) dispari. (nel caso in cui n sia divisibile per 3 una di queste va eliminata perché si ripete una sola volta e non 3)

-se \(n\) è pari scrivo \(n=2h\) allora il numero di numeri pari che lo precedono è \(h-1\), allora ci saranno \(h-1\) terne che si ripetono 3 volte. Saranno terne del tipo \(\Large(\normalsize j,\dfrac{n-j}{2},\dfrac{n-j}{2}\Large)\) con \(j\) pari. (nel caso in cui n sia divisibile per 3 una di queste va eliminata perché si ripete una sola volta e non 3)

tutte le altre terne si ripetono 6 volte.


Allora abbiamo i seguenti risultati:
\[N=
\begin{cases}
\dfrac{(n-1)(n+1)}{12} \,\, \text{se} \,\, n \,\, \text{dispari e} \,\, 3 \nmid n\\
\,\,\\
\dfrac{(n-2)(n+2)}{12} \,\, \text{se} \,\, n \,\, \text{pari e} \,\, 3 \nmid n\\
\,\,\\
\dfrac{(n-1)(n+1)+4}{12}\,\, \text{se} \,\, n \,\, \text{dispari e} \,\, 3 \mid n\\
\,\,\\
\dfrac{(n-2)(n+2)+4}{12} \,\, \text{se} \,\, n \,\, \text{pari e} \,\, 3 \mid n\\

\end{cases}
\]
Dove \(N\) è il numero cercato.

[axpgn]

Non va bene.

Premetto che ho guardato solo i risultati prima di imbarcarmi nell'analisi della tua risposta e non mi tornano.

Ti faccio un esempio: se $n=10$, la tua formula mi darebbe $8$ triangoli ma in realtà ce ne solo solo due ovvero $4+4+2$ e $4+3+3$

Cordialmente, Alex

[jas1231]

Cavolo non ho tenuto conto della condizione di esistenza. Penso che allora l'intero procedimento sia da buttare.
Me ne sarei dovuto accorgere subito .

[axpgn]

Esatto.
Un lato non può essere maggiore della somma degli altri due. E neppure uguale in questo caso.

[Umby2]

number of triangles with integer sides and perimeter n.

https://oeis.org/A005044

[axpgn]

@Umby
Che senso ha una risposta del genere?

[Super Squirrel]

$min=1+(n+1)mod2$

$max=[n/2]-(n+1)mod2$

$N=sum_(i=min)^([n/3])[(i+nmod2)/2]-[i/(n-max-i)](imod(n-max-i))$

Dove le parentesi quadre indicano la divisione intera.

Non è il massimo, ma sembra funzionare!

[axpgn]

Voglio una dimostrazione!

Come verifico che quella funzioni? E ammesso che riesca a scrivere un programma per verificarla (come hai fatto sicuramente tu ), chi mi garantisce che funzioni sempre?

Occorre una dimostrazione.

Cordialmente, Alex

[Umby2]

"axpgn":@Umby

Per me OEIS è la BIBBIA,
non si occupa solo di risolvere problemi,
ma anche trovare l'algoritmo per (n).

Se a te non piace, me ne dispiaccio,
magari qualcun altro lo troverà interessante.. chissà..

[Umby2]

"Super Squirrel":

Non è il massimo, ma sembra funzionare!

Lo mettiamo alla prova ?

fatto con excel... se non ho sbagliato la formula... così provi anche il mio calcolo..

[axpgn]

@Umby

Te lo ripeto: ma che c'entra?

So benissimo cos'è OEIS, l'ho pure citata varie volte ma quando ce n'era motivo, non a sproposito.
Il senso di questo thread (e di questa sezione) è quello di proporre quesiti (si spera interessanti) agli utenti del forum, spingendoli a trovare una soluzione con le proprie forze; cercare una risposta su Internet, peraltro scegliendola da un elenco, non va in questa direzione.
Ovviamente ognuno fa come vuole ...

"Umby":Lo mettiamo alla prova ?

E quindi? Non hai dimostrato niente, solo che funziona per una decina di interi ... e gli infiniti altri?

Cordialmente, Alex

[Super Squirrel]

$a2aa
Dovendo i lati avere misure intere si ottiene:

$n$ dispari --> $max=(n-1)/2=>min=n-2max=1$

$n$ pari --> $max=n/2-1=>min=n-2max=2$

I suddetti risultati possono poi essere generalizzati come:

$min=1+(n+1)mod2$

$max=[n/2]-(n+1)mod2$

Quindi in definitiva avremo che $min<=a,b,c<=max$

Una volta noti i valori assumibili dai singoli lati, l'elenco dei possibili triangoli per un dato perimetro può essere ottenuto generando tutte le combinazioni con ripetizione (degli interi appartenenti all'intervallo $[min;max]$ presi $3$ alla volta) e considerando quelle di somma $n$. In questo modo inoltre andremo anche ad escludere i triangoli tra loro congruenti.

Ipotizzando che gli elementi della singola combinazione siano ordinati in senso crescente, saremo anche in grado di "ordinare" l'intera lista delle combinazioni. Detto $i$ il primo elemento di una generica combinazione "vincente", allora la prima combinazione che inizia con $i$ sarà del tipo:

$i;n-max-i;max$

Ora, per sapere quante sono le combinazioni "vincenti" che iniziano con $i$, basta contare in quanti modi può essere riscritta la quantità $n-i$ come somma di due interi appartenenti all'intervallo $[min;max]$ e con il primo addendo maggiore o uguale al secondo.
Per farlo consideriamo un generico intervallo $[a;b]$ con $b>=a$. Detta $m=b-a$ l'ampiezza dell'intervallo, andiamo a riportare tutti i modi in cui può essere scritta la quantità $a+b$ come somma di due interi appartenenti all'intervallo $[a;b]$:

(a) + (b)
(a+1) + (b-1)
(a+2) + (b-2)
...
(a+m=b) + (b-m=a)

In pratica avremo $m+1$ alternative di cui solo $[(m+2)/2]$ soddisfano la condizione che il primo addendo sia maggiore o uguale al secondo.
Tornando al caso in esame l'intervallo diventa $[n-max-i;max]$ da cui si ricava:

$n$ dispari --> $m=2max-n+i=i-1$

$n$ pari --> $m=2max-n+i=i-2$

Quindi generalizzando abbiamo che i casi in cui il primo addendo sia maggiore o uguale al secondo sono

$[(m+2)/2]=[(i+nmod2)/2]$

Inoltre, dal momento che abbiamo ipotizzato le singole combinazioni ordinate in senso crescente, nel caso in cui il primo lato è maggiore del secondo, ossia

$i>n-max-i=>2i>n-max$

bisognerà sottrarre da $[(i+nmod2)/2]$ la quantità $i-(n-max-i)=2i+max-n$

In pratica

$[i/(n-max-i)](imod(n-max-i))$

è equivalente a

$f(i)={(2i+max-nrarr(2i>n-max)),(0rarr(2i<=n-max)):}$

A questo punto credo che non resti che parlare degli estremi della sommatoria.
Ovviamente il minimo valore che può assumere $i$ è $min$, mentre il massimo sarà $[n/3]$, in quanto abbiamo ipotizzato che gli elementi della singola combinazione siano ordinati in senso crescente.

Non so se quella esposta possa essere considerata una dimostrazione, in ogni caso spero almeno di essere stato in grado di spiegare l'idea di fondo!

"Umby":Lo mettiamo alla prova ?

fatto con excel... se non ho sbagliato la formula... così provi anche il mio calcolo..

Anche a me tornano gli stessi valori!

[Umby2]

"Super Squirrel":

Anche a me tornano gli stessi valori!

Complimenti..

se sei registrato ad oeis, potresti anche proporre la tua soluzione
(per ogni problema, ce ne sono diverse, trovate da utenti diversi, la tua soluzione mi sembra assente... )

[axpgn]

Mi sono un po' perso ad un certo punto ...

Quello che manca ancora è una forma chiusa, senza dover calcolare una sommatoria, insomma un calcolo diretto.

Cordialmente, Alex

[Super Squirrel]

"Umby":
se sei registrato ad oeis, potresti anche proporre la tua soluzione
(per ogni problema, ce ne sono diverse, trovate da utenti diversi, la tua soluzione mi sembra assente... )

Vabbé non mi sembra tutto questo granché come soluzione, poi non saprei nemmeno come fare!
Ti ringrazio comunque per avermi fatto conoscere quel sito, davvero molto interessante!

"axpgn":Mi sono un po' perso ad un certo punto ...

Riporto un paio di output relativi alle combinazioni con ripetizione, magari possono essere utili per rendere più chiara la mia spiegazione

n = 17

TUTTE LE COMBINAZIONI:
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 2 2
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 2 8
1 3 3
1 3 4
1 3 5
1 3 6
1 3 7
1 3 8
1 4 4
1 4 5
1 4 6
1 4 7
1 4 8
1 5 5
1 5 6
1 5 7
1 5 8
1 6 6
1 6 7
1 6 8
1 7 7
1 7 8
1 8 8  --> OK
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
2 2 7
2 2 8
2 3 3
2 3 4
2 3 5
2 3 6
2 3 7
2 3 8
2 4 4
2 4 5
2 4 6
2 4 7
2 4 8
2 5 5
2 5 6
2 5 7
2 5 8
2 6 6
2 6 7
2 6 8
2 7 7
2 7 8  --> OK
2 8 8
3 3 3
3 3 4
3 3 5
3 3 6
3 3 7
3 3 8
3 4 4
3 4 5
3 4 6
3 4 7
3 4 8
3 5 5
3 5 6
3 5 7
3 5 8
3 6 6
3 6 7
3 6 8  --> OK
3 7 7  --> OK
3 7 8
3 8 8
4 4 4
4 4 5
4 4 6
4 4 7
4 4 8
4 5 5
4 5 6
4 5 7
4 5 8  --> OK
4 6 6
4 6 7  --> OK
4 6 8
4 7 7
4 7 8
4 8 8
5 5 5
5 5 6
5 5 7  --> OK
5 5 8
5 6 6  --> OK
5 6 7
5 6 8
5 7 7
5 7 8
5 8 8
6 6 6
6 6 7
6 6 8
6 7 7
6 7 8
6 8 8
7 7 7
7 7 8
7 8 8
8 8 8

N(formula) = 8

N(combinazioni) = 8

n = 43

COMBINAZIONI VINCENTI:
1       21      21
2       20      21
3       19      21
3       20      20
4       18      21
4       19      20
5       17      21
5       18      20
5       19      19
6       16      21
6       17      20
6       18      19
7       15      21
7       16      20
7       17      19
7       18      18
8       14      21
8       15      20
8       16      19
8       17      18
9       13      21
9       14      20
9       15      19
9       16      18
9       17      17
10      12      21
10      13      20
10      14      19
10      15      18
10      16      17
11      11      21
11      12      20
11      13      19
11      14      18
11      15      17
11      16      16
12      12      19
12      13      18
12      14      17
12      15      16
13      13      17
13      14      16
13      15      15
14      14      15

N(formula) = 44

N(combinazioni) = 44

[axpgn]

No, non è per quello; anch'io ho scritto un programmino per verificare i risultati e ne ho testati una decina a caso, e tornano.
Intendevo solo dire che a un certo punto faticavo a seguire la tua dimostrazione e ho lasciato perdere ...

Ciò che ancora manca per completare (se così possiamo dire), è una formula (relativamente) semplice per il calcolo diretto.
La formula non è complicata ma la relativa dimostrazione è più lunga della tua (almeno la mia )

Cordialmente, Alex

[Super Squirrel]

"axpgn":No, non è per quello; anch'io ho scritto un programmino per verificare i risultati e ne ho testati una decina a caso, e tornano.
Intendevo solo dire che a un certo punto faticavo a seguire la tua dimostrazione e ho lasciato perdere ...

Infatti lo scopo di quegli output non era quello di dimostrare la bontà del procedimento, ma di rendere in generale la mia spiegazione più semplice da seguire fornendo alcuni esempi concreti.

"axpgn":Ciò che ancora manca per completare (se così possiamo dire), è una formula (relativamente) semplice per il calcolo diretto.
La formula non è complicata ma la relativa dimostrazione è più lunga della tua (almeno la mia )

Io per il momento passo e attendo le vostre soluzioni!

[axpgn]

Ma avevo capito quello che avevi fatto, l'idea (se così posso dire) mi era chiara; è nei passaggi e nei simboli che mi perdo
(dovrei concentrarmi di più ma non mi viene )

Cordialmente, Alex

[Umby2]

"Super Squirrel":
Io per il momento passo e attendo le vostre soluzioni!

Tengo a precisare, che non ho scritto una linea di codice (non avevo una gran voglia),
mi sono limitato al "copia ed incolla" in excel.

Ne ho provate un paio di soluzioni....

Quella più semplice è:
a(n) = a(n-2) + a(n-3) + a(n-4) - a(n-5) - a(n-6) - a(n-7) + a(n-9)

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

Un po più complessa, ma che differenzia le soluzioni pari da quelle dispari è:
(mi piace di meno, in quanto il risultato andrebbe "arrotondato")

Pari: $(p^2)/48$
Dispari: $((p+3)^2)/48$

... ce ne sono altre...

[axpgn]

E dagli ... che senso ha copiarle da OEIS?

Allora tanto valeva che io le scrivessi nel primo post e la finivamo subito lì ...

L'importante non è (solo) trovarle ma dimostrarle (cosa che Super Squirrel ha fatto)