Связность и связные подграфы (клики)
Ошибка.
Попробуйте повторить позже
У ведущего есть колода из 
карт. Зрители хотят узнать, в каком порядке лежат карты (при этом не уточняя — сверху вниз или снизу
вверх). Разрешается задавать ведущему вопросы вида «Сколько карт лежит между такой-то и такой-то картами?». Один из зрителей
подсмотрел, в каком порядке лежат карты. Какое наименьшее число вопросов он должен задать, чтобы остальные зрители по ответам на
эти вопросы могли узнать порядок карт в колоде?
Первый вопрос задается про две крайние карты, а второй — про 
-ю и 
-ю. Далее задаем вопросы о таких парах карт:
-я и 
-я; 
-я и 
-я; 
-я и 
-я, 
-я и 
-я и т. д. При этом за 
вопроса удается определить положение трех
карт.
Покажем, что меньшим числом вопросов обойтись нельзя. Построим граф: вершинами являются 
карты, а ребром между парой
карт — вопрос. Если вопросов-ребер только 
то в графе не менее 
компонент. Отсюда легко следует, что имеется либо две
компоненты, состоящие из одной вершины-карты, либо компонента, в которой ровно 
вершины. В обоих случаях можно эту
пару карт поменять местами, не трогая остальных: все ответы не изменятся. Тем самым порядок не восстанавливается
однозначно.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
