Можно ли покрасить все клетки доски $%2019\times 2019$% в два цвета так, чтобы у каждой клетки было ровно две соседние по стороне клетки, покрашенные в тот же цвет, что и сама клетка?

задан 12 Май 20:36

изменен 12 Май 22:36

%D0%9A%D0%B0%D0%B7%D0%B2%D0%B5%D1%80%D1%82%D0%B5%D0%BD%D0%BE%D1%87%D0%BA%D0%B0's gravatar image


2.1k19

10|600 символов нужно символов осталось
3

При нечетном n покрасить нельзя, а при четном можно.

Для того, чтобы установить невозможность окраски при нечетном n, отметим одно свойство окраски. Для этого поставим фишку в любую клетку доски и переместим ее в соседнюю клетку того же цвета. Далее будем перемещать фишку в клетку этого цвета, но не в ту, где она находилась на предыдущем шаге. Поскольку возможность такого перемещения будет всегда, то отсюда следует что клетки одного цвета образуют циклически замкнутые ленты. В простейшем случае (при n=2) такая лента представляет собой 2х2-квадрат. Число клеток в замкнутой ленте четно, поэтому сумма всех клеток в лентах, равная числу клеток доски, должна быть четной.

Вариант окраски доски при любом четном n можно получить на основе размещения на доске 2х2-квадратов двух цветов, расположенных в шахматном порядке. Другие варианты окраски возможны на основе укладки колец и различных композиций.

ссылка

отвечен 12 Май 23:16

изменен 12 Май 23:38

1

@Urt: красивое рассуждение!

Во второй строке есть маленькая опечатка (должно быть "нечётном").

(12 Май 23:34) falcao
1

@falcao, спасибо, поправил.

(12 Май 23:38) Urt

@Urt, большое спасибо! И правда, красиво!

(13 Май 15:50) Казвертеночка
2

@falcao, @Казвертеночка, в дополнение можно отметить, что подобные окраски фигур на клетчатых досках обладают также такими свойствами: 1) длина каждого отрезка, образующего сторону фигуры четна; 2) каждая лента замкнута и образует 2kx2k-квадрат; 3) внутри такого 2kx2k-квадрата при k>2 содержится 2(k-1)x2(k-1)-квадрат; 4) (для квадратной доски) при $%k \to \infty$% отношение числа ячеек одного цвета к числу ячеек другого цвета приближается к 1; 5) при окраске квадратной доски с нечетной длиной стороны можно добиться минимум одной неокрашенной клетки и это обязательно будет центральная клетка.

(13 Май 16:40) Urt
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×571
×121
×57
×15
×10

задан
12 Май 20:36

показан
71 раз

обновлен
13 Май 16:48

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru