SNS 2004-2005 Numero 1
-
- Messaggi: 213
- Iscritto il: 28 nov 2005, 17:17
SNS 2004-2005 Numero 1
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.
Si determinino i rettangoli che sono "pavimentabili" con mattonelle rettangolari 3x2.
- enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
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?
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?
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
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...
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...
[url]http://www.aif.it/[/url]
- enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
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..
"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..
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
-
- Messaggi: 213
- Iscritto il: 28 nov 2005, 17:17
- enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
è 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).
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).
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
-
- Messaggi: 213
- Iscritto il: 28 nov 2005, 17:17
Teorema del Piastrellista
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.
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.
[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."
- enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
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.
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.
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.