Newsgroup: it.hobby.enigmi
Titolo: griglia da ricoprire

Si vuole ricoprire una classica griglia n*m rettangolare
        n
 _ _ _ _      _
|_|_|_|_ .... _|
|_|_|_|_ .... _|
| | | |        | m
 .............
|_|_|_|_ .... _|
|_|_|_|_ .... _|
con pezzi a forma di L del tipo:
|_
in modo che sia tutta ricoperta e due lati delle L non si sovrappongono. Per
quali griglie č possibile?
Un saluto,
GaS


Spero di aver capito bene...
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
Dal momento che il pezzo a forma di L copre un segmento orizzontale e uno
verticale, sarà possibile coprire le griglie che hanno un ugual numero di
segmenti orizzontali e verticali, quindi solo le griglie quadrate.
Ciao :-)
Giorgio

"Giorgio Vecchi" risponde:

Ciao Giorgio,
hai capito bene, devi però dimostrare quali griglie quadrate possono essere
coperte.
Il problema vero che volevo proporre è piu difficile, ho pensato di
cominciare con questo per rompere le acque.
Ciao,
GaS
A presto

 ha scritto:

Tutte le griglie quadrate sono ricopribili perche'
si puo' usare almeno un algoritmo di "accrescimento"
partendo dal primo quadrato. Questo:
 _  _
|  |
     _|
 _
|_|  _|
Ciao!!!  ((^__^))'
Livio

 |_|  _|
Perfetto come al solito!
La vera domanda che volevo proporre, in un primo momento, č: quale griglie
possano essere ricoperte con pezzi del tipo
|_ _    ?
Si accetta di ricoprire la griglia anche intersecando due lati, l'importante
č che non si sovrappongano; per esempio č accettata la copertura della
griglia 2x2 che si ottiene mettendo insieme
 _ _
| |     e   _ _|
| |         _ _|
Che ne dite?
GaS


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Ognuno di quei pezzi č composto da 3 segmentini, quindi le griglie dovranno
essere formate da un numero di segmentini divisibile per 3.
Una griglia n*m č formata da n + m + 2*n*m segmentini. Analizzando un po' si
scopre che le griglie il cui numero di segmentini sia divisibile per 3 sono
tutte del tipo:
n = 2 + j*3, m = 2 + k*3
oppure
n = 3 + j*3, m = 3 + k*3
con j e k naturali incluso lo 0.
Ora si tratta di verificare se tutte queste griglie siano effettivamente
ricopribili con i pezzi in questione. Rimango perciň in attesa
dell'intervento di Livio con una opportuna dimostrazione! :-))))))
Ciao :-)
Giorgio

 con j e k naturali incluso lo 0.
Naturalmente esatto, io l'ho dimostrato cosi:
siano (3*j+a)  e  (3*k+b)   le lunghezze dei due lati con "a" e "b" compresi
tra 0 e 2, come gia scritto da Giorgio il numero totale di -  č
 2*(3*j+a)*(3*k+b)+(3*k+b)+(3*j+a)
svolgendo i calcoli si vede che  2*a*b+a+b  debba essere divisibile per 3 e
questo si ottiene esclusivamente per a=b=0  oppure a=b=2.
Io non sono riuscito a diumostrare che questa sia una condizione sufficiente
(oltre che necessaria) per ricoprire la griglia.
Ho le soluzioni per i valori piccoli (2x2,3x3,5x5,6x6) e ho una soluzione
costruttiva per griglie con i lati multipli di 6. Per ora non ho di piů,
qualcuno ha fatto qualche altro passo avanti?
Buona domenica,
GaS

 ho di più, qualcuno ha fatto qualche altro passo avanti?
Ho trasformato il tuo L in un polimino fatto cosi':
   _ _   _ _
 _|_|_| |_|_|
|_|
|_|
e ho costruito una griglia 2x5 cosi':
   _ _   _ _   _ _   _ _   _ _
 _|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_
|_|   |_|   |_|   |_|   |_|   |_|
|_|_ _|_|_ _|_|_ _|_|_ _|_|_ _|_|
 _|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_
|_|   |_|   |_|   |_|   |_|   |_|
|_|_ _|_|_ _|_|_ _|_|_ _|_|_ _|_|
  |_|_| |_|_| |_|_| |_|_| |_|_|
Con il solito Gerard's Polyomino Solution Engine
(with a little help from Livio Zucca) ho "dimostrato"
che non c'e' soluzione, quindi le vostre condizioni
sono necessarie ma non sufficienti.
Dico questo con spirito di gruppo  :o))
Non ho ancora pensato oltre, ma forse si puo'
individuare una qualche forma di "parita' ".
Ci pensero' ancora.
Ciao!!!  ((^__^))'
Livio
PS: Per vedere l'ascii-art usare caratteri fissi.
Con OE:  Visualizza... Carattere... Fisso.

Intanto ho trovato la sol per la griglia 2x8:
 CC DD DD II II MM OO OO
A  C  E  D  F  I  M  P  O
A  C  E  D  F  I  M  P  O
 AA AA FF FF LL LL QQ QQ
B  C  E  H  L  N  M  P  Q
B  C  E  H  L  N  M  P  Q
 BB BB EE HH HH NN NN PP
Purtroppo il Gerard's solver mi dice se c'e' o no una
soluzione, ma non mi dice quale. D'altra parte non ho
mai avuto la pazienza di caricare un altro solver  :(
Se avete un solver che colora pezzi uguali con colori
diversi, farete prima.
Ciao!!!  ((^__^))'
Livio

 soluzione, ma non mi dice quale...
Arrintanto il Gerard's Solver mi dice che c'e' una soluzione
per la griglia 3x9. Una sola!
La congettura sorge spontanea: solo griglie con lati entrambi
pari o entrambi dispari?
Ciao!!!  ((^__^))'
Livio

 pari o entrambi dispari?
Me la boccio da me. La griglia 3x6 ha soluzione. (Una!)
Ciao!!!  ((^__^))'
Livio

 Me la boccio da me. La griglia 3x6 ha soluzione. (Una!)
Strano, il solver di Cutler me ne ha trovate 9 in 0.1 secondi. (escluse R&R)
   GG GG KK KK OO OO
  D  B  G  I  K  L  O
  D  B  G  I  K  L  O
   DD DD FF LL LL NN
  A  B  F  I  H  N  M
  A  B  F  I  H  N  M
   BB EE EE II MM MM
  A  C  F  E  H  N  J
  A  C  F  E  H  N  J
   AA CC CC HH JJ JJ
   DD DD KK KK OO OO
  D  B  E  I  K  L  O
  D  B  E  I  K  L  O
   EE EE GG LL LL NN
  A  B  G  I  H  N  M
  A  B  G  I  H  N  M
   BB FF FF II MM MM
  A  C  G  F  H  N  J
  A  C  G  F  H  N  J
   AA CC CC HH JJ JJ
   GG GG KK KK OO OO
  E  B  G  I  K  L  O
  E  B  G  I  K  L  O
   EE EE FF LL LL NN
  A  B  F  I  H  N  M
  A  B  F  I  H  N  M
   BB CC CC II MM MM
  A  C  F  D  H  N  J
  A  C  F  D  H  N  J
   AA DD DD HH JJ JJ
   EE EE KK KK OO OO
  E  B  F  I  K  L  O
  E  B  F  I  K  L  O
   FF FF GG LL LL NN
  A  B  G  I  H  N  M
  A  B  G  I  H  N  M
   BB CC CC II MM MM
  A  C  G  D  H  N  J
  A  C  G  D  H  N  J
   AA DD DD HH JJ JJ
   EE HH HH MM MM OO
  D  E  I  H  N  M  O
  D  E  I  H  N  M  O
   DD DD II II NN NN
  A  E  F  G  J  L  O
  A  E  F  G  J  L  O
   BB BB FF FF KK KK
  A  C  B  G  J  L  K
  A  C  B  G  J  L  K
   AA CC CC GG JJ LL
   EE FF JJ NN NN OO
  D  E  F  J  I  N  O
  D  E  F  J  I  N  O
   DD DD II II KK KK
  A  E  F  J  K  M  O
  A  E  F  J  K  M  O
   BB BB GG GG LL LL
  A  C  B  H  G  M  L
  A  C  B  H  G  M  L
   AA CC CC HH HH MM
   EE EE KK KK OO OO
  E  F  G  I  K  L  O
  E  F  G  I  K  L  O
   CC FF FF LL LL NN
  A  C  G  I  H  N  M
  A  C  G  I  H  N  M
   BB BB GG II MM MM
  A  C  B  D  H  N  J
  A  C  B  D  H  N  J
   AA DD DD HH JJ JJ
   FF FF KK KK OO OO
  B  G  F  I  K  L  O
  B  G  F  I  K  L  O
   CC GG GG LL LL NN
  B  C  E  I  H  N  M
  B  C  E  I  H  N  M
   BB DD DD II MM MM
  A  C  E  D  H  N  J
  A  C  E  D  H  N  J
   AA AA EE HH JJ JJ
   EE II II LL OO OO
  B  E  D  I  L  N  O
  B  E  D  I  L  N  O
   DD DD FF HH MM MM
  B  E  F  H  L  N  M
  B  E  F  H  L  N  M
   BB CC CC JJ JJ NN
  A  C  F  H  G  J  K
  A  C  F  H  G  J  K
   AA AA GG GG KK KK


E' vero. Stava giusto venendomi il dubbio. Infatti nella soluzione
ci sono sottogruppi di tipo:
 AA AA
B  x  A
B  x  A
 BB BB
che sono chiaramente rovesciabili lasciando inalterato tutto
il resto. C'e' qualche problema che mi sfugge sulla unicita'.
Per il resto dovrebbe essere corretto. Spero che anche a te
risulti impossibile la griglia 2x5 sulla cui impossibilita' non
ho per ora trovato un criterio "tipo parita' " che me lo dimostri.
Questione di nodi?
Ciao!!!  ((^__^))'
Livio

 risulti impossibile la griglia 2x5 
Confermo.
La 3x9 invece, ha 57 soluzioni.

 ...
Questa e' bella:
2x2     SI  ha soluzione
2x5     NO
2x8     SI
2x11   NO
2x14   ???
.
.
.
.
spoilerino
.
.
.
.
.
.
.
.
.
NO!
Tra l'altro, 5x8 SI
Ciao!!! ((^__^))'
Livio

Lo sapevo, non si possono lasciare Livio e Dario da soli per un pomeriggio
che subito viene tirata fuori la forza bruta :o)
A parte gli scherzi, complimenti, avevo pensato di trasformare il problema
in modo che fosse risolvibile da un solver ma non pensavo che potessero
lavorare su pezzi "doppi" (nel senso di pezzi composti da due parti
separate). A questo punto la questione è ancora aperta ma grazie a voi
sappiamo che la condizione riportata da Giorgio è necessaria ma non
sufficiente.
Grazie e buon lavoro :o)
GaS

 individuare una qualche forma di "parita' ".
Ho indagato un po' qualche problema di parità giungendo a conclusioni
opposte a quelle che speravo.
Andiamo a colorare la griglia con due colori A e B in modo che ogni pezzo
inserito sia bi-color (si può fare in diversi modi). Avremo Ta segmenti di
colore A, Tb di colore B, x pezzi del tipo A-A-B e Tb pezzi del tipo A-B-B.
Per ogni griglia e per ogni colorazione scelta bisogna soddisfare le
seguenti:
2x+y=Ta
x+2y=Tb
Affinchè la griglia sia ricopribile, x e y devono essere intere, se non lo
fossero avremmo un problema di parità.
Sostituendo si ottiene:
2(Tb-2y)+y=Ta che risolta diviene 3y=2*Tb-Ta che può essere riscritta come:
3y=3*Tb-(Ta+Tb)
Ma Ta+Tb corrisponde proprio al numero totale dei segmenti che abbiamo
precedentemente imposto multiplo di 3. Per questo motivo y è intero e così
anche x.
Si vede così che colorazioni di questo tipo (qualsiasi siano) non porteranno
mai a problemi di parità, non abbiamo condizioni più restrittive.
Altro, per ora, non so ...
GaS
--------------------------------
Inviato via 
http://usenet.libero.it

 Qual e' la piu' lunga copertura che riuscite a fare?
Con molta fratica sono arrivato a 2x8, una soluzione bella simmetrica.
Ma tu hai provato la 2x32 ?
GaS

 ha scritto:

Ormai sono convinto che soltanto la 2x2 e la 2x8 sono possibili
tra le 2xN. Per dimostrarlo, prova a riempire quella semistriscia
senza preoccuparti di terminarla correttamente, ma solamente di
continuare a coprirla. Ti accorgerai che dopo appena una decina
di colonne, nel migliore dei casi, non riuscirai ad andare avanti.
Con un po' di pazienza si puo' esaminare l'albero delle possibilita'.
Ad es. puoi incominciare solo in due modi, entrambi con una L
di angolo, o coricata o diritta. Seguono sempre alcuni passi
obligati, se non vuoi arrestarti subito.
Se non si riesce neppure a continuare a coprirla, a maggior
ragione non ci saranno soluzioni 2xN.
Ciao!!!  ((^__^))'
Livio

 perche' fa caldo.  :o))
Ora rinfresca un po':
Anche tutte le 3x3k con k=1,2,3,... sono fattibili.
Infatti si possono ricoprire le seguenti griglie:
 _ _ _ _ _ _
|_|_|_|_|_|
|_|_|_|_|
|_|_|_|
 _ _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|_|
      _ _ _ _ _ _
    _|_|_|_|_|_|
  _|_|_|_|_|_|
_|_|_|_|_|_|
con cui si possono formare dalla 3x9 in su'.
(Le 3x3 e 3x6 le abbiamo gia' dimostrate).
Abbiamo gia' verificato che sono ricopribili tutte le
6x3k e anche la 6x6 "aperta" su un lato.
Mi risulta fattibile anche questa 6x6 aperta su 2 lati:
|_|_|_|_|_|_
|_|_|_|_|_|_
|_|_|_|_|_|_
|_|_|_|_|_|_
|_|_|_|_|_|_
|_|_|_|_|_|_
Nonche' la 6x9 aperta sul lato maggiore:
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
Con questi mattoni e' possibile ora formare tutte
le griglie 3k x 3j con k,j=1,2,3,... che diventa
condizione sufficiente.
Ciao!!!  ((^__^))'
Livio

 Anche tutte le 3x3k con k=1,2,3,... sono fattibili....
Non resta che dimostrare la copertura di tutte
le (5+3k)x(5+3j) con k,j=0,1,2,3,...
(Avendo gia' detto sulle 2x(2+3k) ).
Usiamo le seguenti griglie-mattoni che abbiamo verificato
separatamente fattibili:
- 5x5
- 5x8
- 8x8
- 5x6 aperta lato 5
- 6x8 aperta lato 8
- 6x6 aperta da un lato
- 6x6 aperta da 2 lati contigui
Con questi sono realizzabili tutte le griglie (5+3k)x(5+3j)
Riassumendo: sono copribili tutte le griglie rettangolari:
- 3k x 3j con k,j=1,2,3,...
- (5+3k)x(5+3j) con k,j=0,1,2,3,...
- la 2x2 e la 2x8
E con questo ho finito!   :-Ohhhhhhh
Ciao!!!  ((^__^))'
Livio

Complimenti, hai fatto tutto da solo.
Grande Livio!!
GaS