Вы здесь

Совещание в брокерской конторе

Undefined

Директор брокерской конторы поручил 20-и своим сотрудникам подготовить к совещанию обзоры нескольких коммерческих компаний. Компаний в списке оказалось тоже 20, а задания избирались сотрудниками на свое усмотрение, но с условием, что каждый из них изучает ровно 2 компании, а каждая компания должна быть исследована ровно 2-мя сотрудниками. Удастся ли директору составить расписание совещания так, чтобы каждый сотрудник сделал по докладу с обзором одной компании и при этом были рассмотрены все 20 компаний из списка?

Решение. Так как базовый вариант этой задачи был предложен в качестве олимпиадной задачи для учащихся 7-8 классов, то рассмотрим конструктивный способ ее решения, не использующий дополнительного математического аппарата.

Возьмем любую из 20 компаний, присвоим ей номер 1. Возьмем двух сотрудников исследовавших эту компанию и любому из них присвоим номер 1, второму, соответственно, номер 2. По условию задачи больше никто из сотрудников не мог заниматься компанией номер 1.

Если вторая компания, которую изучал сотрудник 1 совпадает со второй компанией сотрудника 2, то, оставив доклады по этим двум компаниям найденным двум сотрудникам, следует перейти к решению аналога поставленной задачи составления расписания докладов остальных 18 сотрудников по остальным 18 компаниям.

Пускай сотрудники 1 и 2 пересеклись в исследовании компании 1, но вторые исследованные ими компании отличаются. Тогда обозначим компанию, которую еще изучал сотрудник 1 номером 0, а вторую компанию сотрудника 2 номером 2. В этом случае у компании 2 по условию задачи должен быть еще один исследователь, которому назначим номер 3. Если второй сотрудник исследовал еще и компанию 0, то опять получим разбиение расписания, на этот раз на 3 + 17. Т.е. сотрудники 1,2,3 и доклады по компаниям 1,2,0, а оставшиеся 17 компаний исследовались оставшимися 17-ю сотрудниками независимо от первых троих.

Пускай сотрудник 3 помимо компании 2 изучал компанию отличную от 0. Это не может быть ни компания 1 – ее исследовали 1 и 2, ни компания 2. Назначим ей номер 3 и найдем второго ее исследователя. Им, естественно, не может оказаться никто из перечисленных ранее сотрудников (1, 2, или 3). Назначим этому сотруднику номер 4. Если этот сотрудник кроме компании 3 изучал компанию 0, то получим разбиение расписания на 4+16: сотрудники 1, 2, 3, 4 делают доклады по компаниям 1, 2, 3, 0, а для остальных 16-ти компаний исследованных остальными 16-ю сотрудниками расписание составляется независимо от первых четырех.

Если сотрудник 4 не исследовал компании 0, то кроме компании 3 у него найдется доклад по еще одной компании и это не 1 (ее изучали 1 и 2) и не 2 (ее изучали 2 и 3), следовательно, этой компании можно предписать номер 4. Кроме сотрудника 4 ее не могли исследовать ни 1, ни 2, ни 3, так как в изложенных выше рассуждениях каждому из них уже предписано по 2 компании. Поэтому найдется еще один исследователь компании 4, которому можно назначить номер 5. Если второй компанией сотрудник 5 исследовал компанию 0, то получим разбиение расписания 5+15: цикл из сотрудников 1, 2, 3, 4, 5 и компаний 1, 2, 3, 4, 0 и независимую задачу о расписании 15-ти компаний среди остальных 15. Если нет, то получим компанию 5 и сотрудника 6 и т.д.

Продолжая рассуждения таким образом, получим либо разбиение задачи на несколько независимых циклов либо за тем же принципом найдем компанию 19 и сотрудника 20, после чего окажется, что второй компанией, которую исследовал сотрудник 20 может быть только компания 0, изученная сотрудником 1, и получим взаимно однозначное соответствие между сотрудниками 1-20 и докладами по компаниям 1-20. Ответ: каким бы образом сотрудники не избирали компании для исследования, придерживаясь поставленных условий, директору удастся составить расписание совещания так, чтобы каждый сотрудник сделал по докладу с обзором одной компании и при этом были рассмотрены все 20 компаний из списка.

Очевидно, использование для решения задачи аппарата графов или отношений позволит получить более простую трактовку доказательства, доступную меньшему количеству любителей математики.

На самом деле, суть задачи состоит в сопоставлении объектов некоторого множества А объектам другого множества В, с учетом заданных в условии ограничений. В первоисточнике множество А составляли ученики, а множество В - решенные ими задачи. Знакомство с интернет-ресурсом forextactic.ru позволило придать условию задачи более современный и истинно прикладной антураж.
author: 
admin
Просмотров: 
2 323
Раздел: