Problema galeriei de arta

[DanDumitrescu]

O galerie de arta are forma unui n-gon.Determinati numarul minim de paznici necesari pentru a pazi galeria,oricare ar fi forma n-gonului.

[dangerous storm]

Am o intrebare:in ce mod pazeste un gardian?Adica pazeste la un anumit unghi(adica are vederea limitata) sau in alt fel?

[DanDumitrescu]

Nu exista nicio restrictie din acest punct de vedere.Ideea este de a imparti n-gonul in triunghiuri si sa coloram varfurile triunghiului in rosu,verde si albastru astfel incat fiecare triunghi sa aiba varfurile colorate in cele trei culori.Vom considera numarul minim de varfuri colorate in rosu si vom pune fiecare gardian in punctele rosii ei pazind astfel toate zidurile galeriei.Un numar minim este parte intreaga de n/3.

[dangerous storm]

Pai daca gardianul poate pazi in orice mod,atunci este de ajuns si un gardian....

[DanDumitrescu]

Intr-adevar,enuntul este destul de ambigu.Problema acasta este in carte lui Arthur Engel la capitolulu de demonstrari prin colorare.Problema are ca scop de fapt ideea de a imparti n-gonul in triunghiuri cu diagonale care sa nu se intersecteze.Cred totusi ca gardianul poate pazi maxim 2 ziduri.

[gigelmarga]

Citiţi cartea asta: http://goo.gl/CFOQd0

[Laurențiu Ploscaru]

Uitați, măi copii.

http://en.wikipedia.org/wiki/Art_gallery_problem