[HOME - BASE Cinque - Appunti di Matematica ricreativa]
Il problema della galleria d'arte
Quanti guardiani servono e dove bisogna piazzarli per
sorvegliare una galleria d'arte?
Immaginate di essere i proprietari di una Galleria d'Arte. Fra
pochi giorni la vostra Galleria ospiterà un'esposizione di quadri del famoso
pittore Pablo Dalì.
Poiché quadri esposti sono preziosissimi, ogni punto della galleria deve essere
sorvegliato costantemente a vista da fidati guardiani. Dovete però ridurre al
minimo le spese di sorveglianza.
Le domande quindi sono:
Occorre inoltre tener conto delle seguenti informazioni:
|
Ogni guardiano, simboleggiato con un bollino rosso, ha un campo visivo
di 180°, cioè può vedere davanti a sé, alla propria destra, e alla
propria sinistra, ma non dietro di sé. A ciascun guardiano viene
assegnata una posizione fissa dalla quale può vedere una certa zona della
Galleria. |
Se la pianta del locale da sorvegliare è un poligono convesso, è
sufficiente un solo guardiano posto in un qualunque punto del perimetro. |
Se invece la pianta è un poligono concavo, cioè ha delle
"rientranze", allora un solo guardiano potrebbe non essere
sufficiente. Nella figura, ad esempio, il guardiano può vedere tutto il
locale tranne la zona colorata di grigio. |
Il primo piano
Il primo piano della vostra Galleria d'Arte ha la seguente pianta.
Impiegherete tre guardiani per sorvegliarlo o ve ne basteranno soltanto due?
Il secondo piano
Questa è la pianta del secondo piano. Potete farla sorvegliare interamente
da un solo guardiano, ma qual è la posizione giusta?
Il terzo piano
Ed ecco la pianta del terzo piano. Qui il compito è un po' più difficile:
dovete utilizzare il numero minimo di guardiani e fare anche in modo che si
vedano a vicenda
L'attico
Siamo giunti finalmente all'attico. La sua pianta è simmetrica e abbastanza
semplice, ma vi basterà un solo guardiano per farla sorvegliare interamente?
Esiste una strategia generale per affrontare questo problema?
Riformuliamo il problema così:
-
Quante telecamere situate sui vertici
della pianta di un locale, avente la forma di un poligono semplice di n
lati, sono necessarie e sufficienti per sorvegliare tutti
i punti del locale stesso?
-
Quante telecamere
situate sui vertici della pianta di un locale, avente la forma di un poligono
semplice di n lati, e contenente h "fori" sono necessarie
e sufficienti per sorvegliare tutti i punti del locale stesso?
Le telecamere hanno hanno un campo visivo di
360° (si può supporre che ruotino ad altissima velocità)
I "fori" sono ostacoli alla visuale.
Possono essere immaginati come colonne, aventi la pianta a forma di poligono
semplice, che vanno dal pavimento al soffitto.
Nota storica.
Il problema fu posto per la prima volta da Victor Klee nel 1973 in
una discussione con Vasek Chvatal.
"Quante guardie situate sui vertici della pianta di un locale,
avente la forma di un poligono semplice, sono necessarie e sufficienti
per sorvegliare tutti i punti del locale stesso?"
Vasek Chvatal, nel 1975, ha dimostrato che sono sufficienti floor(n/3)
guardie.
Nel 1978 Steve Fisk ne ha dato una dimostrazione più semplice
basata sul teorema delle due orecchie "Two Ears" di Gary
Meister.
Vasek Chvatal |
Victor Klee |
Bjorling-Sachs e Souvaine (1991,
1995) e Hoffman et al. (1991) hanno dimostrato che per sorvegliare un locale di n
lati e contenente h fori sono sufficienti floor((n+h)/3) guardie.
Chvátal, V., A combinatorial theorem in plane geometry, JCT (B), 18 (1975)
39-41.
Fisk, S., A short proof of Chvátal's watchman theorem, JCT (B) 24 (1978) 374.
La funzione matematica floor(a) è l'arrotondamento del numero reale a
all'intero superiore.
Ad esempio, floor(7/3) = 3.
Ultimo aggiornamento: aprile 2005
Risposte
& riflessioni
Il primo piano
Il primo piano della vostra Galleria d'Arte ha la seguente pianta.
Impiegherete tre guardiani per sorvegliarlo o ve ne basteranno soltanto due?
Il secondo piano
Questa è la pianta del secondo piano. Potete farla sorvegliare interamente
da un solo guardiano, ma qual è la posizione giusta?
La posizione esatta è segnalata dal bollino rosso. In qualunque
altra posizione, ad esempio quella occupata dal bollino blu, una parte del
locale non è visibile.
Il terzo piano
Ed ecco la pianta del terzo piano. Qui il compito è un po' più difficile:
dovete utilizzare il numero minimo di guardiani e fare anche in modo che si
vedano a vicenda
L'attico
Siamo giunti finalmente all'attico. La sua pianta è simmetrica e abbastanza
semplice, ma vi basterà un solo guardiano per farla sorvegliare interamente?
Sito Web realizzato da Gianfranco Bo