1 Система представителей
Представим себе такую ситуацию. В некоторую организацию одновременно приехали с визитом несколько иностранцев — скажем, англичанин, француз, японец и венгр. Каждый из них умеет говорить только на своем родном языке. Желая должным образом принять гостя, организация стремится послать на встречу с ним одного из своих сотрудников, который бы владел соответствующим языком и, тем самым, помог визитёру сориентироваться в незнакомом городе (на наёмных переводчиков денег жалко). Допустим, нашлись как сотрудники, знающие английский, так и сотрудники, говорящие по-венгерски, и так далее. Однако организация не хочет отрывать слишком много людей от работы и пытается минимизировать количество сотрудников, командируемых на общение с иностранцами. Ведь могут же найтись и такие полиглоты в её рядах, которые одновременно владеют английским и японским или, и того больше, французским, японским и венгерским? Глядишь, приставит организация одного человека сразу к троим посетителям, и проблем станет меньше? В общем случае поставленная задача весьма нетривиальна. Иногда её называют задачей о системах представителей, что вполне естественно. Она нашла многочисленные применения в математике. (Умение решать её позволяет даже повысить вероятность выигрыша в некоторых лотереях!) Андрей Михайлович РАЙГОРОДСКИЙ — доктор физико-математических наук, профессор кафедры математической статистики механико-математического факультета МГУ, заведующий кафедрой дискретной математики факультета инноваций и высоких технологий МФТИ, руководитель исследовательского отдела в Яндексе, автор брошюр «Вероятность и алгебра в комбинаторике», «Остроугольные треугольники Данцера-Грюнбаума», «Хроматические числа», «Проблема Борсука», «Линейно-алгебраический метод в комбинаторике», «Системы общих представителей в комбинаторике и их приложения в геометрии», «Модели случайных графов» и «Гипотеза Кнезера и топологический метод в комбинаторике».
Название:
1 Система представителей
Категория:
Разное