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