Відповідь залежить лише від парності .
Непарне : двох кольорів достатньо. Пофарбуємо клітинку у колір (i + j) \bmod 2. Манхеттенська відстань між клітинками дорівнює |\Delta i| + |\Delta j|, а величина (i+j) змінюється на \Delta i + \Delta j, що має ту саму парність. Тому якщо відстань дорівнює непарному , то суми i+j у двох клітинок мають різну парність, отже кольори різні.
Менше двох кольорів не буває: за умовою k < \min(n, m), тому пара клітинок на відстані рівно у полі точно існує.
Парне : потрібно рівно чотири. Спершу покажемо, що трьох замало. Розглянемо чотири клітинки
(вони цілочисельні саме тому, що парне). Неважко перевірити, що будь-які дві з них перебувають на відстані рівно , тому всі чотири мусять мати різні кольори.
Тепер конструкція на чотири кольори. Перейдемо до повернутих координат
Тоді \max(|\Delta u|, |\Delta v|) = |\Delta i| + |\Delta j|, тобто манхеттенська відстань перетворюється на відстань Чебишова. Отже, для клітинок на відстані виконується |\Delta u| = k або |\Delta v| = k.
Пофарбуємо клітинку парою бітів
що дає чотири кольори. Якщо дві клітинки різняться в координаті рівно на , то їхні значення різняться рівно на одиницю, тобто перший біт відрізняється; аналогічно для . Отже, кольори різні.
Технічна деталь: і особливо можуть бути від'ємними, а цілочисельне ділення від'ємних чисел у більшості мов округлює до нуля, а не вниз. Найпростіше додати до обох координат достатньо велику сталу (наприклад, ), щоб вони гарантовано стали додатними.
Складність — , тобто просто виведення поля.