SNS 2004-2005 Numero 1

[memedesimo]

Non saprei in che sezione mettere questo esercizio, quindi lo faccio qui! Mi interessa sapere il vostro approccio al problema!

Si determinino i rettangoli che sono "pavimentabili" con mattonelle rettangolari 3x2.

[enomis_costa88]

Uccidiamo quest post indegno fatto da uno sporco fisico pezzente (vendetta contro voi fisici che mi votate come 31-esimo, ovviamente senza offesa parlo così con tutti )..

Nessuna idea..il prodotto deve essere figo e un lato non può essere 1..poi si costruisce..

Il prodotto deve essere multiplo di 6.
Se un lato è multiplo di 3 e l'altro di 2 è banale.
Supponiamo che un lato sia multiplo di 6 e l'altro scelto a cazzo ma non multiplo di 2 o di 3 (quindi modulo 6 può essere 1 o 5)
Posso ottenere un rettangolo 6*5 da cui tutti quelli con il lato 5 modulo 6.
Posso ottenere un rettangolo 6*7 da cui tutti quelli con il lato 1 modulo 6 tranne quello con il lato 1.

Ora questo è un vero problema?

[Gufus]

Ci sono due possibilità...
1_O metto tutti i rettangolini 2x3 in verticale, o in orizzontale alla fine posso comunque rigirare la figura e mi esce la stessa cosa...
in questo caso i rettangoli pavimentabili sono quelli il cui lato maggiore è
3x e il lato minore è 2y con x e y non necessariamente uguali...

2_ Sistemo i rettangolini 2x3 in verticale e in orizzontale...
poichè posso avere che il lato maggiore di un rettangolo sia formato da segmenti di 3 e il suo parallelo da segmenti di 2 allora deve essere che 3k=2h
cioè che il lato maggiore sia divisibile sia per 3 che per 2.Magari è anche un'invariante ma non sono sicuro...adesso mi sono bloccato ...quindi...
ciao! e spero di esserti stato anche solo un pochino di aiuto...

[EUCLA]

Supponiamo che un lato sia multiplo di 6 e l'altro scelto a cazzo

dev'essere il rigore matematico di cui ho tanto sentito parlare

[enomis_costa88]

nessuno mi ha sentito al preimo dire alla lavagnetta frasi del tipo:

"il 7 mi stà antipatico e lo chiamo h"

oppure
"questo coso è una costante" indicando una lunga espressione.

Oppure subito dopo chiamare h una funzione con bobo che si mette a ridere dicendo che 7 di x è lineare..

[memedesimo]

Io l'avevo fatto così: se un lato è multiplo di 3 e l'altro di 2, si può. Se un lato è multiplo di 6, allora si può sempre tranne quando l'altro lato è 1. altre configurazioni non esistono.

[enomis_costa88]

è abbastanza la stessa cosa che ho fatto io

Comunque formalmente se volete fare gli sboroni (per questo problema non ne vale la pena ) si scrive esattamente come ho fatto io aggiungendo solo la parola induzione (e togliendo quella cazzo).

[memedesimo]

però a me non sembrava così ovvio! maledetti matematici!!

[Marco]

Rilancio con questo vecchio Teorema, genializzato assieme al buon Mindflyer:

Teorema del Piastrellista
Siano $ a,b,c,d $ interi positivi.

Allora è possibile piastrellare una stanza rettangolare $ a \times b $ con mattonelle rettangolari $ c \times d $ se e solo se:

- entrambi $ c $ e $ d $ dividono almeno uno dei due tra $ a $ e $ b $;
- entrambi $ a $ e $ b $ sono della forma $ cx+dy $, con $ x,y $ interi non negativi.

[enomis_costa88]

Vediamo se dopo un'estate passata a sporcarmi le mani con quella brutta cosa chiamata fisica so ancora risolvere un bel problema di marco

Lemma: I rettangoli piastrellabili con piastrelle 1*n sono solo quelli tali che un lato sia divisibile per n.

Consideriamo la seguente colorazione in n colori.
La casa (x,y) sarà colorata con il colore x+y-1 modulo n.
Ogni rettangolo 1*n copre n caselle di n colori differenti.

Se esiste la piastrellatura allora il numero di caselle colorate in ciascun colore nel rettangolo è uguale per ogni colore.

Claim: il numero di caselle colorate in ciascun colore è uguale per ogni colore se e solo se n divide un lato.

Possiamo “uccidere” i rettangoli n*k (poiché hanno lo stesso numero di caselle per ogni colore uguale) e supporre quindi a e b minori di n (in pratica li considero modulo n).
Wlog $ b\ge a $.
Se n non divide un lato allora a e b non sono nulli.

Nel rettangolo a*a ho esattamente a caselle colorate del colore a (tutta la sua diagonale).
Quindi in ogni rettangolo a*b avrò almeno a caselle colorate di a (in realtà esattamente).
La media di caselle per colore sarà $ \frac{ab}{n}< \frac{an}{n}=a $
Se ne ho a di un colore allora ci sarà anche un altro colore con meno della media e quindi meno di a.
Quindi a deve risultare nullo.
E con questo si dimostra il lemma.

Consideriamo ora le due condizioni..
La seconda è necessaria altrimenti non sarebbe possibile completare il bordo del rettangolo.

Se la prima non fosse necessaria ovvero se esistesse un rettangolo tassellabile tale che c (o d) non divida nessuno dei suoi due lati allora esisterebbe anche un rettangolo tassellabile con piastrelle 1*c e tale che c non divida nessuno dei suoi lati che è assurdo per il lemma 1.

Le due condizioni sono inoltre sufficienti.
Se c divide un lato e d divide l’altro è banale tasselare il rettangolo.
Se c e d dividono lo stesso lato a allora l’altro sarà scrivibile come cx+dy=b e tagliandolo in due rettangoloni cx*a e dy*a ricado nel caso precedente.