Problema 20 della gara a squadre

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Problema 20 della gara a squadre

Messaggioda ercolete » 06/05/2013, 18:22

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?
ercolete
 
Messaggi: 12
Iscritto il: 24/04/2013, 9:09

Re: Problema 20 della gara a squadre

Messaggioda enigma » 15/05/2013, 19:19

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. :mrgreen:
Avatar utente
enigma
 
Messaggi: 124
Iscritto il: 19/03/2013, 20:11


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti