OliForum Matematico

Abbiamo un insieme (finito) di punti del piano a coordinate intere.
È possibili colorarli di rosso e bianco in modo che, in ogni riga e colonna, la differenza tra il numero di rossi e il numero di bianchi sia 0, 1 o -1?

Buon lavoro!
Ah sì, dimenticavo: questo problema sarebbe IMO1986/6.

edriv ha scritto:Abbiamo un insieme (finito) di punti del piano a coordinate intere.

E' un insieme qualunque o il prodotto di due intervalli?

Un insieme qualunque.

Anzi, ora che ci sono aggiungo anche la bonus question:
È possibile fare una colorazione con le stesse proprietà, ma con i colori blu e verde?

edriv ha scritto:È possibile fare una colorazione con le stesse proprietà, ma con i colori blu e verde?

cosa intendi? colorazione a 4 colori?
perche' sostituire il bianco/rosso col blu/verde mi sembra cambiare poco

Sì, ovviamente stavo scherzando sugli altri due colori

Un bel problemino. Peccato che non ci si metta nessuno...

Ecco la mia.
-----------------------
Lemma: ]Sia S un insieme colorato rispettando le ipotesi. Una riga contiene un numero pari di punti, se e solo se la sua differenza rossi - bianchi è 0.

Dim.: Ovvia, considerando la parità dei punti bianchi e rossi sulla riga. []

Claim: Ogni insieme S si colora rispettando le ipotesi.

Dim.: Per induzione sul numero di punti dell'insieme S.

Se S = {}, ogni colonna e ogni riga hanno 0 punti colorati, quindi verifica.

Sia allora S un insieme con n+1 punti e di aver dimostrato la tesi per tutti gli insiemi con al massimo n punti.

Due casi:

1. Esiste un punto P sulla cui riga [colonna] ci sono un numero dispari di punti di S
2. Ogni riga/colonna contiene un numero pari di punti di S.

Caso 1.

Sia S' l'insieme con il punto P cancellato. S' è colorabile per ipotesi induttiva. Consideriamo la riga di P. Essa contiene un numero pari di punti, e quindi la sua differenza bianchi - rossi è 0. Se la colonna di P ha differenza +1 (su S'), posso colorare P di rosso. Se la differenza è -1, coloro P di bianco. Se la differenza è 0, posso colorare P a piacere. In ogni caso, la colorazione risultante di S è ok.

Caso 2.

Scelgo la prima riga di S, che chiamo R. S' è l'insieme ottenuto da S cancellando i punti su R. Si tratta di un insieme più piccolo e quindi, per ipotesi induttiva è colorabile.

Dimostro che:

i) ogni colonna di S' che contiene un punto cancellato, ha differenza +/-1; se non contiene nessun punto cancellato, ha differenza 0.
ii) ogni riga di S' ha differenza 0.
iii) il numero di colonne con differenza +1 (su S') è uguale al numero di colonne con differenza -1.

i): Dato che S ha un numero pari di punti su ogni colonna, su ogni colonna dove cancello un punto restano un numero dispari di punti di S'. Uso il Lemma.

ii): Ogni riga di S' contiene un numero pari di punti. Uso il Lemma.

iii): Considero X definito come il numero totale di punti rossi di S' meno i punti bianchi di S'. Dico che X=0. Infatti: X è la somma di tutte le differenze delle righe di S'. Per (ii) ogni differenza è 0 e quindi la loro somma è 0. D'altro canto, però, X è anche la somma di tutte le differenze delle colonne di S'. Per (i), X = numero di colonne con differenza +1 - numero di colonne con differenza - 1. Uguagliando a 0, trovo (iii).

Ripeto l'algoritmo del caso 1 su ogni colonna che contiene punti di S per colorare i punti cancellati: se la colonna ha differenza +1, coloro di rosso; se -1, di bianco.

Dimostro che così facendo si ottiene una colorazione di S che va bene. Per costruzione, ogni colonna di S che non contiene punti di R, è anche una colonna completa su S', e quindi ha differenza 0. Se invece una colonna contiene un punto di S e di R, allora contiene un numero dispari di punti di S' e, per come funziona l'algoritmo, il punto su R viene colorato in modo da avere differenza 0. Le righe di S diverse da R sono righe complete di S', e come tali hanno differenza 0, per (ii). Invece la riga R ha differenza 0 per (iii). []
-----------------------
Ciao. M.