Games of search and completion
type: Item
instance of: scholarly article
title: Games of search and completion
zbMATH Open document ID: 0866.90149
DOI: 10.1007/BF02362848
author: B. I. Model
published in: Journal of Mathematical Sciences (New York)
publication date: 1997-03-23T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 91A50
Mathematics Subject Classification ID: 90B40
zbMATH DE Number: 993749
zbMATH Keywords: multistep game processes
zbMATH Keywords: guaranteed result
MaRDI profile type: Publication
cites work: Q3274591
cites work: Q3048636
cites work: Q5817866
description: scientific article; zbMATH DE number 993749