Нова задачка в петък

[ql^2/8]

Всъщност, zxc0 беше споменал за решение с 31 опита - светваме всички битове и после гасим бит по бит.
Ако се замислим, последния бит няма нужда да се тества, щото може да се направи извод за него без да
го тестваме. Т.е. тривиалното решение е с 30 опита.
Това, което предлага Krusteva е мъничко по-добро, а звучи много по-сложно.
Приемам предложението, очаквам доказателство.

[zxc0]

Всъщност, като каза че последният няма нужда да се брой след като вече знаем отговора и като махнах първият ми излишен опит стават 29 опита. Обаче са винаги толкова и не може по-рано да познаеш.

Обикновено двойкаджиите са по-късметлии. Мисля друг метод по-късметлийски ама не мога да преценя каква доза късмет да заложа. При него опитите варират от 15 опита при най-големият късметлия до 30 опита при най-големият карък. Ще заложа винаги на вторият метод, особено ако за всеки опит(поправка) се плаща - не знам, не съм ходил на поправка.

Обясненията ще допиша по-късно. Може би първият метод няма да е толкова интересен колкото втория.


PS: Вероятността да се стигне до 30 опита е 1 / 536 870 912

[Krusteva]

Хрумна ми нова идея за 24 опита. Явно не съм се замислила много-много над подсказката.
Сравнително лесно се доказва, че за 5 въпроса опитите са 4 максимум.
30те въпроса могат да се разглеждат като 6 последователни групи от по 5 въпроса. За кратко всяка такава група ще наричам Г1..6 .
Нека на първи опит имаме Х верни отговора.
На следващия ход променяме само отговорите в Г1, по алгоритъма за 5 въпроса, тоест с още 4 опита ще знаем всички верни отговори на Г1 /дотук общо 5 опита/.
Последователно правим същото и за Г2-Г5, тоест общо още 4*4 = 16 или общо дотук 21 опита.
За Г6 вече знаем колко верни отговора съдържа /като извадим от Х сумата на верните отговори в Г1 до Г5/, затова там от 4те опита махаме един и стават 3, тоест дотук 21+3 или общо 24 опита за да знаем всички отговори.

[Wise]

Хм... нещо не ми харесва - мисля, че има разлика между 5 и 30 въпроса. Не мисля, че може така механично да ги мислим.
Може и да греша де. Но да кажем, че за 5 въпроса стигат 4 опита / не съм го гледал, но ви вярвам/ това какво значи за 10 въпроса?

[Krusteva]

Нека имаме пет въпроса. Опитите са:

1ви опит - Знаем колко са верните отговори. Нека са Х, като Х може да 0,1,2,3,4 или 5. Случаите 0 и 5 са ясни, няма нужда от втори опит. Случаите за Х = 1 или 4, както Х = 2 или 3 са еднакви за по-нататъшните разсъждения. Това е така, защото ако инвертираме всички отговори /без да е необходим опит за това/, при 1 верен и 4 грешни получаваме 4 верни и един грешен отговор. Същото за 2 и 3 верни отговора.
И така, може да имаме следните две възможни ситуации, които се нуждаят от последващи опити:

Случай А:

01111
10111
11011 -> 5 варианта при 4(1) верни отговора
11101
11110

Случай Б:

00111
01011
01101
01110 -> 10 варианта при 3(2) верни отговора
10011
10101
10110
11001
11010
11100

2ри опит - едновременно инвертираме /винаги спрямо първия ни опит правим това/ първите три бита. В случай А верните отговори ще намалеят с един в първите три варианта или с три във вторите два. В случай Б верните отговори ще се увеличат с един в три от вариантите, ще намалеят с един в шест от вариантите, или ще намалеят с три в последния вариант. Така се оформят следните подслучаи:

Случай А1:

01111
10111
11011

Случай А2:

11101
11110

Случай Б1:

00111
01011
10011

Случай Б2:

01101
01110
10101
10110
11001
11010

Случай Б3:

11100 -> ако попаднем в него, няма нужда от по-нататъшни опити, ясно е разпределението на битовете

3ти опит - Инвертираме едновременно 2ри, 3ти и 4ти бит. Случаите стават:

Случай А11:

01111

Случай А12:

10111
11011

Случай А21:

11101

Случай А22:

11110

Случай Б11:

00111
01011

Случай Б12:

10011

Случай Б21:

01101
10110
11010

Случай Б22:

01110

Случай Б23:

10101
11001


Случаи А11, А21, А22, Б12 и Б22 вече са решени на този етап.

4ти опит - едновременно инвертираме 2ри и 5ти бит /или 3ти и 5ти, все едно/. Това еднозначно определя една битова комбинация от случаите А12, Б11, Б21 и Б23.

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

Не ми се разписва подробно, но за 6 въпроса ни трябват 5 опита, така че ако делим на групи от по 6, ще имаме 25 опита. За 1,2,3 и 4 въпроса ни трябват 1,2,3,и 4 опита съответно.

[emil vasilev]

Krusteva ,аргументите ви издишат отвсякъде.Аз съм убеден за 29 опита.

[Krusteva]

Krusteva ,аргументите ви издишат отвсякъде

Как точно издишат отвсякъде? Не е изключено да греша, но това пък дори не е аргумент :-)

[emil vasilev]

Ако разделим механично 30 въпроса на 6 групи по 5 въпроса.. За всяка група от 5 въпроса имаме 4 опита Но в обкръжението на останалите 25 въпроса петия въпрос става неопределен.,остават определени само 4 въпроса.

[Krusteva]

Ще се опитам да обясня по-подробно алгоритъма за 30 въпроса.

1ви опит - с него разбираме общия брой верни отговори Х, както и знаем на кой въпрос какъв отговор сме дали. Оттук насетне всяко инвертиране ще е спрямо отговорите, дадени в тоя опит. За решенито на задачата ни е нужно да знаем точно какъв бит е на дадена позиция /0 или 1/, защото това е равнозначното на 'да знаем верния отговор'.

2ри опит - инвертираме първите пет бита. Тези пет бита могат сумарно да представляват 0, 1, 2, 3, 4 или 5 единици. След едновременното им инвертиране ще знаем точно колко верни отговора имаме в тази петорка. Ако са 0 единици, тоест всички отговори са ни били грешни, ще получим Х + 5 верни отговора. Ако сме имали един верен отговор, ще получим Х + 3, ако са били два верни -> Х + 1, ако са били три верни - Х - 1, ако са били четири -> Х - 3, ако са били пет -> Х -5. Това ще бъдат шест различни числа, което еднозначно ще определи броя на верните отговори САМО В ТАЗИ ГРУПА, както и в кой подслучай на първа стъпка от алгоритъма за петте въпроса попадаме. Освен това, автоматично ще ни даде и общо верните отговори в оставащите 25 бита /от Х вадим вече известния брой верни отговори в група Г1/. Последното го уточнявам за да се изясни /ако още не е/ защо в последната група Г6 ни трябват само 3 опита още.

3ти опит - това е втори опит от алгоритъма за петте въпроса, а именно едновременно инвертиране /спрямо първи опит пак, разбира се/ само на първите 3 бита от 30те. Ще получим Х + 3, Х + 1, Х - 1 или Х - 3 верни отговора за съответно 0, 1, 2 или 3 верни общо сред първата тройка. Това пак еднозначно ни определя в кой подслучай от втора стъпка на алгоритъма за петте въпроса попадаме.

4ти опит - същото като в трети опит, но с 2ри, 3ти и 4ти бит. Еднозначно определяме в кой подслучай на трета стъпка от алгоритъма за петте въпроса сме.

5ти опит - едновременно инвертиране на 2ри и 5ти бит, еднозначно определяне на битовата комбинация от първите пет въпроса.

6ти опит - повтаряме втори опит, като инвертираме само битове от 6 до 10 /Г2/. Битовете от 1 до 5 си остават във вида, в който сме ги направили при първия опит, тоест даваме същите пет отговора, както на първи опит. Пак повтарям, това е инвертиране спрямо първия опит. Абсолютно повторение на разсъжденията от 2ри до 5ти опит, тоест повторение на алгоритъма за петте въпроса.
- - - - - - - - - - - - - - -
22ри опит - имаме идентифицирани първите пет групи. Остават последните пет бита. ОБАЧЕ от първия опит имаме общия брой верни отговори, а от 2ри до 21ви - сумарно колко верни отговори има в първите 25 въпроса, тоест знаем колко верни отговора общо имаме в последните пет въпроса /бита/. Това спестява един опит /първа стъпка от алгоритъма за петте въпроса/ и направо пристъпваме към втората му стъпка. В 23ти и 24ти опит правим съответно трета и четвърта стъпка от алгоритъма за петте въпроса и напълно определяме каква е била битовата комбинация от първия ни опит, тоест знаем кои въпроси са били единици и кои нули, демек решена е задачата ни.

Надявам се, че сега изясних целия алгоритъм.

[ql^2/8]

Всъщност, алгоритимът беше ясен още от първия отговор. Ако си помисли човек...

Наистина с групи по 6 стават 25 отговора, а с групи по 5 - 24 отговора. Дотук добре!
Дали някой ще се опита да подобри този резултат?

[Krusteva]

Аууу, искаш да кажеш, че може и с по-малко ли? Няма да скрия, че не ми се занимаваше да проверя дали за N въпроса има вариант за по-малко от N -1 опита и това N разбира се да е под 30.

[ql^2/8]

Аууу, искаш да кажеш, че може и с по-малко ли? Няма да скрия, че не ми се занимаваше да проверя дали за N въпроса има вариант за по-малко от N -1 опита и това N разбира се да е под 30.

Аз бих ти препоръчал да опиташ като втора итерация с 13 въпроса.

- - - - - - - - - -

Да канализираме малко разсъжденията, нещо като трети жокер.
Задачата може да се разглежда като задача за претегляне.
Нека всяка група въпроси "тежи" толкова, колкото правилни отговора "ДА" съдържа.
Да "претеглим" група от въпросите ще рече да тестваме тази група с отговор "да",
а останалите с отговор "не". (Може да говорим и за маски с единици и нули.)

Нека като начало "претеглим" цялата група от "N" въпроса - тя има тегло "n".

Ако разделим въпросите на две групи "А" (с тегло "а") и "B" (с тегло "b")
и претеглим "A", ще получим примерно отговор "x", което е e сума на
отговорите "ДА" в група "А" и отговорите "НЕ" в група "B":
x = a + ( B - b )
От първото претегляне знаем общото тегло "n" на цялата група
n = a + b
можем да съберем равенствата:
x + n = 2a + B
и да изчислим теглото на "А" и "B":
a = 1/2*( x + n - B); b = n - a

[ql^2/8]

Да кажем, че за 30 въпроса има вариант с по-малко от 20 опита.