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

n
2

1 s − [ s / n ]

s i ≤

] .

− − [ /

m m s 2

, ,..., < < ≥

Lemma 3. Lets,n,m,s 1 s 2 s n be integers such that 0 s 2 m, n 2 ,

n
i = 1 s i = s ,

0 ≤ s i ,

s n .
and f the function defined by ( 3.14 ). If for indexes h and k, one of them equal to 1 ,
the inequalities s h >

s 1 ≥ s 2 ≥ ...≥

0 and s k < m are satisfied and we build the new set of integers

given by

s h = s h − 1 ,

s k = s k + 1 ,

s i =

s i i = h , i = k ,

then the difference

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

( , ,..., ) − (

f s 1 s 2 s n f

is equal to

s i

− ∑
i = h , k

( s h − s k − 1 ) P ( 2

s i ) , m −

where

= ∏
j

P

k (

m − s j ) .

= h ,

Proof. By computing the difference

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

= ∑ i ( s i

j = i ( m − s j ) − s i j = i ( m − s j )) ,

(3.17)

we pay first attention only on those terms involving i = h and i = k , so that we find

that

s h ( s k ) s k ( s h ) s h ( m − s k ) P + s k ( m − s h ) P − m − P − m − P

= ∏
j

= 2 ( s h − s k − 1 ) P , where P

k (

m − s j ) .

= h ,

Bearing in mind that one of the indexes h or k is equal to 1, we can assure that
m − s i > 0 for each i = h , i = k . Then, for the remaining terms in ( 3.17 ) we can write