Newsgroup: it.hobby.enigmi
Titolo: Domino perfetto [repost]

Il 7/12/2002 scrissi:
"
Un quadrato perfetto (o meglio: la dissezione perfetta di un
quadrato) si ha quando si riesce a scomporre un quadrato
in tanti quadrati tutti diversi fra loro e dai lati interi.
Il piu' piccolo ottenibile e' di ordine 21 e lo potete vedere ad es. qua:
http://mathworld.wolfram.com/p1img2255.gif
E' chiaro che se lo ridisegno allungato di un rapporto 2:1
ottengo un domino perfetto di ordine 21.
Pero' i domino hanno un altro grado di liberta': possono
essere ruotati di 90°. Con questa liberta', potro' trovare
una soluzione di ordine minore?
"
Mi sembra che la miglior soluzione (17) fu allora trovata da
Maurizio Frigeni, unendo tre rettangoli:
342x1235 formato da: 76, 152, 190, 171, 342;
438x1235 formato da: 8, 16, 40, 48, 44, 70, 140, 219, 438;
325x780  formato da: 65, 130, 325.
Il domino perfetto finale č di 780x1560.
Non e' che adesso che siete "caldi", in argomento, riuscite
ad abbassare il record o a trovare il minimo assoluto?
Ciao!!!  ((^__^))'
Livio

 Il domino perfetto finale è di 780x1560.
Miiii... (come dice Aldo)
mi ero spaventato (della dimensione di questi dominiiiii)
Se ho capito bene bisogna ricoprire un rettangolo K x (2K)
con dei rettangoli di A x (2A) (o (2A)x A) con il vincolo
che siano tutti diversi tra loro.
Ho trovato questi domini (mi sono fermato alla dimensione 52x104).
Il numero fra parentesi e' quello dei sottodominii.
18x36 = (8)
31x62 = (10)
33x66 = (11)
35x70 = (9)
36x72 = (8)
40x80 = (13)
42x84 = (12)
45x90 = (13)
48x96 = (13)
49x98 = (13)
50x100 = (14)
51x102 = (13)
Le decomposizioni vere e proprioe le metto dopo la sequente
spiegazione che funge da spoiler.
Cosi' se uno vuole cimentarsi a trovarle....
(Magari Livio puo' fare un disegnino ASCII-ART per quello piu'
piccolo... io non saprei come fare)
La regola per interpretare le
decomposizioni e' la stessa che avevo usato per i
quadrati. Pero' dopo ogni numero k, dove k indica un domino
k x (2k), metto un meno (-) per indicare che il domino
e' orizzontale o una barra (|) per indicare che e' verticale.
(Quello di partenza e' sempre orizzontale).
Mi sono accorto di una piccola "furbata"
che in prima battuta mi era sfuggita, nei programmi di ricopertura
con i quadrati, ma che si e' rivelata preziosa per i rettangoloni,
che sono piu' ostici.
Io usavo una griglia rettangolare le cui celle con
valore 0 o 1 mi dicono se il quadratino l'ho ricoperto
oppure no. Poi ad ogni passo ricorsivo andavo a cercare
un quadratino libero (il primo in alto a sinistra di una
regione potenzialmente piu' grande) e lo ricoprivo e
poi andavo avanti cosi' ricorsivamente. Tornando
indietro dalla chiamata ricorsiva dovevo ovviamente
ripulire la zona di griglia che avevo occupato.
Ora, usando quadrati (o rettangoli) di una certa dimensione
tutte queste operazioni di marcatura (di una regione)
e ripulitura e di ricerca della prima cella libera cominciavano
ad avere un certo costo.
Allora mi sono accorto (scemo a non pensarci prima!)
che mi bastava "marcare" la griglia solo in corrispondenza
della prima riga del quadrato o rettangolo inserito (quindi una
riga invece di tutto il quadrato). Invece di un 1 ci metto
il valore della riga subito sotto al quadrato inserito.
Poi alla procedura ricorsiva passo come punto da dove
iniziare la ricerca l'angolino in alto del mio quadrato.
Cosi' vede che e' occupato e salta in basso di quanto deve
saltare. Se e' libera la posizione sotto puo' procedere,
altrimenti trovera' un altro indice che lo fa saltare
piu' in basso. Se salta oltre il bordo sa che deve ricominciare
dalla riga 0. etc.etc. Spero che qualcuno sia riuscito a seguire
questo delirio...
Vabbe', con questa ottimizzazione (che tra l'altro accorcia il
codice...) il programma si velocizza di parecchio, soprattutto
per rettangoli grandini. Ecco le soluzioni che ho trovato,
fino al domino 51x102.
18x36 = (8) 10- 8- 2- 3| 1| 4- 7| 9|
31x62 = (10) 17- 14- 3- 11- 10| 4| 6| 7- 1- 12|
33x66 = (11) 17- 16- 8| 11- 6- 3- 13- 5- 4- 2| 10|
35x70 = (9) 19- 16- 8| 11- 4| 1- 15- 9- 10|
36x72 = (8) 20- 16- 4- 6| 2| 8- 14| 18|
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|
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|
49x98 = (13) 18- 15- 16- 3- 6| 8| 25- 4| 24- 12| 1- 5- 10|
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|
===============================================================
ciao,
g.

 50x100 = (14) 28- 22- 11| 9| 4- 12- 8| 2| 16| 1| 6- 3| 10- 20|
oops. Errore di copia e incolla ! Per il 50x100 c'e' anche questa
soluzione (minimale, con 12 domini invece di 14)
50x100 = (12) 24- 26- 16- 4| 17| 11| 1| 5| 2- 6| 20| 10-
Poi la 42x84 ha anche questa decomposizione minimale
alternativa.  (nel senso che sono proprio diversi i
sottodomini, non solo il modo in cui sono messi).
42x84 = (12) 22- 20- 10| 16- 6- 3- 17- 9- 5- 4- 8| 2|
idem per la 48x96:
48x96 = (13) 25- 23- 3- 7- 13- 11- 5- 4| 1- 2| 6| 12| 24|
la 60x120 ha (almeno) queste 6 decomposizioni con domini diversi:
------------------------------------------------------------------------
(11) 34- 26- 13| 10- 16- 17| 14- 6- 12| 23| 7|
(13) 32- 28- 7- 21- 12- 8- 6| 5- 14- 4- 9- 16- 22|
(13) 32- 28- 14| 12- 8- 9- 3- 6- 25- 4- 2| 19- 16-
(15) 32- 28- 8- 20- 16- 11- 5- 1- 7- 6- 4- 10| 2| 12- 24|
(15) 32- 28- 8- 10| 14| 4- 5- 15- 6| 1- 2| 9- 18| 12- 24|
(16) 31- 29- 11- 18- 22- 9- 10| 8- 6| 1- 2| 13- 5- 12- 7- 14|
(18) 26- 16- 18- 8| 2- 6- 10- 9| 1| 4- 3| 7| 19- 13- 11- 17- 12| 30|
------------------------------------------------------------------------
ciao,
g.

 ...
Miiiiiiiiiiiiiii...  non ci posso credereeeeee.........  :o)
Per 3 anni mi sono tenuto dentro l'intuizione che si potesse
fare un domino perfetto ben piu' piccolo di un quadrato
perfetto (21 pezzi). Un anno fa 39 interventi (vedi google:
Dario Uri, Silvio Sergio, Gas, Massimo M, Maurizio Frigeni)
hanno portato alla pur bella soluzione di Maurizio (17 pezzi)
Ora tu in poche ore mi polverizzi il record addirittura con
un domino da 8 semplici pezzi. Non ci posso credere...
Non ho parole. E ne trovi anche tanti altri! Mi studiero' con
calma il tuo metodo. (Non e' che il quadrato da 21 e' battibile?
Non credo, neh... pero'... non si sa mai  :o))
Intanto almeno lo disegno con fido*cad (8 righe!)
E scrivo questo certificato perche' nel frattempo avevo lanciato
il problema agli anglofoni:
****************************************************
* Certifichiamo, ad imperitura memoria di google, che in
* Ottobre il giorno 13 del 2003 alle ore 10:30 del fuso di Roma
* Giovanni Resta ha scoperto il Domino Perfetto da 8 pezzi
* e lo ha reso pubblico su it.hobby.enigmi
****************************************************
Complimentoni!!!!!!!!!  ((^__^))'
Livio
[FIDOCAD ]
RV 10 10 110 60
RV 10 60 90 100
RV 90 60 110 70
RV 90 70 105 100
RV 105 70 110 80
RV 105 80 145 100
RV 110 10 145 80
RV 145 10 190 100

these results were obtained by charles jepsen; see his papers:
My understanding of a 'perfect' integer domino dissection is that no two
dominos are the same size. A 'simple perfect' dissection would have no
'sub-rectangles' such as mine does here.
How then does this one fail?
Size 18*36, Order 8, tiled with sizes 1,2,3,4,7,8,9,10. This is the smallest
such (by area). I'll post some more bigger ones. I see no reason there can't
be one of larger area and lower order.
--
Patrick Hamlyn
Perth, Western Australia
Multiprogramming P/L
Yahoo! Groups Sponsor
Ora bisogna capire come sono assegnati i fusi orari da yahoo,
dove passa la linea del cambiamento di data, ecc...
Coraggio!!!  :o(((
Livio

 
Scusa se sono tardo a capire!
Non ho capito il senso di tutto questo messaggio da te riportato.
Vuoi forse dire che qualcuno aveva trovato questa dissezione
prima, mentre tu pensavi che non fosse nota ?
Sinceramente lo davo quasi per scontato, visto che ne sono
state trovate di molto piu' "difficili".
Pensavo che da qualche parte la 18x36 ci
fosse, solo che ero curioso e come hai detto anche
tu e' stato il lavoro di una mezzora per modificare il
programma del ricoprimento con i quadrati.
Quindi non sono particolarmente affranto.
Comunque se hai altri problemi simili (ricoprimenti di
zone rettangolari con pezzi rettangolari, con vincoli vari)
dimmi pure. (anche se ora il mio tempo sta andando a cercare
di finire una buona volta la versione 2 di verbatron, che
si sta discostando molto dalla versione 2beta).
Non so, per esempio trovare i piu' piccoli quadrato che si
puo' tassellare con domini rettangolari diversi tra loro....
Vedi dopo lo spoiler...
.
.
.
.
.
.
.
.
.
.
.
.
34x34 = (10) 13- 10- 11- 3- 7- 6- 5- 8| 1- 2|
36x36 = (9) 18- 10- 8- 2- 3| 1| 4- 7| 9|
48x48 = (10) 20- 17- 11- 6- 5- 1- 2| 14| 4- 8|
ciao,
g.

 ...
A guardarla bene la cosa e' abbastanza interessante e non sono
piu' affranto.  :o))
Intanto Patrick M Hamlyn ha trovato autonomamente la stessa
tua soluzione piu' o meno nello stesso momento in Australia,
agli antipodi dell'Italia. Guardando la soluzione, ore appare
"non difficile", come tu modestamente dici, ma e' il solito
uovo di Colombo. Un anno fa evidentemente non era apparsa
cosi' facile. Il tuo approccio e' stato diverso da quello tentato
allora da tutti noi.
Lo stesso [polyforms] di yahoo era stato da me tentato e
nessuno allora aveva trovato soluzioni o scovato lavori gia'
fatti. Neppure Dario Uri (ci leggi?) aveva scovato la dissezione!
Ora Mike Reid, in risposta a Patrick tira fuori dal suo archivio
un pezzo tedesco. Pare che 8 sia proprio il minimo ordine
possibile, mentre Patrick diceva che non vedeva alcuna ragione
perche' non potesse essercene uno di maggior area e di
ordine inferiore. Io ero arrivato alla conclusione che, se uno
di ordine 7 dovesse esserci, avrebbe dovuto collocarsi nel
range 50..300. Ma vediamo cosa dice Mike:
"
it doesn't fail.  i should have written "simple perfect dissection" above.
i didn't have the jepsen paper handy when i wrote that, but now i do.
he indeed gives the order 8 perfect dissection patrick found (though
it seems to have been found by mu"ller even earlier than that).
to summarize (hopefully without any errors this time!):
the smallest order of a perfect domino dissection is 8.  i infer from
jepsen's paper that there is a unique such tiling, but i don't see
that he says that explicitly.  perhaps it is mentioned in the mu"ller
paper referenced below.
the smallest order of a *simple* perfect domino dissection is 10,
apparently only the two i previously referred to.
there are also perfect dissections of orders 9, 11, 12, and mu"ller
showed there are such dissections for all orders  >= 13.  see the paper
     carsten mu"ller, perfekte rechteckzerlegung, elemente der
     mathematik 45 (1990), no. 4, pp. 98-106.
(i don't have a copy of this paper, so i don't know its exact contents.)
mike
"
Che si dica "perfekte rechteckzerlegung" in tedesco?  :o))
Ciao!!!  ((^__^))'
Livio

 36x36 = (9) 18- 10- 8- 2- 3| 1| 4- 7| 9|
Come avrai notato, basta aggiungere un domino alle
soluzioni precedenti per avere un quadrato...  :o)
A meno di non trovare una soluzione quadrata da 8 o -
Trimino di trimini?
Forse ti basta cambiare un coefficiente...
Ciao!!!  ((^__^))'
Livio

 Forse ti basta cambiare un coefficiente...
in effetti avevo gia' lanciato il programma per i trimini
senza trovare nulla (trimini distinti) per lati non
troppo grandi.
Magari lo lascio girare questo weekend e se salta fuori qualcosa
lo dico lunedi....
comunque da alcune prove fatte cosi' di corsa mi sembra
proprio che i trimini siano parecchio bastardi (scusate il tecnicismo).
ciao,
g.

 proprio che i trimini siano parecchio bastardi (scusate il tecnicismo).
Beh, una soluzione di ordine 21 esiste di sicuro...  :o)))
Ciao!!!  ((^__^))'
Livio

 Beh, una soluzione di ordine 21 esiste di sicuro...  :o)))
Grazie, non ci avevo pensato.
Questo mi fa capire
1)che sono un pirla e
2)che  ho sbagliato qualcosa nel programma...
ero gia' arrivato a quello 50x150 senza trovare nulla...
ciao, (vado a debuggare)
g.


Rettifioco: son doppiamente pirla...
non avevo capito che quando tu dicevi ordine intendevi
il numero dei sotto-domini, mentre io intendevo il
lato minore... il lato minore di quello che dici
tu (derivato dal quadrato) e' lungo 50+29+33= 112 che
e' ancora molto in la' rispetto a dove sono
arrivato io con la ricerca esaustiva.
ciao, (sono proprio un po' esaurito)
g.

Patrick Hamlyn (Australia) ha scovato un domino perfetto
di ordine 7 su striscia di Moebius- (4|, 1-, 2|, 7-, 6|, 9-, 3-) e uno
di ordine 5 (!) su piano proiettivo, di cui tento l'ascii-art qua sotto.
                 _ _ _
|       8       |
|               |
|               |
|               |
|               |
|_ _ _ _ _ _ _ _|    6
|               |
|       4       |
|               |
|_ _ _ _ _ _ _ _|
      |1|       |
      |_|_ _2_ _|_ _ _
      |               |
      |               |
      |               |
6     |               |
      |               |
      |               |
      |               |
      |               |
      |               |
 _ _ _|       8       |
[per vedere l'ascii-art usare caratteri fissi]
Ciao!!!  ((^__^))'
Livio

 di ordine 5 (!) su piano proiettivo, di cui tento l'ascii-art qua sotto.
Sinceramente mi sfugge cosa sia un piano proiettivo ma penso di capire che
sia una figura impossibile tipo "doppio Moebius", cioè attuando lo stesso
movimento del nastro di Moebius ma su entrambe le coppie di lati paralleli ,
Carroll lo chiamava "Borsellino di Fortunatus"; è cosi?
Ammetendo rapporti irrazionali non è difficile trovare una ricopertura di
ordine 2 su un nastro di Moebius (e quindi anche su un piano proiettivo, se
è quello che intendo io), chi la trova?
Gabriele
P.S.: In realtà pensavo di sapere cosa fosse un piano proiettivo ma nella
mia mente era qualcosa di infinito con dei punti "aggiuntivi" all'infinito
dove convergono delle rette parallele (si lo so, è una spiegazione orrenda).

 dove convergono delle rette parallele (si lo so, è una spiegazione
orrenda).
eh, in matematichese è molto meno suggestivo!
ciao!

 se č quello che intendo io), chi la trova?
|
|
|
|
|
|
|
|
|
spoiler
|
|
|
|
|
|
|
|
|
|
[caratteri fissi]
_ _ _ _
 |   x/2
 |
B|1   A
_|_ _ _
     |
     |B
A    |1
_ _ _|_
x/2   1/(2x)
x=sqr(3)
A = 1*x
B = 1*(1/x)
Moebius = 2*(x/2+1/(2x))
Ciao!!!  ((^__^))'
Livio

 Moebius = 2*(x/2+1/(2x))
Perfetto, è anche la prima soluzione che ho trovato, mi sono però poi
accorto che ne esiste anche un'altra distinta.
  _ _ _ _ _
           |
          2|
           |
  _ _ _ _ _| 5
|         1|
| _ _ _ _ _|
|   sqrt[5]
|2
|
| _ _ _ _ _
   sqrt[5]
Quando ho trovato questa seconda soluzione mi sono venuti dei dubbi sulla
validità di entrambe, non sono sicuro che una striscia con rapporto
2:2sqrt[3] possa essere unita in una striscia di Moebius sul lato lungo. La
seconda soluzione che ho trovato è ancora più oblunga: qualcuno mi sa dire
se esiste un rapporto minimo per cui è possibile richiudere una striscia
come ci ha insegnato il buon Moebius?
GaS

 eh, in matematichese è molto meno suggestivo!
E com'è?
GaS

 buon Moebius?
Se poi proprio insisti, prendiamo forbici e scoch, e proviamo
a farne una. Dopo qualche tentativo mi sono convinto (imho)
che la piu' corta striscia di Moebius fisicamente realizzabile e'
quadrata. Infatti prendi un quadrato di carta e piegalo in quattro
seguendo le diagonali. Ora potrai prendere due lati non
consecutivi ed unirli tra di loro con continuita' delle due
superficie del quadrato.
Pero'... pero'... quando parliamo di striscia di Moebius, gia'
accettiamo l'idea che la superficie non sia piana, ma curva e
non mettiamo nessun limite alla curvabilita' della superficie.
Quindi "crespando" a piacere la carta, raggiungiamo il
rapporto di *bislunghita'* che ci pare!
Il tutto sempre imho.
Ciao!!!  ((^__^))'
Livio

 per un nastro di Moebius è valida anche per il piano proiettivo, o no?
uhm, penso di si; allo stesso modo la soluzione vale anche per la bottiglia
di Klein
in matematichese lo spazio proiettivo di dimensione n è l'unione di tutti i
sottospazi di dimensione 1 di uno spazio affine di dimensione n-1. o n+1.
ora non ricordo bene. cmq alla fin fine, vuol dire che lo spazio proiettivo
è fatto di punti e ogni punto rappresenta una retta nello spazio affine
incluso. ma non fatemi scendere troppo nei dettagli!
ps: spero, anzi, di non aver detto castronerie!
ciao

 rapporto di *bislunghita'* che ci pare!
In pratica 'plissettiamo' (come il tessuto di certe gonne) la
striscia oblunga in un numero dispari di parti (numero pari
di pieghe, e' importante), cosi':
 ________
|________|
|________|
|________|
|________|
|________|
|________|
|________|
|________|
|________|
|________|
|________|
e con questa facciamo la striscia di Moebius giuntandola
di testa. Nessuno potra' dire che questa non e',
matematicamente parlando, una monosuperficie.
Ciao!!!  ((^__^))'
Livio

 matematicamente parlando, una monosuperficie.
Grande come al solito Livio, hai perfettamente ragione. Ad occhio pensavo
che non si potesse fare con ogni rettangolo.
Gabriele