Rettangoli Perfetti

Problema:  Dati 4 numeri naturali mR, mC, tR, tC,  trovare il piu' piccolo rettangolo (i cui lati siano in rapporto mR:mC) che possa essere completamente ricoperto con rettangoli distinti i cui lati hanno un rapporto tR:tC.

Ecco alcune delle soluzioni che ho trovato. Il numero dentro ad ogni rettangolo equivale alla lunghezza del suo lato piu' corto. La dimensione dei piu' piccoli puo' essere desunta  dalla "firma" che ho messo sopra la figura. La "firma" descrive il tiling in modo succinto: immaginando di cominciare la ricopertura dall'angolo in alto a sinistra, e poi di inserire un rettangolo nel primo angolo libero a sinistra, la "firma" mi dice in che ordine devo inserire i rettangoli delle varie dimensioni (ad un valore n corrispondera' un rettangolo con lati (n*tR,n*tC). Il carattere che segue la dimensione indica se il rettangolo deve essere disposto verticalmente ("|") o orizzontalmente ("-").

Sommario

1:2 Tiles1:1, 1:2 1:3 1:41:52:3 3:4, 2:53:5 4:5
1:3 Tiles1:1, 1:21:32:3, 3:5
1:4 Tiles1:4
1:5 Tiles1:5
2:3 Tiles1:1, 2:3, 4:5
3:4 Tiles3:4



1:2 Tiles


1:1 tiled with 1:2

34x34 = (10) 13- 10- 11- 3- 7- 6- 5- 8| 1- 2|


 
 

48x48 = (10) 20- 17- 11- 6- 5- 1- 2| 14| 4- 8|


 

Piu' tutte le soluzioni che si ottengono giustapponendo una soluzione p x (2p) al problema  [1:2 con 1:2], (vedi sotto)  ad un rettangolo p x (2p) in modo da ottenere un quadrato (2p) x (2p).



1:2 tiled with  1:2

18x36 = (8) 10- 8- 2- 3| 1| 4- 7| 9|


 

31x62 = (10)  17- 14- 3- 11- 10| 4| 6| 7- 1- 12|

Altre soluzioni:
33x66 = (11) 17- 16- 8| 11- 6- 3- 13- 5- 4- 2| 10|
35x70 = (9) 19- 16- 8| 11- 4| 1- 15- 9- 10|
40x80 = (13) 14- 13| 11- 15- 7| 5- 4- 8| 1- 17| 6- 3| 20|
42x84 = (12) 25- 17- 7- 10- 1- 6- 13| 2- 4| 5| 3| 21|
42x84 = (12) 22- 20- 10| 16- 6- 3- 17- 9- 5- 4- 8| 2|
45x90 = (13) 20- 5- 10| 11- 14- 8- 3- 17- 16- 4- 12- 9- 18|
48x96 = (13) 30- 18- 10- 8- 2- 3| 1| 4- 7| 6- 12| 9| 24|
48x96 = (13) 25- 23- 3- 7- 13- 11- 5- 4| 1- 2| 6| 12| 24|
49x98 = (13) 18- 15- 16- 3- 6| 8| 25- 4| 24- 12| 1- 5- 10|
50x100 = (12) 26- 24- 4| 16- 2- 5| 11| 1| 6| 17| 10- 20|
50x100 = (14) 28- 22- 11| 9| 4- 12- 8| 2| 16| 1| 6- 3| 10- 20|
51x102 = (13) 26- 25- 1- 12| 20- 7- 4| 16- 15- 10| 8| 3- 6|
etc.etc.



1:3 tiled with 1:2

36x108 = (14) 20- 16- 8| 14- 12- 10- 2- 4| 11| 7| 6- 15| 3| 18|

44x132 = (17) 23- 21- 4| 13- 20- 11- 8- 16- 1- 7- 12- 9- 3- 2| 10| 6| 22|

Piu' le soluzioni che, come le due che seguono, derivano direttamente dalle soluzioni [1:1 con 1:2] (piu' un quadrato grande)
34x102 = (11) 34- 13- 10- 11- 3- 7- 6- 5- 8| 1- 2|
36x108 = (10) 36- 18- 10- 8- 2- 3| 1| 4- 7| 9|


1:4 tiled with 1:2

Delle soluzioni possono essere ottenute affiancando una soluzione di [1:2 con 1:2] (vedi sopra) con un rettangolo 1:2 della stessa taglia, come in
18x72 = (9) 18- 10- 8- 2- 3| 1| 4- 7| 9|

La soluzione piu' piccola non di questo tipo e':
 35x140 = (14) 20- 15- 4- 11- 2| 12| 19- 16- 8| 18- 1- 17- 7- 14|




1:5 tiled with 1:2

Delle soluzioni possono essere ottenute mettendo insieme un rettangolo [1:3 con 1:2] (vedi sopra) con un rettangolo 1:2, come in
36x180 = (15) 36- 20- 16- 8| 14- 12- 10- 2- 4| 11| 7| 6- 15| 3| 18|

Non ci sono altre soluzioni (primitive) per R fino a 41x205.


2:3 tiled with 1:2

18x27 = (7) 10- 8- 2- 3| 1| 4- 7|


 

34x51 = (11) 13- 10- 11- 3- 7- 6- 5- 8| 1- 2| 17|



3:4 tiled with 1:2

36x48 = (8) 19- 17- 2- 3- 6| 10| 1- 8|    and  36x48 = (8) 15- 11- 10- 1- 2| 5- 8| 18|



2:5 tiled with 1:2    (trivial!)


3:5 tiled with 1:2

48x80 = (11) 28- 20- 9- 11- 12- 3- 6| 1- 2- 4| 18|
48x80 = (12) 26- 22- 11| 14- 6- 3| 4- 12| 1| 2- 8- 13|
48x80 = (12) 26- 22- 11| 13| 7| 8- 3| 4| 15| 1| 5| 9|
48x80 = (12) 21- 12- 15- 9- 3- 5- 13- 1- 2| 7- 14| 24|


 



4:5 tiled with 1:2

32x40 = (10) 12- 4- 8| 11- 9- 6| 2- 7- 5- 10|



1:3 Tiles



1:1 tiled with 1:3

  La seguente soluzione e' ottenuta componendo un rettangolo [1:3] con una soluzione di [2:3 con 1:3] (sotto). Non so se questa soluzione e' anche minimale.

96x96 = (12) 32- 27- 18- 19- 9- 8- 1- 7- 13- 3| 6- 15|



1:2 tiled with 1:3

72x144 = (16) 30- 14| 25- 17- 8- 9- 11| 10| 3| 2- 7- 20| 1| 5- 4| 24|



1:3 tiled with 1:3

 57x171 = (16) 30- 27- 9| 18- 12- 10- 17- 3- 7- 6- 5- 1- 4- 11| 8| 19|


 

64x192 = (11) 37- 27- 13- 14- 10- 9| 7- 24- 3| 23- 17-

Altre soluzioni:
59x177 = (18) 20- 13| 15- 24- 2| 9- 26- 11| 14- 19- 4- 12| 10| 1- 3| 7| 8- 17|
63x189 = (14) 38- 25- 11- 14- 8- 3- 18- 2- 6| 17- 16- 4- 12- 21|
68x204 = (13) 39- 29- 12- 17- 19- 2- 6| 27- 5- 22- 10- 9- 3|
69x207 = (16) 44- 25- 11- 14- 8- 3- 5- 12- 19| 13| 6| 4| 7| 9- 20| 23|


2:3 tiled with 1:3

  64x96 = (11) 27- 18- 19- 9- 8- 1- 7- 13- 3| 6- 15|



3:5 tiled with 1:3

  63x105 = (13) 23- 4- 12| 19- 11- 10- 1- 3| 8- 13- 5- 15| 21|




1:4 Tiles



1:4 tiled with 1:4

40x160 = (12) 23- 17- 7- 10- 16- 6- 1- 5- 3- 13- 11- 4|




1:5 Tiles



1:5 tiled with 1:5

48x240 = (11) 28- 20- 8- 12- 19- 13- 4- 16- 6- 7- 5|





2:3 Tiles



1:1 tiled with 2:3

120x120 = (10) 28- 13- 19- 4- 6| 11- 2- 21- 12- 18|



2:3 tiled with 2:3

130x195 = (16) 29- 14- 13- 9- 6| 1- 21- 15- 26| 5- 8- 12| 3- 23- 2| 28|


 



4:5 tiled with 2:3

96x120 = (11) 28- 20- 8- 5- 7- 3- 2- 9- 12- 18| 6|



3:4 Tiles



3:4 tiled with 3:4

168x224 = (12) 29- 27- 13- 14- 18- 11- 7- 16- 1- 15- 9- 12|