Rettangolo da tessellare

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
Igor
Messaggi: 108
Iscritto il: 01 gen 1970, 01:00

Messaggio da Igor »

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.
Igor
Messaggi: 108
Iscritto il: 01 gen 1970, 01:00

Messaggio da Igor »

Errata Corrige : Rettangolo da tassellare
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

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]
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
MindFlyer

Messaggio da MindFlyer »

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\".
MindFlyer

Messaggio da MindFlyer »

<!-- 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).
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

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...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Bloccato