5
Пошаговое объяснение:
Я придумал вот что:
Раскрасим вершины (см. рисунок 1)
Нельзя выбирать больше 2-х одноцветных вершин, иначе эти 3 одноцветные вершины образуют равнобедренный треугольник.
Значит, всего вершин можно выбрать не более 6.
Предположим, можно выбрать ровно 6 вершин. Тогда каждого цвета выбрано по 2 вершины. Либо выбранные и невыбранные вершины чередуются (тогда образовывается много треугольников), либо какие-то 2 выбранные вершины идут подряд. Рассмотрим их (рисунок 2). Вершины левее и правее выбирать нельзя, т.к. образуется треугольник. Но эти 2 вершины были одного цвета. Осталось только 2 другие вершины этого цвета. Мы должны выбрать их (рисунок 3). Можно отметить вершины, которые нельзя выбирать, красным (это делается перебором - для каждой вершины смотрим, образуется ли треугольник, если ее выбрать). Рисунок 4. Остается 2 точки. Мы обязаны их выбрать (чтобы всего было 6). Но тогда все равно образуется треугольник (например, из 3 подряд идущих точек). Противоречие.
Значит, больше 5 вершин выбрать нельзя. Пример на 5: Рисунок 5 (по-моему, он верный).
5
Пошаговое объяснение:
Я придумал вот что:
Раскрасим вершины (см. рисунок 1)
Нельзя выбирать больше 2-х одноцветных вершин, иначе эти 3 одноцветные вершины образуют равнобедренный треугольник.
Значит, всего вершин можно выбрать не более 6.
Предположим, можно выбрать ровно 6 вершин. Тогда каждого цвета выбрано по 2 вершины. Либо выбранные и невыбранные вершины чередуются (тогда образовывается много треугольников), либо какие-то 2 выбранные вершины идут подряд. Рассмотрим их (рисунок 2). Вершины левее и правее выбирать нельзя, т.к. образуется треугольник. Но эти 2 вершины были одного цвета. Осталось только 2 другие вершины этого цвета. Мы должны выбрать их (рисунок 3). Можно отметить вершины, которые нельзя выбирать, красным (это делается перебором - для каждой вершины смотрим, образуется ли треугольник, если ее выбрать). Рисунок 4. Остается 2 точки. Мы обязаны их выбрать (чтобы всего было 6). Но тогда все равно образуется треугольник (например, из 3 подряд идущих точек). Противоречие.
Значит, больше 5 вершин выбрать нельзя. Пример на 5: Рисунок 5 (по-моему, он верный).
