Dato un rettangolo a*b, determinare il massimo numero di rettangoli c*d tali che occupino la regione di piano interna al primo rettangolo(Naturalmente i rettangoli c*d non possono avere delle parti di piano in comune ne quantomeno sovrapporsi).Vi chiedo inoltre se è possibile generalizzare questo
<BR>problema, ossia data una certo poligono A trovare il massimo numero di poligoni B che possiamo trovare all\' interno dell\' area di piano definita da A.
Rettangolo da tessellare
Moderatore: tutor
Ciao Igor.
<BR>
<BR>Stai proponendo un problema o un quesito aperto, di cui nemmeno tu conosci la soluzione? Nel secondo caso, sarebbe più corretto se tu lo dichiarassi nella proposta del problema.
<BR>
<BR>Ad occhio mi sembra una questione tosta (quella sui poligoni di sicuro), ma anche il caso dei rettangoli mi sembra tutt\'altro che semplice.
<BR>
<BR>A parte i casi facili in cui c divide uno tra a e b e d divide l\'altro, in cui è banale, e pochi altri, è improbabile che esista una nice solution.
<BR>
<BR>Controesempi interessanti:
<BR>
<BR>La stima dal basso ovvia NON basta:
<BR>5x5 tassellato con 3x2. La tassellatura naif, con le mattonelle tutte parallele tra loro sistema due mattonelle. Nel ritaglio a L che avanza, se ne può mettere solo un\'altra per traverso. Il massimo possibile è invece 4 mattonelle, lasciando il buco al centro.
<BR>
<BR>La stima dal\'alto ovvia NON basta:
<BR>3x3 tassellato con 2x2: la stima massima ovvia [ab/cd] = 2 non è raggiungibile, in quanto l\'unica possibilità è mettere una sola mattonella.
<BR>
<BR>Con poca difficoltà, puoi costruire analogamente un facile controesempio in cui l\'area tassellabile è minore di 1/4<sup>+</sup> dell\'area totale.
<BR>
<BR>Invece si può dimostrare che riesci sempre a tassellare almeno 1/4 di superficie [ok: a parte il caso cretino in cui non riesci a mettere nemmeno una mattonella: se pretendi di mettere in un quadrato 8x8 mattonelle lunghe 47, non riesci a sistemarne nemmeno una...]
<BR>
<BR>Mi sembra che il problema si risolva sempre (ossia si determina il massimo) nel caso particolare di mattonelle 1 x d (ma non ne sono troppo sicuro, boh, proviamoci...)
<BR>
<BR>Altre idee per ora non me ne vengono.
<BR>
<BR>Alla prox...
<BR>
<BR>Ciao. M.[addsig]
<BR>
<BR>Stai proponendo un problema o un quesito aperto, di cui nemmeno tu conosci la soluzione? Nel secondo caso, sarebbe più corretto se tu lo dichiarassi nella proposta del problema.
<BR>
<BR>Ad occhio mi sembra una questione tosta (quella sui poligoni di sicuro), ma anche il caso dei rettangoli mi sembra tutt\'altro che semplice.
<BR>
<BR>A parte i casi facili in cui c divide uno tra a e b e d divide l\'altro, in cui è banale, e pochi altri, è improbabile che esista una nice solution.
<BR>
<BR>Controesempi interessanti:
<BR>
<BR>La stima dal basso ovvia NON basta:
<BR>5x5 tassellato con 3x2. La tassellatura naif, con le mattonelle tutte parallele tra loro sistema due mattonelle. Nel ritaglio a L che avanza, se ne può mettere solo un\'altra per traverso. Il massimo possibile è invece 4 mattonelle, lasciando il buco al centro.
<BR>
<BR>La stima dal\'alto ovvia NON basta:
<BR>3x3 tassellato con 2x2: la stima massima ovvia [ab/cd] = 2 non è raggiungibile, in quanto l\'unica possibilità è mettere una sola mattonella.
<BR>
<BR>Con poca difficoltà, puoi costruire analogamente un facile controesempio in cui l\'area tassellabile è minore di 1/4<sup>+</sup> dell\'area totale.
<BR>
<BR>Invece si può dimostrare che riesci sempre a tassellare almeno 1/4 di superficie [ok: a parte il caso cretino in cui non riesci a mettere nemmeno una mattonella: se pretendi di mettere in un quadrato 8x8 mattonelle lunghe 47, non riesci a sistemarne nemmeno una...]
<BR>
<BR>Mi sembra che il problema si risolva sempre (ossia si determina il massimo) nel caso particolare di mattonelle 1 x d (ma non ne sono troppo sicuro, boh, proviamoci...)
<BR>
<BR>Altre idee per ora non me ne vengono.
<BR>
<BR>Alla prox...
<BR>
<BR>Ciao. M.[addsig]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
Riecco i rettangoli selvaggi!!
<BR>A <!-- BBCode Start --><A HREF="http://olimpiadi.sns.it/modules.php?op= ... 81&forum=5" TARGET="_blank">QUESTO LINK</A><!-- BBCode End --> è già stato proposto un problema simile e più generale. Ovviamente, nè questo nè l\'altro troveranno una soluzione che i proponenti giudicherebbero \"accettabile\".
<BR>A <!-- BBCode Start --><A HREF="http://olimpiadi.sns.it/modules.php?op= ... 81&forum=5" TARGET="_blank">QUESTO LINK</A><!-- BBCode End --> è già stato proposto un problema simile e più generale. Ovviamente, nè questo nè l\'altro troveranno una soluzione che i proponenti giudicherebbero \"accettabile\".
<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2005-01-27 08:58, marco wrote:
<BR>Invece si può dimostrare che riesci sempre a tassellare almeno 1/4 di superficie [ok: a parte il caso cretino in cui non riesci a mettere nemmeno una mattonella...]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>No, questo è falso. Ci sono casi in cui puoi mettere almeno una mattonella ma non puoi coprire più di un n-esimo di superficie, con n a piacere.
<BR>Ma diventa vero se una mattonella può essere contenuta nel rettangolo in modo che i loro lati siano paralleli (in modo che per ogni lato del rettangolo ci sia un lato del tassello ad esso parallelo).
<BR>On 2005-01-27 08:58, marco wrote:
<BR>Invece si può dimostrare che riesci sempre a tassellare almeno 1/4 di superficie [ok: a parte il caso cretino in cui non riesci a mettere nemmeno una mattonella...]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>No, questo è falso. Ci sono casi in cui puoi mettere almeno una mattonella ma non puoi coprire più di un n-esimo di superficie, con n a piacere.
<BR>Ma diventa vero se una mattonella può essere contenuta nel rettangolo in modo che i loro lati siano paralleli (in modo che per ogni lato del rettangolo ci sia un lato del tassello ad esso parallelo).
E\' vero. Ho dato per scontata l\'ipotesi che le mattonelle andassero sistemate per benino (un problema di scacchiere e non di geometria...)
<BR>
<BR>Cmq, anche con la limitazione dei lati ortogonali, il pb è tutt\'altro che facile e su questo siamo d\'accordo...
<BR>
<BR>Cmq, anche con la limitazione dei lati ortogonali, il pb è tutt\'altro che facile e su questo siamo d\'accordo...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."