Newsgroup: it.hobby.enigmi
Titolo: [MA] Problema tosto

La figura e' un esempio di reticolo di punti su coordinate intere 7x5.
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
Quanti rettangoli distinti si possono disegnare con i vertici su 4 punti 
di un reticolo MxN ?

di un reticolo MxN ?
Ma rettangoli anche quadrati?
-- 
Ciao,		|   Attenzione! campo "Reply-To:"  alterato	|
Remigio Zedda	|   posta: ti.ilacsit@zoigimer  <-- dx/sn  ;^)	|
	-- GNU/Linux 2.4.25 su Slackware 9.1

 
Si' Certamente.
ciao


spoiler
Allora e` semplice.. a meno dei miei soliti errori.
In generale: nm(n-1)(m-1)/4, dunque 210.


 In generale: nm(n-1)(m-1)/4, dunque 210.
Se leggi il thread di qualche giorno fa "Stuzzicadenti" , Giorgio Vecchi 
aveva gia' dato questa formulina, idonea a contare quei rettangoli con i 
lati ortogonali alla griglia.
Qui si chiede di enumerare anche quelli "inclinati".
Il problema mi e' venuto in mente prendendo spunto proprio dal 
precedente, ma non ho idea di quale sia la soluzione.

 ha scritto nel messaggio 
news:B9kyd.54347$C94....@tornado.fastwebnet.it...

Il problema mi sembra veramente tosto, e anch'io non so come si possa 
trovare una soluzione generalizzata per qualsiasi m-n.
Una prima idea che mi viene in mente è quella di considerare che ogni 
rettangolo *inclinato* si può considerare inscritto in un rettangolo 
*dritto*, formato dalle rette orizzontali e verticali passanti per i 
vertici del primo..
Purtroppo la cosa non è reciproca, infatti in un rettangolo dritto 
generico possono essere inscritti nessuno, uno o forse più rettangoli 
inclinati.
Esisterà una regola per contarli?
ciao
paolo

 precedente, ma non ho idea di quale sia la soluzione.
suggerisco di andare per gradi. Chi fosse interessato potrebbe 
cimentarsi con il problema piu' semplice di determinare
quanti quadrati (anche inclinati) ci sono in un lattice quadrato
di NxN punti. Non so esattamente come si risolve, ma so la formula
chiusa ed e' piuttosto semplice...
ciao,
g.

 chiusa ed e' piuttosto semplice...
Io invece ho un procedimento per arrivare alla soluzione, ma non ho la 
formula chiusa :-)
Comincio a contare i quadrati dritti
1 quadrato di lato N-1
4=2^2 quadrati di lato N-2
9=3^2 quadrati di lato N-3
...
(N-1)^2 quadrati di lato 1
In genere (N-K)^2 quadrati di lato K, con K compreso tra 1 ed (N-1)
Ciascun quadrato inclinato può considerarsi inscritto in un quadrato 
dritto.
In un generico quadrato dritto di lato K si possono inscrivere K 
quadrati (compreso lo stesso dritto),.
aventi un vertice sulla base del quadrato dritto con ascissa 
0,1,2,...K-1.
Quindi i quadrati in totale dovrebbero essere
sommatoria ((N-K)^2*K)    [con K compreso tra 1 ed (N-1)]
Il guaio è che non mi ricordo come passare dalla sommatoria alla formula 
chiusa.
-------------------------
Volendo andare per gradi, il prossimo passo potrebbe essere:
Partendo da un rettangolo N*M, trovare il numero di rettangoli dritti o 
inclinati di 45 gradi.
Considerando che i rettangoli inclinati di 45 gradi sono inscritti in un 
quadrato dritto, la cosa dovrebbe essere abbastanza semplice.
ciao
paolo

 aventi un vertice sulla base del quadrato dritto con ascissa 0,1,2,...K-1.
Bravo Paolo!!
SPOILER
col tuo procedimento si calcolano facilmente le soluzioni, generando la 
sequenza 0,1,6,20,50,105,196...
n^2(n^2-1)/12