|
В какой-то компании имеется ровно 20 работников. Компания занимается решением 18 различных проблем. По каждой проблеме в компании есть ровно 5 специалистов (понятно, что существует работник который отвечает на несколько проблем, а также могут быть работники, которые не являются специалистами ни по одной из проблем). Руководство компании хочет создать сильную команду, то есть такую команду с минимальным количеством участников, которая умеет решать все проблемы. Требуется показать, что при некотором раскладе не получиться набрать такую команду из 5 человек (только из 6). задан 22 Апр '17 3:55 
Андрей234443
показано 5 из 15
показать еще 10
|
|
Вариант контрпримера для группы из 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 
Urt |
А сколько специалистов надо, чтобы решить проблему?
@abracadabra11: всего один. Но он должен быть выбран из числа тех пяти, кто её умеет решать.
Единственное, что я пока смог доказать, это то, что по принципу Дирихле при любом раскладе из 7 человек можно сделать команду.
@Андрей234443: задачи такого типа иногда бывают довольно сложными. Я не знаю, какой здесь ответ, но сходу у меня не получилось доказать, что пяти всегда хватает. Контрпример также построить пока не удалось -- хотя, возможно, имеет смысл сделать какое-то построение по принципу "на авось".
Доказательство для 7 человек имеет смысл изложить хотя бы кратко -- может быть, далее это рассуждение станет возможно как-то усилить.
@falcao возможность собрать команду из 7 человек я доказал для произвольного расклада. А невозможность собрать для 5 человек нужно для какого-то конкретного расклада. Поэтому не знаю как одно из другого вывести.
Кратко идея док-ва для 7 человек: 1. существует человек который выполняет 5 заданий => остается 19 человек и 13 заданий. 2. из оставшихся существует человек, который выполняет 4 задания => остается 18 человек и 9 заданий. 3. из оставшихся существует человек, который выполняет 3 задания => остается 17 человек и 6 заданий. и т.д.
@Андрей234443: анализ рассуждений полезен для осознания границ их применимости, что может помочь и для построения примеров. Поэтому любые рассуждения здесь представляют интерес. Пока что я не понимаю концовку. После сказанного получается 16 человек и 4 задания, потом 15 человек и 3 задания. Почему тогда будет 7, а не 8? Ведь в конце для оставшихся трёх заданий, возможно, потребуется 3 специалиста?
@falcao На конец моего предыдущего рассуждения мы взяли в команду 3 человека. Далее получается дальше: из оставшихся существует человек, который выполняет 2 задания => остается 16 человек и 4 задания (взяли 4 человека). Из оставшихся существует человек, который выполняет 2 задания => остается 15 человек и 2 задания (взяли 5 человека). Из оставшихся существует человек, который выполняет 1 задания => остается 14 человек и 1 задание (взяли 6 человек). Из оставшихся существует человек, который выполняет 1 задания => остается 13 человек и 0 заданий (взяли 7 человек).
@Андрей234443: в тот момент, когда взято 4 человека, и остаётся 16 человек и 4 задания, почему найдётся тот, кто способен выполнить 2 задания из числа оставшихся?
@falcao Раз осталось 4 задания => у нас есть 20 специалистов (по 5 специалистов на каждое задание). По принципу Дирихле точно найдется один из 16 человек, который будет специалистом 2 раза.
@Андрей234443: вот этого я как раз не понимаю. У нас есть 20 человек с повторениями на эти 4 задания. Пусть из 16 каждый способен выполнить одно по принципу 4+4+4+4. Остальные могут находиться среди уже выбранных. Понятно, что в этом случае заданий остаётся уже фактически меньше, но тогда действует дополнительный аргумент. В целом-то всё верно, но если этот же аргумент задействовать в случае 17 заданий и 6 человек, то там вроде как тоже можно усилить оценку?
@falcao там мне, честно говоря, не очень понятно как можно усилить оценку.
Но даже если мы сможем это сделать - не совсем понятно как потом из полученных условия и их доказательств придумать решение абсолютно противоположной задачи.
@Андрей234443: по поводу усиления, я посчитал заново, и понял, что Вы имели в виду. Идея вот в чём: Вы описываете некоторое построение для 7. Допустим, что оно "критично". Тогда мы можем начать строить пример с конца. А именно, у нас есть 15 человек, и пусть 5 из них умеют решать задачу 1 и пятеро -- задачу 2. Дальше добавляем 16-го, который умеет решать задачи 3 и 4, а предыдущих снабжаем умением решать 3 и 4 так, чтобы "рекордсмен" умел решать две задачи. И так далее. Если это дело аккуратно строить, то можно получить или пример, или увидеть, почему он не проходит, и какие есть ещё ресурсы.
@Urt: прекрасная конструкция! Как я понял, два специалиста остаются в стороне, потому что они никаких проблем не решают (административные работники :))
Имеет смысл преобразовать Ваш комментарий в ответ.
Интересно, нельзя ли усилить до 7?
@Urt Супер! Классный контр-пример.
@falcao, @Андрей234443? спасибо. Доказать, что в таблице (18х20), содержащей в каждой строке 5 единиц, всегда найдутся 6 столбцов, покрывающих последовательность (11...1) (18 единиц), пока не получается.