Optymalizacja przy danych warunkach

pitgot · Post autor: **pitgot** » 17 lut 2013, o 13:15

Na kwadratowej tablicy podzielonej na 36 jednakowych pól kwadratowych niektóre pola malujemy na czarno tak, aby każde pole zarówno "białe" jak i czarne miało co najmniej jednego sąsiada koloru czarnego. Przyjmujemy, że dwa pola sąsiadują ze sobą, jeżeli mają wspólny bok. Jaką najmniejszą liczbę pól takiej tablicy trzeba pomalować na czarno, aby spełnione były wyżej wymienione warunki?