Bariz - Problem

Source: 17th Durer Competition 2023 E+ P2

Tags: combinatorics, graph theory

oVlad

25.11.2023 13:21

One quadrant of the Cartesian coordinate system is tiled with $1\times 2$ dominoes. The dominoes don’t overlap with each other, they cover the entire quadrant and they all fit in the quadrant. Farringdon the flea is initially sitting at the origin and is allowed to jump from one corner of a domino to the opposite corner any number of times. Is it possible that the dominoes are arranged in such a way that Farringdon is unable to move to a distance greater than 2023 from the origin?

Nice, quick solution: suppose that the flea cannot move far enough, hence it can only move in a bounded area. Consider all the routes the flea can take and make a graph where the vertices are the corners of the dominoes visited by the flea and the edges are the diagonals traversed by the flea. Since the flea can only move in a bounded area, this graph is finite, but the origin has degree one, while every other vertex is the corner of an even number of dominoes, hence it has even degree. Therefore, we have a finite graph with precisely one vertex of odd degree, contradiction.