Остров с лъжци, логическа задача.

[drago]

Един мъдрец попаднал на остров, където живеят честни хора и лъжци. Честните винаги казват истината, а лъжците могат да кажат истината, но могат и да излъжат. Вождът на острова предложил на мъдреца да играят на следната игра.
Вождът разполага около кръгла маса 30 островяни, така както си иска, с единственото условие лъжците измежду тях да са не повече от [tex]N[/tex], където където [tex]N[/tex] e известно число, [tex]0\leq N \leq 30[/tex].
Мъдрецът може да пита всеки един от седналите около масата: "какъв е съседа ти отдясно: лъжец или честен" . След като получи 30 отговора, трябва да посочи поне един честен човек измежду участниците. Ако успее, печели.
Какво е максималното число [tex]N[/tex], за което мъдрецът може безусловно да спечели.

[ptj]

9?

[ptj]

Нека означим двата отговора условно с : [tex]Ч,Л[/tex].
Идеята е да търсим поредица от отговори [tex]\underbrace{ Ч,Ч,...,Ч,Л }_{k}[/tex].
Логично е да предположим, че хората, на чиито отговори тя съответсва, са [tex](k-1)[/tex] "честни" и 1"лъжец".
Оказва се обаче, че последното не винаги е вярно. По-точно същия отговор може да се получи и от:
[tex]l[/tex] "лъжци", [tex](k-l-1)[/tex]"честни" и 1"лъжец" ([tex]0\le l\le l-1[/tex]).

Тогава идеята на решението е:
броя на лъжците да не може да "покрие изцяло" една от най-дългите поредици от отговори от вида:[tex]\underbrace{ Ч,Ч,...,Ч,Л }_{k}[/tex].
Тогава предпоследния отговарял в коя да е от тях винаги ще е "честен", а последния "лъжец".


Контра-примера при 10 лъжци е :
[tex]\underbrace{ Л,Л,...,Л, }_{7}\underbrace{ Ч,Ч,...,Ч,Л, }_{7}\underbrace{ Ч,Ч,...,Ч,Л, }_{7}\underbrace{ Ч,Ч,...,Ч,Л, }_{7}\underbrace{ Ч,Ч }_{2}[/tex],

т.е. броя на лъжците е по-малък или равен на 9.

...

[ptj]

При 9 не съществува контра пример.

Нека [tex]k[/tex] е броя на лъжците в най-дългата поредица (съседи).
Тогава останалите лъжци могат да бъдат разпределени в не повече от [tex](9-k)[/tex] поредици от вида [tex]\underbrace{ Ч,Ч,...,Ч,Л, }_{k}[/tex].
Освен това първия от групата на лъжците също може да участва в подобна поредица,
т.е. по този начин броя на честните е не повече от [tex](9-k+1)(k-1)=-k^2+9k-10[/tex], но те реално са 21.

[tex]-k^2+9k-10<21\Leftrightarrow k^2-9k+31>0 \Leftrightarrow \bigg(k-\frac{3}{2}\bigg)^2+\frac{4.31-9}{4}>0[/tex]

Последния ред показва, че така формиране групи не могат да включат всички честни.
Tогавa съгласно принципа на Дирихле ще съществува група от вида [tex]\underbrace{ Ч,Ч,...,Ч,Л, }_{l}[/tex] и [tex]l>k[/tex],
т.е. тя ще най-дългата група от търсения от нас вид.

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

[drago]

...Контра-примера при 10 лъжци е :
[tex]\underbrace{ Л,Л,...,Л, }_{7}\underbrace{ Ч,Ч,...,Ч,Л, }_{7}\underbrace{ Ч,Ч,...,Ч,Л, }_{7}\underbrace{ Ч,Ч,...,Ч,Л, }_{7}\underbrace{ Ч,Ч }_{2}[/tex],

т.е. броя на лъжците е по-малък или равен на 9.

...

За да докажеш, че тази ситуация е контрапример трябва да покажеш че ако вземем възможните конфигурации с не повече от 10 лъжци, при които са възможни тези отговори, то фамилията от множества с позициите на честните във всяка конфигурация има празно сечение. Сори, но това не го виждам
Пък и нещо повече, при тези отговори мъдрецът може да посочи не един а цели 3 бр. честни. Във втората, третат и четвъртата седморка, последния, който е дал отговор "Л" е честен. Да допуснем противното, например, че последния във втората седморка е лъжец. Тогава всичките 6 преди него(дали отговор "Ч") са също лъжци. До тук имаме 7 лъжци, остават още не повече от 3.Разгледай първата седморка. Ако там има 2-ма честни един до друг, то няма как да се получат тези отговори. Значи там ситуацията е такава:Ч,Л,Ч,Л,Ч,Л,Ч. И така всички останали във третат и четвъртат седмока са честни, но тогава не могат да дадат такива отговори, противоречие. И така без никакво съмнение посочихме 3-ма честни. ??

По втората част, за N=9. Какъв е алгоритъма, по който мъдреца ще открие поне един честен, защото от тези обяснения не виждам как ще го направи.

[ptj]

Май ти не си разбрал.
Поредицата от 7 лъжци могат да дават произволни отговори, затова може да "шифтнем" всичките 30 отговора с до 7 позиции надясно, а тогава мъдреца по никакъв начин няма да може да каже къде има честен или лъжец.
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
За 2-рата част мъдреца търси най-дългата поредица от отговори "честен", завършващи с лъжец. Тогава последния, дал отговор в нея, е честен.

[drago]

Май ти не си разбрал.
Поредицата от 7 лъжци могат да дават произволни отговори, затова може да "шифтнем" всичките 30 отговора с до 7 позиции надясно, а тогава мъдреца по никакъв начин няма да може да каже къде има честен или лъжец.
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
За 2-рата част мъдреца търси най-дългата поредица от отговори "честен", завършващи с лъжец. Тогава последния, дал отговор в нея, е честен.

Не знам какво си представяш, че "шифтваш", но аз ти показаш, че при тези отговори мога да посоча 3-ма които са честни. Прочети го. Не коментирам въпроса, дали въобще тези отговори са възможни, понеже ти го даваш като контрапример, би следвало да се погрижиш.
Относно N=9: Да допуснем, че получените отговори са: ЧЧЧЧЛ, ... това повторено 6 пъти. Кажи ми сега, кой е честен.

[ptj]

"Шифтването" е завъртане с едно надясно. Провери следната комбинация от отговори (за 10 лъжци) [tex]\underbrace{ Ч,Ч,...,Ч,Л, }_{7}\underbrace{ Ч,Ч,...,Ч,Л, }_{7}\underbrace{ Ч,Ч,...,Ч,Л, }_{7}\underbrace{ Ч,Ч,...,Ч,Л, }_{7}\underbrace{ Ч,Л, }_{2}[/tex] - в нея не може да ми кажеш къде има честен.

---------------------------------------------------------------

Последния във всяка група е честен, т.е. съответния на отговор "лъжец".
Имаш задължително 6 лъжци след края на всяка група, а останалите 3-ма не могат да "покрият" 4 отговора "честен".

[drago]

За N=9. Виж сега това по-долу. Горния ред е какви са в действителност хората, долния е отговорите, които дават (за този отдясно).
Л Л Л Л Л, Ч Ч Ч Ч Ч, Л Ч Ч Ч Ч, Л Ч Ч Ч Ч, Л Ч Ч Ч Ч, Л Ч Ч Ч Ч
Ч Ч Ч Ч Л, Ч Ч Ч Ч Л, Ч Ч Ч Ч Л, Ч Ч Ч Ч Л, Ч Ч Ч Ч Л, Ч Ч Ч Ч Л

Виждаш ли петия не е честен. Аналогичен пример може да се даде, така че 10 тия не е честен и т.н.

Сега ти ми дай такъв пример на твойте отговори при твоя пример за N=10, така че поне един от тези тримата, за които твърдя че са честни,да не е такъв.

[ptj]

O.K.
Дадения от теб пример е "контра" за [tex]n\ge9[/tex].
При 9 не може да се каже къде се намира последователността от 5 поредни лъжци, т.е. тя може да съответства произволна група отговори "Ч,Ч,Ч,Ч,Л". Именно това имах предвид под "шифтване". Ако има други лъжци над 9, то те могат винаги да отговарят като честни, а това няма да промени вече намерената конфигурация.

Колкото до идеята ми -трябва да я доизчистя, защото се оказа, че ако максималната група от лъжци е само с 1 по-малка по дължина от максималната група от честни, то двете групи могат да дават индентични отговори.

[drago]

Ами, то не остана повече. Отговорът е [tex]N=8[/tex].
Както ptj забеляза, алгоритъма на мъдреца е простичък:
Взема се най-дългата поредица от отговори ЧЧЧ...Ч и следващия, който дава отговор "Л" е честен.
Аргументите са както в първия ми пост по-горе. Да допуснем, напр че наи-дългата поредица е "Ч,Ч,Ч,Л". Да допуснем противното, че този последния не е честен. Значи всичките трима преди него са също лъжци. Т.е. имаме 4 лъжци, остават не повече 4. Имаме една поредица от 26 човека, измежду тях 4 лъжци, т.е. 22 честни в 5 интервала, т.е. в един от петте интервала между лъжците ще има поне 5 честни, което означава, че ще има една поредица от отговори : "...ЧЧЧЧ...", което е противоречие с избраната макс. дължина на поредни "Ч".
По същия начин се обосновава, ако най дългата поредица "ЧЧ...ЧЛ" се състои от повече от 3 "Ч". Това е.

Задачата е давана на Босненски TST, 2008.