Motto: Acolo unde ideile dau greş, vorbele sunt foarte la îndemână (Goethe)
C. Bătălie navală
O navă lungă de 4 unităţi se deplasează de-a lungul unei linii din plan. Viteza de deplasare este de M unităţi pe secundă (M constant).
La momentul iniţial, capătul din stânga al navei se află într-o locaţie N.
Valorile M, N sunt numere întregi necunoscute; de asemenea nu se ştie dacă nava se deplasează spre stânga sau spre dreapta.
În fiecare secundă tragi un foc la un punct de valoare întreagă. Dacă ai atins nava, ai câştigat şi jocul se termină.
Descrieţi o strategie care să asigure succesul în timp finit.
Autor Edwin Berlekamp, cu menţiunea că problema a fost folosită şi într-un interviu de angajare.
Textul in engleza al problemei:
A battleship 4 units long is traveling along the real line. It is moving with constant speed M units per second, M an unknown integer, but we do not know whether it is moving left or right. It starts with its left end at some location N, again an unknown integer.
At each second you can fire a shot at some integer point; if the shot strikes the battleship, the process ends and you have succeeded.
Describe a strategy that guarantees success in finite time.
Viteza de deplasare a navei poate fi mai mare decat lungimea ei?
Nu apare printre restrictii, ca M ar fi limitat. Problema are solutie pentru orice M si orice N numere naturale.