Newsgroup: it.hobby.enigmi
Titolo: [MA]Erich puzzle

Ed Pegg Jr ha sbattuto in prima pagina il problema
della dissezione dell'esagono brillantemente risolto
qua da Paolo Licheri. 
http://www.mathpuzzle.com/
Mentre vi prego di non mandare soluzioni Italiane  :o)
poiche' Ed sa che il problema e' stato qua dibattuto,
volevo attirare la vs. attenzione sul problema a fianco
di Erich Friedman, combinazione proprio quello del 
packing di cui parlavamo poco fa.
Lo traduco qua per gli anglofobi e i pigri:    :o]
* * *   * * *
* * * *   * *
* * * * * * *
* * * * * * *
  *   *   * *
* * * * * * *
* * * * * * *
Questi sono i vertici di undici quadrati che non hanno
nessun vertice in comune (tratti di lato, magari si').
Erich dice che la soluzione e' unica. Erich e' fissato
con le soluzioni uniche, se lo dice lui, gli crediamo.
Pero' mi sembra impegnativo. Io la soluzione non ce l'ho.
Chi ce l'ha, la mandi anche ad Ed, che fa la sua bella 
figura!
Ciao a tutti    :o)
Livio Zucca
-------------------------
It isn't trivial!
http://www.geocities.com/liviozuc
P.S.
Per vedere bene l'ascii-art usate caratteri fissi.
Al limite:VISUALIZZA SORGENTE HTML
Se l'hai visto con CiaoWeb, non hai visto niente!
-- 
Posted from 
twingo.tiscalinet.it
 [195.130.224.85] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 Erich dice che la soluzione e' unica.
Una prima considerazione: i quadrati non sono tutti orientati nello stesso
modo, devono esistere almeno un quadrato *dritto*, con i lati paralleli a
quelli dello schema, ed almeno un quadrato con i lati inclinati rispetto a
quella direzione.
Infatti i punti ai vertici dello schema possono appartenere solo a quadrati
dritti.
D'altra parte, se gli 11 quadrati fossero tutti dritti, ci dovrebbero essere
22 lati orizzontali, ripartiti su 7 righe, perciò almeno una riga dovrebbe
contenere almeno 4 lati, e quindi 8 vertici distinti, mentre al massimo
contiene 7 punti.
Per il resto non saprei da dove iniziare; la forza bruta mi pare
inapplicabile.
O no?
ciao
paolo

 O no?
Io la sto provando, ed in una nottata di tentativi ancora non ha mai
cambiato la sua prima scelta, ma ha quasi finito le seconde scelte. Quindi
con un quadrato in meno si fa senza problemi. Azzeccassi il primo, sarei a
cavallo. Credo che stasera, se tornando non troverň la soluzione, proverň un
diverso ordine: prima i quattro quadrati che contengono i vertici esterni
(non credo ci sia il quadratone 7X7), poi gli altri.
Servirebbe qualche trucco per "potare" qualche ramo secco, tipo
considerazioni sul baricentro dei punti rimasti (l'ho buttata lě adesso, non
so se abbia qualche senso). Qualche suggerimento?
Silv:o)

 so se abbia qualche senso). Qualche suggerimento?
Qualche piccolissima potatura si potrebbe fare considerando i buchi nello
schema.
Per esempio il punto A1 (notazione scacchistica) non può essere vertice di
un quadrato 2*2, e così via.
Ma mi sembra ancora troppo poco.
Forse (la butto lì anch'io, non ho approfondito) si potrebbero cercare
regole sulla distribuzione delle lunghezze dei lati (tot quadrati 1*1, tot
2*2 ecc.) o sulle pendenze (tot dritti, tot 1/2, tot 2/3 ecc.).
Penso che stavolta l'RCP non serva, ma...
mai dire mai ;-)
ciao
paolo

Non ci posso credere!
6439 tentativi solamente.
1 2 1 . 3 4 2
5 6 3 4 . 5 6
1 7 1 7 8 3 4
9 8 9 3 4 B B
. 7 . 7 . B B
9 2 9 A A 8 2
5 6 8 A A 5 6
Poi vi spiego.
Livio



.
Dunque erano le 16:00. Un cliente mi da il 2
di picche in ufficio dove ho un Pentium 733.
Leggo le risposte di Paolo e Silvio. Mi convinco
che le permutazioni sono tante e difficili da
organizzare. Tento senza convinzione una 
Random Machine. Dall'alto a sinistra a scendere
sceglie un quadrato a caso. Se non ci sta,
riprova. Gli permetto 100 tentativi per ogni X,Y.
Vado a prendere un caffe'. Quando torno non
ha superato i 9 quadrati. Noto buchi sulla
prima fila. Aumento i tentativi, diventa lentissima.
Modifico l'algoritmo: se non trovi
il quadrato in 50 tentativi random, prova in
modo sistematico.
17:27 Risultato: quello che vedete.
Provare per credere! Random + Metodo.
O e' stata una gran botta di... destino?
Tra parentesi, la soluzione e' stata trovata con 
un bug, eliminato il quale, la Machine trova la
soluzione in 100..800 tentativi in 1..5 secondi!
Ciao  :o)


 > 5 6 8 A A 5 6
Uff, arrivo sempre secondo!
Il mio primo approccio aveva una complessità paurosa (oltre a qualche chilo
di bug) perché, piazzato un quadrato, ricominciavo dall'angolo in basso a
sinistra, con complicazioni pazzesche. Ho riscritto il tutto in maniera
molto più semplice e, tadha! in meno di un secondo con un PII 233 spara
fuori la soluzione.
Adesso possiamo anche confermare l'unicità della soluzione.
B 6 B . 9 A 6
1 2 9 A . 1 2
B 7 B 7 3 9 A
5 3 5 9 A 8 8
. 7 . 7 . 8 8
5 6 5 4 4 3 6
1 2 3 4 4 1 2
Ciao, Silv:o)

 fuori la soluzione.
Col senno del poi possiamo dire che la ricerca 
sistematica era la strategia migliore, che le potature
dei rami secchi sono 'automatiche' se esaminiamo man
mano solo i 'possibili' quadrati. Le combinazioni
diventano sorprendentemente pochine, tali da poter
essere esplorate tutte in pochi secondi da un PC.
Ad ogni ciclo i quadrati da esaminare sono cmq
non piu' di undici.  :o)
Insomma, ci sono problemi che sembrano facili ed
invece sono insidiosi, altri viceversa.
Questo: viceversa. 
L'importante era non farsi prendere dal panico.
Buona notte.  :o)
Livio
-- 
Posted from 
mta15-acc.tin.it
 [212.216.176.46] 


Ariscusate!!
Non sono matematici, sono TOPOLOGICI
Ciao
Gianni