* Шестимата музиканти
Публикувано на 16 юни 2009 в раздел Математика.
Шест музиканта се събрали на фестивал. На всеки плануван концерт някои от тях свирели, докато другите ги слушали като част от публиката.
Колко най-малко концерти трябва да се заплануват, така че да съществува разпределение, при което да бъде възможно всеки музикант да слуша от публиката всеки от другите 5?
Andy Liu, Canadian Mathematical Olympiad, 1981
Моля дайте изчерпателни решения
съществуват двойки [1,5], [2,4], [3,3] на броя зрители и изпълнители. След като един от тези случаи се случи на 1 итерация, имаме подзадача с размера на най-голямата цифра и изискване за случване на обратното изслушване.
Най-малката под-задача е с избиране на 1 стъпка [3,3]. Решението на задача с 3 музиканта е 3 стъпково, с 1 избор [1,2] и бинарна подзадача [2], като за да се реши в общо 4 стъпки е необходимо да се избегне инверсното състояние на първоначалната [3,3] двойка.
По така описаното решение, примерно разбиване с 4 стъпки, като просто се стараем от пермутациите да имаме инверсни състояния на 2-та 3-ни квадрата с подзадачи:
Дам, интересно е да се види формула за решението.
Как например ще стане с 1000 музиканти?
Аз ще си поблъскам главата още малко :)
Моето предположение е, че за „n“ музиканта са нужни минимум „n“ концерта. Остава да го докажа :)
Не, дрън дрън та пляс казах. Ето решение с четири концерта:
A, B и C участват в първия концерт; A, D, и E – във втория; B, D и F – в третия, а C, E и F – в четвъртия
За n музиканти са нужни максимум n концерта, ако всеки се изрежда да гледа останалите (n-1). Въпросът е колко концерта е минимума за общия случай n музиканти.
Допускам, че е възможно да се реши с 3 концерта. Ако някои от музикантите слуша 3 концерта, очевидно него никой няма да чуе, следователно всеки от тях трябва да слуша 1 или 2 концерта. Ако един от тях слуша само един концерт, тогава той е слушал сам, следователно останалите 5 са слушали по 2 концерта, но понеже остават само 2 концерта, значи двата концерта са слушани от едни и същи хора. Следователно няма музикатни слушали само 1 концерт.
Остава всички да са слушали по 2 концерта. Понеже музикантите са 6 и всеки слуша по 2 концерта общо за 3те концерта трябва да има заделени 12 места в публиката. Вариантите са даден концерт да са слушали 1,2,3,4 или 5 музиканта.
-1.Вече проверих какво става ако един концерт се слуша от само 1 човек.
-2.Ако един от концертите се слуша от 2 човека остава другите 2 да се слушат от по 5 човека – очевидно 4мата които са свирили на първия немогат да чуят всички защото на последни 2 концерта свири само 1 човек.
-3.Ако един от концертите се слуша от 3ма музиканти, тогава останалите 2 се слушат от 4и5 човека. Отново музикантите свирили на този концерт немогат да чуят всички защото в най-добрия случай са чули общо 3ма.
-4. Ако един от концертите се слуша от 4 човека, тогава другите 2 се слушат от 3и5 или 4и4, 3и5 ни връща към предишните точки, остава 4и4. Понеже и 3те концерта се слушат от по 4 човека остава и на трите да свирят по 2ма, но понеже трябва и 6мата да свирят тогава на всеки следващ концерт трябва да свирят нови хора, следователно остава точно един вариант и това е:
12:3456, 34:1256 и 56:1234 очевидно той не изпълнява условието защото музикантите свирили заедно немогат да се чуят един друг, следователно е невъзможно да се реши с 3 концерта.
Опитах се да направя обобщение за N музиканта. За съжаление тук математическия ми апарат куца сериозно. Ето моите размишления (пускам ви буквално черновата си, в която съм писал „по детски“):
Най-малката задача е с двама музиканти. При тях има едно единствено решение – това са два концерта във вариянт [1, 1] (зрител, музикант). Очевидно е, че комбинации във вариант за концерт [2, 0] или [0, 2] са безсмислени.
Ако добавим нов музикант, получаваме по-голяма задача. В нея възможните комбинации са [1, 2] и [2, 1]. Отново варианта с 0 зрители или 0 музиканти се изключва. Нека да вземем първия вариант [1, 2] – в него музикант A е гледал концерт на B и C. Следователно сега е нужно B да гледа C и A и C да гледа B и A. От тук се вижда, че щом A e гледал всички, то A ще свири във всички следващи концерти. Така ако премахнем A от задачата (ясно е, че той ще свири до края) задачата се свежда до подзадача с двама музиканти. Вече знаем, че за нея са нужни два концерта => за задача с трима музиканти общо 3 концерта.
Аналогично се доказва за [2, 1] – A и B са гледали C. Остава C да гледа A и B, B да гледа A и A да гледа B. Понеже C е гледан от всички, то той-може да бъде зрител до края. Така отново задачата се свежда до задача с двама музиканти.
Така освен всичко друго забелязваме и инверсия – решението на [1, 2] е еквивалентно на [2, 1], като просто се обръщат действията „свири“ и „гледа“.
Така по индукция се продължава за следващата комбинация. Това са 4 музиканти. Възможните концерти са в началото са [1, 3], [3, 1] и [2, 2]. Знаем, че първите варианти [1, 3], [3, 1] са инверсни. те се свеждат до предишната задача с трима музиканти, която имаше решение от 3 концерта, т.е. ще са нужни общо 4 концерта.
Интерес предизвиква подредбата [2, 2]. В нея музиканти A и B са гледали C и D. Остава C и D да се срещнат помежду си, което знаем, че прави два концерта, но също така A и B трябва не само да се срещнат помежду си, но и да са видяни от C и D. Какъв е оптималният вариант?
Ето възможните:
(AB, CD) => (C, ABD) => задачата се свежда до задача с трима музиканти, но единият от тях вече е гледан от другите двама, т.е. задачата се свежда до задача с двама музиканта! Общо 4 концерта.
(AB, CD) => (B, ACD) => B е гледал всички, т.е. задачата се свежда до задача с трима музиканти от които единия е гледал другите двама, т.е. са нужни още два или общо 4 концерта.
(AB, CD) => (CD, AB) => имаме две двойки, които са се гледали помежду си. За всяка една от тях са нужни два концерта, т.е. оптимума е да има още 2 концерта или общо 4 концерта.
(AB, CD) => (AC, BD) => A e гледал всички и може да бъде постоянно на сцена, т.е. задачата се свежда до задача с трима музиканти BCD, от които C вече е гледал BD, но и B е гледал CD, т.е. е нужен още само един концерт или цялата задача се свежда до 3 концерта, което е и оптималното решение!
Останалите пермутации на решенията са ексвивалентни, т.е. решението [2,2] е с три концерта!
Започваме с пет музиканта. Вариантите са:
[1, 4] и еквивалентното [4, 1]: Ясно е, че се свеждат до задача с четири музиканта, т.е. общо ще са нужни 5 концерта.
[2, 3] и еквивалентното [3, 2]: нека разгледаме възможните комбинации на първото:
(AB, CDE) => (C, ABDE) => свежда се до задача с четири музиканти, но от която двама (AB) вече са гледали други двама (CD), т.е. ще са нужни общо 3 концерта, т.е. общо 5.
(AB, CDE) => (B, ACDE) => свежда се до задача с четири музиканта, но от които един (A) e гледал другите трима, т.е. ще са нужни 3 концерта, т.е. общо 5 концерта.
(AB, CDE) => (AC, BDE) => Вече можем да сложим A за постоянно на сцената, защото той е гледал всички останали, т.е. задачата се свежда до задача с четири музиканта BCDE, в която обаче един (C) e гледал трима (BDE) и (B) е гледал трима (CDE), т.е. те може спокойно да свирят до края на сцената, т.е. остават нужни само два концерта – тези, с които D ще види E и E ще види D. Общо за този подход ще бъде с 4 концерта.
(AB, CDE) => (CD, ABE) => Е e гледан от всички, т.е. той може да седне за постоянно на сцената. Задачата се свежда до задача с четири музиканта, в която два по два AB и CD вече са се гледали помежду си, т.е. са ни нужни още два концерта, т.е. общо 4.
Ако продължим по индукция ще забележим, че ако „режем“ музикантите доколкото е възможно наполовина във всеки концерт, то се получава оптимум. Нека на първия концерт да сме разделили музикантите на групи G1 и G2, където G1 гледа G2. На втория концерт разделяме G1 на подгрупи G11 и G12 и разделяме G2 на подгрупи G21 и G22. Тогава комбинираме G11 и G21 да гледат G12 и G22. По този начин свеждаме задачата към по-малка – вече преди това решена, за която отново прилагаме същия принцип.
Конкретно при задачата с 6 музиканти отново се получава 4 стъпково решение.
Предположението ми е, че на всеки два добавени музиканта, броят на концертите се увеличава с един:
[1,1] -> 2 концерта за 2 музиканта
[1,2] -> 3 концерта за 3 музиканта
[2,2] -> 3 концерта за 4 музиканта
[2,3] -> 4 концерта за 5 музиканта
[3,3] -> 4 концерта за 6 музиканта
[3,4] -> 5 концерта за 7 музиканта
[4,4] -> 5 концерта за 8 музиканта
[4,5] -> 6 концерта за 9 музиканта
За съжаление не успях да докажа това математически. Достигнал съм до него по опитен път. Надявам се, че по-добър математик ще може да обобщи задачата по-добре от мен.
Естествено не съм прав… Открих си грешка още в началото:
„(AB, CD) => (AC, BD) => A e гледал всички и може да бъде постоянно на сцена, т.е. задачата се свежда до задача с трима музиканти BCD, от които C вече е гледал BD, но и B е гледал CD, т.е. е нужен още само един концерт или цялата задача се свежда до 3 концерта, което е и оптималното решение!“ – това не е вярно…
Не е вярно, защото не може да се конструира:
(AB, CD) => (AC, BD) => (D, ABC) – D преди това не е слушал никой. Остава проблем – C не е слушал A!
Все пак текущата задача с 6 музиканти е разбита:
(AB C, DE F) => (DE C, AB F) => (AD F, BE C) => (BE F, AD C)
Нужно е обобщение…
Официално решение на задачата за 6 музиканти:
Ако в един концерт свирят k музиканта, то останалите 6-k ги слушат и така събитието “музикант слуша свой колега” се сбъдва k(6-k) пъти.
Функцията k(6-k) достига максимум 9 при k=3.
Всеки от тези 6 музиканта трябва да слуша останалите 5, т.e. минимум 6.5=30 пъти трябва да се сбъдне събитието “музикант слуша свой колега”.
При n концерта, ако всеки път k = 3, то се сбъдва общо 9n пъти.
Изискваме 9n >= 30 , т.e. n >= 10/3, т.е. n >= 4
Следователно минималният брой концерти е 4!