задачка
Отличная задачка от IBM.
Перевод условия: Алиса и Боб играют против казино следующую игру: в каждом раунде Алиса выбирает бит 0/1, потом Боб, потом казино; все выборы публичные. Алиса и Боб выиграли раунд, если все три выбора одинаковые, и проиграли в обратном случае. При таких условиях казино побеждает тривиальным образом (т.к. видит выборы Алисы и Боба), поэтому на самом деле казино заранее записывает все свои выборы и они хранятся в сейфе и открываются по одному.
Алиса и Боб могут договориться о стратегии заранее, но не могут обмениваться информацией во время игры (кроме своих выборов). Перед началом игры Боб подкупает работников казино и получает всю последовательность выборов казино, но он не может уже к этому моменту передать эту информацию Алисе.
При этих условиях Алиса и Боб могут обеспечить себе победу в 50% раундов: на нечетных раундах Боб выбирает то, что Алиса (и Боб) должны поставить в следующем раунде, и таким образом во всех четных раундах они выигрывают.
Нужно доказать, что в игр в n=9 раундов Алиса и Боб могут обеспечить минимум 6 побед.
Я пока что знаю, как обеспечить 5 побед, а 6 не могу. Буду еще думать.
Прошу не спойлерить - если у вас есть полное решение, дайте ссылку на свой журнал или поместите его на pastebin.com и дайте ссылку туда - это занимает ровно минуту без регистрации.
Update: AAAAAAAAAAAAAAAAAAAAAA!
Перевод условия: Алиса и Боб играют против казино следующую игру: в каждом раунде Алиса выбирает бит 0/1, потом Боб, потом казино; все выборы публичные. Алиса и Боб выиграли раунд, если все три выбора одинаковые, и проиграли в обратном случае. При таких условиях казино побеждает тривиальным образом (т.к. видит выборы Алисы и Боба), поэтому на самом деле казино заранее записывает все свои выборы и они хранятся в сейфе и открываются по одному.
Алиса и Боб могут договориться о стратегии заранее, но не могут обмениваться информацией во время игры (кроме своих выборов). Перед началом игры Боб подкупает работников казино и получает всю последовательность выборов казино, но он не может уже к этому моменту передать эту информацию Алисе.
При этих условиях Алиса и Боб могут обеспечить себе победу в 50% раундов: на нечетных раундах Боб выбирает то, что Алиса (и Боб) должны поставить в следующем раунде, и таким образом во всех четных раундах они выигрывают.
Нужно доказать, что в игр в n=9 раундов Алиса и Боб могут обеспечить минимум 6 побед.
Я пока что знаю, как обеспечить 5 побед, а 6 не могу. Буду еще думать.
Прошу не спойлерить - если у вас есть полное решение, дайте ссылку на свой журнал или поместите его на pastebin.com и дайте ссылку туда - это занимает ровно минуту без регистрации.
Update: AAAAAAAAAAAAAAAAAAAAAA!