Междинна (Програмисти...)

[MitkoS]

Не очаквах някой да прояви интерес. Мислех след два-три дни направо да опиша тук алгоритъма.
Но сега се притеснявам, че ще ти разваля кефа да си го откриеш сам. Затова, ще направя само няколко по-дебели подсказки, пък ако седмица-две не стигнат, ще напиша алгоритъма.

1. Тъй като предварително не знаят кои са цветовете, хората в колоната се наговарят да номерират цветовете по тяхното появяване в колоната. За такова номериране вече стана въпрос няколко пъти в тази задача.
2. Нулевия цвят всички го виждат, защото е най-отпред. Само този най-отпред не знае нищо за номерацията на цветовете.
3. Всички които виждат пред себе си поне два цвята, на практика знаят номерата и на трите цвята. Те прилагат алгоритъма на Bibi, който ти си описал по-горе, който важи и за повече цветове. Както ще се разбере накрая, на тях повече им трябва тефтера и химикалката, отколкото на останалите отпред
4. Тези които виждат пред себе си само един цвят (цвят 0), няма как да знаят кой цвят е 1 и кой цвят е 2. Това обаче не им пречи да се спасят, при това с по-малко усилия от тези които знаят номерата и на трите цвята. Обаче алгоритъма за тяхното спасяване се чупи ако цветовете бяха 4 или повече
5. Едно добро начало за размисъл е, какъв цвят трябва да избере предпоследния (предпоследния - този който втори натиска бутона), ако вижда пред себе си само цвят 0. А какво трябва да избере пред-пред последния ако и той вижда само нулевия цвят.

Добавено:
Wise, прочетох пак поста ти - едно такова уточнение може би се налага да направим (// да направим с теб) - след като им нахлупил шапките на главите, шефа застанал най-отпред и размахал три различни шапки, казвайки "шапки с такива три цвята съм ви нахлупил" и всички чак тогава са видели какви са трите цвята на шапките

[Wise]

Проблем ми е програмиста на върхо
То за другите си има ясен алгоритъм, дори и да виждат само еднакви шапки......

Та......чекай де........

[MitkoS]

Проблем ми е програмиста на върхо

Тоя и на мен ми е проблем и съм го отписал.
И съм приел, че намирането на алгоритъм при който се спасяват всички без първия и последния е достатъчно добър резултат.

То за другите си има ясен алгоритъм, дори и да виждат само еднакви шапки......

Ясен е, ама цяла седмица ти трябваше, а ?

Добавено:
Един частен случай при който първия се спасява, е когато той (първия) е преброил, че тези зад него са избрали общо по 33 шапки от всеки цвят. Тогава той трябва да избере цвета който е избрал най-последния в колоната.

Друг частен случай, при който този най-отпред може успешно да си изчисли и познае цвета си, е когато този зад него е избрал същия цвят като на най-последния в колоната. При този сценарий, се разчита и на това, че общия брой хора е 100. Ако общия брой например е 99, то се стига до неопределеност.

[MitkoS]

Ха, ще хвърлям ръкавицата отново
И първия в колоната гарантирано може да изчисли и познае цвета си. Но му трябват задълбочени познания по елементарна аритметика.

[Wise]

Всички, освен последния в редицата, гарантирано остават на работа
Приемаме първия цвят за "нулев", а следващия, различен от него - с тегло "1", останалия - с "2"
Това е достатъчно да се спасят гарантирано всички, без последния в редицата.

И първия в редицата ми беше братовчед.........
Ще го опиша по-късно- но никакви сложни сметки няма - за първи клас е аритметиката

[MitkoS]

Това е достатъчно да се спасят гарантирано всички, без последния в редицата.

Първия в редицата го спасявам, само ако общия брой програмисти не се дели на 3.
В тая задача броя е 100 и затова става, но ако беше 102 или 99 - не става.

[Wise]

Ето и алгоритмите:
1. За виждащите поне 2 различни шапки - там е ясно от задачката на Биби.
2. За виждащите само един (нулевия) цвят:
2.1. Имало е поне по една шапка от ненулевите 2 цвята.
от съответния цвят, който е обявил последния в редицата вадим една бройка
от всеки цвят махаме по 3 броя шапки, а после всички двойки от два цвята
остават само 2 варианта за ненулевите цветове 2+0 и 1+0 (нулевия не се брои)
в първия случай шапката е от цвета на 2-те, а във втория - противна на цвета с 1 брой
2.2. От единия цвят е нямало нито една шапка.
прилагайки премахването на всяка тройка остават 3 варианта за цвета - 0,1,2 бройки
2.2.1. последният в редицата е обявил нулев цвят шапка -
шапката е съответно нулева, противна, еднаква с цвета
2.2.2. последният в редицата е обявил ненулев цвят
шапката е съответно еднаква с обявената, при 0 , а иначе противна на цвета
3. За първия в редицата:
3.1. Имало е поне 1 шапка с цвета, обявен от последния в редицата.
изваждаме я от броя на съответния цвят - 98-1=97 шапки
премахваме всички тройки от даден цвят 97-93 = 4 бр
4,0,0 - 3,1,0 - 2,2,0 - 2,1,1
след корекцията остават 1,0,0 - 2,2,0 - 2,1,1
за да има равновесие шапката е съответнос цвета на 1, на 0 и на 2
3.2. Нямало е шапка с цвета, обявен от последния в редицата.
98 шапки са в 2 цвята премахваме еднаквите тройки 98-96 =2
вариантите са 2,0,0 и 1,1,0 последния цвят е цвета, обявен от последния в редицата
цветът на шапката е с тегло 0 - следователно:
в първия случай е цвета с 0 броя, различен от цвета, обявен от последния в редицата,
а в другия - еднакъв с цвета, обявен от последния в редицата


//не виждам защо да зависи от делението на 3 - според мен и при 99 човека си става

[MitkoS]

Поздравления от мен. Един път, че си намерил алгоритъма (и аз разглеждам същия алгоритъм) и втори път, че си го описал с толкова малко думи и изречения. Аз щях да на пиша разни хиксове и игреци и щеше да бъде доста по-дълго и вероятно доста по-неразбираемо.

Единствената ми бележка е за първия и за общия брой хора:

3. За първия в редицата:
...
след корекцията остават 1,0,0 - 2,2,0 - 2,1,1
за да има равновесие шапката е съответнос цвета на 1, на 0 и на 2
...
//не виждам защо да зависи от делението на 3 - според мен и при 99 човека си става

Ако общия брой хора се дели на 3, то
след корекцията може да останат 0,0,0 (или 1,1,1 или 2,2,2, което пак си е 0,0,0)
и се стига до неопределеност

Добавено:
За тези, които виждат само един цвят, има едно много просто броене с помощтта на пръстите на ръцете:

0. Най-вначалото всички пръсти на ръцете са изправени
1. Чуват единия неизвестен цвят и свиват пръст на едната (лявата) ръка
2. Чуват другия неизвестен цвят и свиват пръст на другата (дясната) ръка
3. Ако на едната от двете ръце се съберат два свити пръста, то те се изправят и се свива пръст на другата ръка
4. Ако и на двете ръце има по един свит пръст, то те се изправят

Това е така, защото по сметката от алгоритъма на Bibi може да се види, че
a) неизвестен1 + неизвестен2 = 0
b) неизвестен1 + неизвестен1 = неизвестен2
c) неизвестен2 + неизвестен2 = неизвестен1
(т.е., ако {x,y}={1,2} ==> a) (x+y)mod3=0, b) (x+x)mod3=y, c) (y+y)mod3=x )

И накрая, когато дойде техния ред, то те имат най-много един свит пръст от всичките 10 пръста на двете ръце.
И карат по твоята сметка в 2.1 или 2.2

[Wise]

Дам....това го бях прозяпал.........
"Ако ... след корекцията ... да останат 0,0,0 (или 1,1,1 или 2,2,2, което пак си е 0,0,0)"

Ами нека тогава допълваме с "мъртви души" - зад първия има още един
призрак с нулева шапка (броят е известен на всички)

//не - трябва предпоследния в редицата да се брои за двама в такава ситуация.
Всеки следващ, след като разбере броя - просто добавя още 1 човек .
А предпоследния си сменя цвета, ако не е нулевия.

[MitkoS]

След три преспивания - признавам си, все още не ми е ясно спасяваш ли го първия или не, за случая когато общия брой се дели на 3 ?
Какво значение могат да имат "виртуалните мъртви души", след като те нямат реална жива уста ?
И при всяко положение - с "мъртви души" или без, първия чува един и същ брой гласове и един и същ брой цветове.

[Wise]

След три преспивания - признавам си, все още не ми е ясно спасяваш ли го първия или не, за случая когато общия брой се дели на 3 ?
Какво значение могат да имат "виртуалните мъртви души", след като те нямат реална жива уста ?
И при всяко положение - с "мъртви души" или без, първия чува един и същ брой гласове и един и същ брой цветове.

Да, спасявам го

Всеки, който е на ред да казва (без предпоследния), преброява колко гласа е чул и колко човека има пред него.
Ако прибавяйки себе си се получи кратно на 3 добавя към сметката си още 1 шапка с цвета на предпоследния в редицата
(все едно там има реален човек). След това си смята по описания общ алгоритъм.
Само предпоследният в редицата прави друго - след като установи, че броят е кратен на 3, казва цвета, различен от
изчисления, при положение, че не е нулевия цвят.
Така редицата нараства с още един човек, макар и виртуален. И неговият глас е чут (виртуално) от всички! angel

[MitkoS]

Така на първо четене, продължавам да не разбирам ... и продължавам да се опитвам да те разбера ... ама не се получава.

И тъй като е възможно да бъркаш нещо, ще се опитам да ти подскажа какво да изясниш - на нас тук, пък и на себе си.

Така или иначе, съществува (поне един) алгоритъм при който се спасяват от втория до предпоследния. Т.е., те казват точно собствения си цвят. Техните цветове и техния брой са фиксирани и те няма как да пренесат допълнителна информация към първия в колоната. Защото те правилно познават цвета си и го казват точно него, независимо по какъв точно алгоритъм смятат.

Единствения, който може да пренесе някак си допълнителна информация е последния ("последния" - този който избира пръв). Но той трябва така да направи преноса, че да не обърка междинните. А също така, евентуално те трябва да са наясно, че става въпрос за допълнителен пренос и да го отчетат в своите си "изчисления" (но така или иначе, те накрая казват/познават вярно своя цвят).

Предлагам да разгледаш и опишеш как точно се спасява първия , когато общия брой е 6 човека (а най-добре да разгледаш и опишеш всичките от 1 до 5) и разпределението е такова:
1 - синя (този е най-отпред в колоната)
2 - синя
3 - червена
4 - зелена
5 - синя
6 - червена (този е най-отзад и цвета му е без значение)

ПП. За по-лесно, можем да приемем, че всички знаят, че общия брой е 6

ПП2. Какво стига до ушите на първия ?
6 - изчислява 0 и казва "синя" по алгоритъма на Bibi. Евентуално казва нещо друго по твой алгоритъм
5 - изчислява 0 и казва "синя" - по Bibi, но трябва да каже "синя" по който е да е друг алгоритъм
4 - изчислява 2 и казва "зелена" - по Bibi, но трябва да каже "зелена" по който е да е друг алгоритъм
3 - изчислява 1 и казва "'червена" - по Bibi, но трябва да каже "червена" по който е да е друг алгоритъм
2 - изчислява 0 и казва "синя" - по алгоритъма който уточнихме с теб, но трябва да каже "синя" по който е да е друг алгоритъм

1 - ??? - чува че: синьо = (синьо + червено + зелено + синьо) mod 3
и след "преобразуване" стига до:
(1.синьо + 1. зелено + 1. червено) mod 3 = 0
това равенство не носи никаква полезна информация за първия и той не може да идентифицира кой цвят е с номер 0. И това се получава само защото общия брой хора е 6 и се дели на 3. Ако беше 7 или 8, след преобразуването щеше да получи друго равенство, което със сигурност носи полезна информация, достатъчна за да се идентифицира цвят 0.

[Wise]

Ами не е така...

нека е по твоето :
с с ч з с х - това е единият случай

1. шестият преобразува до
с с ч з с с х и казва с
2. петият изчислява по бибешки и казва с (защото се е определил като нулев=с)
3. четвъртият преобразува до
с с ч ? с с с и казва з
4. третият преобразува до
с с ? з с с с и казва ч
5. вторият преобразува до
с ? ч з с с с и казва с
6. първият преобразува до
? с ч з с с с и от трите с вади 1 с (на последния)
получава - 2 с 1з 1ч - за да има равновесие той е от с цвят


Нека разгледаме и случай:
с с ч з з х

последният го трансформира в с с ч з з з х и казва по бибешки ч
предпоследният знае с с ч з ? ч и си смята по бибешки и изчислява ч
НО заради броя(дето се дели на 3) казва обратното - з, защото ч=з+з
всички следващи имат с с ч ? з з ч с с ? з з з ч с ? ч з з з ч ? с ч з з з ч


не разбирам какво сложно има
// s bold маркирах добавения човек


Обобщено:
Ако броят на човеците се дели на 3 без остатък:
Предпоследният в редицата обявява обратния на изчисления цвят. /ако е нулевия - си остава същия/
Всички останали мислено нахлупват шапката на предпоследния върху главата на началника и го
поставят зад предпоследния в редицата. Така броят на човеците вече не се дели на 3

[MitkoS]

Добре, съгласявам се, става

[Wise]

Добре, съгласявам се, става

Дамммм.............ега ти междинката


А ако са повечко цветовете? - N цвята??


Ама за мен - стигат и трички .......