Комбінаторна гра — "Зв'язна незв'язність"

Abstract

Комбінаторна теорія ігор — це математична теорія, що вивчає ігри двох осіб, де у кожен момент часу є позиція, яку гравці почергово змінюють певним чином, щоб досягти певного виграшу. Комбінаторні ігри можуть бути інтерпретовані як ігри на графах. У роботі розглядається комбінаторна гра на неорієнтованому графі «Зв’язна незв’язність», яка може бути використаною при моделюванні процесів конкурентної боротьби. Для розв’язання цієї задачі розроблено власний метод фінальних графів, який полягає в аналізі ситуації, яка утворилась за крок до завершення гри. В роботі доводиться оптимальність стратегії, результатом якої є повне розв’язання задачі для довільної кількості вершин. При дослідженні гри встановлено переможця в залежності від остачі, яку дає кількість вершин при діленні на чотири.

The combinatorial theory of games is a mathematical theory that examines the games of two persons, where at each moment of time there is a position that players in turn change in a certain way in order to achieve a certain gain. Combination games can be interpreted as games on graphs. In this paper we consider a combinatorial game on a non-oriented graph «Connective incompatibility», which can be used in the simulation of competitive struggle. To solve this problem, an own method of final graphs has been developed, which consists in analyzing the situation that was formed one step before the end of the game. The optimality of the strategy, which results in the complete solution of the problem for an arbitrary number of vertices, is presented in the paper. In the study of the game set the winner, depending on the remainder, this gives the number of vertices when dividing by four.