СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Математика профильного уровня
≡ математика
сайты - меню - вход - новости



Задания
Версия для печати и копирования в MS Word
Задания Д16 C7 № 526927

Государство Новая Анчурия расположено на острове, имеющем форму круга. В стране 11 городов, расположенных на побережье. Каждый город напрямую соединен с каждым из остальных городов автотрассой.

а) Сколько автотрасс в государстве Новая Анчурия?

б) После наводнения несколько автотрасс в стране закрыли на ремонт. Могло ли оказаться так, что теперь каждый город острова стал напрямую соединен автотрассой ровно с пятью другими городами?

в) Какое наибольшее число автотрасс в Новой Анчурии можно одновременно закрыть на ремонт, чтобы из каждого города можно было добраться на автомобиле до любого другого?

Решение.

а) Из каждого города выходит дорог, поэтому всего есть концов дорог. Значит, дорог

б) Если теперь из каждого города выходит дорог, то всего есть концов дорог. Значит, дорог что невозможно.

в) Можно оставить дорог (например, соединяющих столицу со всеми городами, тогда откуда угодно куда угодно можно будет проехать через столицу), поэтому удастся закрыть

Если оставить всего или меньше дорог на городов, то это будет невозможно. В самом деле, у дорог конца, поэтому найдется город (на самом деле даже минимум 4 таких города) из которых выходит по одной дороге (0 дорог быть не может, из него тогда никуда нельзя доехать). Ясно, что проезжать транзитом через такой город нельзя. Поэтому если мысленно убрать с карты этот город и эту дорогу, на остальной карте можно будет проехать от любого города до любого другого. При этом число дорог снова на меньше числа городов. Продолжая эти действия, придем к ситуации дорог и города, которая нам не подходит.

 

Ответ: а) 55; б) нет; в) 45.

Источник: А. Ларин: Тре­ни­ро­воч­ный ва­ри­ант № 198.