Problema 20 della gara a squadre

[ercolete]

La fortezza in cui devono entrare i nostri ha 2013 finestre e $s$ torri di sorveglianza. Date 2013 sfere nello spazio che lo dividono in regioni, consideriamo due regioni adiacenti se hanno in comune almeno una superficie estesa bidimensionale; $s$ è il massimo valore, al variare della posizione delle sfere, del minimo numero di colori che servono per colorare queste regioni in modo che per ogni coppia di regioni adiacenti, le due regioni siano colorate con colori diversi. Quante torri di sorveglianza ha la fortezza?

[enigma]

Dimostriamo che due colori sono sempre sufficienti a prescindere dalla disposizione delle sfere. Coloriamo una regione di blu o di rosso a seconda che sia contenuta in un numero pari o dispari di sfere: questa colorazione funziona perché spostandosi tra regioni adiacenti il numero di sfere che contengono la regione cambia esattamente di 1. Conclusione: $s=2$.

Commento. Vedi il problema 6 Cadet del Kangourou di quest'anno.