Journal of Mathematical Sciences, Vol. 80, No. 2, 1996

G A M E S OF S E A R C H A N D C O M P L E T I O N B. I. M o d e l '

UDC 519.837

Introduction The subject of this paper is a broad class of multistep game processes, which have received little attention so far. We shall call these processes games of search and completion. The study of games of search and completion, carried out below from the standpoint of the guaranteed result, is interesting both in the mathematical respect (as a consequence of the rather unexpected properties of these games [13, 14]) and in that of possible applications, in particular to studying various sorting processes

[14]. The games of search and completion considered in the article can be represented as follows. Suppose we are given the interval (0,1) of the number line. The points of (0,1) are divided during the game into labeled and unlabeled points. Before the game, m points from (0,1) are labeled (m is a natural number). Two players take part in the game, making moves in turn. On the first move, the first player searches through the labeled points, adding I of them to the unlabeled ones, l < m (we call this process unlabeling). On the second move, the second player augments the set of remaining m - l labeled points, adding I unlabeled points to it (we call this process labeling). On the next move, the first player searches again through rn labeled points and adds l of them to the unlabeled ones. Then the second player augments the set of m - l labeled points by labeling l unlabeled points, etc. The game continues as the move number runs through the set of natural numbers. We say that a point remains labeled after the end of the game if it remains labeled starting from some move. The first player tries to guarantee the least number of points that can remain labeled after the end of the game, whereas the goal of the second player is quite the opposite. The case where the players know only the current state of the game, i.e., the current labeled points, does not present any particular difficulty. In fact, if the second player constantly labels those l points that were unlabeled by the first player during the previous move, then the same I points will become labeled and unlabeled in turn and the remaining m - l points will remain labeled after the end of the game [14]. The case where the players know the current state and have the complete information about the past, does not cause difficulties, either. Indeed, if the first player unlabels those I points in the same order in which they became labeled during the moves of the second player, then each labeled point will become unlabeled, i.e., none of the points will remain labeled after the end of the game [14]. In what follows, from the standpoint of guaranteed result of the search, we shall consider the case which is the most difficult (from the mathematical point of view). In this case, the players know the current state, but the only information concerning the past available to them is the number of the move. Note that the study of this case from the standpoint of guaranteed possibilities of completion does not cause difficulties. In fact, if the first player unlabels points in the same order in which they were labeled by the second player, then each labeled point will become unlabeled, i.e., the second player cannot guarantee that at least one point will remain labeled after the end of the game [14]. The games of search and completion will be studied first without the use of the continuum hypothesis and then with its use [15]. Within the framework of the first approach (without the use of the continuum hypothesis), the following statement can be proved: the first player can guarantee that no more than [ m / ( / + 1)] points will remain labeled after the end of the game (here [.] is the integral part of the number). Translated from Itogi Nauki i Tekhniki, Seriya Sovremennaya Matematika i Ee Prilozheniya. Tematicheskie Obzory, Vol. 18, Vychislitel'naya Matematika i Kibernetika, 1994. 1072-3374/96/8002-1699 $15.00 9 1996 Plenum Publishing Corporation

1699

When the continuum hypothesis is used, the greater possibilities of the first player can be shown, namely, the first player can guarantee that for all m and l at most one point will remain labeled after the end of the game. The games of search and completion played jointly as welt as simultaneous parties are of particular interest both from the viewpoint of studying more complex problems and from the viewpoint of unexpectedness of the results obtained. The simultaneous game of search and completion considered in this paper can be represented as follows. There is a finite or a countable number of intervals (0,1) of the real lines. The first player (assume for definiteness that he is always the same) plays the game of search and completion in each interval with the corresponding second player. On any odd move, the first player can carry out a search in any interval, where the corresponding second player should make a completion on the next move with an even number. The simultaneous party continues as the number of the move runs through the whole set of natural numbers. By analogy, we say that the point remains labeled after the end o f the party if, starting from some move, it remains labeled in one of the games. The first player tries to minimize the number of points which remain labeled after the party, whereas the aim of the second players is quite the opposite. The case where the players know only the current state when they think of the next move (in each game for the first player and at least in a corresponding one for the second players) presents no special problems. Indeed, if the corresponding second player labels permanently the points that were added to the unlabeled points by the first player on the previous move, then the same points will become labeled and unlabeled in turn, and the rest of the points will remain labeled after the party [14]. The case, where the players not only know the current state, but possess the complete information concerning the past moves (for the first player in each game, and at least in his game for each second player) does not present any difficulty either. Indeed, if the first player unlabels points in the same order, irt which the second player labeled them, then each labeled point will become unlabeled, i.e. none of the points will remain labeled after the end of the game [14]. Below we study a rather more mathematically complicated case from the standpoint of the guaranteed possibilities of search. In this case (which is intermediate his intermediate with respect to the above cases) the players know the current state when choosing the next move, but the only available information about the past is the number of the current move (in each game for the first player and at least in his own game for each second player). Note that the study of this case presents no problems from the standpoint of the guaranteed possibilities. Indeed, if the first player unlabels points in the same order in which they were labeled by the second player, then each labeled point will become unlabeled, i.e., the second players cannot guarantee that at least one point will remain labeled after the end of the party [14]. The simultaneous parties of search and completion are studied with the use of the continuum hypothesis. In this case, it is possible to reveal the unexpected possibilities of the first player, namely, he can guarantee that not more than one point will remain labeled after the end of the party. Thus, the least result of the party guaranteed for the first player may turn out to be not better than the le~t guaranteed result of any constituent game. The paper consists of three sections. The games of search and completion are studied from the standpoint of guaranteed possibilities of the search, when the players are informed only of the current state and the number of the current move. In Sec. 1, we study the games of search and completion without the use of the continuum hypothesis. In Sec. 2, the games of search and completion are studied with the use of the continuum hypothesis. In Sec. 3 the simultaneous games of search and completion are studied with the use of the continuum hypothesis. Note that the games of search and completion can be considered as infinite-step processes of successive choice of decisions [la]. Processes of this kind have been poorly studied. They are considered, as a rule, [4, 18, 20] within the context of the infinite-step antagonistic games with complete information and in this context 1700

the problem of the existence of the value of the game is studied [16, 19]. In the papers [7-9, 13] a series of the main propositions of the method of dynamic programming [2] are generalized to infinite-step processes. Infinite-step processes are considered in [5, 6, 10, 17] in connection with the problems of differential games [1]. Infinite-step game processes related to games of search and completion are also considered in [ll, 12]. 1. G a m e s of Search a n d C o m p l e t i o n . T h e F i r s t A p p r o a c h 1.1. Description of the G a m e s We give a precise description of the games of search and completion which will be considered in the first and the second section. The games can take place in arbitrary sets of continuum cardinality. Since we can always establish a one-to-one correspondence between sets of this kind and the interval (0,1) of the real line, we shall assume for definiteness that the games of search and completion take place in (0,1). Let (0,1) be an interval of the real line. The points of (0,1) are either labeled or unlabeled. Before a game begins, there is a set X0 C (0, 1), which consists of m labeled points, and the points from (0, 1)\X0 are unlabeled (m is a natural number). Two players take part in the game and make moves in turn. On his first move the first player searches through X0. In doing so, he subtracts an arbitrary set A1 C X0, which consists of l (l < m) labeled points from X0. Thereby, the points of Ax become unlabeled. Thus, the set Xl = Xo\A1 C (0, 1) appears after the first move. This set consists of m - l labeled points and the points from (0, 1)\X~ are unlabeled. On the second move, the second player completes Xt by adding an arbitrary set/31 C (0, 1)\Xt of I unlabeled points to Xl. In doing so, he labels the points of Bt. Thus, the set X2 = X~ U/31 C (0, 1) consisting of rn labeled points appears in (0,i) after the second move, whereas the points from (0, 1)\X2 remain unlabeled. Suppose there is a set X2k C (0, 1) of m labeled points before the (2k + 1)st move and the points from (0, 1)\X~k are unlabeled (k is a natural number). On the (2k + 1)st move the first player searches through X2k. In doing so, he subtracts an arbitrary set Ak+l C X2k, which consists of I labeled points, from X2k, and the points from Ak+l become unlabeled. Thus, the set X2k+l = X2~\Ak+t C (0, 1) appears in (0,1) after the (2k + 1)st move. It consists of m - I labeled points, whereas the points from (0, 1)\X2k+a are unlabeled. On the (2k+2)nd move the second player completes X2k+1 by adding an arbitrary set Bk+1 C (0, 1)\X2k+l of l unlabeled points to X2k+t. In doing this, he labels the points of Bk+i. Thus, after the (2k + 2)nd move, the set X2k+2 =

X2k+l U/3k+l C (0, 1)

of m labeled points is formed in (0,1) and the points of (0, 1)\X2k+2 are unlabeled. The game continues as the number of the move runs over the whole set of natural numbers. We assume that in the choice of a move each of the players knows the set of available labeled points as well as the number N of the current move. Any function a(.) which maps an arbitrary set X C (0, i) of cardinality rn and an odd number N to the subset A C X, consisting of l points, is called a strategy of the first player. By analogy, we call any function b(.) that maps an arbitrary set X C (0, 1) of cardinality m - l and the even point N, to a subset/3 C (0, [ ) \ X , consisting of l points, a strategy of the second player. We say that a point x E (0, I) remains labeled after the end of the game if x is contained in every set -u C (0, l), N >_ No of labeled points, where & is a natural number. By "P(Xo,a(.),b(.)) we denote the number of points which remain labeled after the end of the game, before which there was a set Xo C (0, l) consisting of m labeled points, and during which the first and the second player chose their moves according to the strategies a(.) and b(-), respectively. The first player tries to minimize and the second player tries to maximize the value of the functional 9(.). The game will be studied from the standpoint of the guaranteed results of the first player. We introduce the following function c(.), which represents the least result guaranteed by the first player, c(rn, l) = rain max ~(X0, a(.), b(.)). ~(.) b(.)

(1.1)

1701

Here, the minimum and maximum taken over all possible strategies of the first and second players, respectively, exist, since the functional T'(-) is integer-valued and bounded. Note that the function c(-) depends on the parameters m and l, but does not depend on the set X0 of the labeled points given before the game. In fact, let another set X~ C (0, i), which consists of m labeled points, be given before the game. W e establish a one-to-one correspondence between two intervals (0,1) of the real lines in such a way that the sets Xo of the first interval and the sets X~ of the second one correspond to each other. Then it is easy to see that the case, where the game begins from the search of X~ and takes place in the second interval, by virtue of the one-to-one correspondence thus established can be identified with the case where the game begins with the search of X0 and takes place in the first interval. Thus, the value of the function c(-) is the same for both cases, i.e., the function c(.) is independent of the set X0 of labeled points given before the game. Now we pass on to the study of the games of search and completion. For brevity, the game of search and completion with parameters m and I will be called the game (m, t). 1.2. T h e G a m e (2,1) The game (2,1) is the game of search and completion with parameters m = 2 and l = 1, i.e., there are two labeled points before this game and the first or second player decreases or increases by 1 the number of labeled points at each move, respectively. In choosing a move, the players know only the number of the move and the labeled points given at the current moment. The following proposition is true. P r o p o s i t i o n 1.2.1. The equality c(2,

:) = 1

holds for the game (2,1). We prove Proposition 1.2.1. Consider the game (2,1). We fix an arbitrary strategy a'(.) of the first player. Since for any initial set Xo and strategy b(.) of the second player the inequality

(x0, a'(-), b(.)) <_ : holds, in terms of (1.1) it is easy to see that to prove Proposition 1.2.I it suffices to show that for the given strategy a'(-) of the first player there exists a strategy b'(-) of the second player such that ~(X0, a'(.), b'(-)) = : holds independently of the initial set X0. A point x N E (0, 1) is called singular for an odd move N, if the strategy a'(-) prescribes that the first player unlabel x g from the set of two labeled points x g and x at the move N for any x E (0, 1)~{xg}. For any move with an odd number there can be not more than one singular point. In fact, if there were two singular points z y ~ yN, { x N yg} C (0, 1), for a move with odd number N, then the equalities a'({zg, y Y } ' g ) = {X N} and a'({zg, y N } , N ) = {yg} would hold simultaneously, which is impossible. Thus, for any move with an odd number there can be no more than one singul~.r point and, therefore, the system X ~ C (0, i) of all points singular for some move with an odd number is not greater than countable. Let a move of the second player for an arbitrary even move number N be considered. Then the strategy b'(:) prescribes that the second player, given a labeled point x E (0, 1), label a point y G (0, 1)\{z} such that if z E X', then y E (0, 1 ) \ X ' ((0, 1 ) \ X ' ~ g), and, if z E (0, 1)\X', then a ' ( { z , y } , g + 1) = {y} (for a given z such a point y exists, since otherwise x would be singular for the move with the number N + 1). Let the first and second players hold to the strategies a'(.) and b'(-), respectively. Then for any initial set, X0, ~ point z E (0, 1)\X' is permanently labeled starting from some move, i.e., it remains labeled after the end of the game, and therefore. 7P(X0, a(.), b(.)) = t. 1702

Thus, the proof of Proposition 1.2.1 is completed.

1.3. The G a m e (3,1) The game (3,1) is a game of search and completion with parameters m = 3 and l = 1, i.e., there are 3 labeled points before this game and the first or second player, diminishes or decreases, respectively, by 1 the number of labeled points, where before the choice of the move the players know only the number of the move and the labeled points known at the moment. The presence of an additional point, as compared with the game (2,1), does not lead to a value c(3, 1) of the function c(.) different from c(2, 1), and therefore, the following proposition is true. P r o p o s i t i o n 1.3.1. The following equality holds for the game (3,1):

c(3,1) = 1. We shall prove Proposition 1.3.1. Consider the game (3.1). As can be seen from (1.i), to prove Proposition 1.3.1 it suffices to show that: (a) there exists a strategy a*(-) of the first player such that for an arbitrary

initial set X0 and a strategy b(.) of the second player P(Xo, a'(')i

_< i holds; (b) for each strategy a'(.)

of the first player there exists a strategy b'(.) of the second player such that, independently of the initial set X0, the equality

b'(.))>__ 1 holds. First, we construct the corresponding strategy a'(.) of the first player. Consider the set {r} of all rational points r of the interval (0, 1). Since the set of all rational points of (0,1) is countable [15], it can be numbered by odd numbers in a way such that {r} = {r 1,r 3 , r s , . . . } . Let X C (0,1) be an arbitrary set consisting of three points. We say that r E {r} partitions X if there is at least one point from X in any interval (0, r] or (r, I). The interval is called singular, if it contains only one point from X. Obviously, there always exists at least one singular interval for r that partitions X, since, otherwise, both intervals (0, r] and (r, I) would have contained no less than two or no less than three points in X. Let a'(-) be a strategy such that for each partitioned r N E {r} of the set X C (0, l) consisting of three labeled points, a*(.) prescribes that the first player unlabel the point z E X, which lies in a special interval. Assume that there is an initial set X0 and a strategy b(-) of the second player for which "P(X0, a'(-), b(-)) > 1. Then there exist two points xt < x2, {x~,x2} C (0, 1) which are contained in each set XN C (0, 1) of the labeled points arising after the move with the number N >_ N', where N ~ is a natural number. Moreover, it is not difficult to see that there exists an infinite subsequence r i~ , r~'2,ri~,.., in {r}, all members of which partition each XN (where N > N') in a way such that xt < r '~ < x2, k = 1 , 2 , 3 . . . (here z1,~2, i3,.., are odd numbers). Then at the move with the number ik, for the number ik > N', the function a*(.) prescribes that the first player for the set Xik-1 of labeled points unlabel either xl or x2, since r ik partitions X,k_l and, either zl, or x2 lies in a singular interval. Therefore, {zl, z2} is not contained in Xi~?I! The contradiction obtained allows one to assert that, for every initial set X0 and strategy b(-) of the second player T'(Xo, a'(.),b(.)) <_ 1. We show now that for every strategy a'(.) of the first player there exists a strategy b'(-) of the second player, where 7)(Xo, a'('),b(-)) > 1, independently of the initial set X0. We fix an arbitrary strategy a'(-) of the first player and the point x' E (0, i). The point x 'v E (0~ 1)\{x'} is called singular for the move with an odd number N if for any x E (0, 1)\{xN,x '} 1703

there exists an odd number M > N such that for a move with an odd number N', N < N' < M, the strategy a'(-) prescribes for three labeled points x N, x', and x that the first player unlabel x' when N < N' < M and zN when N' = M. For any move with an odd number there exists not more than one singular point. In fact, if for a move with an odd number N there were two singular points z g ~ yN, {xN, yN} C (0, 1)\{xt}, then the following equalities would hold:

a'({x N, z', yx}, N') = {z'} when N < N' < M',

a'({xN, x',yN},M') = {x N} and a'({xN, x ' , y N } , g ') : {x'} when N _< N' < M", a'({x N, x'yg}, M") = {yN}, which is impossible (here M ' and M" are odd numbers not less than N). Thus, for each move with an odd number there can be no more than one singular point. Therefore, the set X' C (0, 1) of all points singular for some move with an odd number is not greater than countable, and there exists x" E (0, 1)\(X' U {z'}). Let the strategy b'(-) be such that for an arbitrary even number N and for any set X C (0, 1) that consists of two singular points, b'(.) prescribes that the second player label some point y E (0, 1)\X, which either coincides with z' if z' is unlabeled, or coincides with z" if z" is unlabeled and x' is labeled. In the case where x' and x" are labeled, b(-) is such that starting from the (N + 1)st move, z" is labeled until the first player unlabels y (when X = {x', x"} the point y exists, since otherwise z" would be singular for the move with the number N + 1). Let the first and second players hold to the strategies a'(-) and b'(.), respectively. Then, for each initial set X0 the first player either always unIabels x' or x" then some point in X0 remains labeled, or, starting from a move, x" remains constantly labeled, i.e., in either case some point remains labeled after the end of the game and, therefore, 79(X0, a'(-), b'(-)) _> [. Thus, the proof of Proposition 1.3.1 is completed. 1.4. T h e G a m e (3,2) The game (3,2) is a game of search and completion with parameters m = 3 and l = 2, i.e., there are three labeled points before this game, and on each move the first or second player decreases or increases the number of labeled points by two. In doing this, the players know just the number of the move and the labeled points available at the moment. The following proposition is true. P r o p o s i t i o n 1.4.1. The equality c(3, 2) = 1

holds for the game (3,2). We prove Proposition t.4.1. We consider the game (3,2). We fix an arbitrary strategy a'(-) of the first player. Since for any initial set Xo and strategy b(-) of the second player 7~(X0, a'(.), b(.)) < 1, by (1.1) it suffices to show that for a given strategy a'(-) of the first player, there exists a strategy b'(-) of the second player such that 7'(Xo, a'(-), b'(-)) = 1, independently of the initial set X0. The point x N E (0, 1) is called singular for the move with an odd number N if ~he strategy a'(-) prescribes that the first player at the move with the number N un[abel two points (one of which is x N) of three labeled points x N, xl, and x2 for any xl # x2, {xl,x2} C (0, t)\{xN}. t704

There can be no more than two singular points with odd numbers. In fact, if for a move with an odd number N there were three singular points x N ~ yN, x g gk z N, yN ~k z N, {x N, yg, z N} C (0, 1), then the inclusion {z N, yg, z N} C a'({x N, yN, zN}, N) holds, which is impossible. Thus, for any move with an odd number there can be no more than two singular points and, therefore, the collection X' C (0, 1) of all points that are singular for some move with an odd number is no more than countable. Consider a move with an arbitrary even number N. Let the strategy U(.) prescribe that the second player label two points y~ # Y2, {Yl,Y2} C (0, 1)\{x} such that if x e X', then {ya, y2} C (0, 1)\X' ((0, 1)\X' is an infinite set); if x E (0, 1)\X', then a({x,y~,y2},N + 1) = {Yl,Y2} (such points y~ and Y2 exist for a given x, since otherwise x would be singular for the move with the number N + 1). Let the first and second players hold to the strategy at(.) and b'(.), respectively. Then, for any initial collection X0 some point x E (0, 1)\X', starting from a move, is constantly a labeled one, i.e., it remains labeled after the end of the game, and therefore,

a'(-), b'(.)) = 1. Thus, the proof of Proposition 1.4.1 is completed. 1.5. A C o m b i n e d V e r s i o n of t h e G a m e s (3,1) a n d (3,2) Consider a game of search and completion, the structure of which is somewhat different from the one presented in Sec. 1.1 and is in a sense a combination of the games (3,1) and (3,2). Note that there can be various changes of the construction given in Sec: t.1. The main difference of the game studied here from the games in Sec. 1.1 is that the increase or decrease of the quantity of labeled points is not constant at every move. The combined variant of games (3,1) and (3,2) (we call it the game (3,2)' for the sake of brevity) can be characterized in the following way. There are three labeled points in (0,1) before the first move. At the moves with the numbers I + 4k the first player decreases the number of labeled points by 1, at the moves with the numbers 2 + 4k the second player increases by one the number of labeled points. At the moves with the numbers 3 + 4k the first player decreases the number of labeled points by two, and at the moves with the numbers 4 + 4k the second player increases the number of the labeled points by two. When choosing an arbitrary move, the players know only its number and the labeled points at hand (here k is a non-negative integer). In other respects, the construction of the game (3, 2)' is analogous to the construction presented in Sec. 1.1. In particular, an arbitrary function a(-) that maps any odd number N and the set X C (0, 1), which consists of three points, to a set A C X, consisting of one point if N = 1 + 4 k and of two points if N = a+4k, is called a strategy of the first player. A function b(.) that maps every even number N and the set X C (0, 1), consisting of two points, if N = 2 + 4 k , and consisting of one point, if N = 4 + 4 k , to a collection B C (0, 1)\X, consisting of one point, if N = 2 + 4k, and consisting of two points, if N = 4 + 4k, is called a strategy of the second player. By c'(3, 2) denote the least result which can be guaranteed by the first player, c'(3,2) = minmaxT~(X0,a(-), b(-)). =(.) b(.) Here, analogous to (1.1), 7)(X0, a(.), b(.)) is the number of points that remain labeled after the end of the game (3, 2)'. The initial set Xo C (0, 1) consists of three labeled points; the first and second players choose their moves with respect to the strategies a(.) and b(-), respectively. Note that, as in (1.1), the maximum and minimum taken in the definition of d(3,2) over all possible strategies of the first and second players, respectively, do exist, since the functional ~(.) is integral and bounded and the value of c'(3, 2) is independent of Xo. The following proposition is true. P r o p o s i t i o n 1.5.1. The equality ct(3, 2) = i 1705

holds for the game (3, 2)' for any initial collection Xo C (0, 1) that consists of three labeled points. We now prove Proposition 1.5.1. Consider the game (3, 2)'. We fix an arbitrary initial collection X~ and a strategy a'(-) of the first player. As for each strategy b(-) of the second player

79(Xo, a'(.), b(.)) < 1, then, obviously, it is enough to prove that for given X~ and a'(-) there exists a strategy b'(.) of the second player such that

(Xo, a'(-), b'(.))= t. The point x k E (0,1) is called singular for the moves with the numbers 1 + 4 k and 3 + 4k, if for any set X C (0, 1 ) , X 9 x k, of points labeled before the move with the number 1 + 4k, a n d the point x E (0, 1)\(X\a'(X, I + 4k)) labeled by the second player at the move with the number 2 + 4k, the strategy a'(-) prescribes that the first player unlabel x k at the move with the number 1 + 4k or 3 + 4k (from here on in this section, k denotes a non-negative integer as usual). For any k there can be no more than four points singular for the moves with the numbers i + 4k and 3 + 4k. Assume the inverse; then for some k = k' in (0,1) there are five pairwise different points x l , . . . , xs singular for the moves with the numbers 1 + 4k' and 3 + 4k'. Let the strategy a'(.) prescribe that the first player at the move with the number 1 + 4k t unlabel the point xx from the set of three labeled points xt, x2, x3 (zl, x2, x3 can be properly numbered). Then, since x2, x3 are singular for the moves with the numbers 1 + 4k ~ and 3 + 4k', at(.) prescribes that the first piayer at the move with the number 3 + 4k' from the set of three labeled points x,x2,:ca for any x 9 (0, 1)\{x2,xa} unlabel x2 and xs. Moreover,

1 + 4k') = Indeed, if

a'({xl,x2, x4}, 1 + 4k') = {x'},x' 9 {xl,x4}. then for any y 9 (0,1)\{x",x2},

{x"} = { x l , x , } \ f x ' } ,

a'({~",~2,y},a + 4k') = { x " , ~ d , since x", x2 are singular for the moves with the numbers 1 + 4U and 3 + 4U. Therefore, the equalities

a'(fx", x2, x3}3 4- 4k') --- {x2, xs} and a'({x", x2, x3}, 3 4- 4k') = {x", x2} hold. This is impossible, since xa ~ x". Thus,

a'({x,, x2, z4}, 1 4- 4k') -----{x2}, which implies that a'({x~,x4, z},3 + 4k') = {x,,x4} for each z 9 (0, 1)\{xt,x4}, since x~,x4 are singular for the moves with the numbers 1 4- 4k' and 3 4- 4k'. In an analogous way we obtain a'({x~,x~,xs},t + 4 k ' ) = {x~} (in the reasoning above it suffices to substitute xs for x4). Then

for any y 9 (0, 1)\{x~,x~}, since xl,xs are singular for the moves with the numbers 1 + 4k' and 3 + 4k', Therefore, the equalities

1706

and a " ( { z , , z 4 , z s } , 3 + 4k) = {z,,z5} should hold simultaneously. This is impossible since x, # Xs. Thus, for any k there can be no more than four points singular for the moves with the numbers I + 4k and 3 + 4k. Therefore, the set X ' C (0, 1) of all the points singular for some k at the moves with the numbers 1 + 4k and 3 + 4k is not greater than countable. Let the strategy b'(.) prescribe that the second player at the moves with the numbers 2 + 4k and 4 + 4k, k < k", label one or two points from the infinite set (0, 1 ) \ X ' , respectively, until a point x from (0, 1 ) \ X ' is labeled for some k = k" before the move with the number 4 + 4k" (it is easy to see that the required k always exists). For all subsequent moves with numbers 4 + 4k' and 6 + 4k, k >_ k", the strategy b'(-) prescribes that one label the points in a way such that z remains constantly labeled (this is possible, since otherwise z for some k > k" will turn out to be singular for the moves with the numbers 1 + 4k and 3 + 4k). Let the first and second players keep the strategies a'(.) and b'(-), respectively, and let X~ be the initial set. Then a point a: E (0, I ) \ X ' remains labeled after the game and, therefore,

V(Xo, a'(.), b'(,)) = t. Thus, the proof of Proposition 1.5.1 is completed. 1.6. T h e G a m e ( m , 1 ) We continue the study of the games of search and completion whose description was given in Sec. 1.1. Consider the game (m, 1) for an arbitrary natural m. The game (m, 1) is a game of search and completion with parameters m and 1, i.e., there are rn labeled points before this game and the first or second player decreases or increases by one the number of labeled points at each move, respectively. In choosing a move the players know only its number and the labeled points at hand. The following propositions are true. P r o p o s i t i o n 1.6.1. The relations 1 _ c(m, 1) < [,~/2],

where [-] is the integer part of a number, hold for any natural m not less than 2. We shall prove Proposition 1.6.1. Consider the game (m, 1). As can be readily seen from (1.1), to prove Proposition 1.6.1, it suffices to show that there exists a strategy a*(.) of the first player with the following properties. For any initial set Xo and strategy b(.) of the second player

V(Xo, a*(.),

b(.)) <

and for each strategy a'(-) of the first player there exists a strategy b'(.) of the second player such that V((X0,a'(.),b(.)) _< 1 independently of the initial set X0. First, we construct the corresponding strategy a*(-) of the first player. Consider the collection {R} of all possible ordered sets R = { r l , . . . , r ~ } , 0 < rl < ... < r= < 1, that consist of n = [m/2] pairwise different rational points r t , . . . , r,~ of the interval (0, 1) given in ascending order. Since the set of at[ collections of this type is countable [15], they can be enumerated by odd numbers, i.e., {R} = R t, R a, RS,.... Let X C (0, 1) be an arbitrary set that consists of m points. We say that R = {r~,..,,r,~} E {R} partitions X if there is at least one point from X in any interval (0, rl], (r~, r 2 ] , . , . , (r,~_~, r=], (r~, 1). This interval is called singular if it contains only one point from X. As can be readily seen, there exists at least one singular interval (if R partitions X). since otherwise there would be at least two points in any of the n + t intervals (0, rl], (rl, r2] . . . . , (r,~-l, r~], (r,,, 1) and there would be more than ,n points such that + I) =- ">_[m/'2] + 2 >

- l) + 2 = m ) .

1707

Let the strategy a*(.) be such that at a move with an arbitrary odd number N for an arbitrary partition R N = { r g , . . . , r N} E {R} of the set X C (0, 1) consisting o f m labeled points, a ' ( . ) prescribes that the first player unlabel x E X which lies in any singular interval. Suppose that there exist an initial set Xo and a strategy b(.) of the second player such that 79(X0, a'(.), b(-)) > n = [m/21. Then there exist n + 1 points x i , . . . , x , ~ + l , 0 < xl < ...,x,~+l < 1, contained in every set XN C (0, 1) of labeled points arising after the move with the number N > N', where N' is a natural number. Furthermore, it can be easily seen that there exists an infinite subsequence R q I R '~, Ri3,... in {R}. All members of this subsequence partition any XN when N > N' in a way such that the inequalities 0
ik

1
i~

2 <,..
"


1, k = 1 , 2 , 3 , . . . ,

hold for elements R ;k = { r ~ , . . . , r~k } (here il, i2, i3,.., are odd numbers). Then for ik > N', a*(:) prescribes that the first player unlabel x from {xi,..,,x,~+l} at the move with the number ik for the given collection Xik-i of labeled points, since R i~ divides Xik-1 and only a point from { X l , . . . , x~+i} can lie in a singular interval. Thus, { x l , . . . , x,~+l} is not contained in Xi~ ?!! The contradiction thus obtained allows one to assert that for any initial set X0 and strategy b(.) of the second player

a'(.), 6(.)) _<

= [m/2].

We now show that for any strategy a'(.) of the first player there exists a strategy 6'(-) of the second player, for which

a'(.),6'(.))

>__ i

independently of an initial collection Xo. We fix an arbitrary strategy a'(.) of the first player and a set X' consisting of m - 2 pairwise different points of the interval (0,1) (for m = 2 X ' = ~). A point z N E (0, 1 ) \ X ' is called singular for the move with an odd number N if for every x E (0, 1)\({x N} U X') there exists an odd number M > N such that for the move with an odd number N'i N < N' < M, the strategy a'(-) prescribes that the first player unlabel a point from X ' when N < N' < M and x N when N' = M from m labeled points comprising {x N, x} t5 X'. For any move with an odd number there can be no more than one singular point. In fact, if for some move with an odd number N there were two singular points x N ~ yN, {x N, yN} C (0, I ) \ X ' , then the relations

at({xN, y N} U Xt, N ') C X t for

N<_N'
a'({xN, y N } u X ' , M ')

{x N}

and

a'({xN,y N} U X ' , N ' )

C X'

for N < N' < M", a'({x N, gN} U X', M") = {yN} would hold simultaneously (here M' and M" are odd numbers not less than N), which is impossible. Thus, for any move with an odd number there can be not more than one singular point. Therefore, the collection X" C (0, 1) of all points singular for some move with an odd number is not more than countable, and there exists z" E (0, I ) \ ( X ' U X"). Let the strategy b'(.) be such that for a move with an arbitrary even number N and an arbitrary set X C (0, 1) consisting of m - 1 labeled points at hand, b'(-) prescribes that the second player label a point y E (0, 1 ) \ X , which can coincide with the least point of X' among those that are not 1708

contained in X (if there are unlabeled points in X') or can coincide with z" (if z" is unlabeled and all points from X' are labeled). In the case, where all points of X ' U {z'} are labeled, the strategy b'(-) is such that, starting from the (N + 1)st move, z" remains labeled until the first player unlabels y (for X = X' U {z'} the given point y exists, since otherwise x" would be singular for the move with the number N + i). Let the first and second players hold to the strategies a'(.) and b'(.), respectively. Then for every initial collection X0 either after some move the first player always unlabels only the points from X ' U {z*} and a point of X0 remains labeled, or, starting from a move, z" remains constantly labeled, i.e., in any case, a point remains labeled after the end of the game, and, therefore,

a'(.), b'(.)) >_ 1. Thus, the proof of Proposition 1.6.1 is completed. 1.7. T h e G a m e s (m, m - l ) a n d (m, m ) Consider the games (m, m - 1) and (m, m) for an arbitrary natural m. The game (ra, m - 1) is a game of search and completion with parameters m and m - 1, i.e., before the game there are m labeled points and at every move the first or the second player increases or decreases the number of labeled points by ra - 1, respectively. In choosing the move, the players know only the number of the move and the points that are labeled at the moment. The following proposition is true. P r o p o s i t i o n 1.7.1. The equality c(m, m - 1) = 1 holds for an arbitrary m f o r the game (ra, m - 1).

We prove Proposition 1.7.1. Consider the game ( m , m - 1). We fix an arbitrary strategy a'(-) of the first player. Since for any initial set X0 and a strategy b(-) of the second player "P(X0, a'(.), b(-)) < l, by (1.1) we easily see that (1.1) implies that to prove Proposition 1.7.1 it suffices to show that for a given strategy a'(.) of the first player there exists a strategy b'(.) of the second player, where ~'(X0, a'(-), b'(.)) = independently of an initial set X0. A point z jv E (0, 1) is called a singular point for a move with an odd number N if at the move with the number N the strategy a'(-) prescribes that the first player unlabel m - 1 points, one of which is z iv, from m labeled points x N, z t , . . . , x,~-i for any pairwise disjoint points x l , . . , x m - t , { x l , . . . , x ~ - t } C (0, 1)\{37N}. For any move with an odd number there can be no more than m - i singular points. In fact, if for a move with an odd number N there are at least m pairwise different singular points zN,...,z,~,lv {zNt,.. ., z N} C (0, 1), then the inclusion { X N , . . . , z N} C a ' ( { z l v , . . . , z~}, N) would hold, which is impossible. Thus, for any move with an odd number there can be no more than m - 1 singular points and, therefore, the set X ' C (0, l) of nil points singular for a move with an odd number is not greater than countable. Let the strategy b'(-) at a move with an arbitrary even number N and an arbitrary labeled point z E (0, 1) prescribe that the second player label m - 1 pairwise different points y l , . . . , y m - t , { y t , . . . , y,~-~ } C (0, t ) \ {z} such that if x is a singular for a move with an odd number, then y t , . . - , Y,~-I are not singular for any move with an odd number. If z is not singular for any move with an odd number, then at the (N + 1)st move the first player unlabels (yl,. -., g,,-1) (for a given x the points y l , . . . , y,~-i exist, since otherwise z would not be singular for the move with the number N + 1). Let the first at,d second players hold to the strategies a'(.) and b'(.), respectively. Then for each initial set X0 a point z E (0, I ) \ X ' is constantly labeled starting from some move, i.e., it remains labeled after the end of the game and, therefore, P(Xo, a'(.), b'(.)) = t. 1709

Thus, the proof of Proposition 1.7.1 is completed. The game (re,m) is called a game of search and completion with parameters equal to m, i.e., there are m labeled points before this game and at every move the first and second players decrease or increase by m the number of labeled points, respectively, In choosing the move, the players know only its number and the points labeled at the moment. Since no labeled point remains after each next move of the second player, the following proposition is obviously true. P r o p o s i t i o n 1.7.2. The equality

c(m, m) = 0 holds for an arbitrary natural m for the game (m, m). 1.8. T h e G a m e (re,l) Consider now the game of search and completion with arbitrary natural values m and I of the parameters, where l < m, i.e., the game (m, l) with m labeled points before it. At each move the first or second player decreases or increases the number of labeled points by I. In choosing a move, the players know only its number and the points labeled at the moment. The following proposition is true. Proposition 1.8.1. The relations

0 _< c(m, l) _< [m/(l + 1)], where [.] is the integral part of a number, hold for the game (rn, l) for arbitrary natural values m and l, l < m. We prove Proposition 1.8.1. Consider the game (m, l). Since the inequality 0 < c(m, l) follows immedi' ately from the definitions of the function c(-), it is easy to see that to prove Proposition 1.8.1, it suffices to show that there exists a strategy a*(.) of the first player, where for every initial set X0 and strategy b(.) of the second player

v(x0,a-(.), b(.)) < [m/(l + 1)] holds. We construct the corresponding strategy a*(.) of the first player. Consider the set {R} of all possible ordered sets R = { r l , . . . , r,~}, 0 < rl < ... < r,~ < 1, that consist of n = [rn/(l+ 1)] pairwise different rational points r l , . . . , r,~ of the interval (0,1) situated in ascending order. Since the set of all these sets is countable [15], it can be numbered by odd numbers, i.e., {R} = R 1,R 3, Rh,.... Let X C (0, 1) be an arbitrary set consisting of m points. We say that R = { r l , . . . ,r,~} E {R} divides X if there is at least one point from X in each interval (0, rl], (rl, r2], 9 9 (r~_~, r~], (r~, 1). The interval is called singular if it contains no more than l points from X. It is easy to see that there always exists at least one singular interval for each R that divides X, since otherwise in any of n + 1 intervals (0, r~], (r~, r~],..., (r~-l, r,~], (r,~, 1) there could be no less than l + 1 points and no less than m points in X such that ((l+l)(n+l)=(t+l)[m/(l+l)]+l+l

> (I + l ) ( m / ( l + l) - l) + l + l = m).

Let the strategy a'(-) be such that for a move with an arbitrary odd number N for every set X C (0, 1) partitioned by R N = { r ~ , . . . , r ~ } E {R} and consisting of m labeled points, a*(.) prescribes that the first player unlabel among other points all the points from a singular interval. Suppose that an initial collection X0 and a strategy b(.) of the second player can be found such that ~(X0, a*(-), b(-)) > n = [ m / ( l + t)]. Then there exist n + 1 points xt . . . . ,x,+l, 0 < x l , . . . < x,~+l < 1, contained in any set XN C (0, 1) of labeled points that occur after the move with a number N >__ N', where N' is a natural number. Furthermore, it is 1710

easy to see that there exists an infinite subsequence R '~, R '~, R'~,... in {R}, all members of which divide each XN when N > N' in a way such that for elements R ~ = { r ~ , . . . , r~k} the inequalities 0
*
k <...
~* < z , ~ + t < 1 , k =

1,2,3 . . . . ,

hold (here i~, i2, i3,.., are odd numbers). Then for ik > N' the strategy a*(.) prescribes that the first player unlabet x among others from {xl,...,z,~+t } at the move with the number ik for a given collection Xi~-i of labeled points, since R ~k divides Xi~-t and there is a point from {xa,... ,a:=+l} in any singular interval. Therefore, {zl . . . . ,x,~+l} is not contained in Xi,?!! The contradiction thus obtained allows one to assert that for any initial set Xo and strategy b(.) of the second player P(Xo,a'(.), b(-)) _< n = [m/((l + 1)1. Thus, the proof of Proposition 1.8.I is completed. 1.9. T h e G e n e r a l i z e d G a m e (re,l) Consider a game of search and completion with a structure that is a possible generalization of the construction presented in Sec. 1.1. The main difference of the game presented here from the game presented in Sec. 1.1 consists in the fact that the decrease or increase in the number of labeled points in the first of them is not constant for every move, but varies not exceeding a given number. The generalized game of search and completion with arbitrary natural values of the parameters m and l studied in this section (this game is called (m, l) ~ for the sake of brevity, l < m) can be characterized in the following way. There are m labeled points before the first move in (0,1). At any move with an odd number the first player decreases the number of labeled points by no more than l points and at any move with an even number the second player increases the number of labeled points by not more than l points. In doing this, the players know only the number of the move chosen and the points labeled at the moment. In other respects, the construction of the game (rn, l) ~ is analogous to the construction presented in Sec. 1.1. In particular, an arbitrary function a(-) that maps an arbitrary odd number N and a set X C (0, 1) to some set A C X consisting of no more than l points is called a strategy of the first player. An arbitrary function that maps an arbitrary even number N and a set X C (0, 1) to the set ~ ( C (0, 1)\X, which consists of no more than t points, is called a s~ra~egy of the second player. By c~ I) we denote the least result that can be guaranteed by the first player,

c~

l) = min sup P(X0, a(-), b(-)). ~(') %]

(1.2)

Here, analogously to (1.1), 7~(X0, a(.), b(-)) denotes the number of points remaining labeled after the end of the game (m, I) ~ Before this game, there existed the set Xo C (0, i), which consisted of m labeled points, where the first and second players chose their moves in accordance with the strategies a(.) and (-), respectively. Note that the minimum and supremum in the definition of c~ !) are taken over all possible strategies of the first and second players, respectively. As in (1.1), the minimum exists, since the functional P(.) is integral and bound from above and the value of cO(m, l) is independent of Xo. The following proposition is true. P r o p o s i t i o n 1.9.1. The relations

0 < c~

l) < [m/(l + t)1

hold for the game (m, I) ~ for arbitrary natural values of m and l, where I < re, and ever 9 initial set Xo C (0, 1) consisting of m labeled points ([.] denotes the integral part of a number). We prove Proposition 1.9.1. Consider the game (m, t) ~ Since the inequality 0 _< c~ !) foitows immediately from the definition of the function cQ(.), by (1.2) it is easy to see that to prove Proposition 1.9.1 it 1711

suffices to show that there exists a strategy a'(-) of the first player, where for each initial set Xo and strategy b(.) of the second player the inequality

p(x0, a'(-), b(.)) _< [m/(l + t)] holds. We construct the corresponding strategy a'(-) of the first player. Consider the set {R} of all ordered sets R = {rl . . . . . r,,}, 0 < rl < .,. < r,~ < l, consisting of n = [m/(l + 1)] pairwise disjoint rational points of the interval (0,1) situated in ascending order. Since the set of all sets of this kind is countable [15], it can be enumerated by odd numbers, i.e., {R} = R ~, R 3, RS,.... Let X C (0, 1) be an arbitrary set, where the number of points is no less than n + 1 and no greater than m. We say that R = { r l , . . . , rn} E {R} partitions X, if there is at least one point from X in any of the intervals (0, rl], (r~, r2],..., (r,,_~, r,~], (r,, 1). An interval is called a singular one if it contains at most l points from X. It is easy to see that there is at least one singular interval for R that partitions X, since otherwise there would be no less than l + 1 points in any of n + 1 intervals (0, r~], (rl, r~],..., (r,~_t, r,~], (r,~, i) and there would be more than m points in X such that

> (l + 94

((l+l)(n+l)=(l+l)[m/(l+l)]+l+l

+ l)-

l) + l + l = m ) .

Let the strategy a'(.) be such that at the move with an arbitrary odd number N for an arbitrary set X C (0, l) consisting of p labeled points, it prescribes that the first player unlabel all the points for p _< l, and for p > l unlabel some l points. If max{l,n} < p _< m and R N = { r N , . . . , r~} E {R} divides X, then these l points should include all the points lying in a singular interval (here p is an integer non-negative number). Suppose that there is an initial set X0 and a strategy b(.) of the second player such that P(Xo,a'(.),b(-))

> n = [m/(l +

1)].

Then there exist n + 1 points x l , . . . , x , ~ + l , 0 < xx < ...x,~+l < i, contained in every set X~ C (0, 1) of the labeled points, which occur after the move with the number N > N', where N ' is some natural number. Furthermore, it is easy to note that there is an infinite subsequence R il R i2, R i d , . . . , in {R} such that all its members partition every XN for N >_ N ' in a way such that

0
< x 2 < r ; k < . . . < x , , < r ' ~ ~
1,2,3,...,

(here it,iz, i3 are odd numbers). Then for ik > N' the strategy a*(-) prescribes that the first player, at the move with the number ik for a given set Xi~-i consisting of p, n + 1 < p < rn, labeled points, or if n + 1 < p < l, unlabel all the points or if max{l, n} < p < m unlabel z among all other points from { X l , . , . , z,~=~}, since R ~ partitions Xi~-~ and there is a point from { z ~ , . . . , x,,+~} at every singular point. Therefore, { z l , . . . , x~+t} is not contained in X~ in any case?!! The contradiction thus obtained allows one to assert that for any initial collection X0 and strategy b(.) of the second player the inequality

V(Xo, a*(.),b(.)) < n = [rn/(I q-1)] holds. Thus, the proof of Proposition 1.9.1 is completed. For t = 1, the results obtained in this section can be strengthened, namely the following proposition is true. P r o p o s i t i o n 1.9.2. The relations

i < c~

l) <_ [m/2],

where [-] is the integral part of a number, hold for the game (rn, I )~ for an arbitrary natural value ra greater than one and an arbitrary initial set Xo C (0, l) consisting of rn labeled points. We prove Proposition 1.9.2. Consider the game (m, I) ~ Since the inequality c~ 1) _< [rn/2] follows immediately from Proposition 1.9.1, it is obvious from the definition of the function cO(-) that to prove 1712

Proposition 1.9.2 it suffices to show that for each strategy a'(.) of the first player there is a strategy b'(-) of the second player, for which !

I

"P(X0, a (.), b (.)) ;> 1 independently of the initial set .g0. We fix an arbitrary strategy a'(-) of the first player and the set X' consisting of m - 2 pairwise different points of the interval (0,1) (for rn = 2 X' = 0). The point x g E (0, 1 ) \ X ' is called singular for the move with an odd number N if for any x 9 (0, 1)\({x N} U X') there exists an odd number M >_ N such that at the move with an odd number N', N < N ~ _< M, the strategy at(-) prescribes that the first player not unlabel any point from m points labeled by the moment or unlabel a point from X ' when N <_ N ~ < M and to unlabel x N for N' = M. There can be no more than one singular point for every move with an odd number. In fact, if there were two singular points x N 7~ yN, {x N, yg} C (0, 1)\X', for a move with an odd number N, then the following relations would hold simultaneously:

a'((x

yN} U X', N') C X '

forN<_N'
yN} U X ' , M ' ) = {xN},

a ' ( ( J , yN} U X', N') C X' forN
a'({xN,y N} U X ' , M " ) = {yN}. The latter is impossible (here M ~ and M" are odd numbers no greater than N). Thus, for every move with an odd number, there can be no more than one singular point. Therefore, the set X " C (0, 1) of all points singular for some move with an odd number is not greater than countable, and there exists z* E (0, 1 ) \ ( X ' U X"). Let the strategy b'(-) be such that at the move with an arbitrary even number N for every set X C (0, 1) consisting of m points labeled by the moment, b'(.) prescribes that the second player not label any point. For any set X C (0, L) consisting of m - 1 points labeled by the moment, the strategy b'(-) prescribes that t h e s e c o n d player do not label a point y E (0, 1 ) \ X , which either coincides with the least of the points from X' not contained in X (if there are unlabeled points in X') or coincides with x* if z* is unlabeled and all points of X ' are labeled; in the case where all the points of X' U {x*} are labeled, y is such that starting from the ( N + 1)st move z* remains labeled until the first player unlabels y (when X = X ' U {z*} the point y exists, since otherwise x* would be singular for the move with the number N + 1). Let the first and second players hold to the strategies a'(.) and b'(-), respectively. Then for any initial set Xo either after some move the first player unlabels only the points from X' U {x'} (if any), whereas a point of -g0 remains labeled, or, starting from a move z* remains constantly labeled, i.e., in any case some point remains labeled after the end of the game, and, therefore,

7~(Xo, a(.),b(.)) > i. Thus, the proof of Proposition 1.9i2 is completed. Since, for l = m, after every next move of the first player there can remain no labeled points, the following proposition is obvious. P r o p o s i t i o n 1.9.3. The equality = 0

holds for the game (rn, rn) ~ for an arbitrary natural value of m and an arbitrary initial set Xo C (0, 1) consisting of m labeled points. 1713

1.10. U n s o l v e d P r o b l e m s In concluding the first section, we formulate two main groups of problems not yet solved. These problems are related to the games of search and completion considered above. The first group of problems: Find c(m, l) for the games of search and completion with arbitrary natural values of the parameters m and l, where l < m - 1. The second group of problems: Find c~ l) for the generalized games of search and completion with arbitrary natural values of m and l, where l < m - 1. These problems are interesting from the mathematical point of view, and their solution may be a natural development of the results obtained in Secs. 1.2-1.9. A certain development in the solution of the problems formulated above can be accomplished by using the continuum hypothesis. These problems are studied in the next section. 2. G a m e s o f S e a r c h a n d C o m p l e t i o n . A n A p p r o a c h T h a t U s e s t h e C o n t i n u u m H y p o t h e s i s 2.1. P r e l i m i n a r y R e m a r k s In Sec. 2 we continue the study of the games of search and completion using the continuum hypothesis, whose definition was given in Sec. 1.1. Application of the continuum hypothesis in the games of search and completion allows one to obtain a sharper upper bound for the function c(-) introduced by equality (1.1) as related to Proposition 1.8.1. Namely, it is possible to prove that for arbitrary natural m and l, where l < m, the inequality c(m, l) < 1 holds (in Proposition 1.8.1 we established the inequality c(m, l) <_ [rn/(l+ 1)] without the use of the continuum hypothesis). We begin consideration of the games of search and completion with the game (4,1), since the application of the continuum hypothesis to the games (2,1), (3,1), and (3,2) cannot strengthen the results obtained earlier in Propositions 1.2.1, 1.3.1, and 1.4.1, respectively. 2.2. T h e G a m e (4,1) The game (4,1) is a game of search and completion with parameters m = 4 and l = 1, i.e:, there are four labeled points before this game and at each move the first or second player decreases or increases the number of labeled points by one. In choosing a move, a player knows only its number and the points labeled at the moment. Proposition 1.8.1 implies the inequalities 1 < c(4, 1) _< 2. The use of the continuum hypothesis allows one to establish that the following proposition is true. P r o p o s i t i o n 2.2.1. The equality 4 4 , 1) = 1

holds for the game (4,1). We prove Proposition 2.2.1. Consider the game (4,1). Since Proposition 1.6.1 implies directly the inequality c(4, 1) > l, from (1.1) it can be easily seen that to prove Proposition 2.2.1 it suffices to show that there exists a strategy a'(.) of the first player such that for every initial set Xo and strategy b(.) of the second player the inequality P(X0, a'(.), b(-)) _ 1 holds. Construct the corresponding strategy a'(.) of the first player. We establish a one-to-one correspondence between the points of the intervals (0,1) and the ordinal numbers of the second number class K0 (this is possible if we accept the continuum hypothesis [15]) and denote by 7(() the threshold number that belongs 1714

to K0 and corresponds to the point ( of the interval (0,1). Consider the direct product (0, 1) x (0, 1) and its subsets Rt~ = {(C,r/):C = ~,r/E (0,1) and 7(~r >- 7(q)}, =

(0,

=

and

>

where tc E (0, 1) is fixed arbitrarily. Note that all R~, ~ R~,2x E (0, 1), are countable [15], so that each of them can be enumerated, and, moreover, for any point (~, 7) E (0, 1) • (0, 1) one of two inclusions holds: either (~,r/) E R~ (when 7(~) -> 7(r/)), or (~,q) e R~ (for 7(7?) > 7(~))- Let there be a non-empty set X* consisting of no more than three points of the interval (0,1), and a point x', 0 < x' < min, ex. x. We say that x' is singular with respect to X" and a natural number L if (z', x*) E R~. for some x* from X* and (z', z') has the number L in R~.. Let there be a point x", max~ex, x < x" < 1. Analogously, we say that z" is singular with resoect to X* and a natural number L if (x., x") E R~. for some x. from X* and (x,, x") has the number L in R 1 As can be easily seen, there can be no more than three singular points in any of these cases. We denote by {r} the set of all rational points r of the interval (0,1). Since the set of all rational points (0,1) is countable, it can be enumerated, i.e., {r} = {r~, r2, r3,...}. We denote by q~, q2, q3,- 99 the ascending sequence of all odd prime numbers and introduce the number M = 2 9 3 2. Consider an arbitrary set X consisting of four points of the interval (0,1) and the number n such that the number k of the points in X N (0, r~], where r~ E {r}, satisfies the inequalities 1 _< k _< 3. Let for these X and n the strategy a'(-) of the first player possess the following properties: (1) at the move with the number qn

N=

MqtLq2+ 2 i - - 1,1 < i <

M/2,

prescribes that one unlabel y' E X F1 (0, r,~] such that if there is a point y~ in X N (0, r~] with the number j' in the set of points belonging to (0, r,~] situated in ascending order, singular with respect to a'(X,N)

X r (r~, 1) and L, where j ' mod(4-k).=~, then Y' = Yl,'" (2) at the move with the number qr.

N = Mqtq2 L + 2i - l,1 < i < M / 2 , a*(X, N ) prescribes to unlabel y" e X N (r~, 1) such that if there is a point y~ in X N (r,~, 1) with the number

j " in an ascending set of points that belong to (r~, 1) and are singular with respect to X N (0, r,~] and L, where j,, moa(k}, y,, = z, then = y~ (here i, L are arbitrary natural numbers). n

qn

Note that the sets {Mq~Lq2 + 2i - 1} and {Mq~q2 L + 2i - 1} of the numbers considered do not contain equal elements and are pairwise disjoint. Assume that there are an initial set )to and a strategy b(.) of the second player, for which T~(Xo, a'(.), b(.)) > I. Then there exist two points y~, y2, {y~, y2} C (0, 1), contained in every set X N C (0, 1) of labeled points that arise after the move with the number N > N*, where N" is a natural number. Moreover, r,~. E {r} can be found such that ya <_ r,~. < ye and n" >__ :V" (rF is a natural number). Moreover, either (y~,y2) E R2v2 and has some number L' in R ~y~, or (yt, singular with respect to X N ~ (r~., Assume first that for N >__ N" Q, by 5"( the number Mq~ q'z. Note

y2) E R~ and has some number L" in R lug. Thus, for N >_ N* either y~ is 1) and L', or y~ is singular with respect to XN ~ (0, r~.] and L". the point y~ is singular with respect to X N r3 (r~., 1) and L'. We denote that

N~ =.v~ q~ q.~ > n" >_ N ' .

1715

Let there be k~ points in XN( C3(0, r,,.] after the move with the number Ni" and let yl have the number j'~ in the ascending set of points from (0, r,,.] singular with respect to XN~. O (r,,., 1) and L' (here k~ is a natural number, where 1 < k~ < 3). Then XN(+t ~ y~, if k~ = I, and if k[ > l, then the first player unlabels yl at the move with the number N; = N~" + 2i', - l, i',

m~

=

) .r

.t

t

1,, 1 _< t, _< 4 - k, _< 3,

if yl E XN~-I and the second player did not label the points from (r~.a) at the previous moves after the move with the number N~', or after some move with the number N f = N{" + 2i~', 1 _<7'_< 4 - k~ _< 3, there will be k 2I _-_ k~l - 1 points in XN~, (3 (0, vn*], 1 _< k 2l _< 2 (i~' is a natural number). Let yt have the number J2" I in the ascending order of the set of points from (0, r,,. 1 singular with respect to Xu;, N (r,,., 1) and L'. Then again

XN;,+~ ~ y~ for k~ = 1. When k~ > l, the first player unlabels y~ at the move with the number Ns = N~' + 2(i[' + i~) - 1, i;' + i;

mod(4-k~)

=

.t

-t

32,1 < z 2 < 4 - k

t

2<3,

if Yt E XNI-t and at the previous moves after the move with the number N f the second player did not unlabel points from (r=., 1) or after some move with the number

N;' = N ( + 2i~', 1-< i~' -< 4 - k'2 < 3 , there will be k~ = k~ - 1 = 1 points in XN~, N (0, r,,.] (q' is a natural number). That means that if gt E XN;,, then the first player unlabels Vl at the move with the number N~' + 1. Thus, in the case where ya is singular with respect to XN N (r=., 1) and L', the first player unlabels yl at the move with the number N' =~vtql ,- q2~q = + 2 i ' - i

> N * , l _ < i ' - < M/2,

where i' is a natural number, i.e., yx ~ XNN,, which contradicts the fact that Vl belongs to any set XN when

N>_N*. Assume now that y2 is singular with respect to XN N (0, r,~.] and L" for N >- - N*. By N 1. t t we denote the number Mql

q> Note that

N 1"" = l v'"l q lq~':q2 > n * >_ N*. Let XN.,, N (r~., 1) contain k~' points after the move with the number N~'", and y2 have the number j~' in the ascending set of points that belong to (r~., 1) and are singular with respect to XN~,, N (0, r=.] and L" (here k'( is a natural number, 1 _< k~' _< 3). Then Xx.,,+t ~ y2 for k~' = t and for k~' _> 1 either the first player unlabels g2 at the move with the number

N~'=N~"+2z9 "t/z - l , ~ l "tt

rllo d ( 4 - k l it ) "tt

=

Jl,1
if Y2 E XN~'-I and the second player did not label points from (0, r=.] at the previous moves after the move .t!

with the number N t , or after some move with the number j~;tt

,tt

.~tt

.,it

It

=N 1 +2 h ,1-
there will be k~' = k x' - 1, 1 _< k~' < 2 points in XN~,, A (r~., 1)

(i7" is a natural number). Let y2 have the

.tt

number -h in the ascending ordered set of points that belong to (r~., 1) and are singular with respect to XN2.,, O (0, r,~.] and L". Then again X v.,,+t ~ Y2 for k)' = I, and for k~' >_ 1 the first player unlabels g~, at the move with the number

,%' = 1716

.,,

+ 9_(

,,

+

-

.,

1, i'(' + ,2

m o d ( 4 - k "2 ) "tt

=

h,

<

.It

< 4 -

tt

< 3,

if Y2 E XNI,-t and the second player did not label the points from (0, r..] at the previous moves after the move with the number N ( ' , or there are k~' = k2' - 1 = 1 points in X v;,, N (r.., 1) after some move with the number

N~"=Nf'+2i~,

tt

,,kit

l
II

<3,

(i~ II is a natural number). This means that if y2 E XN;,, then the first player unlabels Y2 at the move with the number N~" + 1. Thus, in the case where y2 is singular with respect to XNM (0, r,~.] and L" for N > N ' , the first player unlabels Y2 at the move with the number N" =

~1 q2+ 2i" - I > N ,

1 < i"

<-M/2,

where i" is a natural number, i.e., y2 r XN-. This contradicts the fact that y2 belongs to every set X u when

N>N*. The contradiction thus obtained allows one to establish the impossibility of the inequality ~'(X0, a(.), b(.)) > i for any initial set X0 and strategy b(.) of the second player. Therefore,

~(Xo, a'(-), b(.)) _< i for any X0 and b(.). Thus, the proof of Proposition 2.2.1 is completed. 2.3. T h e G a m e (re,l) Consider now the game of search and completion with arbitrary natural values m and I of the parameters, where l < m, i.e., the game (rn, l), where there are m labeled points before the beginning and at every move the first or second player decreases or increases the number of labeled points by l, respectively. In choosing moves, the players know only the numbers of the moves and the labeled points at the given moment. The inequalities 0 <- c(m, l) <_ [m/(l + 1)] are proved in Proposition 1.8.1. The use of the continuum hypothesis allows one to obtain a sharper estimate for c(m,l), namely, it allows one to establish that the following proposition is true. P r o p o s i t i o n 2.3.1. The relation

0 <- c(m, l) < 1 holds for the game (m, t) for arbitrary natural values rn and l, where l < m. We prove Proposition 2.3.1. Consider the game (re, l). Since the inequality 0 < c(m,l) follows immediately from the definition of the function c(.), it is easy to see from (1.1) that to prove Proposition 2.3.1, it suffices to show that there exists a strategy a'(.) of the first player such that for any initial set X0 and strategy b(-) of the second player ~(Xo, a*(-), b(.)) <- 1 holds. We construct the corresponding strategy a'(-) of the first player. We establish a one-to-one correspondence between the points of the interval (0,1) and the ordinal numbers of the second number class K0 (this is possible if we accept the continuum hypothesis [15]) and denote by 7(~) the ordinal number that belongs to K0 and corresponds to the point ~ of the interval (0,1). Consider the direct product (0, 1) • (0, 1) and its subsets Rt~ = { ( ~ , q ) : ~ = r~,q E (0,1) and "),(n) >_ (q)}, R2~ = { ( ( , q ) : ~ = (0, I),r/ = ~: and 7(n) > 7(~)}, where n E (0, 1) is fixed arbitrarily. Note that all R~, R~, x E (0, 1), are countable [15]; therefore, each of them can be enumerated. Moreover, for every point (~, q) E (0, l) • (0, l) one of two inclusions holds: either 1717

(~,r/) E R~ (when 7(~) > 7(r/)) or (~,r]) E R~ (when 3,(17) > 7(~)). Let there be a nonempty set ~ " that consists of no more than r n - 1 points of the interval (0, 1), and let a point x ~ be such that 0 < x' < min17ex, x. We say that x ~ is singular with respect to X" and a natural number L if for some x" from X" (x ~, x*) E R~. and (x ~, x") has the number L in R~.. Let there be a point x" such that m a x , e x , x < x" < 1. Analogously, we say that x" is singular with respect to X" and a natural number L if for some x. from X" (x., x") E R 117 , and (x., x") has the number L in R 117. It is easy to see that in each case there can be no more than m - 1 singular points. By {r} we denote the set of rational points r of the interval (011). Since the set of rational points (0,1) is countable [15], these points can be enumerated, i.e., {r} = {rl, r 2 , . . . , }. We denote by ql, q=, qa,... a sequence of ascending-ordered odd prime numbers and introduce the number M = 2(m - l) 2. Let for an arbitrary set X that consists of m points of the interval (0,1) and the number n such that the number k of points in X M (0, r,~], where r,, E {r}, satisfies the inequalities 1 < k < rn - 1, the strategy a*(-) of the first player possess the following properties: (1) at the move with the number N=MqqS'q2+2i-1,

1
either a * ( X , N ) C X M ( 0 , r~] i l l < k, or a ' ( X , N ) D X f q ( 0 , r,~] i f l >_ k. In the case where the interval X M (0, r,] contains a point y~ with the number j ' in the ascending-ordered set of points that belong to (0, r,~] and are singular with respect to X N (r,,, 1) and L, where j ' (2) at the move with the number

rood(m-k).

*.

=

z, a*(X, N ) 9 Yl,

N = Mq~q~ L" + 2i - 1, I < i < M / 2 , or a*(X, N ) C X N (r,~, 1) if l < m - k, or a ' ( X , N ) D X M (r,~, 1) if I _> m - k. In the case where the interval X N (r,~, l) contains a point y~ with the number j " in the ascending-ordered set of points that belong to (r~, 1) and are singular with respect to X Cl (0, r,~] and L, where j " rood(k). = z, a * ( X , N ) 9 Y29 (here i , L are arbitrary n

qn

natural numbers). Note that the sets of numbers considered {Mq~Lq2 + 2i - 1} and {Mql,q2 L + 2i - 1} do not contain equal elements and are pairwise disjoint. Assume that there are an initial set X0 and a strategy b(.) of the second player, for which ~(x0,~'(.),

b())

> t

Then there exist two points Yl < Y2, {Yt,Y2} C (0, 1), contair/ed in every set X N C (0, 1) of labeled points that occurs after the move with the number N _> N*, where N* is a natural numbe~. Furthermore, there is r~. E {r} such that y~ < r,~. < y2 and n" > N* (n" is a natural number). Moreover, either (y~,y~) E R Yz2 --and has the number L ' i n R 2Y 2 ' or (yl ~ y2) E R Y1l and has the number L " i n R~

'

i.e., for N ->- N* e i t h e r y l is

singular with respect to X N fq (r~., 1) and L', or Y2 is singular with respect to XN fq (0, r,~.] and L". Assume first that yl is singular with respect to XN M (r,~., 1) and U when N > N*. By N~" denote the number M q %'q~ Note that 1 rt*

N;'

, x qlqL' q2 > n" > = lvl

N*, ,~r

/

"/

Let, after the move with the number N l , there be k l points in X x ; , N (0, r,~.] and y l have the number 31 in the ascending-ordered set of points that belong to (0, r~.] and are singular with respect to X~r;, O (r,~., 1) and L' (here k't is a natural number, where 1 < k'~ < m - 1). Then for k'~ < l we :,ave XN;,+t ~ Yl and for k~ > l either the first player unlabels Yl at the move with the number .,'v'~ = N ?

1718

t

+ 2.z. , t _ 1,z.,I ~od(,,-~,,) = j ' l , t < _ z.,l < _ r n - k l <, _ r n - l ,

if Yl E XN~-I and for the pre,~ious moves after the move with the number N~" the second player has not unlabeled the points from (r,,., 1) or after a move with the number N~'

Nf+,h,

1

kl < m

l,

there will be k~ points in XN( 13(0, r,,.], 1 < k~ < k~ - 1 (i~', k~ are natural numbers). Let Yz have the number j~ in the ascending ordered set of points that belong to (0, r~.] and are singular with respect to XN;, N (r,,., t) and U. Then XN;,+t ~ Yx, if k~ < l, and for k~ > l either the first player unlabels yx at the move with the number I

.,t

I

N3 = N ( + 2i~', I<_ h < m - k2 < m - l, if yl E XN~-I and the second player has not unlabeled points from (r,~., 1) at the previous moves after the move with the number N ( , or after a move with the number .,~t

N~'=N~'+2i'2' , l < ~


!


there will be k~ points in Xx;, 13 (0, r,~.], 1 < k~ < k~ - 1 (q', k~ are natural numbers) etc. Thus, after a move with an odd number N*', N f < N*' < N ( + 2(m - l)(ra - l - 1), there will be no more than l points in XN., N (0, r~.] if the first player does not unlabel yl at the moves with the numbers from N~" to N " and then XN.,+x ~ Yl. Therefore, in the case where yx is singular for N > N* with respect to XN A (r~., 1) and L', the first player unlabels Yl at the move with the number N'=

lvlql ' " q~" q2 + 2i' - 1 > N*, t < i' < M/2,

where i' is a natural number, i.e., y~ f[ XN,, which contradicts the fact that yt belongs to any set XN when N>N'. Assume now that Y2 is singular with respect to XN 13 (0, r,~.] and L" for N >_ N*. By N I denote the uttt

~wtt/lt/2 . Note that N? " = Mqtq2 , qb- > n* >__N ' .

Let, after the move with the number N ( ' , there be k~' points in XN(, 13 (r,~., 1) and Y2 have the number j~' in the ascending-ordered set of points that belong to (r~., 1) and are singular with respect to X~v(, 13 (0, r~.] and L" (here k~' is a natural number, where i < k~' < m - 1). Then XN;,,+~ ~ y2 for k~' <_ l and for k~' > l either the first player unlabels y~ at the move with the number : .tt . .. .. mod(r~-k'/),. .. . N~' N 1 + 2 h - l , h = j , . 1 < h < m - k~ < m - l , if Y2 E XN~,-1 and the second player did not label points from (0, r~] at the previous moves after the move ,ll

It

.~tl

.$ll

with the number N t , or after a move with the number N ( ' = N~' + 2 h , 1 < h

II

<_ m - k 1 < m - I, there

are k~' points in X N f , 13 (r,~., 1), 1 < k~' _ l either the first player unlabels y2 at the move with the number .,,

N~' = .~vz

+ 2(i7"

+ i~') -

..,,

~, ~

.it m o d ( m - k ~ ' ) ' I t

+ ,~

=

';r

It

~:, ~ < ~ <_ m - ~ _< ~ - t,

if y~ ~ .V,v~,_~ and at the previous moves after the move with the number N~" either the second player has not labeled points from (0, r~.], or after a move with the number It

N~ = N ~

It

9 ..It

--

..l!

+ - z 2 , t <~ 2 < m - k ~

II


there are k~' points in XNf. N (r,~., 1) (i;", k~' are natural numbers), etc. Thus, it is easy to see that after a move with the even number N'", ;a

tH

N~ < N ' " < N ,

+2(m-l)(m-l-1),

there will be no more than l points in XN. , N (r=., i) if the first player did not unlabel Y2 at the moves with .tl

the numbers from N~" to N , and then Xtr ~ y2. Therefore, in the case where N > N* and y2 is singular with respect to XN N (0, r,~.] and L", the first player unlabels y2 at the move with the number

N " = Mqlq~ Z~' + 2 i ' ' - I > N ' , 1 < i" <_ M/2, where i" is a natural number, i.e., yz E XN,,, which contradicts the fact that Y2 belongs to any set XN when

N>N*. The contradiction thus obtained allows one to state the impossibility of the inequality P(X0,a'(-), b(-)) > 1 for any initial set X0 and strategy b(.) of the second player. Therefore, ~o(X0, a'(-), b(-)) < 1 for any X0 and b(-). Thus, the proof of Proposition 2.3.1 is completed. Consider the game (m, l) for l = 1. The inequalities 1 _< c(m, 1) _< [rn/2] are proved in Proposition 1.6.1. The application of the continuum hypothesis allows one to obtain a sharper upper bound for c(m, 1)' Namely, the following proposition follows immediately from Proposition 2.3.1 obtained by means of the continuum hypothesis and Proposition 1.6.1. P r o p o s i t i o n 2.3.2. The equality 1) = 1

holds for the game (rn, 1) for arbitrary natural rn not less than 2. 2.4. G e n e r a l i z e d G a m e (m,1) Now consider a generalized game of search and completion with arbitrary natural values of the parameters m and l, where l < m, which was presented in Sec. 1.9, i.e., the game (m, l) ~ where there are m labeled points before the game and at every move the first or second player decreases or increases the number of labeled points by l, respectively. In choosing a move, the players know only its number and the labeled points at the given moment. The relations 0 < c~ l) < [m/(l + 1)] were proved in Proposition 1.9.1. The use of continuum hypothesis allows one to obtain a sharper upper bound for c~ l), namely, it allows one to prove the following P r o p o s i t i o n 2.4.1. The relations O_
1

hold for the game (rn, l) ~ for arbitrary natural values rn and I, where l < rn, and every initial set Xo C (0, 1) that consists of m labeled points. We prove Proposition 2.4.1. Consider the game (m, I) ~ Since the inequality 0 _< c~ t) follows immediately from the definition of Proposition 2.4.1, it suffices to show that there exists a strategy a(.) of the first player such that for every initial set X0 and strategy b(.) of the second player

P(Xo,a'(.),b(.)) <_ 1. We construct the corresponding strategy a'(.) of the first player. We establish a one-to-one correspondence between the points of the interval (0,1) and the ordinal numbers of the second number class [(0 (this is possible if we accept the continuum hypothesis [15]). By 7((,') we denote the ordinal number that belongs 1720

to Ko and corresponds to the p o i n t ( of the interval (0, 1). Consider the direct product (0, l) x (0, l) and its subsets Rt = {((,r/): ( = x , r / E (0,1) and 7(a) -2_ 7(r/)}, =

(

(0,1),,

=

and

> -y(()},

where ~; E (0, l) is fixed arbitrarily. Note that all R~, R~, ~: E (0, l) are countable [15]; therefore, each of these sets can be enumerated. Moreover, for every point (~, r/) E (0, 1) x (0, 1) one of two inclusions holds: either (~,r/) E R~ (for ";,(() >_ 3,(rt)) or ((,r]) E R~ (for 3,(rt) > 3'(())- Let there be a n o n e m p t y set X" that consists of no more than rn - 1 points of the interval (0, 1) and the point z ~, 0 < x' < min~ex, x. We say that z' is singular with respect to X" and a natural number L if (x', z*) E R~. for some x" from X" and (x', x*) has the number L in R~.. Let a point z" be such that max~sx, a: < z" < 1. We say analogously that z" is singular with respect to X" and a natural number L if (x,, x") E R~. for some x. from X" and (z.,x") has the number L in R t It is easy to see that there can be no more than m - I points in any of these cases. By {r} denote the set of all rational points r of the interval (0, 1). Since the set of rational points of (0,1) is countable [15], they can be enumerated, i.e., {r} = {rt, r2, ra,...}. By q~, q2, qa,.. 9 denote the sequence of the ascending-ordered odd prime numbers and introduce the number M = 2(m - l) 2. Let the strategy a'(.) be such that at the move with an arbitrary odd number for each set that belongs to (0,1) and consists of p labeled points (p is a positive integer), a'(.) prescribes that the first player unlabel for p _< l all the points and for p > l to unlabel some I points. In doing this, let for an arbitrary nonempty set X that consists of no more than rn points of the interval (0,1) and a number n such that the number k of points in X n (0, r,~] is not equal to zero and the number k" of points in X N (r,,, 1] is also not equal to zero (here r,~ E {r}), a'(-) possess the following properties: (1) At the move with the number

N=Mq~2q2+2i-1,

1
either

a ' ( X , N ) C X N (0, r,~] if l < k or

a ' ( X , N ) D X n (0, r~] if I > k. If there exists yl E X N (0, r~], which in the ascending-ordered set of points that belong to (0, r~] and are singular with respect to X N (r~, I) and L has the number J'," where j' mod(k').=~, then a'(X, N) 9 y~.* qn

(2) At the move with the number N = Mqlq2 L + 2i - t, 1 < i < M/2, either a ' ( X , N ) C X n (r~, 1) if l < k', or a'(X, N) D X N (r~, 1) if l _> k*. If there exists y~ E X n (r~, 1), which in the ascending-ordered set of points that belong to (r~, 1) and are singular with respect to X N (0, r~] and L, has the number j", where j,, rood(k}. 9 = ~, then a'(X, N) ~ y~ (here i, L are arbitrary natural numbers). Note that the sets of the numbers considered {mq~q2 + 2i-- 1} and {Mqiq~ ~ + 2 i - 1} do not contain equal ,elements and are pairwise disjoint. Assume that there exists an initial set X0 and a strategy b(-) of the second player such that ~(X0, a'(.), b(-)) > 1. Then there exist two points Yt < y2, {y~,y2} C (0, 1), that are contained in every set X g C (0, 1) Of labeled points that occur after the move with the number N > N*, where N* is a natural number. Furthermore, there is r~. E {r} such that yl < r~. < 92 and n" > N* (n* is a natural number). Moreover, either the pair (y~, y2) E R2y2and has the number L' in R2y~,or the pair (y~, y.2) E R~, and has the number L" in R ~v~, i.e., for ;V > N" either ya is singular with respect to Xx N (r~., i) and L' or y2 is singular with respect to X x N (0, r,~.] and L". 1721

Assume first that for N > N ' , yl is singular with respect to X N f3 (r,~., 1) and L'. By Nf' denote the qn

number MqlLq2. Note that q" > n" >_ g ' . N~ = MqlLq2 '

Let, after the move with the number N l , there be k~ points in XN( N (O,r,~.] and there be k ( points in XN( ~ (r,~., 1) and yl have the number j[ in the ascending-ordered set of points that belong to (0, r,~.] and are singular with respect t o XN;, 0 ( r n , , 1) and L' (here k~, k ( are natural numbers, where 1 _< k~ _< m - 1, 1 <_ k ( <_ m - k' - 1). Then for k[ _< I we have X x ; , + 1 ~ Yl and for k[ > l either'the first player unlabels

Yt at the move with the number ,

N; = N ( + 2 i ' - I - 1 ,

i'~

mod(k()

.t

'

!

j',, l_
k, <_ m - l,

if Yl E XN~-I and at the previous moves after the move with the number N " - 1 the second player did not unlabel points from (r,~., 1), or after a move with the number I

N; =N(+2i[',

..t

l_
l


and there are k~ points in X N ( N (0, r,~.], 1 _< k~ _< k~ - 1, and there are k ( points in AN., (3 (r,,., 1), k ( + 1 < k ( < m - k~ (i~', k'2, k ( are natural numbers). Let yt have the number j; in the ascending-ordered set of points that belong to (0, r,~.] and are singular with respect to X u ( A (r,~., l) and U. Then Xtr t ~ y~

again for k~ <_ l and for k~ > I either the first player unlabels yl at the move with the number ..'

-t m o d ( k ~ ' ) . ,

N~=N(+2(i~'+i'~)-l,~ +~

=

.t

h, l < ~ < k ~

*'

t


if Yl E XN~-~ and at the previous moves after the move with the number N ( the second player did not unlabel points from (r,~., 1), or after a move with the number ,,It

..t

t

i

Na' = N f + 2i~' , l_
l,

there are k; points in XN;, N (0, r,~., 1), 1 _< k~ _< k; - 1, and there are k~' points in XN;, N (r~., 1), k ( + 1 _< k~' _< m - k~ (i~', k~, k~' are natural numbers), etc. thus, it is easy to see that after a move with an even number N*', N(_ N*, yl is singular with respect to X N N (r,~., 1) and L', the first player unlabels yl at the move with the number N I

n*

= Mqlq L q 2 + 2 i ' - 1

> N ** , 1 < i' < M / 2 ,

where i' is a natural number, i.e., Yl ~ XN,, which contradicts the fact that yt belongs to any set X N for N>N*. . .r Assume now that, for N >__ N , Y2 is singular with respect to XN N (0, r,~.] and L " . By N t denote the o

number Mq~q~ ~ . Note that tt t

qrt*

N 1 = M q l % z > n * > N*. tt

.tt

I!

Let, after the move with the number N~" , there be k t points in X N ( , A (r,~., 1) and there be k t points in XN(, A (0, r~.], and Y2 have the number j'( in the ascending-ordered set of points that belong to (r~., 1) and

!722

are singular with respect to XN~,, f) (0, r.o] and L" (here k~", k[I are natural numbers where 1 < k~" < m - 1, Ill

II

.l!

1 _< k1 < m - k('). Then for k 1 < l we have XN;,,+I ~ Y2, and for k 1 > 1 either the first player unlabels y2 at the move with the number --

N;'=N['"+2i~-I,

i i'

mod(k~')

-

.it Jr, l _ < h. t_t <

,x I t

k~ < m -

kI

-

< m -

l,

.,, if Y2 E XN,_t and at the previous moves after the move with the number N 1 the second player did not unlabel points from (0, r~.], or after a move with the number 9w II

Nf'=N;"+2i~",

II

1 <_zt <_kt < m - k

lit

1
,~lt

--

~tl

II

there are k2 points in XN2.,, f) (r,~., 1), 1 _< k'" - 2 < kl - 1, and there are k 2 points in XN2.,, O (0, r,~.], II

I It

,=It

•r

I1

k t + 1 < k~' < m - k 2 (h , k2 , kz are natural numbers). Let y2 have the number j;' in the ascending-ordered set of points that belong to (r=., 1) and are singular with respect to XN;,, f) (0, r..] and L". Then XN;,,+t ~ y: ~t It

21!

again for k2 _< l and for k 2 > l either the first player unlabels y~ at the move with the number .. mod(k~').. - .. . .,, i~"+z2 = 32, l <-z2 <-k2 < - r n - k 2 < _ m - l ,

Na"=N~"+2(i'/'+i'~)-l,

if y2 E XNI,-1 and at the previous moves after the move with the number N f ' the second player did not uniabel the points from (0, r,~.], or after a move with the number

N~"=N~"+2i~",

.=ll

I!

1 <_~: < k : < m - k ~

it


ill

Xr l

*lit

It

l?~lt

there are k3 points in XNj.,, A (0, r,~.], k;1 + 1 _< k~' _< ra - ka (z: , k~ , ka are natural numbers) etc. Thus, it is easy to see that after a move with an even number N

,~ tt

,

N~'" < N ' " <_ N~'" + 2(rn - l)(m - l - t) there are no more than l points in XN.. N (r~., 1) if the first player does not unlabel Y2 at the moves with the -numbers from N l9 ll to N * " and then XN.,,+I ~ Y2- Therefore, in the case where for N > N * , y2 is singular with respect to XN C/(0, r=.] and L", the first player unlabels y2 at the move with the number qn*

N " = Mqtq~ z + 2 i " - 1

> N', 1 <_ i" <_ M/2,

where z~"lis a natural number, i.e., y2 ~ XN,, which contradicts the fact that y2 belongs to every set XN for N>N'. The contradiction thus obtained allows one to state the impossibility of the inequality ~(X0, a'(-), b(-)) > 1 for any initial set Xo and strategy b(.) of the second player. Therefore, P(X0, a'(.), b(-)) <_ 1 for any X0 and b(-). Thus, the proof of Proposition 2.4.l is completed. Consider the game (m, l) ~ when l = 1. The relations 1 _< c~ 1) < [m/2] are proved in Proposition 1.9.2. The application of the continuum hypothesis allows one to obtain a stronger result for c~ 1), namely Proposition 2.4.1 proved by means of the continuum hypothesis and Proposition 1.9.2 imply the following P r o p o s i t i o n 2.4.2. The equality

c~

1) = 1

holds for the game (rn, l) ~ for an arbitrary natural m that is greater than one and for any initial set Xo C (0, 1) that consists of m labeled points. 1723

2.5. U n s o l v e d P r o b l e m s In concluding the second section, we formulate two main groups of unsolved problems related to the games of search and completion considered above by means of the continuum hypothesis. The first group of problems: for games of search and completion with arbitrary natural m and l, where I < m - 1, find whether c(m, l) equals one or zero. The second group of problems: for generalized games of search and completion with arbitrary natural values of m and I of the parameters, where 1 < m - l, find c~ l). These problems are interesting from the mathematical standpoint, and solution of the problems may be a natural development of the results obtained in 2.2-2.4. 3. S i m u l t a n e o u s Sessions of S e a r c h a n d C o m p l e t i o n 3.1. D e s c r i p t i o n of t h e G a m e s In Sec. 3 by means of the continuum hypothesis we consider games of search and completion played together, or simultaneous parties of search and completion. We give a precise definition of simultaneous parties considered below. There is a nonempty finite or countable set of intervals (0,1) of real lines. In each of the intervals the first player (let him be the same for the sake of definiteness) leads the game of search and completion with the corresponding second player. The points of the intervals (0,1) are partitioned into labeled and unlabeled points. Let for the j t h interval I j = (0, 1) there be the set X~ consisting of m j labeled points before the session (the games of the session are numbered in an arbitrary way), and the points from I i \ x ~ be unlabeled (here j and r n j a r e natural numbers, where j runs over a nonempty finite interval of the positive integers or the whole set of positive integers). At the first move of the session the first player searches through arbitrary intervals (one or many). Searching an arbitrary interval [J, the first player unlabels points which belong to an arbitrary set A{ C X~ consisting of P points, Ij _< rn j. Thus, after the first move there is a corresponding set in every interval P . This set either consists of m j - Ij labeled points if the search was carried out at the given move in I j (in doing this X~ = X ~ \ A { ) or consists of m j labeled points if no search was carried out in P at this move (in doing this Xr = X~), the points from [ J \ x r are unlabeled. At the second move of the session in the intervals and only in those where the first search took place, the corresponding second players carry out the completion. In doing so, in any interval [J where the completion takes place, the corresponding set X~ C I j is united with an arbitrary set 13~ C [ J \ X ~ consisting of Ij unlabeled points and, therefore, the points of/3~ become labeled. Thus, after the second move each interval contains the corresponding set X~ consisting of m i singular points. In doing this, either X~ = X~ tO/3~ if there was a completion in [J at the given move, or X~ = X~ if there was no completion at the move. the points from [ J \ X ~ being unlabeled. Let. before the move with the number 2k + 1 in any interval [J there be a corresponding set X~k consisting of m j labeled points and the points from IJ\X~k are unlabeled (k is a natural number). At the (2k + 1)st move of the session, the first player searches through arbitrary intervals (one or many). In each interval P being looked through, he subtracts an arbitrary set A~+ t C X~k from the corresponding set X~k C [J. This set consists of IJ labeled points, thus unlabeling the points of A~,+I. Thus, after the (2k + 1)st move any interval either consisting of m j - l j labeled points if the search took place P contains the corresponding interval X2k+l J ~j J J in I j at the given move (in doing this X.2k+l = X2k\Ak+l), or consisting of m j labeled points if there was no X 2k), j . search in [J a t the given move (in doing this -u J the points from I3\X~k+t being unlabeled. At the (2k + 2)nd move of the session in all those intervals where the search took place at the (2k + 1)st move, the corresponding second players carrv out completions. The session goes on as the number of the move ranges 1724

over the set of all natural numbers (note that the enumeration of moves in the session and the constituent games can be different). We assume that in choosing every move in the session the first player and any of the second players know the number N of a move of the session and the set of labeled points given at the beginning of the move either in every game (for the first player) or in the corresponding game (for the second players). Let a[.] be an arbitrary function that maps an arbitrary odd number N and a sequence { X i } of sets, such that, for any j , X j C I j and X J consists of rnJ points, to the sequence { A j} of some sets, not all of which are empty and such that, for every j , A j C X y, whereas either A j contains lJ points or A j = o (here the natural number j ranges over the whole set of numbers corresponding to the games of the session). Such a function a[.] is called a strategy of the first player in the session. Every function b/(.) which maps every even number N and a set X y C I j to some set B y C I J \ X y such that either B j consists of Ij points if X j consists of m j - l j points, or B j = o if the number of points in X j is different from m j - P. By b[-] we denote the sequence {b/(.)} of all the strategies of the second players taking part in the session. We say that the point x E I j remains labeled after the end of the session if x is contained in every set X ~ C I j of labeled points arising in the game carried out in the interval I j after the move with the number

N > N0~ here j, No are some natural numbers. By 7)[{XJ}, a[.], b[.]] we denote the number of points left labeled after the end of the session such that, before its beginning, in an interval I j with an arbitrary number j there was a corresponding set X~ consisting of m j labeled points, and the first and second players carried out their search and completion or missed their moves in the game played in I i according to the strategies of a[.] (the constituent of the values of a[.] contained i n / J ) and b/(.) 9 b[-], respectively. The first player strives to minimize the value of the functional T~[.], whereas the second player strives to maximize it. The session will be studied from the standpoint of the guaranteed possibilities of the first player. We introduce the function c[.], which is the least result that can be guaranteed by the first player: c[{mJ}, {lJ }l = rain sup 79[(Xg }, a[-], b[-l]. ~[] b[.]

(3. [)

Here the minimum and supremum are taken over all strategies of the first player and the sequences of strategies of the second players possible in the session. The minimum exists, since the functional 79[9] is integral and bounded from below. We note that the given function c[.] depends on the sequences {m y} and {l j} of the parameters of all the games of the session, but is independent of the sequence {X~} of all sets of labeled points of the interval before the session. In fact, let before the session the interval I j with an arbitrary number j contain a corresponding set X j~ that consists of rn j labeled points, which cannot coincide with X~. For each j we construct a corresponding one-to-one map I j to I j in such a way that the set X~ is taken to X~ 1. Then it is easy to see that the case where, for all j, X~ C [J, due to the one-to-one mappings constructed, can be identified with the case, where for all j X~ 1 C I j holds. Thus, the values of the function c[-] are the same in both cases, i.e., the function c[-] is independent of the sequence {X~} of the sets of labeled points given in the intervals before the beginning of the session. Now we pass on to a study of the simultaneous sessions for various values of the parameters corresponding to the games of search and completion. 3.2. Session of the G a m e (2,1) Consider a session of the game (2, 1), i.e., a session such that m y = 2 and l i = 1 for any game played in the interval I i with an arbitrary number j (here j ranges over a nonempty finite segment of positive integers or the whole set of positive integers}. Using the continuum hypothesis, we can show that the best result that can be guaranteed by the first player equals one, i.e., it coincides with the best result guaranteed by the first player in an arbitrary individual 1725

game of the session if the game had been played in the absence of other players (see Proposition 1.2.1), i.e., the following proposition is true. P r o p o s i t i o n 3.2.1. The equality c[{2}, (1}1 = 1

holds for a session of the game (2, 1). We prove Proposition 3.2.1. Consider a session of the game (2,1). It is not difficult to see from (3,1) that to prove Proposition 3.2.1 it suffices to show that there exists a strategy a*[.] of the first player such that for every sequence (X~} of initial sets and strategies b[.] of the second players < 1

holds and for any strategies a'[.] of the first player and the sequence {X~ j } of initial sets there exists a sequence b'[.] of strategies of the second players for which V[{Xo~J), a'[-], b'[-]] > 1. First we construct the corresponding strategy a*[-] of the first player in the session. We establish a one-to-one mapping between the points of the interval (0,1) and the ordinal numbers of the second number class K0 (this is possible if we accept the continuum hypothesis [15]) and denote by 7(~) the ordinal number that belongs to Ko taken to the point ~ of the interval (0,1). Consider the direct product (0, 1) • (0, 1) and its subsets = {(r 7): r = 7 (0, 1) and > = {(r162

(0, 1),7 =

and

> "r(r

where ~; E (0, 1) is arbitrarily fixed. Note that all R~, R2~, ~; E (0, 1), are countable [15] so that all of them can be enumerated and, moreover, for any point (~, 7) E (0, 1) x (0, 1) one of two inclusions holds: either (~, 7) E R~ (for 7(~) -> 7(7)) or (~, 7) E R~ (for 7(7) > 7(~)). Let there be intervals Z' (0, 1), I " = (0, 1) and a pair of points (x', x") E [' • I". We say that x' is singular with respect to x" and a natural number L if (z', a:") e R2,, and (a:', z") has the number n in R~,,. 2 Analogously, we say that x" is singular with respect to x' and a natural number L if (z', z") e R~,, and (z', z") has the number L in R~,. By ql, q2, qa,.., we denote the sequence of odd prime numbers in ascending order. Let the strategy a[.] of the first player have the following properties: qn

(1) at the move with the number N = qj~ for j~ < j2 the strategy a*[.] prescribes that one unlabel y~ in J~ i the interval I j' i 6 {1, 2}, containing an arbitrary set XN_ ~ = {yt,i Y2} of labeled poitats, if y~ is not singular with respect to y~ and L, and to unlabel y~ if y~ is singular with respect to y~ and L; r~

(2) at the move with the number N = qJtqj~ for j~ < j2 the strategy a*[.] prescribes that one unlabel y~ in the interval I j', i E {1, 2}, containing an arbitrary set X~)_t = {y[, y~} of labeled points, if y~ is not singular with respect to yt and L in the pair of points (y~, y~), and unlabel y~, k E {1, 2}, k r i, if y~ is singular with respect to y~ and L in the pair of points (y~,y~) (here j l , j 2 are arbitrary numbers of intervals where the games are piayed, where 1 <_ jt < j2, if the games in the session are played in no less than two intervals and jt = j2 = 1 otherwise; L, n are arbitrary natural numbers and, moreover, 0 < y~ < y~ < 1, 0 < y~ < y~ < 1). Note that for jl < j2 the sets {q~} and {q3~, 9 qJ2 q~} of the numbers considered do not Contain equal elements and are disjoint. Assume that there are sequences {Xg} of initial sets and strategies b[-] of the second players such that ]] > 1

Then there exist two points yt E I j~ and y2 E I ? such that yi, i E (1,2}, are contained in any set of labeled points that occur after the move with the number N > N" in a game of the session played in the interval I j' 17"2_6

(here j t , j z , N" are some natural numbers, where j~ < jz). In the pair of points (y~,yz) either yt is singular with respect to y2 and some natural number L', or y2 is singular with respect to yl and some natural number L". Then it is easy to see that yl or y2 will be unlabeled at the move with the number N ' = qi~q~,lqj~ > N" or n*

qLll

N " = qjlqj2

*

> N , where n" is a natural number, since after the move with the number N' (N") according

to the definition of a'[-] there cannot remain two unlabeled points in the intervals I jr, I ? the first (second) point of which is singular with respect to the other and is not contained in the set of labeled points that occur after the move with the number N' or N " in the game of the session played in the corresponding interval. The contradiction allows one to state that for any sequences {X~'} of initial sets and strategies b[.] of the second players the inequaiity 7~[{Xg}, a*[.], b[.]] < 1 holds. Now, we show that for any strategy a'[.] of the first player and the sequence {X'oj} of initial sets there is a sequence b'[.] of strategies of the second players for which r

t

V[{X0',a [-1, b'[.]] > l. We fix arbitrarily the strategy a'[-] of the first player and the sequence {X0j } of initial sets. The point x N E 11 is called singular for the move with an odd number N if for any x E [ l \ { x N } there exists an odd number M > N such that at the move with an odd number N', N < N' < M, for the given sequence {X't}, where X H = {x N, x}, X 'j = Xo d for every j > 2, all sets of labeled points, the strategy a'[.] prescribes that the first player not unlabel any point from X '1 when N < N' < M and unlabel x N when N' = M. For any move with an odd number there can be no more than one singular point. In fact, if for some move with an odd number N there were two singular points x u ~ y N { x N y N } C [1, then the following relations would hold

( x " = {xN, yN}): 11 Ak+ 1=o

for N < 2 k + l


Ak+ t = {-TN} for 2k + 1 = M 1, and tl

Ak+ ~ = g f o r N _ < 2 k + l < M ' , tl

Ak+l

~___

{yN} for 2k + 1 = M",

which is impossible (here k is a positive integer, M', M " are odd numbers not less than N, the set Ak+ 1 is either empty or contains only one point. The strategy a'[.] prescribes that the first player unlabel this point in X '1 at the move with the number 2k + 1 for the given sequence {X'J} of all sets of the labeled points). Thus, for any move with an odd number there can exist no more than one singular point. Therefore, the set X' C 11 of all points singular for some move with an odd number is no more than countable. Let the sequence b'[-] = {b'i(-)} of the strategies of the second players be such that in the game played in the interval P for an arbitrary j _> 2, at each move b'J(.) prescribes that one label a point from X j that is unlabeled before the move. In the game played in the interval P , at each move such that completion in P takes place, the strategy b't(-) prescribes, for any labeled point z E 11 given before the move, that one label a point y E I I \ { x } such that if x E X', then y E I I \ X ' ( I I \ X ' 5s e), and if x E P \ X 1, then, starting from this move, x remains labeled until the first player unlabels y (for x E I l \ X l the required point y exists, since otherwise x would have been singular for the move with the corresponding number). Let the first player and second players play according to the strategies a'[-] and {b'J(.)}, respectively. Then for the sequence {X0 j } of initial sets either the first player does not accomplish any search in 11 or some 1727

point x E I t \ X ' is constantly labeled starting from some move, i.e., in any case some point remains labeled after the end of the session and, therefore,

v[{x0 nj }, a I [.], 6l []] _ 1. Thus, the proof of Proposition 3.2.1 is completed. 3.3. S e s s i o n of a G a m e o f S e a r c h a n d C o m p l e t i o n

with Arbitrary

Values of Parameters

Consider a session of a game of search and completion with arbitrary values of parameters, i.e., a session for which for any number j a game of search and completion with arbitrary natural values m j and P of the parameters takes place in the interval I j, where Ij _< m j (here j ranges over a finite segment of the positive integers or over the whole set of positive integers). Using the continuum hypothesis, we can show that if the parameters are bound from above, then the least result which can be guaranteed by the first player in the session does not exceed one (see Proposition 3.3.1). Note that this upper bound is not greater than the upper bounds of the least result which can be guaranteed by the first player in an arbitrary individual game of the session if this game were played in the absence of other players (see Proposition 1.8.1 and 2.3.1). We note also that the construction of the strategy of the first player does not require a search in more than one interval at a move with any odd number, unlike the construction of the corresponding strategy of the first player for the proof of Proposition 3.2.1. Thus, we can say that the following proposition is true. P r o p o s i t i o n 3.3.1. Consider the session of the game of search and completion where, for any number j, a game of search and completion with arbitrary natural values m j and lj of the parameters is played in the interval I j, where m j and l j a r e such that Ij < m j < m ~ and m ~ is a natural number. Then the followin 9 relations hold: 0 _< c[{mJ}, {lJ}] < 1 (here j ranges over a non-empty finite segment of positive integers or the whole set of positive integers).

We prove Proposition 3.3.1. Consider the session of a game of search and completion where for each number j the game of search and completion takes place in the interval I j for arbitrary values of m j and Ij of the parameters, where P <_ m j <_ m~ Since the inequality 0 _< c[{mJ}, {lJ}] follows directly from the definition of the function c[-], from (3.1) it is easy to see that to prove Proposition 3.3.1 it suffices to show that there is a strategy a'[. l of the first player, where for every sequence {X~} of initial sets and b[-] of strategies of the second players we have a'[.], b[-]] _< 1.

We construct the corresponding strategy a*[.] of the first player in the session. We establish a one-to-one correspondence between the points of the interval (0,1) and the ordinal numbers of the second number class K0 (it is possible if we accept the continuum hypothesis [15]) and denote by 7({) the ordinal number belonging to K0 assigned to the point C of the interval (0,1). Consider the direct product (0, 1) x (0, 1) and its subsets =

=

E

>_

R2~ = {((, 0): ( E (0, 1), r/ = x and 7(x) > 7(~)}, where x E (0, 1) is fixed arbitrarily. Note that all R~, R~, • E (0, 1), are countable [15] in a way such that all of them can be enumerated and, moreover, for any pair (~, r/) E (0, 1) x (0, 1) only one of two inclusion holds: either ({.~1) E R~ ',when 7({) >- 7(rl)) Or (~,r/) E R~ (when -y(r/) > 3'({))- Let there be an interval [ = (0, 1), a nonempty set X" C F, which consists of no more than m ~ - t points of the interval I, and the point :c' E [, 0 < z' < min~ex, z. We say that z' is singular with respect to X" and a natural number L if. for some z" from X ' , ( x ' , x ' ) E R~. holds and ( z ' , z ' ) has the number L in R~.. Let there be a point 1728

z" E 1, max~ex, x < x" < I. We say analogously that x" is singular with respect to X* and a natural number L if (z.,x") E R~. for some x. from X* and (x., z") has the number L in R ~ . Furthermore; let there be intervals [' = (0, 1), I" = (0, 1), the point y' E I', and a nonempty set Y" that consists of no more than m ~ points of the interval I". We say that y' is special with respect to Y" and a natural number L if, for some y'" from Y " , (y', y ' " ) E R~.,, and (y', y'") has the number L in R2 .... Finally, let there be a nonempty set Y' consisting of no more than m ~ points of the interval [' and the point y" E I". As in the case above, we say that y" is singular with respect to Y' and the natural number L if for some y'. from Y' (y'., y") E Rlu: holds and (y'., y") has the number L in R~,. It is not difficult to see that there can be no more than m ~ singular points (no more than m ~ - 1 in the first two cases). By {r} we denote the set of all rational points r of the interval (0,1). Since the set of all rational points of (0,1) is countable [15], the points can be enumerated, i.e., {r} = {rl, r2, r3,...}. By ql, q2, q3,.., we denote the sequence of ascending-ordered odd prime numbers and introduce the number M = 2(m~ 2. Let j l , j 2 > j l be arbitrary numbers of the intervals where the games with parameters m j~ and l j~ (respectively m j= and Ij= ) take place, let every set X j~ C [J~ consist of rn jl points, X J ~ C [J= consist of m j= points, and every number n such that the number k of points in X a fq (0, r,~], where r, e {r}, satisfy the inequalities 1 <_ k < m jl - 1. In this case, let the strategy a'[.] of the first player have the foltowing properties: (1) at the move with the odd number 2p + t

=

M q2jx_t(t2jI q~ + 2i - 1, 1 < i < M / 2 ,

for the set X jl of labeled points in the interval Ijt either ..p+~,~'J~C X it N (0, r~] if l j~ < k, or --p+ta*/tD X j' N (0, r,~] if Ij~ > k. In this case "p+l 9 y~ if there is a point y~ in X j' (? (0, r,~] that has the number s' in the ascending _

A

"jl

.

set of points from (0, r~] that belong to (0, r~] and are singular with respect to X ~ N (r,~, 1) and L, where s' moa(.~__,~-k))i; (2) at the move with the odd number 2p + 1 = Mq2j~_tq~j, + 2 i -

M/2

1, 1 < i <

for the set of labeled points in the interval I j~ either A;~t C X j~ 0 (r,. 1) if lj~ < m jz - k , or 9

D X j~ fq (r~, 1)

if lj~ >_ rn jl - k. in the case where there is a point y~ in X jt C) (r,. 1) with the number s" in an ascending ordered set of points that belong to (r~, 1) and are singular with respect to X j~ N(0, r.] and L, where s" rood(k). we have A"'p+l * j l ~ Y2, *" (3) at the move with the odd number qn

2p + 1 = Mq2jtL q2j2 + 2i - 1, 1 < i < 2~1/2,

for the sets X j~ C [J~ , X j= C I j2 of labeled points "-p+l A'J2 = o in the intervals [J~, [J2 in the case where there is a point y.l in X j~ with the number t' in the ascending-ordered set of points belonging to P ' singular with respect to X j~ and L, where t' m~

"

*Jl 9 y*~; we have ,4~+~ ,

(4) at the move with the odd number 2p + 1 = Mq 3,q j

+

_ 1, 1 <

<

, *Jl for the sets .Y3~ C I j~, X j~ C [J~ of labeled points, Ap+l = ~, in the case where in X ~ there is a point y'e

with the number t" in an ascending-ordered set of points belonging to [J~ singular with respect to X j' and L, where t" mod(,~:t)i,= we have ,4p+l*A ~ y.2 (here i. L are arbitrary natural numbers and A

TMp+~,~-p+~a'J~are sets,

such 1729

that a'[-] prescribes that one unlabel the points of which in the sets X J1 C P~, X ~ C I ;2, respectively, at the move with the odd number 2p + 1). Note that the sets of the numbers considered qn

{Mq2)l_lq2jlqejl + 2 i ttn

L h + 2i-1} {M%Aq2

1}, {Mq2jt_zq~jl + 2 i -

1},

~q~ + 2 i - 1 } and ~t M q~A~2j2

do not contain equal elements and are disjoint. Assume that there are sequences {Xd} of initial sets and b[-] of the strategies of second players such that

b[.]l > 1. Then one of two cases takes place, namely: either there is a number j t of the interval where the game with parameters m jl a n d Ijl takes place, as welt as two points y~ < yz, {y~,yz} C I j~ contained in any set X ;

C I j'

of labeled points that occur after the move with the number N _> N" (case 1); or there exist numbers j t < j2 of intervals where the games with parameters m j~ and ljl, (respectively, rn j~ and 1j2) take place in the session, 9

jl

-

as well as two points yl E I j~ and y2 E I j~ such that y', i E {1,2}, is contained in every set X N C [ f of labeled points arising after the move with the number N > N* (case 2); here N* is some natural number. Let us consider the first case. Then, there exists r~. E {r} such that Yl _< r,~. < y2 and n" _> N* (n* is a natural number). Moreover, either (y~, y2) e R~2 and has a number L' in R ~, 2 or (yl,y2) e R~l and has a jl number L" in R Yl I ' i.e., for N > - - N* either yl is singular with respect to X N A (r,~. '1 1) and

L !

or y2 is singular

with respect to X ~ A (0, r,,.] and L". Assume first that, for N > N*, y is singular with respect to X ; N (r~-, 1) and Lq By N 1 we denote the ~zf q'riLl

n u m b e r ~**q2j,_~q2i,. Note that

N~'

= l "" V l q 2q~;~ jl_lq2jl

>

n*

N*.

~

/

*!

!

Let, after the move with the number N l , there be k t points in X jt , N (0, r~.], and yl have the number s I in the ascending set of points in (0, r~.] singular with respect to XNt, jt (3 (r,~., 1) and L* (here kt is a natural number and 1 < - k~ -< rnJ' - 1). Then X N~" jl , +~ ~ Yl for k 'l <_ Ijl, and for k '1 > 111 either the first player unlabels y~ in the interval I j~ at the move with the number N; = N ( + 2i'~ - 1, il

m~

=

I ~ itl ~

m j l - - k '1 "~ m j l - - I j l ,

51 ~ and no points from (r,~., 1) were labeled on the previous moves after the move with the number if Yl E XN~_ N~', or there will be k;, 1 _< k~ _< k[ - 1 points in XN, , N (0, r,~.] after some move with the number .~t

N~' = N~' + 2i~', 1 <_ h <- rn~ - lJl, (1 _< k~' _< k '~ - l , z *' ,k~' are natural numbers). Let y~ have the number %~ in the ascending-ordered set of points that belong to (0, r~,.] and are singular with respect to XY~'N~f-1 (r,~., 1) and L'. Then X ,N~. ~ +~ ~ y~' if for k~ <_ tit, and if k~ > P~, then either the first player unlabels ya in the interval I j~ at the move with the number ,% = N ? ' + ~ ( i ;

'

,*'

+ i;) -

'/ r a ~

~, ~, + ,~

=

t

~,

.j~

-,

t _< ,~ _< mJ' -

v',

if Yl ~ XN~_ ~ and no points from (r,~., i) were unlabeled in I ~I on the previous moves after the move with the number N ( , or after a move with the number N j t = N ; ' + 2i;', i <_ i;' <_ r # ' - k'~ < m j' - Ij', 1730

there will be k~ points in X Na" ~" N (0, r,,.], (i < k a' _< k 2' - I and z"" 2 , k a' are n a t u r a l n u m b e r s ) and so on. Thus, it is easy to see t h a t after some move with an even n u m b e r N " , .t

i

N 1 _< N " <_ N~' + 2 ( m j' - / J ' ) ( m j~ - I j~ - 1) jt there will be no more t h a n P' points in X N . , Cl (0, r,~,] if the first player does not untabel 91 in the interval I j' j~ , +1 ~ Yl. Therefore, in case 1, where, for N > N*, at the moves with numbers from N 1"' to N "' , and t h e n X N" j' Yl is singular with respect to X N N (r~., 1) and L', the first player unlabels yl in the interval I j' at the move with the n u m b e r N ' = Mq2j~_lq2 " " q~'; j, + 2i' -- 1 > N*, 1 <_ i' <_ M / 2 , jl where i' is a n a t u r a l n u m b e r , i.e., yl ~ X~,, which contradicts the fact t h a t yl belongs to any set X N for N>_N*. Assume now that, for N >__ N ' , y2 is singular with respect to X gjl gl (0, r~.] and L". B y N 1"" denote the r*" A,f q L tt n u m b e r ~,,q2jl-lq2j, 9 Note that

NI

.tl

rl~

qLjl

= Mq2j'-lq2j,

> n" > N*.

Let, after the move with the n u m b e r N~", X j' ,, N (r,~., 1) contain k" points, and y2 have the n u m b e r s i' in an N; ascending set of points t h a t belong to (r=., l) and are singular with respect to X i' ,, N (0, r=.] and L" (here N; " J ' k Itt is a natural n u m b e r , where 1 _< k Itt _< m J~ - t). T h e n Xx?,,+t {~ y2 for k t1l < l j', and for k 1I I > I jx either the

first player unlabels y2 at the m o v e with the n u m b e r ..

N~' = N l " + 2i~ - l, h

moa(,~Jx-k~

')

=

.

,.

9

.

9

at, 1 <_ z 1 <_ m " - k, < r e " - Ij',

jl if y= E XN~, 1 and the points from (0, r=.] were not unlabeled on the previous moves after the move with the ,tt

n u m b e r N t , or after the m o v e with the n u m b e r Nil .It ..Jr ..it =N~ +2 h , l_
j ~ - l j'

there will be k~', 1 _< k~' < k~' - 1 points in XJN~,, n (r~., 1) (i~", k~' are n a t u r a l n u m b e r s ) .

Let y= have the

n u m b e r sg in the ascending-ordered set of points t h a t belong to (r,~., 1) and are singular with respect to j I XJ'N;" Cl (0, r,~.] and L". T h e n XN;,,+I {~ Y2 again for k 2I I _< l jl, and for k 2I I > Ij' or in the interval I j' the first

player unlabels Y2 at the m o v e with the n u m b e r = ) _ 1, h..,, +z=.,, mod((mJx-k'2'))S~ , 1 <_ Z.It2 _< m j ' -- k2" _< m jl _ lj' '

N a' = N [ ' " + 2 ( i ~ " + i i '

jl if g2 E XN~,_ 1 and no points from (0, r,~.] were labeled in lit on the previous moves after the move with the ,,it

n u m b e r N 2 , or after a move with the n u m b e r 9

N~" = N~" + . z :

"tIt

_

"lIt

_

_

, t < z 2 < reJ~

ii

_

_

k: < reJ'

Ij~

,

there will be k~' points in .V j~ , N (r,,o 1) (1 < k~' < k'~' - 1, i~", k.~' are n a t u r a l n u m b e r s ) and so on. Thus, N~ . . . . after some move with the even n u m b e r N N;" " _ < N ' " < N ' " < ~

"

+ 9.m (

,,tl

,

2

-

j'

-

z,'

-

1),

1731

there will be no more than l j' points in X yj' . t t N (r,~. 1), if the first player does not unlabel y2 in the interval I j' at the moves with the numbers from N~" to N ' " , and then X Njl* . + 1 ~ Yz- Therefore, in the first case, when, for N > N ' , y2 is singular with respect to X ~ N (0, rr~.] and L", in the interval [P the first player unlabels Y2 at the move with the number N"

=

~:r~ iv1 , q 2 j l _ l t / 2~q~" jl

+ 2i" - 1 > N ' , 1 < __ i" < __ M / 2 ,

jl jl where i" is a natural number, i.e., 92 ~ XN,,, which contradicts the fact that y2 belongs to every set X N when N>_N*. The contradiction thus obtained allows one to assert the impossibility of case 1. Let the second case take place. Then either (yl,y2) E R2u= and has the number L' in R 2u2,or (yl,y2) E R~I j2 y2 and has the number L" in RI~, i.e., for N > N" either yl is singular with respect to X N and L', or is singular with respect to X ~ and L". Assume first that y1 is singular with respect to X ; and L' for N > N*. Let yl have the number t' in the ascending ordered set of points that belong to I j~ and are singular with respect to X j2 and L'. Then the first player unlabels y' in the interval I j~ at the move with the number N' = lvlq2jl "" qf" q212 + 2i' - 1 > N ' , i' m~=

t ,' 1 <_ i' __ < m j2 <_ M / 2 ,

if yl E X Nj,, I. Therefore, yl ~ X ; , , which contradicts the fact that yl belongs to any set X N jl for N _> N*. Jl and L" . Let y2 have the number t" in Assume now that, for N >_ N ' , y2 is singular with respect to X N

the ascending ordered set of points that belong to lJ= and are singular with respect to X j~ and L". Then the first player unlabels y2 in the interval I j~ at the move with the number ~" + 2i" N " = Mq2j~q~j~'

-

1 > N*,

i"

m~=

)t", 1 <_ i" <_ rnJ ~ <_ M / 2 ,

if y2 E X Nj~, , 1. Therefore, y2 ~ X Nj~, , which contradicts the fact that y2 belongs every set X nj2 for N >__N*. The contradiction obtained allows one to assert the impossibility of case 2. The impossibility of cases 1 and 2 allows one to assert the impossibility of the inequality j 9 [.],b[-]] > i for any sequence {X~} of initial sets and strategies b[-] of the second players. Therefore, for any {Xoj } and b[.] j , [.],b[.]] < Thus, the proof of Proposition 3.3.1 is completed. Consider now the session of the game of search and completion where for each number j the game of search and completion for arbitrary natural values m j and Ij of the parameters takes place in the interval [ j (where Ij <_ m j and j ranges over a nonempty finite interval of positive integers or the whole set of positive integers), where the parameters are not only bound from above, but are such that P' < m y for at least one value j = j', and in this case either P' = 1 or P' = mJ' - 1. In this case, the results obtained in this section can be strengthened. Namely, by means of the continuum hypothesis we can show that the least result that the first player can guarantee in the session is equal to one (Proposition 3.3.2). Note that the least result that the first player can guarantee in an arbitrary j t h game of the session, where i < m, if the game has been played in the absence of the other players, is not less than one (see Propositions 1.6.t, 2.3.2, and t.7.t). Thus, we can state the following: P r o p o s i t i o n 3.3.2. Consider a session of a game of search and completion where, for each number j in each interval I j, a game of search and completion with arbitrary natural values rnJ and Ij of the parameters 1732

such that P < rn~ < m ~ is played (here rn u is a natural n u m b e r and j ranges over a n o n e m p t y finite interval or the whole real line), where f o r at least one value j = j ' , Ij' < m y and either l j' = i or P' = mJ' - 1. Then the following equality holds:

c[{mq, {PI] = 1. We prove Proposition 3.3.2. Consider a session a game of search and completion where, for each number j ill the interval I j, a game of search and completion is played in the interval I j for arbitrary natural values rnJ and P such that Ij < rn j < m ~ and either Ij' = [, or Ij' = m Y - I. Since in Proposition 3.3.1 we established the inequality e[{mq, {lq] < 1, it is easy to see from (3.1) that to prove Proposition 3.3.2 it suffices to show that for any strategy a'[ .] of the first player and sequence {X~} of initial sets, there exists a sequence b'[-] of strategies of the second players, such that

b'[-l] > 1. X,-Ij t

We fix an arbitrary strategy a'[-] of the first player, the sequence {Xo j } of initial sets, and a set X' C ~-0 that contains rn~' - lJ' - 1 pairwise different points (X' = o for Ij' = mJ' - 1). The point z y E I J ' \ X ' is called singular for the move with an odd number N, if for any set X C P ' , X D ({z N} U X ' ) that consists of mJ' pairwise different points, there exists an odd number M > N such that for a move with an odd number N', N <_ N " < _ M , for a given sequence { X ' J } , where X ' ; = X, X 'j = X~j for any j # j', of all sets of singular points, the strategy a'[.] prescribes that the first player not unlabel points from X \ X ' for N _< N' < M in

the interval [J' and unlabel x N in I j' for N' = M. For every move with an odd number there can exist no more than l j' pairwise different singular points. In fact, if for a move with an odd number N there are Ij' + 1 different singular points z N , . : x N in I J ' \ x ', then for 9 '

X j'

=

(~,..

N

lJ'+l

., ::CO,+1 } (..J

Xr

the relations Ar

k+t rq

. . , x t , , + l } = o for N < _ 2 k + I < M ;

hold simultaneously, and j, Ak+ 1 9 x ~ f o r 2 k + [ = M i for any i E { 1 , . . . , P ' + i}, which is impossible. Here k is a non-negative integer, M 1 , . . . , M v'+l are odd '3' l is a set either empty or containing Ij' pairwise different points, which the numbers not greater than N, Ak+ strategy a'[.] prescribes that the first player unlabel in X 'j' at the move with the number 2k + 1 for a given sequence {X 'j } of the sets of singular points. Thus, for any move with an odd number there can "exist no more than Ij' pairwise different singular points. Therefore, the set X" C P ' of all points singular with respect to a move with an odd number is not greater than countable. Let the sequence b'[.] = {b'J(-)} of strategies of the second players be such that in the game played in the interval I j with any number j :fi j ' it prescribes at every move where completion in I j' takes place, to label P' points from X',j unlabeled before this move, and in the game played in the interval I j', b'J'(.) prescribes at every move where completion in I / takes place, to label l j' that constitute the set B or belong to X ' if there are unlabeled points in X' (note that since P' = [ or l j' = m j' - 1, there can be only lJ' = 1 labeled points in X' 76 0), or belong to P ' \ ( X '

O X") if there are no unlabeled points in X ' and one of the point

1733

from X" is labeled, or be such that if there are no unlabeled points in X ' and there are no labeled points in X", then any labeled point x E [ J ' \ ( X ' U X " ) given before the given point will remain labeled in I j' starting from this move until the first player unlabels in [J' all the points from the set/3 (for x E [ J ' \ ( X ' U X " ) the required P' points comprising the set/3 exist since, otherwise, z would have been singular for the move with the corresponding number). Let the first and second players hold to the strategies a'[.] and {b'J(.)}, respectively. Then for the sequence

{X'oj } of initial sets a point x E [J'\(X't-JX '') is constantly labeled starting from a certain move, i.e., it remains labeled after the end of the session, and, therefore,

v [ { x g , a'[.], b'[-]] _> 1. Thus, the proof of Proposition 3.3.2 is completed. Consider, finally, a session of a game of search and completion, where for each number j a game of search and completion is played in the interval [J with equal natural values m j = lj of parameters (here j ranges over a nonempty finite interval of a real line or the whole real line). Since, during his moves, the first player can search arbitrary intervals and after a search there remains no labeled point in the interval where the search took place, the following proposition is obvious. Note that the use of the continuum hypothesis is not required here. F r o p o s i t i o n 3.3.3. For a session of game of search and completion such that for every number j a game of search and completion is played in the interval I j with arbitrary equal natural values m j = Ij of parameters, the equality

c[{mJ}, {lJ}] = 0 holds (here j ranges over a nonempty finite interval of the set of integers or the whole set of integers).

3.4. Generalized Session of G a m e s of Search and C o m p l e t i o n We consider a session of games of search and completion, the structure of which is one of the possible generalizations of a construction represented in Sec. 3.1. The main difference of the session studied here from the session presented in Sec. 3.1 consists in the fact that in the first one the search, as well as the completion, are carried out in arbitrary intervals. In doing this both the reduction and increase in the number of labeled points are not constant at every move in any of the corresponding intervals, but are arbitrary, not exceeding a certain number given for the interval under the condition that the number of labeled points does not exceed the initial number for the interval after every move in any interval. A generalized session of the game of search and completion may be characterized in the following way. Before the beginning of a generalized session, in the interval [J for every number j, there are m j labeled points (here j and rnJ are natural numbers, where j ranges over a nonempty finite interval of the natural row or the whole natural row). In a generalized session for any move with an odd number, the first player carries out the search in arbitrary intervals. In doing so, he decreases the number of labeled points by not more than P in every interval where the search takes place. At an arbitrary move with an odd number in a generalized session in arbitrary intervals the corresponding second players carry out completion, where in each interval I j where completion takes place the number of labeled points increases by not more than lj, in a way such that after the move the number of labeled points does not exceed m j (here l j is a natural number which does not exceed mJ). We note that the structure of such a game of search and completion played in an arbitrary interval differs from the construction presented in Sec. 1.1 and corresponds to the generalization given in Sec. 1.9. In choosing an arbitrary move in a generalized session, the first player and each of the second players know the number of a move carried out, as well as the set of labeled point- given before this move either in an arbitrary game (for the first player) or for a corresponding own game (for the second players). In other respects, the construction of a generalized session of a game of search and completion is analogous to the construction presented in Sec. 3.1. In particular, a strategy of the first player is an arbitrary function 1734

a[.] relates an odd number N and a sequence {X J } of sets such that X J C P for any j, and X J consists of no more than rnJ points, to the sequence {A j} of some sets such that A j C X i for any j and {A j} contains no more than 1j points (here the natural number j ranges over the whole set of numbers that correspond to the games of a generalized session), is called a strategy of the first player in a generalized session. A strategy of the second player is an arbitrary function Y(.) which takes an even number N and a set X j C [J, which consists of no more than m j points to a set B i C [ J \ x j with no more than lj points is called a strategy of the second player in a generalized session for a game with an arbitrary number j , if the number of points in X j U/3 j does not exceed mJ. By b[.] we denote the sequence {bJ(.)} of all strategies of the second players that take part in the generalized session. We introduce the following function cO[.], which is the least result guaranteed in a generalized session by the first player, then c~

{lJ}] = rain sup P[{Xg}, el-I, b[']l. o[.1

(3.2)

b[.l

Here, analogously to (3.1), P[{Xg}, a[.], b[.]] is the number of points that remain labeled after the end of the generalized session such that before its beginning, in an interval I j with an arbitrary number j, there is a corresponding set Xg that consists of m j labeled points, and the first and second players of the game played in [i carried out their search and completion according to the strategies a[.] (i.e., to the Constituent values of a[-], which are contained in P ) and b/(-) E b[.], respectively. Note that the supremum and the minimum are taken in (3.2) over all strategies of the first player possible in the generalized session. The minimum does exist, since the functional P[-] is integral and bounded from below, where the value of c~ {lJ}] is independent of {X~} as in (3.1). The use of the continuum hypothesis allows one to establish that the following proposition is true. P r o p o s i t i o n 3.4.1 Consider a generalized session of a game of search and completion, where for any number j the corresponding game of search and completion with arbitrary natural values m i and Ij of the parameters is played such that Ij <_ m j < rn ~ where m ~ is a natural number. Then, the following inequalities hold:

0 < c~

{lJI] < 1

(here j ranges over a nonempty finite interval of the natural numbers or the whole set of natural numbers). We prove Proposition 3.4.1. Consider a generalized session of a game of search and completion, where for each number j the corresponding game of search and completion is played for arbitrary natural values m j and P of the parameters, where Ij < m j < m ~ Since the inequality 0 _< c~ {lJ}] follows directly from the definition of the function c~ it can be easily seen from (3.2) that to prove Proposition 3.4.1, it suffices to show that there exists a strategy a'[-] such that for all sequences {X~} of initial sets and strategies b[.] of the second players,

P[{Xg},a'[.l,b[.l] <_ 1. We construct the corresponding strategy of the first player in the generalized session. We establish a one-to-one correspondence b e t w e e n the points of the intervals (0,1) and the ordinal numbers of the second number class K0 (if we accept the continuum hypothesis, this is possible [15]) and denote by 7(•) E K0 the corresponding number that belongs to K0 and corresponds to the point ~" of the interval (0,1). Consider the direct product (0, t) x (0, l) and its subsets Rt~ = {(~, r~): ( = ~, 77 E (0, 1) and 7(~) >_ "~(r/)}, R2, = {(~,r?): r / = ~,~ E (0,1) and 7(~) > 7(~)}, where ~ E (0, l) is fixed arbitrarily. Note that all R~, R~, ~: E (0, 1), are countable ([15]), so each of them can be numbered and, moreover, for every point (~, ~) E (0, 1) x (0, l) only one of two inclusions holds: either 1735

(~,q) E R~ (when 7(~) > 7(r/)) or (~,r/) 6 R~ (when 7(r/) > 7(~)). Let there be an interval I = (0, 1), a nonempty set X" E l that consists of no more than m ~ - 1 points of the interval I, and the point x' 6 I, 0 < z t < min,~x, z. We say that x' is singular with respect to X* and a natural number L, if, for some x* from X ' , ( x ' , x ' ) 6 R~. and ( x ' , x ' ) has number L in R ,2. . Now let there be a point x" 6 I, m a x , e x , x" < 1. We say analogously that x" is singular with respect to X" and a natural number L, if for some x. from X* ( x . , x " ) 6 R t~. and ( x . , x " ) has the number L in R*~.. Furthermore, let there be intervals [' (0, 1), [" = (0, 1), a point y' E I' and a nonempty set Y" that consists of no more t h a n m ~ points of the interval [". We say that y' is singular with respect to Y" and a natural number L, if for some y .It from VII

(y',

y'") 6 R2v., and (y', y*") has the number L in R2y.... Finally, let there be a n o n e m p t y set y' that consists of no more than m ~ points of the interval [', and the point y" E l". Analogously to what was mentioned above, we say that y" is singular with respect to Y' and a natural number L if, for some y'. from Y', (y'., y") E R~, and (y.~,y") has the number L in R~,. As can be easily seen, there can be no more t h a n m ~ points in any of these cases (no more than m ~ - 1 in the first two cases). By {r} we denote the set of all rational points of the interval (0,1). Since the set of all rational points (0,1) is countable [15], the points can be enumerated. i.e., {r} = {rt, r2, r 3 , . . . } . By q,, q2, q3,--- we denote the sequence of ascending-ordered odd prime numbers, and we introduce the number M = 2(m~ 2. Let the strategy a'[. 1 on a move with any odd number in every interval [J where the search takes place prescribe that the first player unlabel all labeled points if there are no more than lj such points in [J, or label some lJ points if there are more than l j points in [J. Moreover, let jl, j2 > jl be arbitrary intervals in which in the generalized session the games with parameters m j~ and Ijx (respectively, rn j2 and Ij2) take place, let every set X j~ C I jl that consists of m *jl <_ rn j~ points, X j= C [J2 that consists of m "j= < m j2 points (m *j~, m *j2 are non-negative integers), and every number n such that the number k of the points in X j* (-1 (0, r,~] is not equal to zero and the number k* of points in X j' f3 (r=, 1) is also not equal to zero (here r= E {r}), a*[.] have the following properties: (1) At the move with the odd number q.

2p + l = Mq2~_~q2j, + 2 i - 1 ,

1 < i < M/2,

for the set of labeled points X j~ given in the interval [J~ either "p+xa'J~ C X j~ N (0, r,~] holds if Ijx < k, or A .p+l a D X j' f'l (0, r,~] if Ij~ > _ k. In the case where in X jx N (0, r~] there is a point y~" with the number s' in the ascending-ordered set of points that belong to (0, r,~] and are singular with respect to X j' Cl (r,~, 1) and L, where s' rood(k*). = z, we have A'J1 (2) At the move with the odd number 2p + l = Mq2j,_,q~j, + 2 i - 1 ,

1 < i < M/2,

for the set X a of labeled points given in the interval I j~ either "'v+la*J'C X j~ f3 (r,~, 1] if Ij~ < k" or "'v+ta*Jx D X j~fq(r,~,l) i f I j~ >_ k'. In the case where in X j~ N ( r ~ , l ) there is a p o i n t y~ with the number s" in the ascending ordered set of points that belong to (r,, 1) and are singular with respect to XJ~ N (0, r=] and L, where s" mod(k). = z, we have --p+l A*Jl 9 Y2. " n

(3) At the move with the odd number 2p + 1 = Mq~j~q2j2 + 2i - 1, 1 < i < M / 2 , for the sets X j~ C I a , X j2 C [J2 of labeled points given in the intervals [ a, [J2 , a'J2 "p+t :fi ~ holds and in the case where there is a point y.1 in X j~ with the number t' in the ascending-ordered set of points that belong to [Jx and are singular with respect to .u

and L, where t' m~

we have . 4 ~ t 9 y**.

(4) At the move with the odd number 2 p + [ = M q 2 j ~ q ~ i ~ + 2 i - 1, 1 < i < M / 2 , 1736

for the sets X s~ C I n , X ~2 C I s: of labeled points given in the intervals I J', I s2 --p+t A *a = o, and in the case where there is a point y*~ in X j2 with the number t" in the ascending ordered set of points that belong to I j2 and are singular with respect to X j' and L, where t" m~

we have A ~ 1 9 y.2 (here i, L are arbitrary

natural numbers and Ap+t, "J~ Ap+ *J~l are sets such that a*[-] prescribes t h a t one unlabel the points of them at the move with the odd number 2p + t in the sets X j~ C t i~ , X j2 C I is, respectively). qrL

qn

Note that the sets of numbers considered { and { M q s j ~ q ~ + 2 i -

+ 2 i - 1 }, { Uq j,_,

.

qn

.

+ 2 , - 1 },

+ 2 , - 1 }, {

1} do not contain equal elements and are disjoint.

Assume that there are sequences {X0J } of initial sets and strategies b[.] of the second players such that

a[.], b[.]] > 1. Then one of two cases holds, namely: either there exists a number j l of the interval where a game with parameters rn jl and l jl takes place in the generalized session and two points yx < ys, {yl,ys} C [J~, that are jl contained in any set X u C I j~ of labeled points arising after the move with the number N > N" (case 1), or there exist numbers jl < j 2 of intervals, where the games with parameters rn j~ and lj~, (respectively, rn j2 and lP) take place in the generalized session as well as two points yl E I j~ and y2 E I j2 such that yi, i E {1,2} is ji

contained in every set X g C I :/' of labeled points arising after the move with the number N _> N" (case 2); here N" is a natural number. Let the first case take place. Then there is r,~. C {r} such that yl < r,~. < y2 and n" > N* (n* is a natural number). Moreover, either (yl,ys) E R 2Y2 and has the number L' in R Y2 2 ~ or (y~, ys) E R t and has the jl number L" in R Yl1 ' i.e., for N > N* either yl is singular with respect to X N V1(r,~., 1) and L', or Y2 is singular Yl

with respect to X N j l gl (0, r~.] and

L/I.

J~ C?(r~., i) and Assume first that, for N > N , yt is singular with respect to X N "

number Mqsj~_lqsj~. Note that N~" = ~,, q2j~_lqsj~ >

>

L'.

By N~ ' we denote the

Let, after the move with the number N ( there

be k'~ points in X j' , N (0, r~.], k " points in X j' , f3 (r,~., 1), and yx have the number s~ in the ascending-ordered g~"

N l"

set of points that belong to (0, r~.] and are singular with respect to X NJ'( ~ (r~., 1) and L' (here k~, ' k~' are natural numbers, where 1 .< k~. < m. j~ -. 1 .1 < k~' < m j' - k ~ ) .

Then X g~'+l j~, ~ yt when k 'l < Ij~ , and for

k[ > Ij~ either in the intervals I j' the first player unlabels yx at the move with the number mod(k:'~

N~=N~'+2i'

1-1,h

--

"

'

. "

st,'

<- h -"t <

1

k ~ ' <-

m s l - - k '1 <

9

m sl -- I jl ,

j~ if Yl ~ XN~_ ~ and the points from (r~., 1) were not unlabeled at the previous moves after the move with the number N~", or after a move with the number ..t

"

I

"

N;' = N~' + 2i'~', 1 < z~ <_ k~' <_ rn ~ - k, <_ ms' - Ij~, there are k~ points in X ~' , N (O,r,~.], 1 < k~ < k~ - 1, and there are k~' points (k~' + 1 < k~' < m ~ - k;) in X ~ , N (r=., 1) (i~', k~, k~' are natural numbers). Let yt have the number s~ in the ascending-ordered set of points that belong to (0, r~.] and are singular with respect to XJ~N~'0 (rn. , l) and L'. Then X ~N~,,+t ~ y~ again for k' < l? and for k.~ > l? either in the interval 1~ the first player unlabe[s yl at the move with the number ,

, .!

9 .., .t

.., "

1 < z~ < k s < m :~

I

-

k 2 ~_ m j '

mod(k~'), --

.!

"

k 2 ~ m ~t

-

Ij~, 1737

j~

ifyl E X ~ _ 1 and no points from (r,~., 1) were unlabeled in I j' at the previous moves after the move with the number N~', or after a move with the number ,tt

-

!

N~' = lV( + 2i;', 1 < ~2 < k;' <_ m j'

'

k 2 < m J' - l j',

jl Cl (0, r,,.]. Moreover, there will be k~' points in XN;, J' n ( r . . , 1), there wilt be k~, 1 _< k 3, < k 2, - I, points in XN;, k ~ ' + 1 < k~' < m j~ - k;

(i~', k~, k~' are natural numbers) and so on. Thus, it is not difficult to see that after a move with the even number N " N?' < N;' < g ; ' + 2(ra~' - lJ~)(m j' - P ' ) ( m jl - 15-' - 1), .il there will be no more than 15~ points in XN., N (0, r~.], if the first player does not unlabel y~ in the interval I j' at the moves with the numbers from N~" to N*', and then XN.,+I ~ yl. Therefore, in case 1, where N >__N ' , jl yl is singular with respect to X N F) (r,~., 1) and U, and in the interval I jl the first player unlabels yl at a move with the number N ' = M"" qRj~_lq2jl q~: + 2i' - i > N * ,

1 < i ~ < M/2,

J~ when N >_ N ' . This contradicts the condition that yl E X ~ for where i' is a natural number, i.e., Yl ~ XN, N>_N'. Assume now that Y2 is singular with respect to X xjl N (0, r~.] and L' when N _ N*. By N~" we denote the n*

n*

qL u 9 Note that Mq2j~-lq2j~ qL" > rF > -number Mq2jl-lq2j, ..

jl

N'*.

Let, after the move with the number N 1,Je , there be

jl

t!

It

k~ points in XN.,, Cl (r,~., 1), k~ points in XN~,, fq (0, r,~.], and Y2 have the number s~ in the ascending-ordered set of points that belong to (r,~., 1) and are singular with respect to XN~,, j~ fq (0, r,~.] and 9 It

"

ll

L"

(here k~*" , k~" are

"

natural numbers such that 1 <. k 1 . < m . ~ - . 1, 1 < k I < m 3~ - k('). Then X j~N~,,+I ~ y2 when k l''', and for .,, k 1 > l j~ either the first player unlabels y2 in the interval [jl at the move with the number .

N; = N t " + 2i'[ - 1 ,

i'[

rnod(k") It

=

"U ~

st, 1 < h - -

It ~

kt

*"

rn j' - k~ <_ rn j' - Iil,

jl if y: fi Xx;,_t and the points from (0, r~.] were not unlabeled at the previous moves after the move with the .,, number N t , or after a move with the number It

It

"I It

N~ = N~ + 2i'(', 1 <_ h

It

"

'

<- k, <_ rn" - k~" < m ~' - Ij', It

roll

II

jl

there will be k~*" points in XJl'"x~ ~ (r,~., 1), 1 <_ k~ <_ k t - 1, and there will be k~ points in XN;,, N (0, r,~.], kttl + 1 <_ k:tt <_ m j~ - k~. " ( h"." , k~. " ,

~!

are natural numbers). Let y~ have the number s~tt in the ascending-

ordered set of points that belong to (r,~., 1) and are singular with respect to X Njl( , f'l (0, r,~.] and L" . Then jl

..

.u

again XN~,,+~ j y~ if ke _< P', and if k~ > Iit, then either the first player unlabels y2 in the interval I j' at the move with the number :V2=N; 1<

1738

"ll

"

-) .*"

+z(,, II

~ < k~

<_ m~ "

+i~')-t,,, .It

k~

.*" '

.t/ mod(k;') tt

+,~

< m ~ - P~,

=

.~,

if y2 E XJ',, N ~ - i and the points from (0, r,.] were unlabeled in IJ ~ at the previous moves after the move with the number N~" , or after a move with the number It

.lit

II

"

.It

N~" = N~ + 2i~", t < ~: <_ k2 < me' - k: .

ji

."

there will be k~ points in X N ; , , N ( r , . , 1 ) , 9

.It

.

tt

.it

1 < k3

'

< m ; - l2 ,

*"

tt

jt

_< k 2 - 1, there will be k 3 points in XN;,,N(O,r,~.],

Ig

k~' + 1 _< k~' _< m Jx - k3 (z , k 3 , k 3 are natural numbers), etc. Thus, it is easy to see that after a move with an even number

N .,, , N 1.,l <_ N'" <_N~*" + 2 ( m J ~ - P ' ) ( m J ' - l J ~ - l ) , there will be no more than p! points in X N* j~ , N (r~., 1), if the first player does not unlabel y2 in the interval ..

31

[J~ at the moves with the numbers from N 1 to N*", and then NN.,,+t ~ Y2. Therefore, in case 1, when, for J~ ~ (0, r~.] and N >_ N " , y2 is singular with respect to X N number

L",

the first player unlabels y2 at a move with the

n*

q L tt N" . . . .[ [ / f q2j~--lq2j~ + 2i" -- 1 >

N*

, 1 <__i t' <__M / 2 ,

jl when N > N*. where i" is a natural number, i.e., y2 r X Njl , , . which contradicts that y2 belongs to every set X N The contradiction obtained allows one to establish the impossibility of case I. Assume now that the second case takes place. Then either the pair (yl, y2) E R2v2 and has the number L' in Ru2~, or (yt, y2) E Rly~ and has the number L" in Rive, i.e., when N >_ N* either y ~ is singular with respect J~ and L' or y2 is singular with respect t o X NJ~ and L". Assume first that yl is singular with respect to to X N X ~ and L' when N _> N ' . By N "'1 denote the number lvlq2jx q27. Note that

l~4q~};'q2j2 > N ' .

N"I=

9 .j2 . j2 Let there be m *?, 1 _< m 1 <__ m J~ points in Xu., t after the move with the number N *'~ and yt have the j2 number t '1 in the ascending-ordered set of points that belong to I j~ and are singular with respect to X N . ~

and L' (here m~ ? is a natural number, where 1 __ m~? _< rnJ~). T h e n the first player makes y~ unlabeled .j2

9

= rn J2 in the interval I j~ at the move with the number N '2 = N "ll + 2i '1 - 1, i 'l

when m 1

1 < i 'l < rn~? < rn? if yl E XJ~,~ --

--

N

rnod(m[

=

)2

) 'I

t ,

and no points were unlabeled in [J~ at the previous moves after the move

-1

with the number N *'l, or after a move with the number .

N*'2 = N*'l

+2z

--*'i

,

I_< i*'l <__rn-1? < r n :2' ,

j2 there will be rn; ? points in XN.,~, rn 1.j~ + 1 <_ rn.*? 2 <__rn ~" (i ''1, rn; j2 are natural numbers). Let yt have the number t '2 in the ascending ordered set of points that belong to I j~ and are singular with respect to X";., 2 .j2

and U. Then again for rn 2

=

m ?

the first player unlabels y I in the interval [J~ at the move with the number

No3 = N., 1 + 2 ( i ' " + ~0 .,~) - i , i., 1 + ~0" ...... "'2 < m ~'2, ~ " J2)t, 2 , i < ~0 vjl

.j2

if y~ E . , x o a t, and for m.2

.~

< m ~', then either in the interval I j' the first player unlabels yl at the move

with the number N ''~= N " ' 1 + 2 ( i " ' l + i ' ~ ) - l ,

9-'1

~

+ i ''2

m~

)t'2

"2

, 1 _<~

.j2


9


if yl E XN,~_I J' and at the previous moves after the move with the number N "'2 no points were unlabeled in

I j*, or after a move with the number N "'3

N ' ' 2 + 2 z "- '2 , 1 ~_i "'2
j2

,

fl .fl 9 . .j2 there will be rn*3j2 points in XN.,3, m 2 -{- 1 _< m3J* < m J2 (i *'2, m 3 are natural numbers), etc. Thus, it is

easy to see that after a move with the number No' = N * " + 2 i * ' ,


0
9

1),

,

j2

I

where z*' is an integer, and there will be rn ~2 points in XN~,, and yl will have a number t o in the ascendingordered set of points that belong to [J~ singular with respect to X;0., and L' if the first player does not unlabel yl in the interval I jl at the moves with the numbers from N *'I to N~ 1 and then yl will be unlabeled in I j~ after the move with the number ,

N "'~+2(i*'+io' )-1,

.., rnod(m

i* + z o

j2

=

).1

.*'

"

to, 1 < , 0 -< mJ2.

Therefore, in case 2, when, for N > N*, yl is singular with respect to X ; and i f , the first player unlabels yl in the interval [J~ at the move with the number qt N*

No = Mq2),

q27 + 2i'o - 1

> N*, 1 <_ i o <_ M / 2 ,

9i jl jl where ~0 is a natural number, i.e., yt ~ XN;, which contradicts the fact that yl belongs to every set X N for N>N*. Assume now that, for N >__ N*, y2 is singular with_ respect to X yJ~ and L". By N *'q we denote the number

M q 2 p q ~ S " " Note that M q 2 j ~ q ~ " > N*. Let, after a move with the number N *''1, there be m *J~ 1 points in j~ XN.,, ~ and y2 have the number t 'q in the ascending-ordered set of points that belong to I ? and are singular with respect to X Nj~* ,,~ and L" (here rn*tj' is a natural number, where 1 < m'~j' < m j~). Then for rn~ j' = m j' --the first player unlabels y2 in the interval [j2 at the move with the number -"1 m ~

No 2 = N * ' ' x + 2 i o ' - 1 , j2 if y2 E XN~,2 1 and for

/7/'1 jl

*o

=

t

"1

""1

jl

, l_<*o -
< m j l , then either the first player unlabels y2 in the interval [j2 at the move with

the number N ' ' 2 = N *''x+2i ' q -

1, z,,~ -,od(~7' )t 'q, 1 < i,, 1 _< rn~j, _< rn J~,

j2 if y2 E Xw,,2,1 and at the previous moves after the move with the number N*" no points were labeled or after a move with the number N " ' ' ~ = N *''~+2z

, 1 <_z '''~
'*"1

-

-

jl

,

9j~ yj~ ,,~ .j~ ~..,,~ .j~ there will be rn 2 points in " N * rn~~ + 1 < rn 2 < rn~ U , m~ are natural numbers) 9 --.

Let Y2 have the number t ''2 in the ascending-ordered set of points that belong to I j2 and are singular ~ ~ and L". Then again for rn 2"J~ = m )~ in the interval [J~ the first player unlabels y~ at with respect to XN.,, the move with the number .'~"3 . =

1740

j,~/~*"l

+2(i"

"1

+*0

""'2

)-

1,

'="1 '"2 m ~ rn~l ) "2 * +~o = t , 1

,,.~

<__io ' _ < m

jl

,

.

,

if y2 E XJ;~,~_I, and if m : J < m

jz

, then either the first player unlabels y2 in the interval I P at the move with

the number "o2

N ''3=N ''q+2(i '''l+z o)-1,

i"

'q

'"2 rn~

+z o

2l

=

) "2

t

, 1_<

i"2

"

_
i2 if y2 E XNg,3 1 and no points were unlabeled in the interval I j2 after the move with the number N "''2 or after a move with the number 9, N *''3 = N *''2 + 2z..,r 2 , 1 < z."r'2 _< m:. j l < m J~

jl 3 , rn~jl + 1 < m3Jl < mJ~ ~ ri., 2 , m .3j l are natural numbers) etc. Thus, it is there will be m~ il points in XN.,, easy to see that after a move with the number N~" = N *''1 = 2i*", 0 < i*" < m J l ( m jl - 1), where i'" is an integer, there will be m j~ points in X~g,, and y2 will have a number t~ in the ascending-ordered set of points that belong to [j2 and are singular with respect to X j~ ,, and L", if the first player unlabels y2 in g0*

the interval I j2 at the moves with the numbers from N *''1 to N~", and then y2 will be unlabeled in [j2 after the move with the number t

N ' ' ' 1 + 2 ( i ' ' ' + z ..', o )-1,

)/.,, 1 <~ i 0' < m jl. z.#, +zo..,, mod_(rnJ ~ -

Therefore, in case 2, when, for N :> N* y: is singular with respect to X gJ~ and L", the first player unlabels y2 in the interval I j2 at the move with the number N*

It

Z A~"

~ L1t

"1!

N O = ~v~q2j, q2j~ + 2% - 1 > N*, 1 < i'o' <_ M / 2 , .. j2 j~ where z0 is a natural number, i.e., y2 ~ XN~, ' which contradicts the fact that y2 belongs to every X N when N>_N*. The contradiction obtained allows one to state the impossibility of case 2. The impossibility of cases ~ and 2 ~llows one to establish the impossibility of the inequality P[{X~}, a'[-], b[-]] > 1 for no sequences {Xos } of initial sets and b[-] of the strategies of the second players. Therefore,

p[(xg},a'[ ],b[.]] <_ for any {X~} and b[-]. Thus, the proof of Proposition 3.4.1 is completed. For some additional assumptions, with the use of continuum hypothesis, the results obtained above in this section, can be strengthened, namely, we can prove the following: P r o p o s i t i o n 3.4.2. For a generalized session of games of search and completion such that for each number j the corresponding game of search and completion in the interval [J with arbitrary natural values of p a r a m e t e r s m j and l j is played, such that Ij < m j < rn ~ (here rn ~ is a natural number and j ranges over a nonempty finite segment of positive integers or the whole set of natural numbers), where at least f o r one value j, j = j' we have that 1 = Ij' < m , the following equality holds: c~

{l'}] = 1

We prove Proposition 3.4.2. Consider a generalized session of the game of search and completion, where for each number j in the interval I j the corresponding game of search and completion with arbitrary natural values m s and Ij of the parameters is played, such that Ij <_ mJ < 7n~ where for some value j = j', 1 = Ij' < m j' 1741

holds. Since the inequality c~

{P}] < 1, holds it is easy to see from (3.2) t h a t to prove Proposition 3.4.2

it suffices to show that for every strategy a'[.] of the first player and sequence iX0 j} of initial sets there exists a sequence b'[.] of strategies of the second players, for which

7:'[{Xo~, a'[.], b'[-]] ___ 1. We fix an arbitrary strategy a'[.] of the first player, a sequence of iX0 j } of initiat sets, and a set X ' C X'oj', which contains m j' - 2 pairwise distinct points (X' = o for rnJ' = 2). The point z N E I i ' \ X ' is called singular for the move with an odd number N if for every set X C [ i ' X D ({x N} U X ' ) I which consists o f m i' pairwise distinct points, there exists an odd number M > N such that at the move with an odd number N',

N < N' < M, for every sequence {X b}, where X 'j' = X , X 'j = Xo i for every j ~ j' of every set of labeled points, the strategy a'[-] prescribes that the first player unlabel x N in the interval I Y for N' = M. For any move with an odd number there can be no more than one singular point. In fact, if for a move with the odd number N there were two singular points x N r x N in I i ' \ X ', then for X'J' = {xx~, x N} t_J X ' the relations ,y ,j, Ak+1 M { x ~ , z ~ } = o would hold simultaneously for N ___ 2k + 1 < M ~, A~+ 1 9 x N when 2k + 1 = M ~ for every i E {1,2}, which is impossible (here k is an integer nonnegative number, M 1 and M 2 are odd numbers Jj r

no greater than N, Ak+ 1 is either empty or contains only one point. The strategy a'[-] prescribes that the first player unlabel this point at the move with the number 2k + 1 when there is a set { X 'i} of all sets of labeled points). Thus, for any move with an odd number there can be no more than one singular point. Therefore, the set X " C 1i' of all points singular with respect to a move with an odd number is no greater than countable. Let the sequence b'[-] = {b'J(-)} of strategies of the second players be Such t h a t in the game carried out in the interval [J, for any number j ~ j', then b'J(.) prescribes at every move with an even number, before which there are only m j - 1 labeled points in [J that one label exactly that point from X0j, which was unlabeled before this move (or label none). In the game carried out in the interval I j', at every move with an even number, before which there are only m j' labeled points, the strategy b'/(.) prescribes to label a point y that either belongs to X ' if there is an unlabeled point in X' or belongs to [J'\(X' U X") if there are no unlabeled points in X' and a point from X " is labeled, or a point such that if there are no unlabeled points in X' and there are no labeled points in X " , then every labeled point z E [JJ\(x ' U X") given before this move, starting from this move remains labeled in I s' until the first player unlabels y in [1' (when x E [J'\(X' U X')), the given point y exists, since otherwise x would be singular for a move with this number). Let the first and second players hold to the strategies a'[-] and {b'J(.)}, respectively. Then for a sequence

{X'oi} of initial sets a point x E [J'\(X' U X") remains constantly labeled starting from a move, i.e., remains labeled after the end of a generalized session and, therefore, 'J

[{x0 }, a'[.], b'[-]] > 1

Thus, the proof of Proposition 3.4.2 is completed. Finally, consider a generalized session of a game of search and completion, for which it is not difficult to find the value of the corresponding function c'[.] without use of the continuum hypothesis. The following proposition is true. P r o p o s i t i o n 3.4.3. The equality {li}] :

0

holds for a generalized session of search and completion where for each number j the corresponding game of search and completion is carried out in the interval [J with arbitrary equal values m j = li of the parameters (here j ranges over a nonempty finite segment of nonnegative integers or the whole set of positive integers). The proof of Proposition 3.4.3 is obvious, since at every move the first player can carry out searches in arbitrary intervals such that after each search there remains no labeled point in an interval where the search takes place. 1742

3.5. U n s o l v e d P r o b l e m s In the concluding of the third section, we formulate two main groups of problems that are not solved completely and are related to sessions and generalized sessions of games of search and completion. These problems were considered above by means of the continuum hypothesis. The first group of problems: For a session of games of search and completion with arbitrary natural values of the parameters of the games that take place in the session, find the value of the corresponding function c[-]. In particular, determine whether this value equals one or zero in the case where the parameters of all games of the session are bounded in totality and the absolute value of the difference of the parameters is greater than one, at least for one game of the session. The second group of problems: For a generalized session of games of search and completion with arbitrary natural values of the parameters of the games that take part in the session, find the value of the corresponding function cO[.]. In particular, determine whether this value equals one or zero in the case where the parameters of all games of the generalized session are bounded in totality and the parameters of a game of the generalized session are not equal in at least one game and the least parameter is greater than one. These problems are interesting from the mathematical point of view, and their solution can be a natural development of the results obtained in Secs. 3.2-3.4.

REFERENCES 1. R. iizeks, Differential Games [Russian translation], Mir, Moscow (1987). 2. R. Bellman, Dynamic Programming [Russian translation] Inostrannaya Literatura, Moscow (1960). 3. Yu. B. Germeier, Introduction to Operations Research Theory [in Russian], Nauka, Moscow (1971). 4. V. A. Gurvitch, "On the theory of multistep games," Zh. 1485-1500 (1973).

Vychisl. Mat. i Mat. Fiz., 13, No. 6,

5. N. N. Krasovskii and A. I. Subbotin, Positional Differential Games [in Russian], Nauka, Moscow (1974). 6. N. N. Krasovskii, "Differential games. Approximate and formal models," Mat. Sb., 107, No. 4, 541-571 (1978). 7. B. I. Model', "On certain problems of dynamic programming," Mashinostroenie, No. 3, .39-44 (1974). 8. B. I. Model', "On the existence of a unified e-optimal strategy and satisfaction of the Bellman equation in the extended class of dynamic processes. Part I," [zv. Akad. Nauk SSSR, Set. Tekh. Kibern., No. 5, 16-22 (1975). 9. B. [. Model', "On the existence of a unified ~.-optimal strategy and satisfaction of the Bellman equation in the extended class of dynamic processes. Part II," lzv. Akad. Nauk SSSR, Set. Tekh. Kibe7a., No. 6, 14-20 (1975). 10. B. L Model'. "On a class of differential games." [zv. Akad. Nauk SSSR, Set. Tekh. Kibern., No. 2, 53-59 (1978). 11. B. I. Model', "On a family of infinite-step positional games," Izv. Kibern., No. 3, 188-189 (1984).

Akad.

Nauk SSSR, Set.

Tekh.

1743

12. B. I. Model', "On properties of a joint price function in the class of processes of sequential decision making," lzv, Akad. Nauk SSSR, Set. Tekh. Kibern., No. 3, 188-189 (1984). 13. B. I. Model', Elements of the Theory of Multistep Processes of Sequential Decision Makin9 [in Russian], Nauka, Moscow (1985). 14. B. [. Model', Multistep Processes of Search with Augmentation [in Russian], Nauka, Moscow (1990). 15. I. P. Natanson, Theory of Real Functions [in Russian], Moscow, Nauka (1970). 16. J. Neimann and O. Morgenstern, Theory of Games and Economic Behavior [Russian translation], Moscow, Nauka (1970). 17. B. N. Pshenichnyi, "Linear differential games," Avtomat. Telemekh., No. 1, 65-78 (1968). 18. E. D. Stotskii, "On descriptive game theory," In: Problems of Cybernetics [in Russian], Fizmatgiz, Moscow (1962), pp. 45-54. 19. E. Zermelo, "On application of set theory to the theory of chess games," In: Matriz Games [in Russian], Fizmatgiz, Moscow (1961), pp. 167-172. 20. D. Gale and F. Stewart, "Infinite games with perfect information," In: Contributions to the Theory of Games, Princeton Univ. Press (1953), pp. 245-266.

1744