Каскадный · [ Стандарт ] · Линейный+ Математический клуб, 10+

[NathZh]

Задача:
Alice and Bob are imprisoned by an evil warden. They are each placed in a cell that has some number of trees in it, and each person can only see the trees in their own cell. Every day the warden asks Alice, "Are there 18 or 20 trees in total?" (he guarantees one of these is correct), and Alice can either answer or choose to pass. If she chooses to pass, Bob gets the same question (and can also choose to pass). If either person answers correctly at any point, then they are both freed, but if either answers wrong, they are both put to death. Can Alice and Bob guarantee that they escape?

перевод, наверное, сильно вольный)

Алиса и Боб попали в плен. Каждый из них содержится в клетке, в каждой из которых )давайте читать "как видно из окна", так логичнее что ли...) некоторое кол-во деревьев и каждый из пленников может видеть только свои деревья.
Каждый день охранник спрашивает Алису: деревьев всего 18 или 20?)один из этих ответов точно верный), и Алиса может ответить или отказаться отвечать. Если она отказывается, охранник идет к Бобу и задает тот же вопрос и Боб так же может ответить или отказаться. На след. день все повторяется.
Если кто-нибудь из них ответит верно, их обоих освободят. Если кто-то ответит неверно, их обоих казнят. Могут ли Алиса и Боб гарантированно спастись )т..е они не будут рисковать и пытаться угадать)

[Иванова Лена]

NathZh, а вместе они гарантированно видят ВСЕ деревья?
Ели Алиса видит 5, а Боб 6, то задача не решается точно
И множества бобиных деревьев не пересекается с множеством алисиных?
Обговорить заранее стратегию ответов они могут?

Я так прочитала, что каждый в клетке, и внутри этой же клетки сколько-то деревьев. Каждый видит деревья внутри своей клетки. А в чужой не видит.
И всего в двух клетках или 18 или 20.

[NathZh]

Иванова Лена, всего 18 или 20.
Каждый видит только свои и не может видеть другие )деревья в клетке это странно, поэтому мне удддобнее, что они их видят из окна)))))
Множества не пересекаются

стратегию обговорить не могут. То, что они знают о Perfect mind ддруг друга- это и есть их стратегия- они могут делать 100% верные выводы из ответа или отказа отвечать друг друга

[Иванова Лена]

NathZh,
День1. Если Алиса видит 20 или 19 деревьев, она говорит ответ20. Иначе пасует.
Если Боб видит 20 или 19 деревьев, он говорит ответ 20
Если Боб видит 0 деревьев, он говорит 18
Иначе пасует.
День2. Если А видит 18 деревьев, она говорит 20, иначе пасует.
Если Б видит 1 или 2 дерева, то говорит 18. Иначе пасует.
День 3. Если А видит 16 или 17 деревьев, то говорит 20. Иначе пасует
Если Б видит 3 или 4 дерева, то говорит 18. Иначе пасует.
День 4. А 15 или 14 - говорит 20. Иначе пасует
Б 5 или 6 - говорит 18. Иначе пас.
День 5. А 13 и 12
Б 7 и 8
День 6. А 11 и 10
Б 9 и 10
И т.д.

[NathZh]

NathZh,
День1. Если Алиса видит 20 или 19 деревьев, она говорит ответ20. Иначе пасует.
Если Боб видит 20 или 19 деревьев, он говорит ответ 20
Если Боб видит 0 деревьев, он говорит 18
Иначе пасует.
День2. Если А видит 18 деревьев, она говорит 20, иначе пасует.
Если Б видит 1 или 2 дерева, то говорит 18. Иначе пасует.
День 3. Если А видит 16 или 17 деревьев, то говорит 20. Иначе пасует
Если Б видит 3 или 4 дерева, то говорит 18. Иначе пасует.
День 4. А 15 или 14 - говорит 20. Иначе пасует
Б 5 или 6 - говорит 18. Иначе пас.
День 5. А 13 и 12
Б 7 и 8
День 6. А 11 и 10
Б 9 и 10
И т.д.

Если в 1 день Боб видит 1 дерево, он тоже может сказать 18, т.е. Алиса уже знает, что у него минимум 2 и
на 2 день говорит 20, если видит 18 или 17

Все правильно, только немножно быстрее можно

[Иванова Лена]

NathZh, угу. Мне тоже было подозрительно, что в 1 день меньше информации выходит, чем в последующие, но не додумала этот момент.

[Soul]

В варианте Лены много повторов.

Я села и разобралась, что вычитать нужно )))
Когда считали варианты из трёх красок то вариант ЖК (желтый и красный) был посчитан в ЖКС и в ЖКЗ. Итак, любой двухкрасочный вариант был посчитан дважды - один раз лишний, именно его и нужно вычесть - всего двухкрасочных вариантов (из 4 по 2)*2^6.
Когда считали двухкрасочные варианты, то вариант К попадал в ЖК, ЗК и СК - вместо одного раза мы учли эти элементы три раза, два лишних, то есть нужно вычесть 2*(из 4 по 1)*1^6.
Итого получаем
4^6 - 4*3^6 + 6*2^6 - 8=4096 - 729 + 384 - 8 = 3743.
Мой ответ пока посередине )))

[NathZh]

Soul, это вы посчитали не верно.
У вас получается 1556, не хватает 4 потому что однокрасочных варианта 4, надо отнимать 4, а не 8

[Иванова Лена]

Алисе и Бобу дали по карточке с цифрой от 1 до 9. А потом они поговорили:
А: я не знаю чье число больше
Б: я не знаю чье число больше
А: я не знаю чье число больше
Б: я не знаю чье число больше
Какое число у Боба?

А1 - у меня не 1 и не 9.
Б1 - у меня не 1, не 2, не 9, не 8.
А2- у меня не 1, не 2, не 3, не9,8,7.
Б2 - у меня не 1,2,3,4, не 9,8,7,6
У Боба 5

[NathZh]

У Боба 5

Лена, первая для разминки перед второй была))