Vrijeme: 02:09

Ukrainski lanac | Ukraine chain #4

Taras također voli igrati igrice na računalu. Jedna od njih je sljedeća: postoji ploča 7 \times 7, a na ovoj ploči može, ali i ne mora biti jedan bojni brod veličine 2 \times 2, a on je nevidljiv. Dopušteno mu je postaviti nekoliko detektora u neke ćelije ploče. Nakon što su postavljeni i nakon što pritisne gumb "Idi", svaki detektor će reći (svi odjednom) sadrži li bojni brod ćeliju s tim detektorom. Koji je najmanji broj detektora potreban da bi se sigurno moglo reći je li bojni brod prisutan ili ne, i ako jest -- reći njegovu točnu poziciju?
Taras also likes to play computer games. One of them is the following: there is a board 7 \times 7, and there may or may not be one battleship of the size 2 \times 2 on this board, and it is invisible. He is allowed to place a few detectors in some cells of the board. Once they are placed and once he presses the button "Go", each detector will tell (all at once) whether the battleship contains the cell with this detector. What is the smallest number of detectors required to surely be able to tell whether the battleship is present or not, and if it is -- tell its exact position?