Poligoni di Pick

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Poligoni di Pick

Messaggio da giobimbo »

Un poligono di Pick è un poligono i cui vertici sono soltanto punti-griglia, vedere la corrispondente pagina di Base5:

http://digilander.libero.it/basecinque/ ... ckteor.htm" onclick="window.open(this.href);return false;

Nell'ultimo numero di Amer. Math. Monthly c'è un articolo che parla di alcune nuove disuguaglianze trovate usando i termini del teorema di Pick, che sono:
I = il numero dei punti-griglia che stanno dentro il poligono
P = il numero di punti-griglia che stanno sul perimetro del poligono
A = area.
Ad ogni poligono di Pick convesso corrisponde una superficie toroidale, la cui formula (un polinomio) si ottiene dai punti P, il cui grado è dato da 2A e il cui genere sezionale è uguale a I. Una delle disuglianze trattate è
P <= 2I + 7
che, per I = 1, ci dice che i poligoni di Pick convessi con un solo punto-griglia all'interno hanno al massimo 9 punti-griglia sul perimetro del poligono.

Problema: trovare tutti i poligoni di Pick convessi distinti con un solo punto interno, cioè con I = 1.
Con la parola distinti s'intende che anche dopo rotazioni o riflessioni sono diversi, p.es. un rettangolo 4x2 e un rettangolo 2x4 non sono distinti, ma equivalenti. Da poligoni equivalenti si ottiene una stessa formula, una sola superficie toroidale.
Se al reticolato del professor Bo assegniamo un sistema di coordinate e indichiamo con (0,0) il bollino giallo in basso a sinistra, non occorre disegnare i poligoni, basta dare le coordinate dei vertici. Ad esempio (0,0)+(0,3)+(3,0) corrisponde a un triangolo rettangolo con P=9 e I=1, quindi tale poligono è uno di quelli che bisognava trovare; in tutti gli altri sarà P<9.

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Poligoni di Pick

Messaggio da panurgo »

Mentre metto in bella il mio pensiero vi lascio con una domanda: quali valori può assumere $I$ dato un poligono di Pick convesso con $P\/=\/\infty$? :wink:

P.S.: $P\/=\/\infty$ è una licenza poetica per $P$ grande a piacere...
il panurgo

Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

Pigreco
Livello 3
Livello 3
Messaggi: 91
Iscritto il: ven mag 27, 2005 2:06 pm
Località: Milano-Sondrio
Contatta:

Re: Poligoni di Pick

Messaggio da Pigreco »

Ciao a tutti, è da un po' che manco ma vi seguo sempre!
Questo problema è molto interessante e non pensavo ci fossero simili risultati su ZxZ (io lo chiamo il geopiano).

Per quanto riguarda il problema ho un piccolo dubbio (ci ho pensato ieri ma magari mi sbaglio):
(uno una terminologia molto barbara incrociando RxR e ZxZ, perdonatemi per questo)

Posto che tutti i triangoli sono convessi, considero un triangolo ABC costruito in questo modo:
A=(0,0) B=(2,0) C=(k,2) con $k \in N$
I punti candidati a poter stare all'interno sono quelli del tipo (x,1). (Perchè i punti interni al triangolo hanno $y \in (0,2)$ estremi esclusi per costruzione)

Se k è pari... non ho punti interni

Codice: Seleziona tutto

Ora consideriamo i punti interni al triangolo di questo tipo. Per il teorema di talete, dato che la base del triangolo è lunga 2, questi punti formano un segmento lungo 1. Questo mi dice che i triangoli di questo tipo possono avere al più un punto interno.
Più precisamente, se k è pari il lato AC del triangolo cade su un vertice (posso vederlo per via analitica oppure osservare che il lato AC interseca la retta y=1 nel punto che ha come coordinata x la media tra k e 0 (e quindi k/2) )
Dato che il lato è lungo 1 succede una cosa analoga anche per CB (e ci sono anche qui 100 modi almeno per mostrarlo)
Per cui se k è pari non ho punti interni!
Se k è dispari... ho un punto interno

Codice: Seleziona tutto

Se k è dispari posso fare un ragionamento analogo a sopra..

Considero il segmento che unisce C con il punto (1,0) questo è interno al triangolo perchè è una mediana. Inoltre questa mediana ha un punto al suo interno di coordinate intere (facendo la media degli estremi).
Questo punto è interno al triangolo e per quanto visto prima è l'unico che sta dentro.
Per cui se k è dispari ho un solo punto interno
Quindi la classe di triangoli ABC con A=(0,0) B=(2,0) C=(2k+1,2) ha sempre un punto interno.

Dalla domanda mi aspettavo che i poligoni da trovare fossero in numero finito. Invece no? (oppure mi sono dimenticato qualche ipotesi?)
Ci penso su nei prossimi giorni.

grazie del problema interessantissimo!!
Allegati
triangolo.jpg
triangolo.jpg (9.95 KiB) Visto 7499 volte
Pi greco

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Poligoni di Pick

Messaggio da panurgo »

I poligoni di Pick convessi con $I\/=\/1$ sono un'infinità numerabile :shock: : prendendo come riferimento il punto interno abbiamo, per esempio, una prima classe di poligoni formati dai punti $\left(-k,-1\right)$, $\left(k+1,1\right)$ e $\left(-1,0\right)$...
il panurgo

Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Errore mio

Messaggio da giobimbo »

Problemi di connessione e impegni vari non mi lasciano frequentare il forum come vorrei, ma cercherò perlomeno di chiudere questo argomento che ho proposto.

Il numero delle figure è finito, sta tra 10 e 20, ma dopo quanto detto da Pigreco mi son riletto l'articolo e ho visto che la mia definizione di equivalenza era incompleta, quindi non si ha solo che un rettangolo 4x2 e un rettangolo 2x4 sono equivalenti, ma ogni deformazione del triangolo descrivibile tramite una certa matrice forma un poligono equivalente, per esempio il trapezio (0,0) (1,1) (4,1) (3,0). I triangoli di cui parla Pigreco sono tutti equivalenti al poligono di coordinate:
(0,0) (2,0) (1,2)

Scusatemi e lasciate pure perdere questo problema mal spiegato :(

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Poligoni di Pick

Messaggio da panurgo »

No, no! E' un ottimo problema: è chiaro che i poligoni sono in numero infinito ma sono invece finite le classi di poligoni di cui ho fornito un esempio. Non ho il tempo di metterlo in bella ma cercherò di aggiornarmi quanto prima...
il panurgo

Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Poligoni di Pick

Messaggio da panurgo »

Dal marzo del 2009 risorge questo problema. Sebbene fosse risolto da (molto) tempo lo ho lungamente covato per decidermi su come presentarlo.
Mi sarebbe piaciuto farlo seguendo il filo della scoperta, così come l’ho risolto ma mi sono deciso a semplificare di molto: le cose sono così presentate in un ordine logico, anche se con gran dispendio di energie e pagine rispetto a quello che potrebbe essere fatto per una “vera” pubblicazione. In verità, tutti i punti di vista e le sorprese mi si sono presentati mischiati e il filo conduttore è un’elaborazione posteriore. La matematica è quella del Liceo.

Spero che sopporterete la mia prolissità e che questo mio scritto possa risultare comunque interessante: riporto per vostra comodità il quesito originale.
giobimbo ha scritto:Un poligono di Pick è un poligono i cui vertici sono soltanto punti-griglia, vedere la corrispondente pagina di Base5:

http://digilander.libero.it/basecinque/ ... ckteor.htm" onclick="window.open(this.href);return false;

Nell'ultimo numero di Amer. Math. Monthly c'è un articolo che parla di alcune nuove disuguaglianze trovate usando i termini del teorema di Pick, che sono:
I = il numero dei punti-griglia che stanno dentro il poligono
P = il numero di punti-griglia che stanno sul perimetro del poligono
A = area.
Ad ogni poligono di Pick convesso corrisponde una superficie toroidale, la cui formula (un polinomio) si ottiene dai punti P, il cui grado è dato da 2A e il cui genere sezionale è uguale a I. Una delle disuguaglianze trattate è
P <= 2I + 7
che, per I = 1, ci dice che i poligoni di Pick convessi con un solo punto-griglia all'interno hanno al massimo 9 punti-griglia sul perimetro del poligono.

Problema: trovare tutti i poligoni di Pick convessi distinti con un solo punto interno, cioè con I = 1.
Con la parola distinti s'intende che anche dopo rotazioni o riflessioni sono diversi, p.es. un rettangolo 4x2 e un rettangolo 2x4 non sono distinti, ma equivalenti. Da poligoni equivalenti si ottiene una stessa formula, una sola superficie toroidale.
Se al reticolato del professor Bo assegniamo un sistema di coordinate e indichiamo con (0,0) il bollino giallo in basso a sinistra, non occorre disegnare i poligoni, basta dare le coordinate dei vertici. Ad esempio (0,0)+(0,3)+(3,0) corrisponde a un triangolo rettangolo con P=9 e I=1, quindi tale poligono è uno di quelli che bisognava trovare; in tutti gli altri sarà P<9.
panurgo ha scritto:I poligoni di Pick convessi con $I = 1$ sono un’infinità numerabile :shock:
È facile convincersi che i poligoni di Pick con un punto interno sono un’infinità numerabile.
Osserviamo in figura tre classi di poligoni

Immagine

Fissata convenzionalmente l’origine di un sistema di riferimento nel punto interno, le tre classi sono rappresentate rispettivamente dai punti

$\displaystyle \begin{array}{lC} \mathcal{ C }_{ \small 1} \equiv \left\{ \left( 1 + k ; 1 \right) , \left( -1 ; 0 \right) , \left( -k ; -1 \right) \right\} \\ \mathcal{ C }_{ \small 2} \equiv \left\{ \left( 1 , 0 \right) , \left( k ; 1 \right) , \left( -1 ; 0 \right) , \left( -k ; -1 \right) \right\} \\ \mathcal{ C }_{ \small 3} \equiv \left\{ \left( 1 , 0 \right) , \left( 1 + k ; 1 \right) , \left( 1 + 2 k ; 2 \right) , \left( k ; 1 \right) , \left( -1 ; 0 \right) , \left( 1 - k ; -1 \right) \right\} \end{array}$

con $k \in \mathbb{ Z }$.
Le classi sono definite in modo che la distanza tra punti adiacenti in orizzontale sia costante: in questo modo il numero dei punti interni non può cambiare.

Possiamo dunque cambiare l’obiettivo della nostra ricerca dal contare i poligoni al classificarli (sperando di ottenere un numero finito di classi).

Per far ciò è necessario individuare delle relazioni di equivalenza che in questo caso sono trasformazioni geometriche: per servire allo scopo una trasformazione geometrica deve essere applicabile un numero infinito di volte. Questo perché vogliamo utilizzare un numero finito di classi per contenere infiniti oggetti. Una trasformazione che coinvolgesse un solo punto, per esempio

Immagine

non servirebbe allo scopo perché sarebbe limitata ad un numero finito di applicazioni: in questo caso, cinque

Immagine

Le simmetrie del reticolo degli interi

Immagine

rappresentate dalle trasformazioni

$\begin{array}{lC}
I \equiv \left\{ \begin{array}{lC} x \gets x \\ y \gets y \end{array} \right. \qquad &
S \equiv \left\{ \begin{array}{lC} x \gets -y\\ y \gets x \end{array} \right. \qquad &
S^{ \small 2 } \equiv \left\{ \begin{array}{lC} x \gets -x \\ y \gets -y \end{array} \right. \qquad &
S^{ \small 3 } \equiv \left\{ \begin{array}{lC} x \gets y \\ y \gets -x \end{array} \right. \\
R_{ \small xy } \equiv \left\{ \begin{array}{lC} x \gets y \\ y \gets x \end{array} \right. \qquad &
R_{ \small y } \equiv \left\{ \begin{array}{lC} x \gets -x \\ y \gets y \end{array} \right. \qquad &
R_{ \small yx } \equiv \left\{ \begin{array}{lC} x \gets -y \\ y \gets -x \end{array} \right. \qquad &
R_{ \small x } \equiv \left\{ \begin{array}{lC} x \gets x \\ y \gets -y \end{array} \right.
\end{array}$

non sono utilizzabili dato che formano un gruppo e quindi l’applicazione ripetuta di ciascuna corrisponde sempre all’applicazione singola di una di esse. Torneranno comunque utili per mappare il piano nel primo quadrante.

Osserviamo nuovamente la prima figura

Immagine

Non è difficile vedere che la relazione tra gli elementi di ciascuna delle tre classi della prima figura è la trasformazione geometrica

$\displaystyle \left \{ \begin{array}{lC} x \gets x + k\, y \\ y \gets y \end{array} \right. \qquad k \in \mathbb{ Z }$

E si vede anche subito che due trasformazioni successive equivalgono ad una sola trasformazione nella quale il coefficiente della $y$ corrisponde alla somma dei coefficienti delle due trasformazioni di partenza

$\left \{ \begin{array}{lC} x \gets x + k_{ \small 2 } y \\ y \gets y \end{array} \right. \quad \otimes \quad \left \{ \begin{array}{lC} x \gets x + k_{ \small 1 } y \\ y \gets y \end{array} \right. \quad = \quad \left \{ \begin{array}{lC} x \gets x + \left( k_{ \small 1 } + k_{ \small 2 } \right) y \\ y \gets y \end{array} \right.$

Indichiamo con $H^{ \small k }$ l’operatore della trasformazione: possiamo così scrivere $\text{P} \gets H^{ \small k } \text{P}$, dove $\text{P}$ è un punto del reticolo degli interi.

La composizione ($\otimes$) di due trasformazioni è rappresentata dal prodotto dei due operatori corrispondenti, $H^{ \small k_{ \small 1 }} H^{ \small k_{ \small 2 }} = H^{ \small k_{ \small 1 } + \small k_{ \small 2 }}$, e ogni operatore ha il suo inverso cosicché l’applicazione dei due corrisponde all’assenza di cambiamenti, $\text{P} = H^{ \small -k } H^{ \small k } \text{P} = H^{ \small 0 } \text{P}$, e $H^{ \small 0 } = I$ (dove $I$ è l’operatore dell’identità).

La simmetria del reticolo degli interi ci suggerisce come ottenere una seconda relazione di equivalenza: scambiando la $x$ con la $y$ prima e dopo l’applicazione di $H^{ \small k }$ abbiamo una trasformazione geometrica, $V^{ \small k } = R_{ \small xy } H^{ \small k } R_{ \small xy }$, che opera in verticale

$\displaystyle V^{ \small k } \equiv \left \{ \begin{array}{lC} x \gets y \\ y \gets x \end{array} \right. \quad \otimes \quad \left \{ \begin{array}{lC} x \gets x + k\, y \\ y \gets y \end{array} \right. \quad \otimes \quad \left \{ \begin{array}{lC} x \gets y \\ y \gets x \end{array} \right. \quad = \quad \left \{ \begin{array}{lC} x \gets y \\ y \gets x \end{array} \right. \quad \otimes \quad \left \{ \begin{array}{lC} x \gets y + k\, x \\ y \gets x \end{array} \right. \quad = \quad \left \{ \begin{array}{lC} x \gets x \\ y \gets k\, x + y \end{array} \right.$

sempre con $k \in \mathbb{ Z }$, avente esattamente le stesse caratteristiche della precedente:

$\displaystyle \begin{array}{lC} \text{P} \gets V^{ \small k } \text{P} \\ \text{P} \gets V^{ \small k_{ \small 2 }} \text{P} \otimes \text{P} \gets V^{ \small k_{ \small 1 }} \text{P} = \text{P} \gets V^{ \small k_{ \small 1 } + k_{ \small 2 }} \text{P} \\ \text{P} = V^{ \small -k } V^{ \small k } \text{P} = V^{ \small 0 } \text{P} \qquad V^{ \small 0 } = I \end{array}$

Osserviamo la composizione delle due trasformazioni $H^{ \small k }$ e $V^{ \small k }$ non è commutativa (come è evidente in figura)

Immagine

Andiamo ora a considerare gli elementi che formano i nostri poligoni: punti e segmenti.

Se consideriamo le rette a coefficienti interi passanti per l’origine osserviamo che ciascuna di esse incontra gli infiniti punti per i quali il rapporto tra $x$ e $y$ è uguale alla pendenza della retta stessa.
La retta $m\, x - n\, y = 0$ ($m$ e $n$ primi tra loro) intercetta tutti i punti della classe $\mathcal{ C } \equiv \left\{ \left( k\, n; k\, m \right), k \in \mathbb{ Z } \right\}$. Tra l’origine e il punto $\left( k\, n; k\, m \right)$ vi sono esattamente $k - 1$ punti e la condizione per cui un punto è un punto di confine (cioè “vede” l’origine) è $k = \pm 1$.
Ma $\left| k \right|$ è il massimo comun divisore di $x$ e $y$ per cui possiamo ridefinire la nostra condizione come $\gcd \left( x, y \right) = 1$.

Consideriamo adesso la retta definita da due punti di confine, $\text{P}_{ \small 1 }$ e $\text{P}_{ \small 2 }$.

Essa ha equazione

$\displaystyle \left( y_{ \small 2 } - y_{ \small 1 } \right)\, x - \left( x_{ \small 2 } - x_{ \small 1 } \right)\, y - \left(x_{ \small 1 } y_{ \small 2 } - x_{ \small 2 } y_{ \small 1 } \right) = 0$

Operiamo la traslazione

$\displaystyle \left\{ \begin{array}{lC} x^{ \small \prime } \gets x - x_{ \small 1 } \\ y^{ \small \prime } \gets y - y_{ \small 1 } \end{array} \right.$

e l’equazione diventa

$\displaystyle y^{ \small \prime }_{ \small 2 } x^{ \small \prime } - x^{ \small \prime }_{ \small 2 } y^{ \small \prime } = 0$

Per gli stessi motivi di prima, tra $\text{O}^{ \small \prime }$ e $\text{P}^{ \small \prime }$ vi sono esattamente $\gcd \left( x^{ \small \prime }_{ \small 2 }, y^{ \small \prime }_{ \small 2 } \right) - 1$ punti e $\text{P}_{ \small 1 }$ e $\text{P}_{ \small 2 }$ si “vedono” quando $\gcd \left( x_{ \small 2 } - x_{ \small 1 }, y_{ \small 2 } - y_{ \small 1 } \right) = 1$.

Tornerà utile considerare come tali solo i segmenti per cui

$\gcd \left( x_{ \small 1 }, y_{ \small 1 } \right) = \gcd \left( x_{ \small 2 }, y_{ \small 2 } \right) = \gcd \left( x_{ \small 2 } - x_{ \small 1 }, y_{ \small 2 } - y_{ \small 1 } \right) = 1$

un poligono dei nostri avrà così tanti segmenti quanti sono i punti sul perimetro.

Cosa possiamo fare ai nostri punti con gli operatori $H$ e $V$? Prendiamo un punto $\text{P}$ nel primo quadrante e applichiamo il seguente algoritmo:

$\displaystyle \begin{array}{lC} \text{while } \left( x \neq y \right)\; \left\{ \text { if } \left( x > y \right)\; \text{ then } \text{P} \gets H^{ \small -1 } \text{P}\, \text{ else } \text{P} \gets V^{ \small -1 } \text{P} \right\} \\ \text{P} \gets V^{ \small -1 } \text{P} \end{array}$

Cioè, fino a che i valori di $x$ e $y$ sono diversi tra loro togliamo il più piccolo dal più grande dopodiché poniamo $y = 0$: in figura vediamo cosa succede con il punto $\left( 11; 3 \right)$

Immagine

e con il punto $\left( 15; 6 \right)$

Immagine

Questo algoritmo, almeno fino all’ultimo passo, non è altro che l’algoritmo di Euclide per il calcolo del massimo comun divisore: vediamo in dettaglio

$\begin{array}{lC} 11 : 3 = 3 & \text{ resto } 2 & \left( 2;\, 3 \right) \gets H^ { \small -3 } \left( 11;\, 3 \right) \\ 3 : 2 = 1 & \text{ resto } 1 & \left( 2;\, 1 \right) \gets V^ { \small -1 } \left( 2;\, 3 \right) \\ 2 : 1 = 2 & \text{ resto } 0 & \left \{ \begin{array}{lC} \left( 1;\, 1 \right) \gets H^ { \small -1 } \left( 2;\, 1 \right) \\ \left( 1;\, 0 \right) \gets V^ { \small -1 } \left( 1;\, 1 \right) \end{array} \right. \end{array}$

e

$\begin{array}{lC} 15 : 6 = 2 & \text{ resto } 3 & \left( 3;\, 6 \right) \gets H^ { \small -2 } \left( 15;\, 6 \right) \\ 6 : 3 = 2 & \text{ resto } 0 & \left \{ \begin{array}{lC} \left( 3;\, 3 \right) \gets V^ { \small -1 } \left( 3;\, 6 \right) \\ \left( 3;\, 0 \right) \gets V^ { \small -1 } \left( 3;\, 3 \right) \end{array} \right. \end{array}$

L’ultimo passo è modificato in modo da far finire l’algoritmo sempre sull’asse delle ascisse: nel primo caso l’algoritmo termina sul punto $\left( 1; 0 \right)$, e infatti $11$ e $3$ sono primi tra loro, nel secondo termina sul punto $\left( 3; 0 \right)$, ed è proprio $\gcd \left( 15,\, 3 \right) = 3$.

Il nostro algoritmo porta quindi un generico punto $\left( x; y \right)$ del primo quadrante nel punto $\left( \gcd \left( x; y \right); 0 \right)$ e qualunque punto può essere portato nel primo quadrante da una delle simmetrie del reticolo opportunamente scelta: di conseguenza, tutti e soli i punti di confine possono essere portati in $\left( 1; 0 \right)$.

Questo significa che possiamo portare qualunque punto di confine in qualunque altro punto di confine: portiamo entrambi i punti nel primo quadrante con le opportune simmetrie, applichiamo ad entrambi l’algoritmo ottenendo per ciascuno una sequenza di operatori e invertiamo gli operatori e la simmetria del punto di arrivo.

Prendiamo per esempio $\left( 11; 3 \right)$ e $\left( -4; 7 \right)$.

Per il primo sappiamo già che l’operatore complessivo è $O_{ \small 1 } = V^{ \small -1 } H^{ \small -1 } V^{ \small -1 } H^{ \small -3 } I$ (la simmetria che porta il punto nel primo quadrante è l’identità, $I$).

Per il secondo operiamo la rotazione di $270^{ \small \circ }$, $S^{ \small 3 }$ e poi applichiamo l’algoritmo

$\begin{array}{lC} 7 : 4 = 1 & \text{ resto } 3 & \left( 3;\, 4 \right) \gets H^ { \small -1 } \left( 7;\, 4 \right) \\ 4 : 3 = 1 & \text{ resto } 1 & \left( 3;\, 1 \right) \gets V^ { \small -1 } \left( 3;\, 4 \right) \\ 3 : 1 = 3 & \text{ resto } 0 & \left \{ \begin{array}{lC} \left( 1;\, 1 \right) \gets H^ { \small -2 } \left( 3;\, 1 \right) \\ \left( 1;\, 0 \right) \gets V^ { \small -1 } \left( 1;\, 1 \right) \end{array} \right. \end{array}$

e il secondo operatore è $O_{ \small 2 } = V^{ \small -1 } H^{ \small -2 } V^{ \small -1 } H^{ \small -1 } S^{ \small 3 }$, il cui inverso è $O^{ \small -1 }_{ \small 2 } = S\, H\, V\, H^{ \small 2 } V$.

Abbiamo dunque $\left( -4; 7 \right) \gets O^{ \small -1 }_{ \small 2 } O_{ \small 1 } \left( 11; 3 \right) = S\, H\, V\, H\, V^{ \small -1 } H^{ \small -3 } \left( 11; 3 \right)$, cioè

Immagine

Abbiamo deciso di considerare come segmenti le coppie ordinate di punti che soddisfano la condizione

$\displaystyle \gcd \left( x_{ \small 1 }, y_{ \small 1 } \right) = \gcd \left( x_{ \small 2 }, y_{ \small 2 } \right) = \gcd \left( x_{ \small 2 } - x_{ \small 1 }, y_{ \small 2 } - y_{ \small 1 } \right) = 1$

ma tale condizione non è sufficiente a garantire che un segmento sia un segmento di confine, ovvero formi sempre con l’origine un triangolo che non racchiude altri punti, come dimostrano i segmenti $\left\{ \left( 2 ; 1 \right), \left( 1 ; 4 \right) \right\}$, $\left\{ \left( 5 ; 1 \right), \left( 2 ; 3 \right) \right\}$ e $\left\{ \left( 4 ; 1 \right), \left( 3 ; 2 \right) \right\}$ in figura

Immagine

Per trovare una condizione sufficiente, con riferimento alla figura seguente,

Immagine
l’area del triangolo $\text{O} \text{P}_{ \small 1 } \text{P}_{ \small 2 }$ è $A = I + P/2 - 1 = I + 1/2$ perché si tratta di un poligono di Pick con tre punti sul perimetro: $\text{O}$, $\text{P}_{ \small 1 }$ e $\text{P}_{ \small 2 }$ si vedono ovvero $\gcd \left( x_{ \small 1 }, y_{ \small 1 } \right) = \gcd \left( x_{ \small 2 }, y_{ \small 2 } \right) = \gcd \left( x_{ \small 2 } - x_{ \small 1 }, y_{ \small 2 } - y_{ \small 1 } \right) = 1$.

Se $\text{P}_{ \small 1 } \text{P}_{ \small 2 }$ è un segmento di confine allora deve essere $I = 0$ e $A = 1/2$.
Calcoliamo l’area per via geometrica: sempre con riferimento alla figura, $A = \frac { \overline{ \text{P}_{ \small 1 } \text{P}_{ \small 2 }} \times d} 2$, dove $d$ è la distanza dall’origine della retta $r$, passante per $\text{P}_{ \small 1 } \text{P}_{ \small 2 }$. La distanza dall’origine di una retta rappresentata dall’equazione $a x + b y + c = 0$ è

$\displaystyle d = \frac { \left| a \cdot 0 + b \cdot 0 + c \right| } { \sqrt { a^{ \small 2 } + b^{ \small 2 }}} = \frac { \left| c \right| } { \sqrt { a^{ \small 2 } + b^{ \small 2 }}}$

Nel nostro caso l’equazione della retta è

$\displaystyle \left( y_{ \small 2 } - y_{ \small 1 } \right)\, x - \left( x_{ \small 2 } - x_{ \small 1 } \right)\, y - \left(x_{ \small 1 } y_{ \small 2 } - x_{ \small 2 } y_{ \small 1 } \right) = 0$

ed è

$\displaystyle \sqrt { a^{ \small 2 } + b^{ \small 2 }} = \sqrt { \left( y_{ \small 2 } - y_{ \small 1 } \right)^{ \small 2 } + \left( x_{ \small 2 } - x_{ \small 1 } \right)^{ \small 2 }} = \overline{ \text{P}_{ \small 1 } \text{P}_{ \small 2 }}$

da cui segue

$\displaystyle d = \frac { \left| x_{ \small 1 } y_{ \small 2 } - x_{ \small 2 } y_{ \small 1 } \right| } { \overline{ \text{P}_{ \small 1 } \text{P}_{ \small 2 }}}$

e

$\displaystyle A = \frac { \left| x_{ \small 1 } y_{ \small 2 } - x_{ \small 2 } y_{ \small 1 } \right| } 2$

In conclusione, la condizione per avere un segmento di confine è che sia $\left| x_{ \small 1 } y_{ \small 2 } - x_{ \small 2 } y_{ \small 1 } \right| = 1$ ovvero $\left( x_{ \small 1 } y_{ \small 2 } - x_{ \small 2 } y_{ \small 1 } \right) = \pm 1$.

Dimostriamo ora che la condizione

$\displaystyle \left( x_{ \small 1 } y_{ \small 2 } - x_{ \small 2 } y_{ \small 1 } \right) = \pm 1$

implica la condizione

$\displaystyle \gcd \left( x_{ \small 1 }, y_{ \small 1 } \right) = \gcd \left( x_{ \small 2 }, y_{ \small 2 } \right) = \gcd \left( x_{ \small 2 } - x_{ \small 1 }, y_{ \small 2 } - y_{ \small 1 } \right) = 1$

Poniamo $x_{ \small 1 } = d_{ \small 1 } x^{ \small \prime }_{ \small 1 }$, $y_{ \small 1 } = d_{ \small 1 } y^{ \small \prime }_{ \small 1 }$, $x_{ \small 2 } = d_{ \small 2 } x^{ \small \prime }_{ \small 2 }$ e $y_{ \small 2 } = d_{ \small 2 } y^{ \small \prime }_{ \small 2 }$, con $d_{ \small 1 } = \gcd \left( x_{ \small 1 }, y_{ \small 1 } \right)$ e $d_{ \small 2 } = \gcd \left( x_{ \small 2 }, y_{ \small 2 } \right)$.

Abbiamo

$\displaystyle \left( x_{ \small 1 } y_{ \small 2 } - x_{ \small 2 } y_{ \small 1 } \right) = d_{ \small 1} d_{ \small 2 } \left( x^{ \small \prime }_{ \small 1 } y^{ \small \prime }_{ \small 2 } - x^{ \small \prime }_{ \small 2 } y^{ \small \prime }_{ \small 1 } \right) = \pm 1$

e, dato che $d_{ \small 1 }, d_{ \small 2 } \in \mathbb{N}$ deve essere $\left( x^{ \small \prime }_{ \small 1 } y^{ \small \prime }_{ \small 2 } - x^{ \small \prime }_{ \small 2 } y^{ \small \prime }_{ \small 1 } \right) = \pm 1$ e $d_{ \small 1} = d_{ \small 2 } = 1$.

Poniamo ora $d = \gcd \left( x_{ \small 2 } - x_{ \small 1 }, y_{ \small 2 } - y_{ \small 2 } \right)$, $x_{ \small 2 } - x_{ \small 1 } = \Delta x = d\, \Delta x^{ \small \prime }$ e $y_{ \small 2 } - y_{ \small 1 } = \Delta y = d\, \Delta y^{ \small \prime }$, e riarrangiamo

$\left( x_{ \small 1 } y_{ \small 2 } - x_{ \small 2 } y_{ \small 1 } \right) = \left(x_{ \small 1 } y_{ \small 2 } - x_{ \small 1 } y_{ \small 1 } - x_{ \small 2 } y_{ \small 1 } + x_{ \small 1 } y_{ \small 1 } \right) = \left( x_{ \small 1} \Delta y - \Delta x\, y_{ \small 1 } \right) = d_{ \small 1} d\, \left( x^{ \small \prime }_{ \small 1} \Delta y^{ \small \prime } - \Delta x^{ \small \prime }\, y^{ \small \prime }_{ \small 1 } \right) = \pm 1$

da cui segue $d = 1$ per quanto visto più sopra. Q.E.D.

Introduciamo adesso un cambio di notazione approfittando del fatto che una coppia ordinata di numeri interi rappresenta sia un punto del reticolo degli interi sia un vettore a componenti intere: $\left( x; y \right) \equiv \left( \begin{array}{cC} x \\ y \end{array} \right)$.

Le trasformazioni da noi utilizzate, simmetrie del reticolo, $H$ e $V$, sono trasformazioni lineari che possono essere rappresentate da matrici $2 \times 2$ di numeri interi:

$\begin{array}{lC} I \equiv \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \qquad & S \equiv \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} \qquad & S^{ \small 2 } \equiv \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix} \qquad & S^{ \small 3 } \equiv \begin{pmatrix} 0 & 1 \\ -1 & 0 \end{pmatrix} \qquad \\ R_{ \small xy } \equiv \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \qquad & R_{ \small y } \equiv \begin{pmatrix} -1 & 0 \\ 0 & 1 \end{pmatrix} \qquad & R_{ \small yx } \equiv \begin{pmatrix} 0 & -1 \\ -1 & 0 \end{pmatrix} \qquad & R_{ \small x } \equiv \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \qquad \end{array}$

e

$H^{ \small k } \equiv \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix} \qquad V^{ \small k } \equiv \begin{pmatrix} 1 & 0 \\ k & 1 \end{pmatrix}$

In questa notazione anche un segmento $s$ è rappresentato da una matrice $2 \times 2$ formata concatenando i vettori che rappresentano i punti alle estremità del segmento stesso:

$\displaystyle s = \text{P}_{ \small 1 } \text{P}_{ \small 2 } \equiv { x_{ \small 1 } \choose { y_{ \small 1 }}} \bigsqcup { x_{ \small 2 } \choose { y_{ \small 2 }}} = \begin{pmatrix} x_{ \small 1 } & x_{ \small 2 } \\ y_{ \small 1 } & y_{ \small 2 } \end{pmatrix}$

La condizione per avere un segmento di confine altro non è che $\left( x_{ \small 1} y_{ \small 2} - x_{ \small 2 } y_{ \small 1 } \right) = \det s = \pm 1$. Ma se scambiamo tra loro le colonne della matrice cambia il segno del determinante: questo significa che tale segno dipende dall’ordine in cui prendiamo i punti, l’orientamento del segmento.
Osserviamo che un segmento orientato in verso trigonometrico (antiorario) ha determinante positivo. Osserviamo inoltre che le trasformazioni $H$ e $V$ e le rotazioni hanno determinante $1$ e conservano l’orientamento dei segmenti mentre le riflessioni lo invertono ed hanno determinante pari a $-1$.
Poiché noi utilizziamo le simmetrie solo per portare punti e segmenti nel primo quadrante possiamo limitarci alle sole rotazioni e adottare la convenzione di elencare i punti in ordine trigonometrico (ovvero, di orientare i segmenti positivamente): in questo modo la condizione perché $s$ sia un segmento di confine diviene $\det s = 1$.

In questa rappresentazione matriciale non vi è differenza tra operatore e segmento: abbiamo l’insieme delle matrici $2 \times 2$ con elementi interi e determinante uguale a $1$, su cui è definita l’operazione prodotto per la quale valgono le proprietà:

1) il prodotto di due elementi dell’insieme è un elemento dell’insieme

$\displaystyle \begin{pmatrix} a & b \\ c & d \end{pmatrix}\, \begin{pmatrix} x & y \\ z & t \end{pmatrix} = \begin{pmatrix} a x + b z & a y + b t \\ c x + d z & c y + d t \end{pmatrix}$

perché somme e prodotti di interi sono interi e $\det A B = \det A \cdot \det B = 1$

2) esiste l’elemento neutro $i = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$;

3) ogni elemento ha il suo inverso perché $\det s = 1 \neq 0$.

Questo implica che ciò che facciamo, dalle simmetrie al nostro algoritmo, manda punti di confine in punti di confine e segmenti di confine in segmenti di confine in quanto non cambia il valore di $\det s$.

Dato un punto di confine possiamo trovare tutti i punti (di confine) che formano con esso un segmento di confine imponendo la condizione

$\displaystyle \begin{vmatrix} x_{ \small 1 } & x \\ y_{ \small 1 } & y \end{vmatrix} = 1$

e i punti giacciono sulla retta $y_{ \small 1} x - x_{ \small 1 } y + 1 = 0$; oppure

$\displaystyle \begin{vmatrix} x & x_{ \small 1 } \\ y & y_{ \small 1 } \end{vmatrix} = 1$

e i punti giacciono sulla retta $y_{ \small 1} x - x_{ \small 1 } y - 1 = 0$: per esempio (vedi figura), per $\text{P} \equiv {{ -1 } \choose 1 }$ le rette sono $x + y \pm\, 1 = 0$ mentre per $\text{Q} \equiv { 3 \choose 2 }$ le rette sono $2x - 3y \pm\, 1 = 0$.

Immagine

Dalla figura è evidente che le rette $y_{ \small 1 } x - x_{ \small 1 } y \pm 1 = 0$ contengono solo segmenti di confine: dalla teoria delle equazioni diofantine sappiamo che un’equazione a coefficienti interi $a x + b y + c = 0$ ammette infinite soluzione della forma $\left( x + k b, y - k a \right)$, dove $\left( x, y \right)$ è una soluzione particolare dell’equazione, se $\gcd \left( a, b \right)$ divide $c$. Il punto ${{ x_{ \small 1 }} \choose {y_{ \small 1 }}}$ è un punto di confine e $\gcd \left( x_{ \small 1 }, y_{ \small 1 } \right) = 1$ quindi le coordinate di due punti consecutivi, giacenti sulle rette $y_{ \small 1 } x - x_{ \small 1 } y \pm 1 = 0$, differiscono per $x_{ \small 1 }$ e $y_{ \small 1 }$ rispettivamente.
Se i due punti giacciono sulla retta $y_{ \small 1 } x - x_{ \small 1 } y + 1 = 0$, il segmento orientato $s$ è rappresentato dalla matrice $\begin{pmatrix} x + x_{ \small 1 } & x \\ y + y_{ \small 1 } & y \end{pmatrix}$ e abbiamo $\det s = x\, y + x_{ \small 1 } y - y\, x - y_{ \small 1 } x = - \left( y_{ \small 1 } x - x_{ \small 1 } y \right) = 1$; viceversa, se i due punti giacciono sulla retta $y_{ \small 1 } x - x_{ \small 1 } y - 1 = 0$, il segmento orientato $s$ è rappresentato dalla matrice $\begin{pmatrix} x & x + x_{ \small 1 } \\ y & y + y_{ \small 1 } \end{pmatrix}$ e abbiamo $\det s = x\, y + x\, y_{ \small 1 } - y\, x - y\, x_{ \small 1 } = y_{ \small 1 } x - x_{ \small 1 } y = 1$.
Le due rette sono dunque tassellate di segmenti di confine: sono “rette di confine” e nella fascia di piano da esse delimitata giacciono solo i punti appartenenti alla retta $y_{ \small 1 } x - x_{ \small 1 } y = 0$.

Il nostro algoritmo manda il punto $\text{P}_{ \small 1 }$ di $s$ in ${ 1 \choose 0 }$ e il punto $\text{P}_{ \small 2 }$ dovrà giacere sulla retta $y = 1$: applichiamo infine $H^{ \small - x_{ \small 2 }}$ e avremo portato $s$ in $i \equiv \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$.

Ma, un momento! Abbiamo un modo diretto per portare $s$ in $i$: l’operatore complessivo − formato dalla simmetria che porta il punto nel primo quadrante, dall’algoritmo di Euclide e da $H^{ \small – x_{ \small 2 }}$ − altro non è che l’inverso di $s$, $s^{ \small - 1 }$, che esiste per ogni segmento di confine.

Ora, un poligono dei nostri è formato dalla concatenazione di segmenti di confine, ciascuno dei quali viene mandato da un qualsiasi dei nostri operatori in un altro segmento di confine: quindi un poligono con un punto interno viene mandato in un altro poligono con un punto interno.

In particolare, dato che qualsiasi segmento di un qualsiasi poligono può essere mandato in $i$, tutti i poligoni di Pick con un punto interno sono equivalenti ad un qualche poligono contenente $i$ stesso: non ci rimane che elencare questi poligoni e classificarli.

Partiamo dunque da $i$ e aggiungiamo i segmenti in verso trigonometrico.
Vediamo quali sono i vincoli: il poligono deve essere convesso per cui i punti che lo formano devono giacere a sinistra della retta $x + y - 1 = 0$ passante per $i$, nel semipiano che contiene l’origine (il punto interno); data la simmetria del reticolo degli interi la stessa cosa deve valere anche per la retta $x - y - 1 = 0$; infine, i segmenti di confine che partono dal punto ${ 0 \choose 1 }$ terminano sulla retta $\displaystyle \begin{vmatrix} 0 & x \\ 1 & y \end{vmatrix} = 1$, cioè $x = -1$.
Abbiamo quindi a disposizione i cinque punti in figura

Immagine

Abbiamo appena dimostrato che, nei nostri poligoni, non vi possono essere più di cinque punti allineati perché il primo di essi può sempre essere portato in ${{ -1 } \choose 2 }$ e il secondo in ${{ -1 } \choose 1 }$ con un’opportuna scelta del segmento da portare in $i$: in questo modo il sesto punto verrebbe a trovarsi in ${{ -1 } \choose { -3 }}$ a destra della retta $x - y - 1 = 0$.

Chiuso l’inciso, aggiungiamo ora il punto ${{ -1 } \choose 2 }$ e otteniamo la figura

Immagine

La retta di confine è rappresentata dall’equazione

$\begin{vmatrix} -1 & x \\ 2 & y \end{vmatrix} = 1 \qquad \Rightarrow \qquad 2 x + y + 1 = 0$

e i punti devono giacere a sinistra della retta $x = 1$ per mantenere la concavità del poligono.
Con l’aggiunta del punto ${{ -2 } \choose 3 }$ otteniamo la figura

Immagine

e aggiungendo il punto ${{ -3 } \choose 4 }$ otteniamo

Immagine

Qui abbiamo a disposizione un solo punto per continuare in quanto ${{ -3 } \choose 4 }$ è il quinto punto allineato e gli ulteriori punti sulla retta $4 x + 3 y - 1 = 0$ cadono a destra di $x = 1$: possiamo solo aggiungere i punti uno alla volta fino ad ottenere il primo dei nostri poligoni

Immagine

Come rappresentante di questa classe di poligoni prendiamo quello con perimetro minore (L’area è uguale perché sono poligoni di Pick con lo stesso numero di punti.

Ora non resta che tornare indietro fino a quando c’è di nuovo una possibilità di scelta

Immagine

e passare al punto successivo,

Immagine

poi al successivo e così via...

Io l’ho fatto e ho classificato i poligoni che contengono $i$ nelle $16$ classi riportate in figura

Immagine
Ciao! :wink:
il panurgo

Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

giobimbo
Livello 5
Livello 5
Messaggi: 343
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Poligoni di Pick

Messaggio da giobimbo »

Semplicemente eccezionale...
Ho controllato le soluzioni con quelle date nella rivista e confermo la correttezza di quanto ottenuto dal compagno di Pantagruele:
BRAVISSIMO !

Rispondi