Newsgroup: it.hobby.enigmi
Titolo: Triangoli nel quadrato.

Non ho capito bene il problema di Peter Hendriks, mi viene in mente
l'Invincibile Armata che si scontra con l'Insormontabile Difesa.
Però me ne viene in mente un altro di packing che non vedo nelle
pagine specializzate, e ve lo propongo:
Che forma devono avere N triangoli congruenti (uguali, sovrapponibili
al limite rovesciandoli) per riempire al meglio un quadrato ???
Mi sembra interessante per N=1,3,5,6,7,9,...
Ciao!!!  :o)
Livio


Tu mi vuoi male... rischio di non lavorare piu'...
Per quello con 3 triangoli penso sia difficile battere lo 0.75 che
si puo' ottenere in modo banale con 3 triangoli rettangoli isosceli.
Anche io non ho capito molto bene il problema di Hendriks.
ciao,
g.

 si puo' ottenere in modo banale con 3 triangoli rettangoli isosceli.
Oh penso invece proprio di sì. Ho qua un 0.866+  :o)
Ciao!!!  :o)
Livio

 Oh penso invece proprio di sě. Ho qua un 0.866+  :o)
Che figuretta!! D'altra parte sono sempre stato negato
per la rappresentazione spaziale. Gia' confondo destra e
sinistra... comunque ho una mezza idea di come potresti
aver fatto, ma ogni volta che cerco di disegnarla riempio
solo il quadrato di scarabocchi...
ciao,
g.

 solo il quadrato di scarabocchi...
Partendo dall'esagono, per N=6 c'è una soluzione fantastica!
Ciao!!!  :o)
Livio

 ... Ho qua un 0.866+  :o)
E si può fare meglio!
Ciao!!!  :o)
Livio
PS: Come ebbi già occasione di dire, il max del sadomaso è inventare
i problemi e poi provare a risolverli.

 Non ho capito bene il problema di Peter Hendriks,
Io non l'avevo capito per come l'aveva annunciato
su usenet. Ma sul sito e' piu' comprensibile, perche'
fa riferimento ad un set di lati fissati con i quali
costruire i possibili triangoli.
Rimane comunque, per quel che mi riguarda, inavvicinabile ,come
peraltro il tuo enigma...
ciao,
g.

 si puo' ottenere in modo banale con 3 triangoli rettangoli isosceli.
ma come li metti questi tre triangioli rettangoli isosceli?
Fai così:
due li affianchi a formare un mezzo quadrato, e il terzo lo metti con 
l'ipotenusa lungo la diagonale del mezzo quadrato, centrata. Si vede 
facilmente che con questa figura puoi coprire un quadrato sprecando solo due 
piccole punte.
La superficie è 1/(18-12sqrt(2)) = 0.9714+
[FIDOCAD]
LI 90 15 160 15
LI 160 15 160 85
LI 160 85 90 15
LI 95 15 95 80
LI 95 80 160 80
LI 160 15 125 50
sempre se ho capito il problema!
-- 
Ciao, Silv:o) 

 sempre se ho capito il problema!
Non mi sarò spiegato abbastanza io!
Quello che proponi è un problema di copertura (covering), non di
packing. Io volevo proporre il miglior riempimento di un quadrato,
cioè i triangoli devono stare tutti dentro il quadrato riempiendolo a
un tot %.
Ecco la più vecchia pagina web di packing:
http://www.stetson.edu/~efriedma/packing.html
Ciao!!!  :o)
Livio

 un tot %.
ah, ecco.
Trisecando un angolo del quadrato si infilano agevolmente tre mezzi 
triangoli equilateri.
Eccolo il tuo 0.866+ (che a scriverlo sqrt(3)/2 si aiuta troppo :)
-- 
Ciao, Silv:o)

 Eccolo il tuo 0.866+ (che a scriverlo sqrt(3)/2 si aiuta troppo :)
Che però si può battere...
'Notte!!!  :o)
Livio

 'Notte!!!  :o)
se mi dici cosě, difficile dormire :)
-- 
Silv:o)

 ma sei sicuro?
Verifico............................................
Sì!
Ciao!!!  :o)
Livio


Per N pari c'e'  sempre una soluzione totale semplicissima.
Se L e' il lato del quadrato, triangoli rettangoli con un cateto L e
l'altro 2L/N

 Eccolo il tuo 0.866+ (che a scriverlo sqrt(3)/2 si aiuta troppo :)
A me piace di piu' la forma trigonometrica: sen(60°), o, se preferite,
 sen(pigreco/3) . Non chiedetemi perche', non lo so neanch'io :-)


Vabbeh, non ci siete cascati.
Ma ci sarà qualcuno che ci è cascato e non lo dice!
Ciao!!!  :o)
Livio
PS: questo ci dice anche che per N=9 bisognerà trovare una sol
migliore del 90%

 migliore del 90%
Esatto. 90% e' quello che ottiani dalla soluzione totale con N=10
togliendo un triangolo.
Piu' in generale, se esiste una soluzione totale per N ne esiste
sicuramente una (1-1/N) per N-1

 sicuramente una (1-1/N) per N-1
Ma, almeno fino a N=9, non sono le migliori.
Ciao!!!  :o)
Livio

 Sì!
Con triangoli di 30 gradi, non credo si possa fare meglio.
A meno di non passare a schemi diversi, che non riesco proprio a 
immaginare, mi pare che l'unica via sia fare triangoli con angolo 30+ 
sacrificando qualcosa nell'ipotenusa o nel cateto.
Ho controllato analiticamente alcune soluzioni ottenute da quella base 
variando qualche parametro, per esempio spostando il punto di contatto 
dei vertici di 30 gradi lungo la bisettrice del quadrato, oppure lungo 
uno dei lati. Le funzioni si sono dimostrate monotone decrescenti, 
quindi niente massimi locali ma solo peggioramenti.
Ora mi resta solo da controllare un'altra idea, ma non mi pare 
semplicissima da affrontare con l'analisi matematica.
- accorcio di un epsilon le tre ipotenuse
- faccio scorrere il triangolo centrale di epsilon lungo la sua (ex) 
ipotenusa
- allargo gli angoli di 30 gradi per quanto possibile
Forse si guadagna qualcosa, anche se a occhi mi pare di no, visto che 
perdo tre triangolini di area epsilon/4 per quadagnare una regione di 
area nell'ordine di epsilon/sqrt(3), che è abbastanza minore di 3/4.
Che dici, vado avanti?
--
Ciao, Silv:o)

 Che dici, vado avanti?
No, ricomincia da dove eri partito (backtrack :o)
Ciao!!!  :o)
Livio

 No, ricomincia da dove eri partito (backtrack :o)
Poi quando avete finito
(1) mi fate un disegnino, cosi' capisco anche io
(2) risolvete il problema speculare: cioe' che forma deve avere un
triangolo per poter contenere al meglio 1,2,3,.... quadrati.
grazie,
ciao,
g.


Sarei proprio contento ti dedicassi un po' a questo problema.
A me sembra molto interessante. Ci ho provato anche nel weekend
su un blocco notes. E a maggior ragione sarebbe interessante 
risolverlo
come di solito fai tu, cioè cercando un sw che lo risolva. Ma è più
difficile di un normale problema di packing, perchè ci sono più
variabili e molti *minimi ralativi*. Ad es., per passare dalla 
soluzione
0.866 che ha descritto Silvio ad una un po' migliore, occorre fare un
salto (paradigmatico?), non si può procedere a piccoli passi.
Ciao!!!  :o)
Livio

 (1) mi fate un disegnino, cosi' capisco anche io
forse basta l'asciiart
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
|\-.                          |
| \ '-.                       |
|  \   '-.                    |
|   \     '-.                 |
|    \       '-.              |
|     \         '-.           |
|      \           '-.        |
|       \             '-.     |
|        \               '-.  |
|         \                 '-|
|          \                ./|
|           \            .-'  |
|            \        .-'     |
|             \    .-'        |
|              \.-'           |
|               \             |
|                \            |
|_ _ _ _ _ _ _ _ _\_ _ _ _ _ _|
Come faccia Livio a miglioralo, mi pare un miracolo.
Io avevo pensato di limare qualcosa dalle ipotenuse, poi sfialre un 
po' il triangolo centrale e poi allargare gli angoli da 30 gradi per 
quanto possibile. Ma il gioco non vale la candela, pare.
--
Silv:o)

 Che però si può battere...
Vediamo se mi smonti anche questo:
 _________________________
|\                       *|
|                      *  |
|   \                *    |
|                  *      |
|   .  \         *        |
|     .        *          |
|  '    . \  *            |
|         .*              |
| '         .°            |
|             . °         |
|'              .  °      |
|                 .   °   |
|___________________.____°|
X è il lato in comune dei due triangoli in alto (e giace sulla diagonale), 
ed è anche la base del triangolo in basso.
Deve essere X+1/X=sqrt(2), da cui si ricava X.
La superfice complessiva dei tre triangoli vale 3/2*(2-sqrt(2)) = 0,878+
-- 
Ciao, Silv:o) 

 La superfice complessiva dei tre triangoli vale 3/2*(2-sqrt(2)) = 0,878+
YesssSirr!!!
Quando l'hai visto, hai subito pensato ch'era lui, vero? :o)
E adesso non ci resta che risolverlo per N=5,7,9,11,...
Vediamo se ora ci da una mano qualcuno.
Ciao!!!  :o)
Livio

 triangolo per poter contenere al meglio 1,2,3,.... quadrati.
Per n=3 qualcuno ha trovato qualcosa di meglio di 2/3 che si ottiene 
mettendo i quadrati a L in un triangolo rettangolo isoscele?
--
Ciao, Silv:o)

 Vediamo se ora ci da una mano qualcuno.
speriamo
--
Silv:o)

 Vediamo se ora ci da una mano qualcuno.
Io ci provo, ma senza successo.
Per ora il massimo che ho trovato e` un'altra soluzione con N=5 e
copertura 5/6, usando triangoli di lato 1, sqrt(2)/3 e sqrt(5)/9:
due coppie di triangoli con il lato lungo sui lati del quadrato e il
lato corto su di una diagonale del quadrato, il quinto triangolo del
buco che rimane in mezzo (probabilmente non si capisce niente, ma il
disegno non mi viene).
        Mauro