Newsgroup: it.hobby.enigmi
Titolo: piastrelle di due misure

Dobbiamo riempire una stanza quadrata utilizzando due soli tipi di
piastrelle più piccole, di misure diverse. Di ciascuno tipo ne possiamo
usare sei. Non sono ammesse sovrapposizioni o sconfinamenti. Qual è la
massima porzione copribile?
A scanso di equivoci: con 7 per tipo potremmo coprire un'area di 36/37 in
questo modo:
 ___ ___ _
|   |   |_|_
|___|___|_|_|
|   |   |_|_|
|___|___|_|_|
|   |   |   |
|___|___|___|
Ciao, Silv:o)

 piastrelle più piccole, di misure diverse. 
Quadrate a loro volta ?
Altrimenti si ottiene subito il 100%.
:)dario

 Altrimenti si ottiene subito il 100%.
Pensavo fosse scontato, però... siete liberi di suggerire forme differenti,
anche per la stanza, tipo stanza e piarstrelle rotonde, o triangolari. Anche
il numero di pezzi può essere variato per rendere più interessante il
problema. Intanto cominciamo con 6+6 quadrati nel quadrato.
Silv:o)

 massima porzione copribile?
Inizio con una soluzione banale, e poi con un lievissimo miglioramento (che
sicuramente non rappresenta ancora il ricoprimento ottimale).
Per comodità considero fisso, pari a 2 unità, il lato della piastrella
grande, e variabili il lato della stanza e quello della piastrella piccola.
La prima soluzione che viene in mente è quella di disporre le piastrelle
grandi secondo un rettangolo 6*4 oppure a scaletta, e completare con sei
piastrelle piccole di lato 1 variamente disposte, per esempio come nel
disegno seguente; il ricoprimento risulta
30/36 = 0.8(3)
.    ___ _ _ _ _
.   |   |_|_|_|_|
.   |___|_|_|
.   |   |   |
.   |___|___|___
.   |   |   |   |
.   |___|___|___|
Alcune considerazioni mi portano a ritenere che questo sia il ricoprimento
massimo se si dispongono tutte le piastrelle con i lati paralleli a quelli
della stanza.
Provo allora  a disporre le sei piastrelle grandi, e cinque piastrelle 1*1,
in questo modo:
.    ___ ___   _
.   |   |_|_| |_|
.   |___|___   _
.   |   |   | |_|
.   |___|___|_|_|
.   |   |   |   |
.   |___|___|___|
piazzo poi la sesta piastrella piccola inclinata di 45 gradi, in modo che la
metà di un lato cada sul vertice della piastrella grande centrale.
Vedo che la sesta piastrella piccola non tocca i vertici delle altre tre che
le stanno intorno; provo quindi a dilatare tutte le piastrelle piccole in
modo da recuperare il gap.
Non ho voglia di cercare analiticamente la misura ottimale, graficamente
trovo la soluzione con piastrelle piccole di lato 1.07 (o poco più) e area
1.1449.
Il ricoprimento risulta 30.8694/36 = 0.7548..., migliore, se pure di
pochissimo, del precedente.
ciao paolo

 pochissimo, del precedente.
Ancora un piccolo miglioramento:
 .    ___       _
 .   |   |_    |_|
 .   |___|_|_
 .   |   |   |_
 .   |___|___|_|_
 .   |   |   |   |
 .   |___|___|___|
Sempre in una stanza 6*6, sei piastrelle grandi di lato 2 e tre piastrelle
di lato 1.083, disposte come in figura.
Nello spazio vuoto ci sta una fila, inclinata di 45 gradi, con le altre tre
piastrelle da 1.083.
Il ricoprimento risulta 0.862...
ciao
paolo

 Il ricoprimento risulta 0.862...
Non credo che nessuno sia riuscito a fare di meglio.
Per una panoramica dei migliori risultati raggiunti con n + m piastrelle
(n,m<=17) vedi
http://www.stetson.edu/~efriedma/mathmagic/0400.html
Silv:o)

 Credo che nessuno sia riuscito a fare di meglio.
Però ieri sera quel diavolo di Livio mi ha scritto di aver trovato un
miglioramento (.864+) che ci mostrerà al ritorno dal week-end, se nel
frattempo non l'abbiamo raggiunto o superato.
La sfida è aperta, io per ora non ho trovato nulla.
Ciao, Silv:o)

 La sfida è aperta, io per ora non ho trovato nulla.
Vorrei potervi dire che vi ho fatto uno scherzo.
E invece mi sono proprio SBAGLIATO!
La soluzione che giovedi' sera appariva cosi' lineare ed
elegante non passa la verifica del lunedi' mattina.
Magra consolazione: in questi problemi di packing non si
e' mai sicuri di aver raggiunto l'ottimo. Salvo rarissimi
casi, non c'e' dimostrazione matematica.  Il dubbio 
serpeggia sempre tra le fila. Mi ricorda quell'avvocato
che difese il suo assistito in un caso di omicidio dove
non si era mai trovato il cadavere: disse "Se vi dicessi
che la presunta vittima sta entrando or ora da quella
porta in carne ed ossa?". Tutti si voltarono, non entro'
nessuno ma l'uomo fu assolto per insufficienza di prove.
Ecco: assolvetemi per insufficienza di prove!
Per addolcire la pillola vi segnalo il sito sul
packing dell'amico Erich. E' un buon punto di riferimento:
http://www.stetson.edu/~efriedma/packing.html
Ciao e scusatemi   :o(
Livio
-- 
Posted from 
mta03-acc.tin.it
 [212.216.176.34] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG