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

s : s i are integers, s i ≥

i = 1 s i = s

n

B = 0 ,

Then A ⊂ B, and the following equality

min
s

f ( s )= min

s

f ( s ) (3.41)

∈ B ∈ A

is satisfied. That is to say, the minimum of ( 3.32 ) subject to ( 3.33 ) is obtained with
an s ∈ A.

Proof. The relation A ⊂ B is clear. To proof equality ( 3.41 ) first let us suppose d > 0 .

n
∑
i =

Let s ∈ B be given, then s i = s and s i = a i + δ i is satisfied, where δ i , i = 1 , 2 ,..., n ,

1

are integers. If every δ i different from zero has the same sign (that is δ i ≥ 0for

= , ,...,

i 1 2 n )then

n
i = 1 s i =

n
i = 1 a i +

n
i = 1 δ i = s − d +

n
i = 1 δ i

n
i = 1 δ i = d

⇒

and so s ∈ A . If, on the contrary, not all the δ i have the same sign, let us call

H 1 = { i : δ i > 0 }, H 2 = { i : δ i < 0 }.

We can write

n
i = 1 s i =

n
i = 1 a i + ∑

H 1 δ i + ∑

+ ∑
i H 1 δ i + ∑ H 2 δ i =

s − d

H 2 δ i =

s .

i ∈ i ∈ ∈ i ∈

δ i for i

Then

i ∈ H 1 δ i =

d − ∑

i ∈ H 2 δ i >

d , and we can select K ⊂ H 1 and ∈ K such that

∑

n
∑
i =

δ i are integers, 1 ≤ δ i ≤ δ i and

1 δ i =

d . Now we can build s ∈ A as follows

s i = a i + δ i

for i ∈ K ⊂ H 1 ,

s i = a i for i ∈ K .

We h ave

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

2

= i ∈ K c i ( s i − r i )

2

+ i ∈ K c i ( s i − r i )

2

f ( s − r )=

≥ i ∈ K c i ( s i − r i )

2

+ i ∈ K c i ( a i − r i )

2