Volevo raccontare una storiella, ma è diventata troppo complicata, quindi formulo il problema in termini puramente matematici.
Sia Q (il quartiere) l'insieme dei punti dello spazio a coordinate intere; due punti di Q si dicono vicini se hanno due coordinate coincidenti e nella rimanente differiscono di 1 unità. Per intenderci, i vicini di (x,y,z) sono
$ (x,y,z\pm 1)\ (x,y\pm 1,z)\ (x\pm1,y,z) $
Dimostrate che esiste un sottoinsieme C di Q (il comitato di quartiere) tale che:
(i) se un punto appartiene a C allora non vi appartiene nessuno dei suoi vicini
(ii) se un punto non appartiene a C allora vi appartiene esattamente uno dei suoi vicini.
Questo è difficilotto, quindi ...
HINT : esaminate prima i casi 1dimensionale e 2dimensionale, poi sovrapponete tanti casi 2dimensionali ...
Comitato di quartiere e problemi di vicinato
Visto che nessuno risponde… provo a debuttare.
Pongo $ x = (2, -1, 0), y = (1, 1, 1), z = (1, 0, -2) \in \mathbb{Z}^3 $, dopodiché $ C = \left< x, y, z \right> = \left\{ ax + by + cz\ |\ \alpha, \beta, \gamma \in \mathbb{Z} \right\} $.
Sia $ (\alpha, \beta, \gamma) \in \mathbb{Z}^3 $. Pongo $ (\alpha, \beta, \gamma) = ax + by + cz $; risolvendo l'equazione, risulta il sistema: $ \left\{\begin{array}{l} 7c = \alpha + 2\beta - 3\gamma\\ a = \gamma - \beta + 2c\\ b = \beta + a\end{array}\right. $. Potendo variare al più uno tra $ \alpha $, $ \beta $ o $ \gamma $, il secondo membro della prima equazione può assumere sette valori interi consecutivi, tra cui uno e uno solo darà una soluzione intera per $ (a, b, c) $. Quindi se $ (\alpha, \beta, \gamma) \not\in C $, tra i suoi vicini ci sarà esattamente un elemento di $ C $, se invece già appartiene, tra i suoi vicini non ci saranno altri elementi di $ C $.
Pongo $ x = (2, -1, 0), y = (1, 1, 1), z = (1, 0, -2) \in \mathbb{Z}^3 $, dopodiché $ C = \left< x, y, z \right> = \left\{ ax + by + cz\ |\ \alpha, \beta, \gamma \in \mathbb{Z} \right\} $.
Sia $ (\alpha, \beta, \gamma) \in \mathbb{Z}^3 $. Pongo $ (\alpha, \beta, \gamma) = ax + by + cz $; risolvendo l'equazione, risulta il sistema: $ \left\{\begin{array}{l} 7c = \alpha + 2\beta - 3\gamma\\ a = \gamma - \beta + 2c\\ b = \beta + a\end{array}\right. $. Potendo variare al più uno tra $ \alpha $, $ \beta $ o $ \gamma $, il secondo membro della prima equazione può assumere sette valori interi consecutivi, tra cui uno e uno solo darà una soluzione intera per $ (a, b, c) $. Quindi se $ (\alpha, \beta, \gamma) \not\in C $, tra i suoi vicini ci sarà esattamente un elemento di $ C $, se invece già appartiene, tra i suoi vicini non ci saranno altri elementi di $ C $.
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Non ho ancora letto la soluzione di Zviad..probabilmente stiamo solamente dicendo la stessa cosa in modo differente (ormai avevo già tutto scritto su blocco note) 
Sia definito C come segue.
Nello spazio (x,y,z) i punti $ \in $ C sono:
i punti con $ y \equiv -2x-3z (mod 7) $ (ovviamente con x,y,z interi).
Dimostro che godono della proprietà 2:
i vicini di P (x,y,z) sono (x+-1;y;z)(x;y+-1;z)(x;y;z+-1)
se $ P \not \in C $ e nessuno dei vicini di P $ \in $ C allora valgono le seguenti:
$ -2(x+1)-3z \not \equiv y (mod 7) $
$ -2(x-1)-3z \not \equiv y (mod 7) $
$ -2x-3z \not \equiv y+1 (mod 7) $
$ -2x-3z \not \equiv y-1 (mod 7) $
$ -2x-3z \not \equiv y (mod 7) $
$ -2x-3(z+1) \not \equiv y (mod 7) $
$ -2x-3(z-1) \not \equiv y (mod 7) $
ovvero:
$ -2x-3z \not \equiv $ y;y+1;y+2;y+3;y-1;y-2;y-3 (mod 7) che è assurdo perchè y;y+1…y-3 coprono tutti i rappresentanti modulo 7.
Inoltre massimo una delle precedenti è falsa perché i rappresentanti di y;y+1…y-3 modulo 7 sono tutti differenti. Quindi se $ P \not \in C $ ovvero $ -2x-3z \not \equiv y (mod 7) $ almeno e solo uno dei suoi vicini appartiene a C.
Inoltre analogamente mostro che se P $ \in C $ ovvero -2x-3z $ \equiv $ y (mod 7) allora nessuno dei suoi vicini $ \in C $.
Spero torni tutto
Sia definito C come segue.
Nello spazio (x,y,z) i punti $ \in $ C sono:
i punti con $ y \equiv -2x-3z (mod 7) $ (ovviamente con x,y,z interi).
Dimostro che godono della proprietà 2:
i vicini di P (x,y,z) sono (x+-1;y;z)(x;y+-1;z)(x;y;z+-1)
se $ P \not \in C $ e nessuno dei vicini di P $ \in $ C allora valgono le seguenti:
$ -2(x+1)-3z \not \equiv y (mod 7) $
$ -2(x-1)-3z \not \equiv y (mod 7) $
$ -2x-3z \not \equiv y+1 (mod 7) $
$ -2x-3z \not \equiv y-1 (mod 7) $
$ -2x-3z \not \equiv y (mod 7) $
$ -2x-3(z+1) \not \equiv y (mod 7) $
$ -2x-3(z-1) \not \equiv y (mod 7) $
ovvero:
$ -2x-3z \not \equiv $ y;y+1;y+2;y+3;y-1;y-2;y-3 (mod 7) che è assurdo perchè y;y+1…y-3 coprono tutti i rappresentanti modulo 7.
Inoltre massimo una delle precedenti è falsa perché i rappresentanti di y;y+1…y-3 modulo 7 sono tutti differenti. Quindi se $ P \not \in C $ ovvero $ -2x-3z \not \equiv y (mod 7) $ almeno e solo uno dei suoi vicini appartiene a C.
Inoltre analogamente mostro che se P $ \in C $ ovvero -2x-3z $ \equiv $ y (mod 7) allora nessuno dei suoi vicini $ \in C $.
Spero torni tutto
