Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
ИТМО - задания по годам

Тема ИТМО (Открытка)

ИТМО - задания по годам → .04 ИТМО 2018

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела итмо (открытка)

Разделы подтемы ИТМО - задания по годам

ИТМО 2015 и ранее

ИТМО 2016

ИТМО 2017

ИТМО 2018

ИТМО 2019

ИТМО 2020

ИТМО 2021

ИТМО 2022

ИТМО 2023

ИТМО 2024

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#73684

В некоторой стране $450$ городов и $6$ авиакомпаний. Каждые два города соединены рейсами одной из шести авиакомпаний. Можно ли утверждать, что найдется авиакомпания и больше $150$ городов, между любыми двумя из которых можно добраться рейсами этой авиакомпании (возможно, с пересадками)?

Источники: ИТМО 2018

Показать ответ и решение

Построим контрпример. Разобьём города на $6$ групп по $75$ городов. Назовём эти группы $A,B,C,D,E,F.$

Внутри каждой группы соединим города рейсами компании номер $1.$

Компания номер $2$ будет соединять города группы $A$ с городами группы $B,C$ с $D,$ а $E$ с $F.$

Компания номер $3$ будет соединять города группы $A$ с городами группы $D,B$ с $E,$ а $C$ с $F.$

Компания номер $4$ будет соединять города группы $A$ с городами группы $C,B$ с $F,$ а $D$ с $E.$

Компания номер $5$ будет соединять города группы $A$ с городами группы $E,B$ с $C,$ а $D$ с $F.$

Компания номер $6$ будет соединять города группы $A$ с городами группы $F,B$ с $D,$ а $C$ с $E.$

Таким образом, рейсы компании номер $1$ связывают по $75$ городов, а рейсы остальных компаний ровно по $150.$

Это построение схематически изображено на рисунке. Разные компании обозначены разными цветами.

$PIC$

Ответ:

Нет

Предыдущая подтема

Следующая подтема