Разделы 
Дополнительно
Задача по математике - 3127
2019-05-19 
Город $n$ построен так, что каждая его улица соединяет две площади, а на каждую площадь выходит по три улицы от разных площадей. На карте этого города играют двое. Они поочередно окрашивают изображения площадей. В их распоряжении имеются краски четырех цветов. Начинающий хочет, чтобы для каждой улицы цвета площадей, на которые она выходит, были различны, а второй, наоборот, хочет, чтобы в одинаковые цвета оказались окрашенными хотя бы две площади, соединенные улицей. Однако второй пользуется сначала первой, потом второй, потом третьей, потом четвертой, потом снова первой и т. д. красками. При каком числе площадей (найти все значения) начинающий может играть так, что он выиграет, как бы ни играл второй?
Решение:
При $n > 8$ при правильной игре выигрывает второй (см. решение задачи 3126).
Пусть $n < 8$. Обозначим через $j$ число улиц. Ясно, что $3n = 2j$. Поэтому $n$ есть четное число.
I. $n=4$. Начинающий закрашивает первую свою площадь третьей (четвертой) краской, а при втором своем ходе пользуется четвертой (третьей) краской. Начинающий выигрывает.
II. $n = 6$. Существует всего два таких города (рис.).
Назовем треугольником тройку площадей, каждая из которых соединена с двумя другими. Заметим, что в городе не более двух треугольников.
Стратегия начинающего.
Первым своим ходом начинающий закрашивает некоторую площадь четвертой краской; вторым своим ходом он закрашивает некоторую площадь первой краской. Ясно, что начинающий может сделать второй свой ход так что после этого:
а) закрашенные первой краской площади не будут соединены улицей;
в) в каждом треугольнике {если он имеется) будет закрашена хотя бы одна площадь.
Вторым своим ходом второй играющий закрашивает какую-либо площадь второй краской. Имеются две возможности.
I случай. Эта площадь соединена с обеими незакрашенными. В этом случае две незакрашенные площади не соединены улицей. Первый играющий закрашивает любую из оставшихся площадей третьей краской и выигрывает.
II случай. Эта площадь не соединена хотя бы с одной из незакрашенных площадей. Закрасив ее второй краской, начинающий выигрывает.
Ответ: $n=4, n=6$.
Замечание. Отметим, что начинающий не пользовался никакой краской дважды (хотя по условию задачи он имел на это право).
Город $n$ построен так, что каждая его улица соединяет две площади, а на каждую площадь выходит по три улицы от разных площадей. На карте этого города играют двое. Они поочередно окрашивают изображения площадей. В их распоряжении имеются краски четырех цветов. Начинающий хочет, чтобы для каждой улицы цвета площадей, на которые она выходит, были различны, а второй, наоборот, хочет, чтобы в одинаковые цвета оказались окрашенными хотя бы две площади, соединенные улицей. Однако второй пользуется сначала первой, потом второй, потом третьей, потом четвертой, потом снова первой и т. д. красками. При каком числе площадей (найти все значения) начинающий может играть так, что он выиграет, как бы ни играл второй?
Решение:
При $n > 8$ при правильной игре выигрывает второй (см. решение задачи 3126).
Пусть $n < 8$. Обозначим через $j$ число улиц. Ясно, что $3n = 2j$. Поэтому $n$ есть четное число.
I. $n=4$. Начинающий закрашивает первую свою площадь третьей (четвертой) краской, а при втором своем ходе пользуется четвертой (третьей) краской. Начинающий выигрывает.
II. $n = 6$. Существует всего два таких города (рис.).
Назовем треугольником тройку площадей, каждая из которых соединена с двумя другими. Заметим, что в городе не более двух треугольников.
Стратегия начинающего.
Первым своим ходом начинающий закрашивает некоторую площадь четвертой краской; вторым своим ходом он закрашивает некоторую площадь первой краской. Ясно, что начинающий может сделать второй свой ход так что после этого:
а) закрашенные первой краской площади не будут соединены улицей;
в) в каждом треугольнике {если он имеется) будет закрашена хотя бы одна площадь.
Вторым своим ходом второй играющий закрашивает какую-либо площадь второй краской. Имеются две возможности.
I случай. Эта площадь соединена с обеими незакрашенными. В этом случае две незакрашенные площади не соединены улицей. Первый играющий закрашивает любую из оставшихся площадей третьей краской и выигрывает.
II случай. Эта площадь не соединена хотя бы с одной из незакрашенных площадей. Закрасив ее второй краской, начинающий выигрывает.
Ответ: $n=4, n=6$.
Замечание. Отметим, что начинающий не пользовался никакой краской дважды (хотя по условию задачи он имел на это право).
