Problem

Source: 42nd International Tournament of Towns, Junior O-Level P5, Spring 2021

Tags: combinatorics, board, Tournament of Towns



There are several dominoes on a board such that each domino occupies two adjacent cells and none of the dominoes are adjacent by side or vertex. The bottom left and top right cells of the board are free. A token starts at the bottom left cell and can move to a cell adjacent by side: one step to the right or upwards at each turn. Is it always possible to move from the bottom left to the top right cell without passing through dominoes if the size of the board is a) $100 \times 101$ cells and b) $100 \times 100$ cells? Nikolay Chernyatiev