Problem

Source: 239 School Open MO, 2023, Junior league, Problem 1

Tags: combinatorics, board, colorings



Each cell of an $100\times 100$ board is divided into two triangles by drawing some diagonal. What is the smallest number of colors in which it is always possible to paint these triangles so that any two triangles having a common side or vertex have different colors?