Games of search and completion (Q676805)

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 such games, carried out 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 and in that of possible applications, in particular to studying various sorting processes. The games of search and completion considered 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 \(l\) 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 \(l\) unlabeled points to it (we call this process labeling). On the next move, the first player searches again through \(m\) 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.