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

s

k =

n
j = 1 c − 1

j

then

c i r i = k , i = 1 , 2 ,..., n . (3.36)

n
∑

n
∑

and from ( 3.36 ) and the relation x i = r i = s we have

i = 1 i = 1

n
i = 1 c i x i =

n
i = 1 c i ( x i − r i )

n
i = 1 c i r i

2

+

and the proof is complete.

If we denote x =( x 1 , x 2 ,..., x n ) and therefore r =( r 1 , r 2 ,..., r n ) , equality ( 3.35 ) can

be written briefly as

f ( x )= f ( r )+ f ( x − r ) . (3.37)

From Lemma 5 we obtain the following considerations.

Remark 1. For any non-negative x =( x 1 , x 2 ,..., x n ) and y =( y 1 , y 2 ,..., y n ) such that

n
∑

n
∑ x i = s and y i = s , (integers or real), it follows that

i = 1 i = 1

n
∑
i = 1

n
∑
i = 1

n
∑
i = 1

n
∑
i = 1

c i x i ≤ c i y i ⇔

2 2 ,

(a) c i ( x i − r i ) ≤ c i ( y i − r i )

(b) f ( x ) − f ( y )= f ( x − r ) − f ( y − r ) .

Therefore, finding the point ¯

α =( α 1 , α 2 ,..., α n ) with α i integers, which minimizes

is equivalent to finding the point ¯ f ( s )= f ( s 1 , s 2 ,..., s n ) α which minimizes f ( s −

n
∑

r )= f ( s 1 − r 1 , s 2 − r 2 ,..., s n − r n ) where s =( s 1 , s 2 ,..., s n ) , s i are integers, s i = s ,

i = 1

and r =( r 1 , r 2 ,..., r n ) ,the r i given by ( 3.34 ).

Once the real numbers given by ( 3.34 ) have been obtained we determine the integers
a 1 , a 2 , ..., a n , such that

a i − 1 / 2 ≤ r i < a i + 1 / 2

that is to say

[ r i ] if [ r i ] ≤ r i ≤ [ r i ]+ 1 / 2

=

a i (3.38)

[ r i ]+ 1if [ r i ]+ 1 / 2 < r i < [ r i ]+ 1

where [ x ] denotes the integer part of x . Now let us write

b i = r i − a i (3.39)

and

n
i = 1 a i ,

d = s − (3.40)