BIE-VAK Selected Combinatorics Applications
Go to course navigation

4. Fixed Point Game

Consider a game plan that is formed by an arbitrary triangulation inside a square. An illustration of one such plan can be found in the figure below. On this plan, a two-player game of player GG and RR is played. At the beginning of the game, the player GG occupy the vertices aa and cc, while the player RR occupy the vertices bb and dd. Players alternate in turns, and in each turn a player may occupy (paint with his color) any previously unoccupied vertex. A player wins if he manages to occupy all the vertices on some path between his initial vertices. If the player who is currently on the turn has nowhere else to move, but neither player has completed their path, the game ends in a draw. The starting player is the player GG.

An illustration of the game plan
Figure 1. An illustration of the game plan

Your task is to prove the following claim:

Claim

The game defined above cannot result in a draw.

Instructions

  • Read the task and solve it by yourself.
  • Then, send scanned and hand-written solution as a single PDF file using MS Teams.
  • The deadline for submission is March 20, 2025, 23:59:59. The deadline is strict.
Bonus Assignment

In a programming language of your choice (except HQ9+ and its derivates), write non-empty source code such that, without any inputs, it print itself to the standard output. In particular, the source code cannot use any file operations.