Newsgroup: it.hobby.enigmi
Titolo: Ricoprire un rettangolo

Abbiamo un rettangolo di lati mxn (interi) e vogliamo ricoprirlo con
quadrati.
Diciamo che il ricoprimento è "non-banale" se i quadrati che usiamo hanno
tutti il lato maggiore del massimo comun divisore tra m e n (perchè se
potessimo usare quadrati di quella dimensione sarebbe banale ricoprire il
rettangolo).
Alcuni rettangoli NON ammettono ricoprimenti non-banali, ad esempio il
rettangolo 5x4, invece altri ammettono ricoprimenti non-banali, ad esempio
il rettangolo 6x5 si ricopre con due quadrati 3x3 e tre quadrati 2x2 (e il
MCD è 1).
Domanda: quanti e quali rettangoli ammettono un ricoprimento "non-banale"?
Ciao,
Marco

 Domanda: quanti e quali rettangoli ammettono un ricoprimento "non-banale"?
Non e' banale risponderti!  :o)
Io intanto ho notato questo:
che la probabilita' di avere un ricoprimento non-banale sembra
proporzionale alla sua dimensione. Un rettangolo molto grande
ha una buona probabilita' di essere ricoperto da una sommatoria
di piccoli quadrati perche' le combinazioni possibili aumentano.
Ad es. un rettangolo 16xN, con N=5..27, dispari puo' sempre
essere ricoperto (brute force).
Forse (forse) e' piu' interessante trovare quelli che ammettono
solo il "ricoprimento banale". E se fossero di numero finito?  :o)
Ciao!!!  ((^__^))'
Livio

 solo il "ricoprimento banale". E se fossero di numero finito?  :o)
E' vero... potremmo chiederci se esistono famiglie infinite di rettangoli
non ricopribili...
Ciao!!
Marco

"LordBeotian"

Quali e quanti, ancora non lo so. Però quello che riporto in seguito
potrebbe essere un metodo per generare almeno alcuni di tali rettangoli.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Ammettono un ricoprimento non-banale tutti quei rettangoli in cui, trovate
tutte le possibili scomposizioni in fattori del lato maggiore (m), e
ottenuta la somma dei fattori di ciascuna scomposizione (n), vi è almeno una
scomposizione per cui il MCD(m,n) è minore di ogni fattore della
scomposizione. Chiaro, no? :-)
Faccio un esempio:
Prendo un rettangolo con lato maggiore m = 12. Lo scompongo in fattori (non
considero il fattore 1 per motivi che spiegherò più avanti). Le
scomposizioni possibili sono:
2, 2, 3
2, 6
3, 4
Le loro somme sono rispettivamente 7, 8, 7.
Prendiamo la prima somma, 7. Il MCD(12, 7) è 1 che è minore di ogni fattore
della scomposizione (2, 2, 3  o 3, 4). Quindi il rettangolo 12x7 ammette una
ricopertura non-banale. In questo caso 12 quadrati da 2 e 4 da 3 oppure 4 da
3 e 3 da 4.
In sostanza questo procedimento realizza la scomposizione del rettangolo
iniziale in "strisce" di altezza corrispondente ai fattori della
scomposizione, che possano essere tassellate con un numero intero di
quadrati di lato corrispondente. Non considero il fattore 1 perché otterrei
strisce tassellabili dal quadrato di lato 1 che che non è mai maggiore di
alcun MCD.
Tutto ciò non toglie che si possano trovare altri rettangoli tassellabili in
altro modo.
Comunque già con questo metodo mi sembra che ne vengano fuori parecchi. A
occhio e croce direi infiniti. O no?
Ciao :-)
Giorgio

 non ricopribili...
Con un lato molto piccolo... 2,3,4
Gia' con 5, no.
Prendiamo i rettangoli 5xN con N primo a 5:
sono ricopribili in modo non-banale?
5x6  SI
5x7  NO
5x8  NO
5x9  NO
5x11 SI
5x12 SI
5x13 NO
5x14 NO
5x16 SI
5x17 SI
5x18 SI
5x19 NO
5x21 SI
5x22 SI
5x23 SI
5x24 SI
5x26 SI
5x27 SI
5x28 SI
5x29 SI
5x31 SI
5x32 SI
5x33 SI
5x34 SI
5X36 SI
5X37 SI
5X38 SI
5X39 SI
Notare come i NO si rarefacciano. Penso sia facile
dimostrare che non ne verranno piu' fuori.
Mi pare verosimile che i solo-banali, per dimensione superiore
ad un tot, siano veramente pochini.
Ciao!!!  ((^__^))'
Livio

>rettangolo).
Mi restringo al caso in cui m e n sono primi tra loro.
Ovvero voglio trovare una ricopertura che non usi il quadratino 1x1.
Allora mi sembra che si possa mostrare facilmente (costruttivamente)
che
se il rettangolo ha un lato pari ed uno dispari
con il pari uguale a 6, 10, 12, o maggiore o uguale a 16 e il dispari 
maggiore o uguale a 5 allora esiste sempre una ricopertura.
se il rettangolo ha due lati dispari entrambi maggiori uguali a 9
e almeno uno dei due uguale a 15, 21, 25, 27 o maggiore o uguale a 31 
allora esiste una ricopertura.
Probabilmente si possono ridurre le limitazioni, ma ora non ho
voglia di fare i vari casi...
Comunque il risultato sopra si puo' ottenere cosi':
consideriamo la costruzione del 6x5 che si ottiene mettendo una pila di
2 quadrati 3x3 a fianco di una pila di 3 quadrati 2x2.
Aggiungendo delle pile larghe 3 o 2 possiamo chiaramente ottenere
tutti i rettangoli 6xL dove L>1. (Ovviamente le 6x2, 6x3, 6x4, 6x6,...
si possono ottenere con un solo tipo di  quadrato. Non sono
ricoperture buone in generale, ma qui lo sono perche' le usiamo solo
come mattoni).
Possiamo fare la stessa cosa con una piletta di 2 5x5 e di 5 2x2
ottenendo tutte le striscie 10xL dove L={2,4,5,6,7,8,9,.... }
cioe' tutti i valori L>1 con L!=3.
A questo punto dovendo ricoprire un rettangolo PxD con pari P>=16
e D>=5 dispari mi basta scomporre P come somma di multipli
di 10 e 6 (cosa che e' fattibile per tutti i numeri maggiori o uguali a 
16) e giustapporre le fascie corrispondenti.
Per quello con due lati dispari faccio la stessa cosa ma mi aiuto
con la fascia dispari con lato dispari che si ottiene usando i
quadrati 3x3 e 5x5 ottenendo una fascia alta 15 e larga
{3,5,6,8,9,10,11,12,13,...} insomma manca il 7.
Dopo di che la fascia 15 la posso combinare con fascie da 6 e da 10 per
ottenere tutti i numeri dispari maggiori uguali a 31.
Chiaramente i limiti si possono abbassare, perche'
ho usato scomposizioni molto semplici.
ciao,
g.

 Domanda: quanti e quali rettangoli ammettono un ricoprimento "non-banale"?
Riassumendo, per rettangoli con lati primi tra di loro, NON hanno
ricoprimenti non-banali questi:
2xN, 3xN, 4xN
5x7, 5x8, 5x9, 5x13, 5x14, 5x19
7x8, 7x9, 7x11, 7x15
8x9, 8x11, 8x13
9x11
Non ne trovo altri.
Ciao!!!  ((^__^))'
Livio