В государстве 1000 городов и совсем нет дорог. Король Василий I хочет соединить каждую пару городов дорогой. Для этого он каждый год разбивает города на две группы и проводит между всеми парами городов из разных групп недостающие дороги. За сколько лет он управится (в ответе укажите наименьшее возможное значение)

задан 7 Окт 19:46

10|600 символов нужно символов осталось
0

Рассмотрим случай, когда городов 2^n. Закодируем каждый город двоичной последовательностью. В i-й год применим разбиение на две группы по признаку i-го члена последовательности (одна группа с 0, одна с 1 в i-м разряде). Поскольку любые две последовательности различаются хотя бы в одном разряде, они в некотором году окажутся соединены. Поэтому n дней точно хватит. Понятно, что та же схема работает при числе городов <=2^n. Поэтому королю хватит 10 лет ввиду неравенства 2^10 > 1000.

Покажем, что 9 лет уже не хватит. В первый год возникнут какие-то две группы. В какой-то из них не менее 500 городов. На следующий год из этих 500 городов найдутся 250, которые по-прежнему находятся в одной группе. Потом получатся числа 250, 125, 63, ... и так далее. После 9-го года строительства останутся два города, которые всё время были в одной и той же группе, то есть дорогой они не соединены.

ссылка

отвечен 8 Окт 0:30

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,086
×491

задан
7 Окт 19:46

показан
39 раз

обновлен
8 Окт 0:30

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru