Двудольные графы и переформулировки к ним

Первое решение. Всего король сделал хода, причем при горизонтальных и вертикальных ходах менялся цвет клетки, на которой он стоит, а при диагональных — не менялся. Всего цвет должен был смениться четное число раз, значит, горизонтальных и вертикальных ходов суммарно четное число, но тогда и диагональных ходов четное число.

Второе решение. Предположим противное. Рассмотрим условие задачи в виде графа. Клетки — вершины, вершины соединены ребром, если из клетки, соответствующей одной вершине, король перешёл в клетку, соответствующую другой вершине. Диагональные ходы соответствуют рёбрам, соединяющим одноцветные клетки, недиагональные — наоборот. Если количество диагональных ходов нечётно, то количество недиагональных — тоже, потому что всего хода. Пусть всего было сделано недиагональных ходов. Посчитаем количество рёбер, соединяющих белые вершины с белыми. Нетрудно понять, что степень каждой вершины — , и что всего белые вершины. Сумма степеней белых вершин равна рёбер из белых вершин идут в чёрные, значит между белыми вершинами проходит рёбер. Это число должно быть целым, но в силу нечётности это не так, пришли к противоречию.