задачка

[avva]

Отличная задачка от IBM

Comments

[alexeybobkov]

При этих условиях Алиса и Боб могут обеспечить себе победу в 50% раундов: на нечетных раундах Боб выбирает то, что Алиса (и Боб) должны поставить в следующем раунде, и таким образом во всех четных раундах они выигрывают.

Ничего не понимаю. Почему? И как в этой стратегии учитывается то, что Боб знает выбор казино?

[alexeybobkov]

А, всё понятно. Прочитал в оригинале)

[avva]

Неужели я так плохо перевел? :)

[alexeybobkov]

Хорошо, но слишком сокращённо :)

[korchy]

Из оригинала не очень ясно, Боб договаривается о стратегии с Алисой уже зная, что украдет ходы казино? Вроде же после кражи договариваться уже ни о чем нельзя.

[avva]

Это действительно не очень понятно, вы правы. Я исходил из того, что они договариваются, зная, что он украдет. Ваше второе замечание не очень понятно: если бы после кражи они могли договориться, он бы просто передал ей ходы казино, и они бы вдвоем их повторяли и выигралы все раунды. Вся сложность в том, что Боб знает заранее ход казино в каждом раунде, а Алиса не знает.

[korchy]

Если они обговаривают стратегию, зная, что Бобу будут известны ходы казино, 6 из 9 решается, как мне кажется, достаточно влоб.

[avva]

Очень может быть. У меня пока не получилось.

[kaathewise]

Это очень напоминает одну известную задачку с карточным фокусом, но там попроще сделать 2/3.

[avva]

Да, я над той задачкой долго думал лет 10 назад. Но она действительно немного другая.

[ile_eli]

ну так откройте непосвященным, что за задачка.

[kaathewise]

Вот в таком виде она была на ММО в 2004 году:

Перед экстрасенсом лежит колода из 36 карт рубашкой вверх (4 масти, по 9 карт каждой масти). Он называет масть верхней карты, после чего карту открывают и показывают ему. После этого экстрасенс называет масть следующей карты и т. д. Задача экстрасенса --- угадать масть как можно большее число раз.

Рубашки карт несимметричны, и экстрасенс видит, в каком из двух положений лежит верхняя карта. Помощник экстрасенса знает порядок карт в колоде, не может менять его, но может расположить рубашку каждой из карт тем или иным образом.

Мог ли экстрасенс так договориться с помощником, когда тот ещё не знал порядок карт, чтобы обеспечить угадывание масти не менее чем a) 19 карт; б) 23 карты?

[metaguest]

Интересно что в оригинале Боб просто украл информацию из сейфа, а у Вас подкупил работников.

[ext_2087110]

Отличная задачка, и правда.
5 из 8 или 6 из 10 - тривиально. а вот 6 из 9 что-то в голову никак не лезет.

[huzhepidarasa]

А как сделать 5 из 8? У меня почти получается, но не совсем. Что-то я не понимаю.

Упыды: понял уже.