Аннотация:В данной магистерской диссертации рассматривается натуральный ряд, обозначенный через N и его подмножество K(2p), в котором удалены точки кратные 2p, где p - простое число, то есть удалена одна арифметическая прогрессия \(2p,2p) с началом в точке 2p и шагом 2p: K(2p)=N \\ \(2p,2p). В некоторых точках этого подмножества сидят угонщик и милиционеры. От каждой точки, где сидят милиционеры, вычисляются кратчайшие расстояния до угонщика, то есть расставляются радары таким образом, чтобы милиционеры могли однозначно определить позицию угонщика.
В данной задаче есть только два типа шагов (±2) и (±p). Расстоянием ρ(a,b) между двумя клетками a и b называется минимальное число шагов, которое нужно сделать, чтобы попасть из точки a в точку b, причём из чётных клеток нельзя передвигаться с шагом 2, а с клеток кратных p нельзя передвигаться с шагом p. В рамках данной работы доказывается существование конечной системы множеств милиционеров, которая всегда будут ловить угонщика, а также нахождение минимальной мощности такой системы. Говорим, что конечная система милиционеров ловит угонщика, если любой набор расстояний должен быть порождён однозначно точкой из K(2p) и положениями милиционеров.
Ключевые слова: множество натуральных чисел, обобщённая арифметическая прогрессия, несжимаемая прогрессия, мощность конечной системы.
Abstract
This master's thesis considers the natural series, denoted by N and its subset K(2p), in which the points that are multiples of 2p are removed, where p is a prime number, that is, one arithmetic progression (2p,2p) with the beginning at the point 2p and step 2p: K(2p)= N \(2p,2p). At some points in this subset, a hijacker and policemen sit. From each point where the policemen sit, the shortest distances to the hijacker are calculated, that is, the radars are placed in such a way that the policemen can unambiguously determine the position of the hijacker.
In this problem, there are only two types of steps (±2) and (±p). The distance ρ(a,b) between two cells a and b is the minimum number of steps that you need to take to get from point a to point b, and you cannot move from even cells with a step of 2, and from cells that are multiples of p you cannot move with a step p. Within the framework of this work, the existence of a finite system of sets of policemen who will always catch the hijacker is proved, as well as finding the minimum power of such a system. We say that the final system of policemen catches the hijacker if, by any set of distances to the policemen, it is possible to uniquely restore the position of the hijacker.
Keywords: set of natural numbers, generalized arithmetic progression, incompressible progression, cardinality of a finite system.
