8. В таблице 6 × 6 некоторые клетки закрашены. Известно, что существует ровно один способ выбрать шесть закрашенных клеток — по одной в каждой строке и каждом столбце. Какое наибольшее число клеток может быть закрашено в такой таблице?

Рассмотрим закрашенные клетки как рёбра между строками и столбцами. Единственный выбор по одной клетке в каждой строке и каждом столбце означает, что существует ровно одно совершенное паросочетание. При таком условии среди строк и столбцов найдётся вершина степени 1: иначе можно было бы пройти по чередующимся незакрашенным в выбранном наборе и выбранным рёбрам и получить альтернативный выбор. Удаляя такую строку и её столбец, повторяем рассуждение для оставшейся таблицы.

При последовательном удалении можно убрать не более 6, затем 5, затем 4, 3, 2 и 1 закрашенную клетку. Значит, всего их не больше \(6+5+4+3+2+1=21\).

Это число достижимо: закрасим клетки так, чтобы в строке 1 были закрашены столбцы 1–6, в строке 2 — столбцы 2–6, …, а в строке 6 — только столбец 6. Получится 21 клетка. Выбор по одной клетке в каждой строке и каждом столбце тогда единственный — по главной диагонали.

Ответ: 21 клетка.