Si consideri l'insieme degli interi modulo $n$ ovvero ($0$,...,$n-1$), dove $n$ è un intero positivo. Ne coloriamo alcuni con le seguenti regole:
i) se coloro $x$ devo colorare pure l'inverso, ovvero il numero $y$ tale che $x+y \equiv 0 \pmod{n}$
ii) non posso colorare tutti i numeri
iii) se due numeri $x$ e $y$ sono tali che $x+y \pmod{n}$ è colorato, allora almeno uno tra $x$ e $y$ deve essere colorato.
Sia $k$ il numero di numeri che ho colorato. Dimostrare che $MCD(n,k) = n-k$
Colorando qualche numero
Re: Colorando qualche numero
Vabeh, per non farlo rimanere irrisolto...
Sia $X$ l'insieme dei numeri non colorati; vediamo che $|X|=n-k$
$0\in X$ perché se $0$ fosse colorato, allora per ogni $x$ grazie alla iii) uno tra $x$ e $-x$ deve essere colorato; ma per la i) devono esserlo entrambi. Allora avremmo colorato tutti i numeri in contrasto con la ii).
Inoltre per la i) se $a\in X$ allora $-a\in X$, dato che coloro sempre un numero ed il suo opposto.
Infine se $a,b\in X$ allora $a+b\in X$ perché se per assurdo fosse colorato, allora per la iii) uno tra $a,b$ dovrebbe essere colorato.
Ora, per ogni $a\in\mathbb Z/n\mathbb Z$ considero l'insieme $a+X=\{a+x:x\in X\}$; vediamo che $|a+X|=|X|=n-k$ per ogni $a$ (se fosse $a+x\equiv a+y$ avremmo $x\equiv y$).
Vediamo che succede se per qualche $a,b$ vale $a+X\cap b+X\neq\emptyset$; allora esistono $x,y\in X$ tali che $a+x\equiv b+y$, ovvero $a-b\equiv y-x\equiv y+(-x)$ e quindi $a-b\in X$; ma questo vuol dire che $a+X=b+a-b+X=b+X$ perché dato un elemento $x\in X$, data la terza proprietà, $x+X=X$.
Quindi gli insiemi $i+X$ sono un po' uguali e un po' disgiunti; vediamo che ogni elemento di $\mathbb Z/n\mathbb Z$ sta in uno di questi insiemi. Prendiamo ora una copia per ogni insieme disgiunto (prendiamo ovvero degli $a_i$ tali che $a_i+X\neq j+X$ per ogni coppia) e vediamo che allora $(a_1+X)\cup\dots\cup(a_h+X)=\mathbb Z/n\mathbb Z$; ma sono disgiunti quindi vale $|a_1+X|+\dots+|a_h+X|=n$, ovvero $h\cdot(n-k)=n$, cioè $n-k\mid n$ che è la tesi dato che $\gcd(n,k)=\gcd(n,n-k)$.
Ok, può sembrare un casino, ma in realtà mi potevo fermare alla terza riga... infatti considerando $\mathbb Z/n\mathbb Z$ come gruppo (ciclico) rispetto all'addizione, le tre proprietà del testo, riscritte come ho fatto io, mi dicono che $X$ è un sottogruppo di $\mathbb Z/n\mathbb Z$; allora posso invocare Lagrange che mi dice che l'ordine di un sottogruppo divide l'ordine del gruppo... in pratica tutte le cose sugli $i+X$ sono una dimostrazione di Lagrange...
Sia $X$ l'insieme dei numeri non colorati; vediamo che $|X|=n-k$
$0\in X$ perché se $0$ fosse colorato, allora per ogni $x$ grazie alla iii) uno tra $x$ e $-x$ deve essere colorato; ma per la i) devono esserlo entrambi. Allora avremmo colorato tutti i numeri in contrasto con la ii).
Inoltre per la i) se $a\in X$ allora $-a\in X$, dato che coloro sempre un numero ed il suo opposto.
Infine se $a,b\in X$ allora $a+b\in X$ perché se per assurdo fosse colorato, allora per la iii) uno tra $a,b$ dovrebbe essere colorato.
Ora, per ogni $a\in\mathbb Z/n\mathbb Z$ considero l'insieme $a+X=\{a+x:x\in X\}$; vediamo che $|a+X|=|X|=n-k$ per ogni $a$ (se fosse $a+x\equiv a+y$ avremmo $x\equiv y$).
Vediamo che succede se per qualche $a,b$ vale $a+X\cap b+X\neq\emptyset$; allora esistono $x,y\in X$ tali che $a+x\equiv b+y$, ovvero $a-b\equiv y-x\equiv y+(-x)$ e quindi $a-b\in X$; ma questo vuol dire che $a+X=b+a-b+X=b+X$ perché dato un elemento $x\in X$, data la terza proprietà, $x+X=X$.
Quindi gli insiemi $i+X$ sono un po' uguali e un po' disgiunti; vediamo che ogni elemento di $\mathbb Z/n\mathbb Z$ sta in uno di questi insiemi. Prendiamo ora una copia per ogni insieme disgiunto (prendiamo ovvero degli $a_i$ tali che $a_i+X\neq j+X$ per ogni coppia) e vediamo che allora $(a_1+X)\cup\dots\cup(a_h+X)=\mathbb Z/n\mathbb Z$; ma sono disgiunti quindi vale $|a_1+X|+\dots+|a_h+X|=n$, ovvero $h\cdot(n-k)=n$, cioè $n-k\mid n$ che è la tesi dato che $\gcd(n,k)=\gcd(n,n-k)$.
Ok, può sembrare un casino, ma in realtà mi potevo fermare alla terza riga... infatti considerando $\mathbb Z/n\mathbb Z$ come gruppo (ciclico) rispetto all'addizione, le tre proprietà del testo, riscritte come ho fatto io, mi dicono che $X$ è un sottogruppo di $\mathbb Z/n\mathbb Z$; allora posso invocare Lagrange che mi dice che l'ordine di un sottogruppo divide l'ordine del gruppo... in pratica tutte le cose sugli $i+X$ sono una dimostrazione di Lagrange...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: Colorando qualche numero
Bene 
Lo scopo del problema era proprio quello di notare la struttura di sottogruppo del complementare (mascherato nelle ipotesi) e poi concludere applicando Lagrange xD
Per chi non conosce Lagrange secondo me è più facile notare che se non coloro un certo $a$, allora non coloro neanche $MCD(a,n)$ e se non coloro neanche $b$ allora non coloro neanche $MCD(a,b)$. Quindi l'insieme dei numeri non colorati viene generato dall'MCD dei suoi elementi (prendendo anche l'MCD con $n$) e quindi la sua cardinalità è un divisore di $n$.
Lo scopo del problema era proprio quello di notare la struttura di sottogruppo del complementare (mascherato nelle ipotesi) e poi concludere applicando Lagrange xDPer chi non conosce Lagrange secondo me è più facile notare che se non coloro un certo $a$, allora non coloro neanche $MCD(a,n)$ e se non coloro neanche $b$ allora non coloro neanche $MCD(a,b)$. Quindi l'insieme dei numeri non colorati viene generato dall'MCD dei suoi elementi (prendendo anche l'MCD con $n$) e quindi la sua cardinalità è un divisore di $n$.