Insieme nordico di punti vicini

[Sepp]

Un insieme finito $ S $ di punti nel piano a coordinate intere è detto two-neighbor-set (come lo tradurreste? ) se, per ogni punto $ (p, q) $ in $ S $, esattamente due dei punti $ (p + 1, q), (p - 1, q), (p, q + 1), (p, q - 1) $ sono in $ S $. Per quale $ n $ esiste un two-neighbor-set che contiene esattamente $ n $ punti?

[Catraga]

Per ogni $ n $?
A parte gli scherzi, penso che la domanda sia da sistemare....

[Sepp]

Se non ho capito male il problema non penso sia per ogni $ n $ perchè

se, per ogni punto $ (p, q) $ in $ S $, esattamente due dei punti $ (p + 1, q), (p - 1, q), (p, q + 1), (p, q - 1) $ sono in $ S $.

[Catraga]

Ok, ci sono. Misunderstanding.

[Marco]

two-neighbor-set (come lo tradurreste? )

Un ....insieme bivicinale??

Orsù, è un bel problemetto. Chi lo risolve?

[edriv]

Claim: n è un numero pari, escludendo 2 e 8.

Dato un punto, l'insieme dei punti "vicini" è l'insieme dei punti {quello sopra, quello sotto, quello a destra, quello a sinistra}, cioè per ogni punto in S ce ne sono esattamente due vicini in S.

Definendo la relazione di equivalenza:
- ogni punto è attaccato a se stessso
- due punti vicini sono attaccati
- si impone la proprietà transitiva
, dividiamo l'insieme in classi tra loro staccate.

Sia S' una qualsiasi di queste classi e P un punto a caso di S'. Definiamo una funzione da S' in S':
f(P)=P', dove P' è uno qualsiasi dei punti vicini a P
Ora applichiamo questo algoritmo:
- sia X l'ultimo punto su cui è definita la funzione.
- se f(f(X)) è già definito, termina.
- f(X) ha due punti vicini, uno dei quali è X. Definiamo f(f(X)) = l'altro.
- torna al passo 1
I punti sono finiti, quindi l'algoritmo termina.

Osserviamo che
Ora, coloriamo tutti i punti del piano come una scacchiera, ci vorrà un bel po', ma è necessario.
Verifichiamo che, se |S'|=n, allora $ f^n(X)=X $ per ogni X.... fatto abbastanza noto ed evidente, ma comunque applicando il principio dei piccioni e il fatto che sono tutti collegati se ne viene fuori. Ma torniamo al problema.

Coloro a scacchiera tutti i punti (a coordinate intere) del piano.
E' chiaro che se X è nero, f(X) è bianco e viceversa.

Dunque, se n fosse dispari e X è bianco, per induzione otteniamo che $ f^n(X) $ è nero, ma questo è proprio X, assurdo. Quindi n è pari.

Somma di numeri pari è pari, quindi sommando la cardinalità di tutte le classi di equivalenza di S rispetto a "essere attaccati", otteniamo un numero pari di elementi. Abbiamo la condizione necessaria.

Ora, costruire un insieme valido con 2n punti (n >= 4) è semplice, basta partire dal quadrato 3x3 (tolto il quadratino al centro), con 8 punti, e allungare due lati opposti di k punti.

Costruire un insieme di 4 punti è anche facile:
x x
x x

E' impossibile che ci sia un insieme di 2 punti Preso il primo punto P, dovrebbero esserci altri due vicini, ma siamo già a 3.

E' impossibile costruire un insieme di 6 punti. L'insieme non può essere un segmento verticale o orrizzontale (agli estremi c'è solo un punto vicino). Partiamo dall'angolo così:
x °
x x
Ora, costruendo un albero delle possibilità per posizionare i restanti punti, ci rendiamo conto che è impossibile con 6.

[Marco]

Sì. Ti faccio solo notare un typo nell'enunciato del Claim:

Claim: n è un numero pari, escludendo 2 e 8.

Ovviamente intendevi dire 6.

Una dimostrazione alternativa all'impossibilità del dispari.

Coloriamo a scacchiera come dice Edriv. Consideriamo il grafo che ha i vertici nei punti di S e gli archi che congiungono i punti vicini.

Ogni nodo ha grado due e ha gli estremi di colori distinti. Allora, detti B il numero di nodi bianchi e N il numero di nodi neri, gli archi uscenti da nodi bianchi sono 2B, mentre quelli entranti nei nodi neri sono 2N. Da cui B=N e il numero totale dei nodi è pari. []