Нашествие на извънземни!/МС

[drago]

Извънземни нашественици са похитили 100 земни учени, за да тестват интелекта им. Те са подготвили 101 тениски, които на гърба са номерирани с числата съответно от 1 до 101. В деня на теста, строяват земляните в една колона, един след друг. Една произволно избрана тениска бива унищожена, без учените да знаят точно коя. След това на всеки землянин се дава да облече случайна тениска от останалите 100. По този начин всеки учен вижда номерата на всички по-предни в колоната, без да знае собствения си номер и номерата на тези зад него.
След това им се дава възможност, последователно да отгатнат собствения си номер, в ред, който сами си изберат. Един по един, всеки от тях прави на глас предположение, което всички останали чуват. Казан вече номер не може да се повтаря. Ако човекът не е познал номера си, бива убиван на място, ако го познае- се пуска.
Каква стратегия трябва да измислят учените, за да минимизират броя на жертвите.

[kmitov]

Добра задача за учени хора. Браво.

[pal702004]

Предпоследният нe вижда три номера: (неговият, на последният и липсващият). За него това са номерата [tex]A>B>C[/tex]. Последният му казва кой е неговият номер по схемата [tex]$A\rightarrow B,B\rightarrow C,C\rightarrow A[/tex] (Ако аз кажа A, ти казваш B, ако кажа B ти казваш C, ако кажа C ти казваш A). Така последният оживява с вероятност 1/2 и казва на предпоследният неговият номер. Останалите се ориентират като им дойде реда.

[pal702004]

Ама може и да не могат да се ориентират. Например при трима човека (номера на фланелки от 1 до 4) и в конфигурация [tex]2,1,4[/tex] и в конфигурация [tex]3,1,4[/tex], първият ще чуе еднакви отговори. (че и верни). Така че май ще трябва да се групират по двойки с мат. очакване [tex]\frac 3 2[/tex] оцелели на двойка...не е добре.

Абе в условието не е казано, че трябва да се събщават числа от 1 до 101. Последният, който не вижда само два номера[tex]x_1,x_2[/tex], що не вземе да каже [tex]1000x_1+x_2[/tex] - чисто самоубийство, но поне другите ще му издигнат паметник.

[drago]

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

[pal702004]

Мился, Драго. Това с шестцифреното число беше шега, разбира се. По принцип би трябвало да може да се построи биекция. Дали последният оживява или умира е допълнителна информация, която трябва да се използва. Ще се опитам да я построя за 3 човека (24 възможни конфигурации). Би трябвало да може. Може да е нещо лесно и елегантно, ама не ми идва на акъла.

[drago]

Аз нямах шанс да реша тази задача. Предложението ми беше нещо подобно на твоето, като мислех, че по-оптимално няма, след което видях решението. И така, има стратегия, която осигурява 99 учени да оцелеят, като освен това има 50% шанс и последния(този който пръв отгатва) да не бъде убит.
Значи това, че нямат право да повтарят номер, мисля, че е сложено само може би като подсказка!
И така, като се има предвид това, последния би следвало да каже един от двата номера, които не вижда, иначе ще ангажира номер, който може да спаси някой напред. Кой точно?? С това трябва да подаде някаква информация на предния!
И още един жокер. Информацията дали последния ще загине, не е необходима на другите преди него, поне за стратегията, която знам.

[pal702004]

Да, наистина информацията дали последният умира не е необходима. Не е трудно да се напише примерно решение за трима човека (фланелки с номера от 1 до 4). По-долу е таблица, която всички знаят. В първата колона е какво вижда третият, в другата - какво трябва да каже:

Код: Избери целия код

12  3
13  4
14  2
-----
21  4
23  1
24  3
-----
31  2
32  4
34  1
-------
41  3
42  1
43  2


Изискването - ако при [tex]ab[/tex] избира [tex]c[/tex], то при [tex]ba[/tex] избира [tex]d[/tex].
Вижда се, че вторият си разбира номера веднага след отговора на третият (без значение убит ли е, или не).
Също така и първият след двата отговора еднозначно определя своят номер.
Мисля, че може да се докаже, че ако е възможно при [tex]n[/tex], е възможно и при [tex]n+1[/tex] човека.
Иначе съм сигурен, че има ефикасен и прост алгоритъм, но...
Ако няма други желаещи да се включат, може да напишеш алгоритъма.

[drago]

Да предположим, че унищожената фланелка е сложена най-отзад в редицата, след последния. Последният не вижда 2 номера и той ги подрежда мислено така че пермутацията на числата от 1 до 101, която се образува в редицата да е четна. (при възможните две подреждания едната пермутация е четна, другата-нечетна). Казва числото, което съответства при това подреждане на неговото място. Има 50% шанс да уцели. Предпоследния не вижда 3 номера, но той знае, кой номер е казал последния. Останалите 2 номера той подрежда мислено така че пермутацията да е четна. И сега основния момент! Забележете,че двете мислени пермутации, на последния и предпоследния, съвпадат. Но последния знае номера на този пред него и в неговата мислена подредба той си съответства с реалността. И така, предпоследния казва този номер и се спасява. По същия начин и другите пред него.

[pal702004]

Ами да, четност на пермутацията. Даже съм ги наптравил четни в табличката и я глееедам като теле. Както и да е, едва ли щях да се сетя - хубава задача. Хайде и от мен една от тази опера. Ама по-добре да не е в нова тема, много хора може да я знаят. Тъп фокус: А си избира 5 карти от пълна колода от 52 и ги дава на B. B отделя една карта, останалите 4 подрежда по определен начин и ги дава на B. B носи на C така подредените 4 карти и C познава коя е отделената карта. Въпроса е ясен: Как с помощта на тези 4 подредени карти A може да предаде на C необходимата информация?

[drago]

Искаш ли да я усложним малко.
Една карта се маха от тестето, като А и С виждат коя е тя. След това А си избира 4 карти от останалите 51 (без да ги вижда), след което ги вижда и ги дава на В. В отделя една и ги връща на А. А ги подрежда някак и ги дава на В да ги занесе на С. Може ли А и С да направят някаква с-ма, така че С да познае, коя е картата?

[pal702004]

Драго, така както аз разбирам условието е невъзможно - уточни. Това, което разбирам - А и С правят фокуса.

Една карта се маха от тестето, като А и С виждат коя е тя

Тоест, тесте от 51 карти. (Асо пика го няма).

След това А си избира 4 карти от останалите 51 (без да ги вижда)

Щом не ги вижда, все едно че B ги е избрал.

В отделя една и ги връща на А.

Значи В си избира една карта от тестето, показва я на А, и му хвърля още три карти да се оправя.

Може ли А и С да направят някаква с-ма, така че С да познае, коя е картата?

Не, абсурд.
[tex]A_{51}^3<C_{51}^4\cdot 4[/tex].
Даже ако приемем, че А избира коя от четирите да остане, пак е невъзможно - [tex]A_{51}^3<C_{51}^4[/tex]. Дай да ги уточним тези неща - кой какво вади, какво разбърква...

Между другото, аз съм оплескал условието на задачата, дето съм я дал. Накратко: А и С правят фокуса: В си избира пет карти, А отделя една от тях, а останалите 4 подрежда, В ги носи на С и С познава коя е отделената.

[drago]

Точно си разбрал. С три карти да се кодира информацията за една от останалите 48. Защо да не може? И какво означава [tex]A^3_{51} < C^4_{51}\cdot 4[/tex] ?

[pal702004]

A-вариации, C-комбинации.

Какво може да получи C. По принцип. Наредена тройка числа от 1 до 51
Броят на тези тройки е [tex]51\cdot 50\cdot 49[/tex]
От друга страна: По колко начина могат да се изберат 4 карти от 51? [tex]\frac{51\cdot 50\cdot 49\cdot 48}{1\cdot 2\cdot 3\cdot 4}[/tex] Или броят на тези четворки е [tex]51\cdot 50\cdot 49\cdot 2[/tex].
Броят на наредение тройки е по-малък от броят на четворките.

Сюрекция наредени тройки [tex]\rightarrow[/tex] четворки е невъзможа.

[drago]

Добре, ама какво общо имат наредени тройки и четворки?
Нещата опират до това с кои да е три карти да се кодират примерно числата от 1 до 48. И аз твърдя, че това може!

[pal702004]

С кои да е три карти може да се кодира число от 1 до 6. Освен ако не ги мачкаме, прегъваме, обръщаме.....Ааааа обърнати с лице и гръб - някои с лице, други с гръб? Някои под прав ъгъл спрямо другите ...това ли имаш предвид?

[drago]

Е, чак под прав ъгъл... тогава ще кодираме много повече. С лице и гръб е достатъчно. От пермутациите на 3 карти- 6 възможности, всяка карта с гръб или лице- 8 за всяка една от тези 6 ... и ето ти ги 48.
Само картите трябва да се занесат на С по начина, който ги е поставил на масата А, да не се обръща тестето от трите, иначе комбинациите ще паднат наполовина. ОК?

[pal702004]

В "моята" задача не се предвижда/разрешава обръщане с лице и с гръб. С получава 4 наредени карти, с тяхна помощ може да се кодира число от 1 до 24. Липсват 48. Значи А трябва да предаде още един бит допълнителна информация (малко-голямо, четно-нечетно, червено-черно и т.н). Откъде да го вземе? - Той избира коя карта от петте да махне.

[drago]

Да, разбрах чак сега, смисъла на задачата. Хубава е.
Нека си мислим за картите като числата от 1 до 52 и [tex]X=\{1,2,\cdots,52\}[/tex]. Ще построим една функция [tex]f[/tex] която на всяка петорка, подмножество на [tex]X[/tex] съпоставя множество състоящо се от някои 4 от тях. Конструкцията е следната: Нека [tex]A_1\subset X[/tex] e петелементно. Нареждаме елементите му във възходящ ред, сумираме ги и нека [tex]a[/tex] e остатъка от делението на тази сума на 5. След това намираме [tex]a+1[/tex]-вия подред елемент от подредените, махаме го и ако [tex]A_2[/tex] са останалите 4 дефинираме [tex]f(A_1)=A_2[/tex].
Сега, нека A получава(5 карти) множеството [tex]A_1[/tex]. Прилага към него ф-ята [tex]f[/tex] и получава 4 елементно мн-во [tex]A_2[/tex], като нека [tex]a[/tex] е манхатия елемент. След това намира всички числа [tex]x[/tex], за които [tex]f(A_2\cup \{x\})=A_2[/tex]. Забележете, че те не са чак толкова много, няктде от порядъка на 52/5, но във всички случаи са по-малко от 24. Подрежда ги в редица и намира на коя позиция стои [tex]a[/tex]. Остава да кодира тази позиция с някаква пермутация на числата от [tex]A_2[/tex].
По-същия начин този, който трябва да отгатне, разкодирва посланието.

[pal702004]

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

С 4 подредени карти може да се кодира число от 0 до 23.
Разбира се, картите са номерира. А ги подрежда в кръг, а петте избрани карти обръща. Обърнатите пет карти разделят кръга на шест сектора. Под големина на сектора ще разбираме броят на необърнатите карти между две обърнати (може и да е 0, ако са обърнати две съседни карти). Общата големина на всички сектори е 47 (52-5). А избира най-големият сектор (ако са повече от един - който и да е от тях) и маха обърната карта, която маркира неговото начало (предварително са се разбрали ориентацията да е по часовниковата стрелка). С останалите 4 карти кодира големината на сектора, на който махната карта се явява край. Той не може да е повече от 23. (ако е по-голям от 23, то иай-големият трябва да е повече от 23 и общата им големина трябва да е поне 48 - противоречие).
С също подрежда картите в кръг, обръща четирите получени карти, които разделят кръга на 5 сектора, единият от които е най-голям, отброява от началото му кодираното число...и си свирка.

[drago]

Абстрактната идеята е една и съща. Трябва да се построи функция/конструкция, правило/, която на всеки 5 числа, между 1 и 52, по-някакъв начин съпоставя определени 4 от тях. Тя трябва да има свойството: Ако знаем резултата/множество от 4 числа/, то възможностите за 5-тото махнато число да не са чак толкова много. При твоето правило махнатото число е по часовн. стрелка от левия край на най-гол. интервал на не повече от 23 позиции., т.е. неопределността е 23. При конструкцията, която предлагам, ако знаем останалите 4 числа, възможностите за махнатото са от порядъка на 52/5, т.е. можем да кодираме махнатата карта с по-малко количество информация

Между другото, първоначалната задача за извънземните е давана на олимпиада Л.Ойлер, 2014.