Tools to Manage Search Games on Lattices - Search Theory: A Game Theoretic Perspective - page 40

s 1 =

s 1 − 1

s i = s i , 2 ≤ i ≤ n − 1

s n = s n + 1

= =

Now, from Lemma 3 with h 1and k n it follows

s 1 , s 2 ,..., s n )

( , ,..., ) − (

f s 1 s 2 s n f

n 1

i = 2

−

s i

=( − − ) ( −

s i ) ≥

.

s 1 s n 1 P 2 0

m −

If this difference is greater than 0 then f ( s 1 , s 2 ,..., s n ) is not a minimum. If the

s 1 , s 2 ,..., s n ) difference is equal to 0 then f ( s 1 , s 2 ,..., s n )= f ( and we can remove

the set of integers { s 1 , s 2 ,..., s n } from set S to find the minimum of f and the proof

of the lemma is complete.

To state the following theorem we will write

s 1 = a = s − b ,

s 2 = b =[ s / 2 ] , (3.22)

s i = 0 , i > 2

Theorem 4. Lets,n,m,beintegers 0 < s < 2 m, n ≥ 3 . Then the minimum of function

f ( s 1 , s 2 ,..., s n ) defined by ( 3.14 ) for integers s 1 , s 2 ,..., s n , satisfying ( 3.15 ) is either

q − 1

(

n − q − 1

K =( ms − np ( p + 1 ))( m − p − 1 ) m − p ) (3.23)

where p =[ s / n ] and q = s − pn, achieved with the values s i = s i defined by ( 3.18 ), or

K =( m n − 2

ms − 2 ab ) , (3.24)

= − , =[ / ] =

where a s b and b s 2 , achieved with the values s i s i defined by ( 3.22 ).

Proof. Given a set of integers s 1 , s 2 ,..., s n satisfying ( 3.15 ), the symmetry of the

function ( 3.14 ) allows us to assume that

s 1 ≥ s 2 ≥ ...≥ s n .

s i

n − 1

If inequality

s i ≤

2thenitfollowsfromLemma 4 that

∑

i = 2

m −

f ( s 1 , s 2 ,..., s n ) ≥ f ( s 1 , s 2 ,..., s n )

q − 1 n − q − 1

=( ms − np ( p + 1 ))( m − p − 1 ) ( m − p )

with s i defined by ( 3.18 )and p and q defined by ( 3.19 ). Now let us suppose that