Эйлер 2026 · Математика · 8 кл., №8 — решение

Условие

На рисунке изображён автодром; точки — это перекрёстки, отрезки — дороги. Каждый отрезок между соседними точками машина проезжает ровно за минуту. Приехав на перекрёсток, машина немедленно уезжает с него по любой дороге, кроме той, по которой она приехала. Сначала несколько машин расположены на перекрёстках, затем они одновременно начинают двигаться по указанным правилам. При каком наибольшем количестве машин может случиться, что они смогут неограниченно долго ездить, никогда не встречаясь (ни на перекрёстках, ни на дорогах)?

Рисунок к условию

О задаче · 8 класс

Олимпиада: Олимпиада имени Леонарда Эйлера, XVIII олимпиада
Этап: Региональный этап
Предмет / класс: Математика · 8 класс
Дата: 2–3 февраля 2026

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

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Исследуй задачу

Самостоятельное исследованиеВыбери дороги для своих машин

Пробуй свои варианты. Разбор останется закрытым.

Своя расстановка

Выбери дороги для своих машин

Расставь машины на 51 перекрёстке, задай им направления и проверь один общий шаг. Сможешь организовать движение без встреч?

Нарисуй точный граф с шестью развилками и шестью дорогами в каждой цепочке. Отмечай все машины одновременно, проверяя встречи и на вершинах, и на дороге.

Подсказка 1

Выдели перекрёстки с тремя дорогами. Что вынуждена делать машина между двумя такими перекрёстками?

Подсказка 2

Между соседними развилками шесть дорог. Рассмотри только моменты 0,1,2,3,4,5: сколько разных пар «время — развилка» есть и сколько их занимает каждая машина?

Разобрать решение по шагам

Выделяем шесть развилок

Назовём угловые перекрёстки A,B,C,D, а внутренние — U,V. Это все шесть перекрёстков, из которых выходят три дороги. Каждая пара соседних развилок соединена цепочкой из шести дорог. На промежуточном перекрёстке только две дороги. Поскольку разворот запрещён, машина обязана продолжить движение вперёд по той же цепочке.

Считаем только первые шесть моментов

Возьмём целые моменты времени от 0 до 5 включительно. Если машина начинает на развилке, она находится на ней в момент 0; следующей достигнет только через 6 минут. Если начинает внутри цепочки, до ближайшей по ходу развилки ей осталось от 1 до 5 дорог. Она достигнет её в один из выбранных моментов, а до следующей не успеет. Поэтому каждая машина занимает ровно одну пару «один из 6 моментов — одна из 6 развилок».

Получаем верхнюю оценку

Всего таких пар $6\cdot6=36$ Две машины не могут занять одну пару: тогда они одновременно встретятся на одном перекрёстке. Поэтому машин не больше 36. Рассуждение относится к любым допустимым маршрутам; периодичность движения для этой оценки не предполагается.

Достигаем оценки

Выберем два непересекающихся контура: A–B–U–A и D–C–V–D. Каждый состоит из трёх цепочек по 6 дорог, то есть имеет 18 перекрёстков. Поставим по машине на каждый перекрёсток обоих контуров. Пусть все 18 машин верхнего контура едут по кругу в одном направлении; на нижнем также выберем одно общее направление.

Почему это работает неограниченно долго

На каждом контуре расстояние между соседними машинами всё время равно одной дороге. Встречных машин там нет, а два контура не имеют общих перекрёстков или дорог. На перекрёстках машины продолжают путь по выбранному контуру и не разворачиваются. Через 18 минут положение повторится, поэтому 36 машин могут так двигаться сколько угодно долго.

Проверка

Точный граф:51 перекрёсток,54 дороги,6 развилок и 9 цепочек по 6 дорог. Оценка 36 и два непересекающихся 18-цикла проверены отдельно; конечный опыт модели не заменяет доказательство бесконечного движения.

Ответ

36 машин.

Ответ

36 машин.

Главная идея

Движение по длинным цепочкам позволяет посчитать редкие посещения развилок вместо всех непрерывных траекторий.

Где легко ошибиться

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

Источник и авторство

Олимпиада имени Леонарда Эйлера · XVIII олимпиада, сезон 2025/26 · региональный этап · второй день · 2–3 февраля 2026 · математика · 8 класс. Официальная задача 8, 7 баллов.

Условия задач (PDF организатора) ↗ · Решения организатора, день 1 ↗ · Решения организатора, день 2 ↗ · Архив олимпиады ↗

Условие — из официального файла организатора, рисунок перерисован по нему. Подсказки, объяснение и модели — Popov Academy. Авторский разбор Popov Academy.

Продолжить тему: Графы →

Тема, знания и приёмы

Графы · Начальный вход

Принцип Дирихле
Подсчёт времени по числу дорог
Движение в одном направлении по циклу

Приёмы решения: Принцип Дирихле или худший случай · Первый закон для цикла

Задать вопрос по задаче →