Difference between revisions of "Golygons"

Revision as of 11:47, 23 September 2010

per semplificare la questione ed evitare simmetrie, rotazioni e rotture di cazzo il primo lato di lunghezza 1 sarà orientato orizzontalmente verso dx

dato un generico goligono di N lati:
- la sommatoria dei lati dispari sarà N²/4
- la sommatoria dei lati pari sarà N²/4 + N/2

affinché il goligono sia chiuso:
- i lati dispari che vanno a dx devono avere sommatoria uguale a quelli che vanno a sinistra, pari a N²/8
- i lati pari che vanno in alto devono avere sommatoria uguale a quelli che vanno in basso, pari a N²/8 + N/4

Dimostrazione che i goligoni devono necessariamente avere numero di lati multiplo di 8 - i lati pari che vanno in alto devono avere sommatoria uguale a quelli che vanno in basso, pari a N^2/8 + N/4</blockquote>ipotizziamo per assurdo che N sia multiplo di 4 ma non di 8, allora può essere scritto nella forma N = 4A dove A è un intero dispari.
allora la sommatoria verso l'alto (o basso) dei lati pari sarà N^2/8 + N/4 = 2A^2 + A

ma se A è dispari ==> 2A^2 + A è dispari ==> impossibile perché una sommatoria di numeri pari deve essere per forza pari ==> A deve essere pari ==> N deve essere divisibile per 8

Alcune considerazioni aggiuntive (che vengono dalla lettura di un articolo congiunto di L. Sallows, M. Gardner, R. Guy e D. Knuth del 1991, Serial Isogons of 90 degrees):

-Supponiamo, senza perdita di generalita', di cominciare con uno spostamento orizzontale in direzione positiva: affinche' il goligono si chiuda, e' necessario che gli spostamenti orizzontali sommino a zero. E' pero' anche necessario che gli spostamenti ,i>verticali sommino a zero, perche' altrimenti il cammino compiuto non ritornera' mai alla linea del reticolo che passa per l'origine.

- Esiste un modo di mostrare geometricamente che per chiudere un goligono si necessitano di 4n lati, con n eventualmente dispari: se supponiamo di colorare a scacchiera il piano, e senza perdita di generalita' di partire da una casella nera, saremo obbligati (per motivi di parita') a seguire il pattern (se B=casella bianca, N=casella nera) BBNN. Allo stesso modo (l'argomento e' di Gardner -1991- che pero' non lo dimostra) per un N-goligono che si chiude deve essere N=0 (mod 8). Si puo' procedere pensando di porlo su una (quasi)schacchiera fatta cosi'
<img src="http://img696.imageshack.us/img696/5320/schermata2q.png" alt="" title="">

-Si puo' mostrare che la condizione di congruita' N = 0 (mod 8) e' necessaria e anche sufficiente: per esempio, disponiamo i numeri da 1 a 16 su una riga
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
poniamo due segni "+" all'inizio e alla fine:
+1+2 3 4 5 6 7 8 9 10 11 12 13 14+15+16
poniamo due segni meno all'inizio e alla fine:
+1+2-3-4 5 6 7 8 9 10 11 12-13-14+15+16

Procediamo cosi' fino a "saturare" tutti i 16 termini di questa sommatoria: fa zero! E non solo, per costruzione sia la somma ristretta ai pari segnati, che quella ristretta ai dispari segnati fa zero. Si usa, in breve, un risultato aritmetico che invito i piu' geek a scrivere e dimostrare:

<img src="http://latex.codecogs.com/gif.latex?%5Cbg_black%20%5C120dpi%20%7B%5Ccolor%7Bwhite%7D%20%5Csum_%7Bk=1%7D%5E%7BN%7D%28-1%29%5E%7B%5Clfloor%20%5Cfrac%7Bk-1%7D%7B2%7D%5Crfloor%7D=0%20%5Ciff%20N%5Cequiv%200%5Cpmod%7B4%7D%7D">

Chiaramente cosi' si generano solo una parte dei goligoni possibili, ma hey, e' gia' qualcosa.

- A chi non bastasse pero' si puo' dire all'orecchio che esiste una formula garantita al limone per produrre un goligono "come vogliamo noi" dato un qualunque N=8n. Provare per credere, mettete gli N numeri in fila come sopra, date segno "+" ai primi 2n e agli ultimi 2n numeri, segno - a quelli in mezzo e... la somma e' zero. Provate voi a riscriverlo e a trovare una legge generale: a me non piace molto e l'euristica dopo pranzo non mi sconfinfera.

Verifica di autointersecazione si considerano tutte le combinazioni [ {vertice i, vertice i+1} ; {vertice j, vertice j+1} ] con i, i+1 vertici dei lati orizzontali e j, j+1 vertici dei lati verticali e si verifica se:
min(x_i, x_i+1) <= x_j <= max(x_i, x_i+1)
&
min(y_j, y_j+1) <= y_i <= max(y_j, y_j+1)
Se si verifica è autointersecante.

Number of serial isogons of order 8n (or Golygons). 1, 28, 2108, 227322, 30276740, 4541771016, 739092675672, 127674038970623, 23085759901610016, 4327973308197103600, 835531767841066680300, 165266721954751746697155, 33364181616540879268092840

<img src="http://img299.imageshack.us/img299/5882/goly1.png" alt="esatto, non chiavo" title="esatto, non chiavo">

REFERENCES

L. Sallows, M. Gardner, R. K. Guy and D. E. Knuth, Serial isogons of 90 degrees, Math. Mag. 64 (1991), 315-324.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).