11 июл. 2012 г.

Разноцветные шляпы и бозон Хиггса

Добрый день.

Опять мы можем наблюдать, как на этот блог с поисковых систем приходят десятки людей по запросу «27 августа в 00:30, подними глаза и посмотри на ночное небо. В эту ночь планета Марс, пройдет всего лишь в 34,65 тыс. милях от земли». Это означает, что уже середина июля, поэтому половина лета уже почти прошла.

Кстати, если вам тоже очевидна физическая глупость текста из приведённой выше цитаты (про грамотность промолчу), то, возможно, заметка «Что такое бозон Хиггса» как раз для вас. В ней автор кратко и весьма доступно рассказывает, в чём был смысл исследования, результаты которого недавно обнародовали учёные, работающие на большом адронном коллайдере, какие статистические вопросы возникают при анализе результатов детекторов, как дальше жить физикам и так далее. В тексте есть реверансы на тему «на самом деле всё не так», но на то это и передний край науки спереди, чтобы не иметь даже надежды узнать точно, как устроен мир.

Теперь вернёмся к математике: задачу про 100 мудрецов в колонне, мы неплохо порешали, поэтому можно осмотреться, что ещё бывает в этой области:

- задача про 99 мудрецов и два цвета:
99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным — другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию) Осторожнее переходите по ссылке выше, так как там есть ответ и решения!

- задача про бесконечное количество мудрецов (сложная, парадоксальная, но полезная). Текст здесь не привожу, но любителям прекрасного рекомендую ознакомиться с условием.

Первая задача интересна тем, что правильный ответ многие могут почувствовать, а вот для оформления честного решения требуются гораздо большие усилия. Вторая же задача является ещё более чудесным поводом помассировать мозг.

Благодарю всех, кто нашёл время поделиться информацией о хороших книгах. Похоже, формулировка «это такая хорошая книга, которую мало кратко похвалить, а следует посвятить ей подробную, качественную и продуманную рецензию, чем я и займусь, как только найду чуть-чуть времени» объясняет небольшое количество рекомендаций. Поэтому я призываю: забудьте про совершенство формы, поделитесь содержанием!

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

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

  1. Анонимный11.07.2012, 16:58

    Интуиция подсказывает:

    1. Возможно k=49+25, если додуматься как выбрать начало отсчета на круге.
    2. Также возможно k=99-1, если додуматься до чего то более существенного, пока выразить не могу, ощущения на кончиках пальцев.

    Долго думать пока нет времени.

    ОтветитьУдалить
    Ответы
    1. Анонимный12.07.2012, 7:47

      У меня уточняющие вопросы.

      1. Мудрецы както пронумерованы? Знают ли мудрецы свои номера?

      2. Как осуществляется проверка? Нужно чтобы номер мудреца совпадал с номером цвета? Или чтобы общее количество красных \ синих ответов совпадало с соотношением 50\49 или наоборот 49\50?

      Удалить
    2. 1) Да, мудрецы могут заранее договориться, у кого какой номер.

      2) Я не понимаю вопрос о совпадении номера мудреца с номером цвета. Требуется следующее: как минимум k мудрецов должны правильно написать на бумажке цвет шляпы, которая на каждом из них надета.

      Выдерживать какое-то фиксированное общее количество цветов в ответах не требуется.

      Удалить
  2. Анонимный11.07.2012, 17:19

    99, т.к. 49 мудрецов сразу напишут свой цвет, а после этого остальные поймут что у них другой цвет. Но это если при условии что они все пишут на бумажке.

    ОтветитьУдалить
    Ответы
    1. Анонимный11.07.2012, 18:35

      Нет, не пройдет, ведь "Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака". Поэтому 50 из них не успеют посмотреть на тех 49, которые сразу поймут свой цвет.

      Удалить
  3. Видимо, все уже решили задачу про 99 мудрецов в других местах. Раз никто не пишет, расскажу свой ответ (я тоже решал, когда ее опубликовал автор, на коорого Вы ссылаетесь).

    Гарантированно получается 49+25. 49 узнают свой цвет, потому что видят 48 шляп одного цвета и 50 другого. А остальные, которые видят 49 и 49, договариваются так. Каждый делит сидящих за столом на две половины: правую и левую. И называет цвет, которого больше в правой половине от него. (Можно "больше" заменить на "меньше", а "правую" на "левую", главное, чтобы все выбрали одинаковую половину и одинаковое неравенство.) Ровно 25 из них назовет цвет своей шляпы. Осталось привести строгое математическое доказательство. Этого я, к сожалению, сделать не могу.

    ОтветитьУдалить
    Ответы
    1. Ух, оказывается, по ссылке все решения уже раскрыты. Тогда понятно, почему никто не комментировал. Ну и ладно, я всё равно сам решил :).

      Удалить
    2. Анонимный18.07.2012, 7:24

      А если и справа и слева одинаковое количество разных цветов, тогда как? У меня есть пример расклада где у каждого равное количество слева и справа. Пока что не вижу очевидности того, что "Гарантированно получается 49+25."

      Удалить
    3. lord-corwin и уважаемый аноним,
      если сформулировать правило, например, как "называть тот цвет, которого больше среди 49 человек, сидящих справа", то коллизии 49+49 не будет.
      Конечно, можно придумать массу способов, чтобы из 50 человек ровно 25 дали один ответ. Вообще говоря, можно было аккуратно доказать, что существует способ делать такое для любой перестановки. Но предъявить решение, конечно, гораздо лучше.

      Удалить
    4. Да, Илья, именно такую формулировку я и имел в виду. Видимо, недостаточно строго выразился, раз уважаемый аноним меня неверно понял. Насчет доказать — даже не представляю, с чего начинать, к сожалению.

      Удалить
  4. Анонимный18.07.2012, 10:35

    --- У меня есть пример расклада где у каждого равное количество слева и справа.
    Извиняюсь, это у меня получалось на другом, упрощенном примере, когда син\кра =4\5, а всего 9 мудрецов.

    ОтветитьУдалить
    Ответы
    1. Анонимный18.07.2012, 10:39

      PS
      Если видоизменить задачу так, что всего 101 мудрец, из них 51 одного цвета, 50 другого, какова будет Ваша стратегия Илья?

      --- Вообще говоря, можно было аккуратно доказать, что существует способ делать такое для любой перестановки.
      Что Вы этим имели ввиду? Что существует стратегия для любого количества мудрецов, например для 101?

      Удалить
    2. > Если видоизменить задачу так, что всего 101 мудрец, из них 51 одного цвета, 50 другого, какова будет Ваша стратегия Илья?

      Естественно, если поменять остаток от деления количества мудрецов на четыре, то задача и её решение меняется (всё становится менее красивым).

      Я вижу примерно такое решение:
      С теми, кто видит ситуацию 49+51 всё понятно (их будет ровно 50). Разберёмся с 51 мудрецом, которые видят 50+50. Можно показать, что более 25 из них не смогут гарантированно называть свой цвет. Тогда предъявим решение для 25. Пусть каждый мудрец знает свой номер (число от 0 до 100). Тогда мудрец, чётность которого совпадает с чётностью наблюдаемой им перестановки, называет первый цвет, а остальные - второй.

      > Что Вы этим имели ввиду?
      Что можно было доказать существование алгоритма для задачи про 99 мудрецов, а не предъявлять этот алгоритм. В некоторых задачах (как и в этой) придумать решение может быть даже проще, чем доказать, что его можно построить. Но бывают задачи, для которых так и не удаётся найти чего-то более удобного и естественного, чем алгоритм построения очень большой таблицы, по которой должны ориентироваться мудрецы.

      Удалить
    3. Анонимный19.07.2012, 8:02

      --- Можно показать, что более 25 из них не смогут гарантированно называть свой цвет.
      Тогда оставшихся менее 25, а не ровно 25. Или здесь очепятка?

      ---Что можно было доказать существование алгоритма для задачи про 99 мудрецов, а не предъявлять этот алгоритм.
      Если имеется конструктивное доказательство в виде готового алгоритма, то зачем далее теоретизировать? - Не понимаю. Ладно, думаю не важно, забудьте.

      Удалить
    4. > --- Можно показать, что более 25 из них не
      > смогут гарантированно называть свой цвет.
      > Тогда оставшихся менее 25, а не ровно 25. Или здесь очепятка?
      Да нет, 25 смогут, а более 25 не смогут.

      > Если имеется конструктивное доказательство в виде
      > готового алгоритма, то зачем далее теоретизировать?
      А если не имеется готового алгоритма, то иногда достаточно предъявить способ его построить (само построение может быть невероятно ресурсоёмким).

      Удалить
  5. Анонимный19.07.2012, 7:54

    --- Пусть каждый мудрец знает свой номер (число от 0 до 100). Тогда мудрец, чётность которого совпадает с чётностью наблюдаемой им перестановки, называет первый цвет, а остальные - второй.

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

    Условно назовем красными тех кто видит 50\50.

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

    В таком случае слева\справа почти каждого красного почти всегда будут синие. Найдется только два красных (номер 1 и номер 101) слева\справа которых есть и красный и синий.

    Как Вы в таком случае занумеруете перестановки, чтобы ровно половина из тех из них и только тех из них, которые видны красным, были нечетными.

    ОтветитьУдалить
    Ответы
    1. Да, похоже, я тут погорячился (не надо учитывать чётность мудреца). Но это детали. И это очень правильно, что Вы стараетесь проверить потенциальное решение на крайних случаях! Это очень хорошая техника для отсечения неудачных гипотез.

      > Как Вы в таком случае занумеруете перестановки?
      Можно прочитать, например, в википедии, что такое чётность перестановки.

      Удалить
    2. Анонимный19.07.2012, 9:46

      Занумеровать можно всё что угодно и как угодно. Вопрос был о другом. Есть ли у Вас решение для случаев 1+4n мудрецов? - 5, 9, ... 101 и т.д. По Вашим ответам я этого не понял.

      Удалить
    3. > Занумеровать можно всё что угодно и как угодно.
      Это верно. И я предъявил один из способов в ответ на Ваш вопрос.

      > Есть ли у Вас решение для случаев 1+4n мудрецов?
      Гм. Я думаю, что решение есть. Например, для 101 мудреца мы можем достигнуть результата в 50+24 правильных ответов следующим образом:
      - если видим ситуацию 51+49, то называем цвет, которого меньше среди всех 100 человек, (они дадут ровно 50 правильных ответов)
      - а если видим ситуацию 50+50, то называем тот цвет, которого меньше среди 49 человек, сидящих справа (они дадут от 24 до 26 правильных ответов).

      Когда будет время, подумаю, можно ли поднять оценку с 24 до 25.

      Удалить

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

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



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

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