MathDB

2

Part of 2021 Regional Olympiad of Mexico Center Zone

Problems(1)

Travelling through Mictlán

Source: 2021 Mexico Center Zone Regional Olympiad, problem 2

1/17/2022
The Mictlán is an n×nn\times n board and each border of each 1×11\times 1 cell is painted either purple or orange. Initially, a catrina lies inside a 1×11\times 1 cell and may move in four directions (up, down, left, right) into another cell with the condition that she may move from one cell to another only if the border that joins them is painted orange. We know that no matter which cell the catrina chooses as a starting point, she may reach all other cells through a sequence of valid movements and she may not abandon the Mictlán (she may not leave the board). What is the maximum number of borders that could have been colored purple?
Proposed by CDMX
Mexicocombinatoricsboard