Блог пользователя AlexanderBolshakov

Автор AlexanderBolshakov, история, 9 лет назад, По-русски

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

Условие: Алиса и Боб загадали по однобайтовому числу (пусть эти числа будут называться a и b соответственно). Требуется придумать протокол общения между Алисой и Бобом, позволяющий им понять: равны ли a и b? При этом хочется, чтобы Алиса и Боб выдали друг другу как можно меньше информации о своих числах (в идеале — только сам факт равенства/неравенства). Предполагается, что Алиса и Боб будут строго следовать протоколу. Предполагается, что посторонних участников в задаче нет.

Прошу писать идеи решения в комментариях и прятать их под спойлеры.

UPD. hellman_ предложил решение, которое на первый взгляд удовлетворяет вышеописанному требованию к идеальному решению.

UPD2. OWNAGE от eatmore.

UPD3. Опубликовал неидеальное авторское решение.

  • Проголосовать: нравится
  • +57
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Сомневаюсь, что автор хочет именно это.

»
9 лет назад, # |
Rev. 10   Проголосовать: нравится 0 Проголосовать: не нравится

спойлер

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Понял, что ещё одно плохое решение

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем AlexanderBolshakov (предыдущая версия, новая версия, сравнить).

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Спойлер

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Простой вариант

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Хорошее решение?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем AlexanderBolshakov (предыдущая версия, новая версия, сравнить).

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Спойлер.

»
9 лет назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем AlexanderBolshakov (предыдущая версия, новая версия, сравнить).

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Авторское решение

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Спойлер

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    В смысле, CF удаляет старые правки?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      Никто ничего не удаляет, конечно.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Ну я как-то открываю подобную тему, там описывается какая-то задача, и просьба писать в спойлеры. Вижу спойлер....спойлер....спойлер....спойлер. А там либо стрелочки нет, либо не работает (уже не помню).

      Не знаю, может пофиксили уже.

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Долго не мог понять, где же решение, видя одни только спойлеры =)