Am primit trei soluţii: de la Cristian Ciobanu, Zoltan Szabo şi Aurel Ionescu.

Le prezint pe toate, în ordinea expedierii.

1. Cristian Ciobanu:

Consideram axa ON, OM cu valori numere intregi, pozitive si negative.

Dupa care, luam pe rand cate un patrat incepand de la baza, patrate ce sunt centrate in (0,0), si a caror latura sa fie pe rand de 2, 4, 6, ....
Pentru fiecare patrat in parte, cautam (x,y) de pe patrat ce ar reprezenta un presupus N si M. Cu acest x si y, tragem urmatorul foc:
x+i*y, unde i reprezinta a cata tragere este (pleaca de la 1 si creste cu cate 1 la fiecare tragere).
De exemplu, pentru prima patratica cu latura de 2, vom avea:
1. x=-1;y=1: shoot: -1+1*1 = 0
2. x=0; y=1: shoot:0+2*1 = 2
3. x=1; y=1: shoot:1+3*1 = 4
4. x=1; y=0: shoot:1+4*0 = 1
5. x=1; y=-1: shoot:1+5*(-1) = -4
6: x=0; y=-1: shoot:0+6*(-1) = -6
7: x=-1; y=-1: shoot:-1+7*(-1) = -8
8: x=-1; y=0: shoot: -1+8*0 = -1
In total pentru prima patratica am avut: 1*2*4 trageri.
Pentru a doua patratica vom avea nevoie de 2*2*4 trageri.
Pentru a 3-a patratica: 3*2*4
........
Mergem in felul acesta mai departe pana ajungem la patratica cu latura de MAX(|N|,|M|)+1 - adica maximum intre modul de N si modul de M +1.
Cand am ajuns aici, suntem siguri ca nava va fi nimicita, intrucat am simulat toate pozitiile de start din interiorul patratelului cu latura de
MAX(|N|,|M|)+1;
Deci numarul maxim total de trageri de care avem nevoie este: 1+1*2*4 + 2*2*4 +3*2*4 + ....+ [MAX(|N|,|M|)+1]*2*4=1+(1+2+...+[MAX(|N|,|M|)+1])*8=
1+ [MAX(|N|,|M|)+1]*[MAX(|N|,|M|)+2]*4
Intrucat numerele N si M sunt numere intregi cunoscute, rezulta ca numarul total de trageri de care avem nevoie este finit: 1+ [MAX(|N|,|M|)+1]*[MAX(|N|,|M|)+2]*4.

Acel +1 din numarul total de trageri (1+ [MAX(|N|,|M|)+1]*[MAX(|N|,|M|)+2]*4) provine din lovitura 0 (x=0, y=0) pentru a acoperi cazul in care M=0 si N=0, adica nava sta pe loc pe pozitia 0

2. Zoltan Szabo:

Trebuie să găsim o strategie prin care verificăm fiecare pereche (M,N) ce defineşte traiectoria navei, verificând atât la stânga cât şi la dreapta, întrucât nu ştim în ce direcţie se deplasează nava, fără să pierdem vreun caz pentru o valoare a lui N sau M.

Dacă am cunoaşte valoarea exactă a lui M şi N, atunci poziţia vasului în momentul t ar putea fi pe una din poziţiile:

·    N + t*M , dacă nava se deplasează spre dreapta

·    N - t*M  , dacă nava se deplasează spre stânga

Pentru a putea verifica fiecare pereche (N,M) vom aranja perechile într-un tablou bidimensional infinit, cu originea în colţul stânga sus, apoi vom parcurge toate elementele acestui tablou diagonal, investind în fiecare element-pereche (pe care îl vom numi în continuare element sau pereche) al tabloului două încercări, una pentru deplasarea navei spre sânga şi una pentru deplasarea navei spre dreapta.

Vom considera că N şi M sunt numere naturale nenule (includerea valorii 0 în soluţie nu schimbă metoda de lucru).

Construim tabelul pentru toate valorile naturale ale lui N şi M:

(1,1) (1,2) (1,3) (1,4) (1,5) (1,6) ...

(2,1) (2,2) (2,3) (2,4) (2,5) (2,6) ...

(3,1) (3,2) (3,3) (3,4) (3,5) (3,6) ...

(4,1) (4,2) (4,3) (4,4) (4,5) (4,6) ...

(5,1) (5,2) (5,3) (5,4) (5,5) (5,6) ...

(6,1) (6,2) (6,3) (6,4) (6,5) (6,6) ...

vom parcurge diagonal elementele pornind din colţul st-sus:

(1,1) (1,2) (2,1) (1,3) (2,2) (3,1) (1,4) (2,3) (3,2) (4,1) (1,5) (2,4) (3,3) (4,2) (5,1) ....

pentru fiecare pereche de numere vom face verificare în două direcţii, cu excepţia primei coordonate, pentru care, în momentul 0, st=dr.

Astfel vom trage câte un foc în coordonatele:

timpul 0. perechea (1,1)    :  1 + 0*1

timpul 1. perechea (1,2)   :   1 + 1*2   (dreapta)

timpul 2. perechea (1,2)   :   1 - 2*2    (stânga)

timpul 3. perechea (2,1)   :   2 + 3*1     (dreapta)

timpul 4. perechea (2,1)   :   2 - 4*1   (stânga)

timpul 5. perechea (1,3)   :   1 + 5*3   (dreapta)

timpul 6. perechea (1,3)   :   1 - 6*3   (stânga)

timpul 7. perechea (2,2)   :   2 + 7*2   (dreapta)

timpul 8. perechea (2,2)   :   2 - 8*2    (stânga)

...

timpul t.       perechea (N,M) :  N + t*M   (dreapta)

timpul t+1.  perechea (N,M) :  N - (t+1)*M   (stânga)

În acest fel, într-un număr finit de încercări vom parcurge toate diagonalele până ce ajungem la diagonala care conţine perechea (N,M).

De cât timp avem nevoie să localizăm nava care iniţial avea parametrii (N,M)?

Pentru a răspunde la această întrebare, vom denumi diagonalele cu suma celor două elemente ce formează perechea.

Astfel:

Diagonala 2, este formată din elementul (1,1) – conţine 1 element

Diagonala 3, este formată din elementele (1,2) (2,1) – conţine 2 elemente

Diagonala 4, este formată din elementele (1,3) (2,2) (3,1)– conţine 3 elemente

...

Diagonala M+N, este formată din elementele (1,M+N-1), (2, M-N-2), ... , (M+N-1, 1)  - conţine M+N-1 elemente

Elementul (M,N) se află pe diagonala M+N. Această diagonală conţine în total M+N-1 elemente, şi va fi parcursă parţial.

Diagonala M+N-1 va fi verificată în întregime şi conţine M+N-2 elemente.

Astfel putem da câte o limită inferioară şi superioară pentru numărul de încercări.

Avem formula 1 + 2 + 3 + ... +(M+N-2) = (M+N-2)(M+N-1)/2

Ţinând cont de  faptul că fiecare element este ţintit de două ori cu excepţia primului element, obţinem:

(M+N-2)(M+N-1) -1 <= nr de încercări <= (M+N-1)(M+N) -1

Valorarea exactă a momentului se poate calcula ţinând cont că pe ultima diagonală, elementul este ţintit în unul din momentele 2M-1 sau 2M

Altfel spus nava care are parametrii (N,M) va fi nimerit în cel mai rău caz în momentele

(M+N-2)(M+N-1)+2M-2 sau (M+N-2)(M+N-1)+2M-1, dar ţinând cont, că are lungime 4, există posibilitatea ca accidental să fie lovit şi mai devreme.

3. Viorel Ionescu:

La un moment t nava se afla in punctul N+Mt. Vom stabili ca pentru M pozitiv nava se deplaseaza spre dreapta, iar daca M e negativ nava se va deplasa spre stanga.

In fiecare secunda trage un foc la un punct de valoare intreaga, deci t=1,2,3….

Dac