В какой-то компании имеется ровно 20 работников. Компания занимается решением 18 различных проблем. По каждой проблеме в компании есть ровно 5 специалистов (понятно, что существует работник который отвечает на несколько проблем, а также могут быть работники, которые не являются специалистами ни по одной из проблем). Руководство компании хочет создать сильную команду, то есть такую команду с минимальным количеством участников, которая умеет решать все проблемы. Требуется показать, что при некотором раскладе не получиться набрать такую команду из 5 человек (только из 6).

задан 22 Апр '17 3:55

А сколько специалистов надо, чтобы решить проблему?

(22 Апр '17 13:45) abracadabra11

@abracadabra11: всего один. Но он должен быть выбран из числа тех пяти, кто её умеет решать.

(22 Апр '17 16:20) falcao

Единственное, что я пока смог доказать, это то, что по принципу Дирихле при любом раскладе из 7 человек можно сделать команду.

(23 Апр '17 14:04) Андрей234443

@Андрей234443: задачи такого типа иногда бывают довольно сложными. Я не знаю, какой здесь ответ, но сходу у меня не получилось доказать, что пяти всегда хватает. Контрпример также построить пока не удалось -- хотя, возможно, имеет смысл сделать какое-то построение по принципу "на авось".

Доказательство для 7 человек имеет смысл изложить хотя бы кратко -- может быть, далее это рассуждение станет возможно как-то усилить.

(23 Апр '17 14:14) falcao

@falcao возможность собрать команду из 7 человек я доказал для произвольного расклада. А невозможность собрать для 5 человек нужно для какого-то конкретного расклада. Поэтому не знаю как одно из другого вывести.

Кратко идея док-ва для 7 человек: 1. существует человек который выполняет 5 заданий => остается 19 человек и 13 заданий. 2. из оставшихся существует человек, который выполняет 4 задания => остается 18 человек и 9 заданий. 3. из оставшихся существует человек, который выполняет 3 задания => остается 17 человек и 6 заданий. и т.д.

(23 Апр '17 14:26) Андрей234443

@Андрей234443: анализ рассуждений полезен для осознания границ их применимости, что может помочь и для построения примеров. Поэтому любые рассуждения здесь представляют интерес. Пока что я не понимаю концовку. После сказанного получается 16 человек и 4 задания, потом 15 человек и 3 задания. Почему тогда будет 7, а не 8? Ведь в конце для оставшихся трёх заданий, возможно, потребуется 3 специалиста?

(23 Апр '17 14:51) falcao

@falcao На конец моего предыдущего рассуждения мы взяли в команду 3 человека. Далее получается дальше: из оставшихся существует человек, который выполняет 2 задания => остается 16 человек и 4 задания (взяли 4 человека). Из оставшихся существует человек, который выполняет 2 задания => остается 15 человек и 2 задания (взяли 5 человека). Из оставшихся существует человек, который выполняет 1 задания => остается 14 человек и 1 задание (взяли 6 человек). Из оставшихся существует человек, который выполняет 1 задания => остается 13 человек и 0 заданий (взяли 7 человек).

(23 Апр '17 17:59) Андрей234443

@Андрей234443: в тот момент, когда взято 4 человека, и остаётся 16 человек и 4 задания, почему найдётся тот, кто способен выполнить 2 задания из числа оставшихся?

(23 Апр '17 18:56) falcao

@falcao Раз осталось 4 задания => у нас есть 20 специалистов (по 5 специалистов на каждое задание). По принципу Дирихле точно найдется один из 16 человек, который будет специалистом 2 раза.

(23 Апр '17 19:00) Андрей234443

@Андрей234443: вот этого я как раз не понимаю. У нас есть 20 человек с повторениями на эти 4 задания. Пусть из 16 каждый способен выполнить одно по принципу 4+4+4+4. Остальные могут находиться среди уже выбранных. Понятно, что в этом случае заданий остаётся уже фактически меньше, но тогда действует дополнительный аргумент. В целом-то всё верно, но если этот же аргумент задействовать в случае 17 заданий и 6 человек, то там вроде как тоже можно усилить оценку?

(23 Апр '17 19:28) falcao

@falcao там мне, честно говоря, не очень понятно как можно усилить оценку.

Но даже если мы сможем это сделать - не совсем понятно как потом из полученных условия и их доказательств придумать решение абсолютно противоположной задачи.

(23 Апр '17 20:58) Андрей234443

@Андрей234443: по поводу усиления, я посчитал заново, и понял, что Вы имели в виду. Идея вот в чём: Вы описываете некоторое построение для 7. Допустим, что оно "критично". Тогда мы можем начать строить пример с конца. А именно, у нас есть 15 человек, и пусть 5 из них умеют решать задачу 1 и пятеро -- задачу 2. Дальше добавляем 16-го, который умеет решать задачи 3 и 4, а предыдущих снабжаем умением решать 3 и 4 так, чтобы "рекордсмен" умел решать две задачи. И так далее. Если это дело аккуратно строить, то можно получить или пример, или увидеть, почему он не проходит, и какие есть ещё ресурсы.

(23 Апр '17 22:02) falcao

@Urt: прекрасная конструкция! Как я понял, два специалиста остаются в стороне, потому что они никаких проблем не решают (административные работники :))

Имеет смысл преобразовать Ваш комментарий в ответ.

Интересно, нельзя ли усилить до 7?

(23 Апр '17 23:23) falcao

@Urt Супер! Классный контр-пример.

(23 Апр '17 23:41) Андрей234443

@falcao, @Андрей234443? спасибо. Доказать, что в таблице (18х20), содержащей в каждой строке 5 единиц, всегда найдутся 6 столбцов, покрывающих последовательность (11...1) (18 единиц), пока не получается.

(23 Апр '17 23:59) Urt
показано 5 из 15 показать еще 10
10|600 символов нужно символов осталось
2

Вариант контрпримера для группы из 5 специалистов. Пусть $% M $%- (18х18)-матрица, причем $% M=(A_{i,j}); i,j \in \{1,2,3\} $%, где $% A_{i,j} $%- (6х6)-матрицы: $% A_{i,j}=0$% при $%i\ne j $% и $% A_{i,i} $%- матрица, диагональные элементы которой равны 0, а остальные 1.

ссылка

отвечен 23 Апр '17 22:51

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

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

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

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

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

отмечен:

×338

задан
22 Апр '17 3:55

показан
522 раза

обновлен
24 Апр '17 1:24

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

по почте:

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

по RSS:

Ответы

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

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