Кажется, вы правы. Возможно, они имеют в виду то, что таккой набор будет не столько стратегией Алисы, сколько приложением ее стратегии; саму стратегию, как функцию от всех возможных префиксов казино и Боба, труднее описать.
Но это еще связано у меня вот с каким сомнением. Тот факт, что они не просят прислать стратегию Алисы, заставляет меня думать, что у них есть простой способ проверить корректность решения только по решению Боба, но я не могу понять, что это может быть за способ. Проверить сам факт сушествования стратегии для Алисы по решению Боба кажется сложной задачей (и если бы они так поступали, то наверняка действительно скорее попросили бы прислать набор Алисы).
Поэтому я склоняюсь к тому, что у них есть на уме какая-то особенно простая и интуитивная стратегия поведения Алисы, к которой подходит какой-то конкретный набор Боба (или один из класса наборов). Что-то вроде примера для 50% - Боб задает правильное значение четных раундов на нечетных - сложнее, но ненамного. Увы, ничего такого я не смог придумать. Я тоскую, потому что типичные стратегии, которые я рассматривал, в которых биты Боба кодируют всякие относительно сложные факты для Алисы, к таким не относятся - если бы такая стратегия была верна, мне непонятно, как они бы проверили мое решение без описания "моего" поведения Алисы.
Тот факт, что они не просят прислать стратегию Алисы, заставляет меня думать, что у них есть простой способ проверить корректность решения только по решению Боба, но я не могу понять, что это может быть за способ. Проверить сам факт сушествования стратегии для Алисы по решению Боба кажется сложной задачей
Так это ведь задача о кодировании: если в одной части бит (меньшей), можно передать информацию о другой части бит (большей), то из алгоритма "сжатия" информации легко получается алгоритм "распаковки".
Но вот придумать такой алгоритм сложно. Видимо, тут не только биты надо задействовать (в трёх битах информацию о шести не закодируешь), но и их местоположение (как в алгоритме на чётных-нечётных раундах).
Но это еще связано у меня вот с каким сомнением. Тот факт, что они не просят прислать стратегию Алисы, заставляет меня думать, что у них есть простой способ проверить корректность решения только по решению Боба, но я не могу понять, что это может быть за способ. Проверить сам факт сушествования стратегии для Алисы по решению Боба кажется сложной задачей (и если бы они так поступали, то наверняка действительно скорее попросили бы прислать набор Алисы).
Поэтому я склоняюсь к тому, что у них есть на уме какая-то особенно простая и интуитивная стратегия поведения Алисы, к которой подходит какой-то конкретный набор Боба (или один из класса наборов). Что-то вроде примера для 50% - Боб задает правильное значение четных раундов на нечетных - сложнее, но ненамного. Увы, ничего такого я не смог придумать. Я тоскую, потому что типичные стратегии, которые я рассматривал, в которых биты Боба кодируют всякие относительно сложные факты для Алисы, к таким не относятся - если бы такая стратегия была верна, мне непонятно, как они бы проверили мое решение без описания "моего" поведения Алисы.
Reply
> саму стратегию, как функцию от всех возможных префиксов казино и Боба
Ну, я хотел сказать, что это ведь необязательно, ибо они сговорились, и оба знают, что любая комбинация префиксов Алисе не встретится.
Reply
Так это ведь задача о кодировании: если в одной части бит (меньшей), можно передать информацию о другой части бит (большей), то из алгоритма "сжатия" информации легко получается алгоритм "распаковки".
Но вот придумать такой алгоритм сложно. Видимо, тут не только биты надо задействовать (в трёх битах информацию о шести не закодируешь), но и их местоположение (как в алгоритме на чётных-нечётных раундах).
Reply
Leave a comment