8 окт. 2013 г.

Математические ментальные вирусы

Добрый день.

А иногда так бывает: услышал где-то задачку, а она почему-то заинтересовала. И вот уже несколько дней, двигаясь куда-либо пешком, полностью улетаешь в какой-то параллельный мир... А друзья потом обижаются, что не поприветствовал их, хотя проходил в двух шагах. Да, у меня пока хорошее зрение! Да, я с удовольствием бы поговорил с вами. Но в тот момент меня не было в том пустом теле.

Давайте приведём несколько примеров:

1) Недавно avva перепечатал сентябрьскую задачку от IBM. Приведу здесь его перевод:

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

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

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

Нужно доказать, что в игре из n=9 раундов Алиса и Боб могут обеспечить минимум 6 побед.


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

Разглядывая эту проблему, я вспомнил очень близкую по духу и совсем недавно разобранную задачку с Турнира Городов о выборе четырёх карт из пяти. Если вы её ещё не решили, то настоятельно рекомендую это сделать, потому что это приятно и интересно. Если знаете и решили про 52 карты, но не видели модификации с 53 картами (ещё и с джокером), то рекомендую продумать её (если что, разбор опубликован). С моей точки зрения, эта задачка очень похожа, но проще приведённой выше задачи об Алисе, Бобе и казино.

2) Другой пример ментального вируса формулируется гораздо короче, но тоже пожирает много времени. И делает это он не из-за того, что у меня много времени, а по той простой причине, что хорошо составлен. Ну или просто удачно подходит к моим уязвимостям.

Звучит задачка так: Докажите, что у уравнения «сумма кубов трёх целых чисел равна трём» (x3 + y3 + z3 = 3, где x, y и z являются целыми числами) конечное число решений.

Я почти уверен, что есть всего два решения. А вы? Какие видите идеи решения?

3) А помните, как мы с островом Беззеркалья боролись? Чудесное время было :)

А какие задачки самопроизвольно захватывали вашу голову? (особенно в ситуациях, когда собралась большая очередь настоящих важных дел)

Хорошего дня!

P.S.
Приношу извинения перед всеми, кого только что заразил математическими ментальными вирусами. Иначе я не мог, вирус требует (кстати, о подобном распространении заразы рекомендую забавное видео про зомби и прочие радости, которое с точки зрения ни разу не биолога является познавательным и расширяющим кругозор (настоящие биологи, что вы думаете про такую популяризацию науки?))

9 комментариев:

  1. Анонимный08.10.2013, 22:20

    Очень часто проигрываю разные алгоритмы в уме, прежде чем написать код. А ещё частенько считаю вероятность чего-либо, пока еду в общественном транспорте.
    P.S. Есть неплохая документалка про паразитов: ‹‹Паразиты. Битва за тело.››, а в этом видео про "зомби" куча ляпов.

    ОтветитьУдалить
  2. Анонимный10.10.2013, 2:46

    Важное замечание, отсутствующие в переводе - при выборе тактики Алиса и Боб знают про то, что Боб узнает последовательность Казино.

    ОтветитьУдалить
    Ответы
    1. Да, совершенно верно! И я не обратил на этот момент внимания, так как считал его очевидным для сохранения смысла задачи.

      Удалить
  3. мне кажется, что в задаче с казино надо как то использовать задачу о шляпах и мудрецах (http://knop.livejournal.com/107564.html)

    ОтветитьУдалить
  4. Касательно второй задачи, два ответа быстро приходят на ум - x=y=z=1 x=y=4 z=-5
    Доказать отсутствие других вариантов будет сложнее.
    Логично предположить, что как минимум одно из трех чисел должно быть отрицательно (за исключением трех единиц). Если все числа разные, наиболее вероятная область поиска y=[x]+1, z=[y]+1. Однако простым перебором можно понять, что такой тройки нет и ее сумма все больше и больше отдаляется от 3 при увеличении х.
    Вторая область - это x=y, z=[x]+1, но здесь только один вариант, при увеличении модуля х сумма опять все дальше уходит от 3.
    Стоит оформить это как-то более систематически...

    ОтветитьУдалить
  5. Первая же фраза в http://oeis.org/A003325 говорит о том, что это нерешенная проблема:
    It is conjectured that this sequence and A052276 have infinitely many numbers in common, although only one example (128) is known.
    Вы ожидаете увидеть как специалист по эллиптическим кривым изобретен новую теорию на пару сотен страниц и напишет вам в комментариях?

    ОтветитьУдалить
    Ответы
    1. Спасибо!
      Что я ожидал? Что это обычная школьная олимпиадная задача на делимость, которую я из-за недостаточной внимательности всё никак не мог одолеть.

      Удалить
  6. Задача про казино:
    следует разбить все 9 раундов на группы 1 4 3 1, таким образом у нас формируются куски двоичных кодов, с помощью которых можно выиграть раунд у казино, либо передать информацию для последующих шагов. Объяснение может быть запутаным, поэтому и на простоту не претендует (тем более на лаконичность).

    Боб анализирает последовательность банка: если во второй группе (из 4х бит) количество единиц и нулей одинаково, то первая группа (1 бит) будет передевать информацию для третей группы. Иначе же первая группа задает значение, которое Алиса будет выкидывать на стол. Если это значение нужно переключить для третьей группы, то четвертый бит второй группы используется, чтобы Алиса переключила бит для третьей группы. То же самое происходит для четвертой группы. Все биты, которые не совпали для казино и боба, будут интерпретироваться Алисой как информация для последующих групп.
    Итого: первый бит скорее всего не совпадет, во второй группе мы выигрываем 2 или 3 + 2 или 1 бит информации для третьей группы. В третьей группе мы выиграем как минимум 2 бита, если нужно будет переключить четвертую, и выиграем все 3 бита третьей и один бит четвертой - если они все одинаковые. Минимум 6 выигранных мы сможем получить.
    Как-то так. Прошу прощения за скомканность разъяснений.

    ОтветитьУдалить
    Ответы
    1. Sergey, спасибо за описание! Оно достаточно ясное для любого человека, который думал про эту задачу. Мне показалось удобнее разбивать на группы 1 3 3 2, а потом выкручиваться, но здесь, скорее всего, срабатывает следующий эффект: свой подход роднее, поэтому, даже если он чуть сложнее, в его рамках удобнее думать.

      Удалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний