Добрый день.
Опять мы можем наблюдать, как на этот блог с поисковых систем приходят десятки людей по запросу «27 августа в 00:30, подними глаза и посмотри на ночное небо. В эту ночь планета Марс, пройдет всего лишь в 34,65 тыс. милях от земли». Это означает, что уже середина июля, поэтому половина лета уже почти прошла.
Кстати, если вам тоже очевидна физическая глупость текста из приведённой выше цитаты (про грамотность промолчу), то, возможно, заметка «Что такое бозон Хиггса» как раз для вас. В ней автор кратко и весьма доступно рассказывает, в чём был смысл исследования, результаты которого недавно обнародовали учёные, работающие на большом адронном коллайдере, какие статистические вопросы возникают при анализе результатов детекторов, как дальше жить физикам и так далее. В тексте есть реверансы на тему «на самом деле всё не так», но на то это и передний край науки спереди, чтобы не иметь даже надежды узнать точно, как устроен мир.
Теперь вернёмся к математике: задачу про 100 мудрецов в колонне, мы неплохо порешали, поэтому можно осмотреться, что ещё бывает в этой области:
- задача про 99 мудрецов и два цвета:
99 мудрецов сели за круглый стол. Им известно, что пятидесяти из них надели колпаки одного из двух цветов, а сорока девяти остальным — другого. Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака. Для какого наибольшего значения k можно гарантировать, что не менее k мудрецов могут сделать это правильно? (Разумеется, мудрецы могут заранее — до надевания колпаков — выработать совместно используемую стратегию) Осторожнее переходите по ссылке выше, так как там есть ответ и решения!
- задача про бесконечное количество мудрецов (сложная, парадоксальная, но полезная). Текст здесь не привожу, но любителям прекрасного рекомендую ознакомиться с условием.
Первая задача интересна тем, что правильный ответ многие могут почувствовать, а вот для оформления честного решения требуются гораздо большие усилия. Вторая же задача является ещё более чудесным поводом помассировать мозг.
Благодарю всех, кто нашёл время поделиться информацией о хороших книгах. Похоже, формулировка «это такая хорошая книга, которую мало кратко похвалить, а следует посвятить ей подробную, качественную и продуманную рецензию, чем я и займусь, как только найду чуть-чуть времени» объясняет небольшое количество рекомендаций. Поэтому я призываю: забудьте про совершенство формы, поделитесь содержанием!
Хорошего дня!
Интуиция подсказывает:
ОтветитьУдалить1. Возможно k=49+25, если додуматься как выбрать начало отсчета на круге.
2. Также возможно k=99-1, если додуматься до чего то более существенного, пока выразить не могу, ощущения на кончиках пальцев.
Долго думать пока нет времени.
Начало хорошее :)
УдалитьУ меня уточняющие вопросы.
Удалить1. Мудрецы както пронумерованы? Знают ли мудрецы свои номера?
2. Как осуществляется проверка? Нужно чтобы номер мудреца совпадал с номером цвета? Или чтобы общее количество красных \ синих ответов совпадало с соотношением 50\49 или наоборот 49\50?
1) Да, мудрецы могут заранее договориться, у кого какой номер.
Удалить2) Я не понимаю вопрос о совпадении номера мудреца с номером цвета. Требуется следующее: как минимум k мудрецов должны правильно написать на бумажке цвет шляпы, которая на каждом из них надета.
Выдерживать какое-то фиксированное общее количество цветов в ответах не требуется.
99, т.к. 49 мудрецов сразу напишут свой цвет, а после этого остальные поймут что у них другой цвет. Но это если при условии что они все пишут на бумажке.
ОтветитьУдалитьНет, не пройдет, ведь "Все мудрецы должны одновременно сообщить (написать на бумажке) цвет своего колпака". Поэтому 50 из них не успеют посмотреть на тех 49, которые сразу поймут свой цвет.
УдалитьВидимо, все уже решили задачу про 99 мудрецов в других местах. Раз никто не пишет, расскажу свой ответ (я тоже решал, когда ее опубликовал автор, на коорого Вы ссылаетесь).
ОтветитьУдалитьГарантированно получается 49+25. 49 узнают свой цвет, потому что видят 48 шляп одного цвета и 50 другого. А остальные, которые видят 49 и 49, договариваются так. Каждый делит сидящих за столом на две половины: правую и левую. И называет цвет, которого больше в правой половине от него. (Можно "больше" заменить на "меньше", а "правую" на "левую", главное, чтобы все выбрали одинаковую половину и одинаковое неравенство.) Ровно 25 из них назовет цвет своей шляпы. Осталось привести строгое математическое доказательство. Этого я, к сожалению, сделать не могу.
Ух, оказывается, по ссылке все решения уже раскрыты. Тогда понятно, почему никто не комментировал. Ну и ладно, я всё равно сам решил :).
УдалитьА если и справа и слева одинаковое количество разных цветов, тогда как? У меня есть пример расклада где у каждого равное количество слева и справа. Пока что не вижу очевидности того, что "Гарантированно получается 49+25."
Удалитьlord-corwin и уважаемый аноним,
Удалитьесли сформулировать правило, например, как "называть тот цвет, которого больше среди 49 человек, сидящих справа", то коллизии 49+49 не будет.
Конечно, можно придумать массу способов, чтобы из 50 человек ровно 25 дали один ответ. Вообще говоря, можно было аккуратно доказать, что существует способ делать такое для любой перестановки. Но предъявить решение, конечно, гораздо лучше.
Да, Илья, именно такую формулировку я и имел в виду. Видимо, недостаточно строго выразился, раз уважаемый аноним меня неверно понял. Насчет доказать — даже не представляю, с чего начинать, к сожалению.
Удалить--- У меня есть пример расклада где у каждого равное количество слева и справа.
ОтветитьУдалитьИзвиняюсь, это у меня получалось на другом, упрощенном примере, когда син\кра =4\5, а всего 9 мудрецов.
PS
УдалитьЕсли видоизменить задачу так, что всего 101 мудрец, из них 51 одного цвета, 50 другого, какова будет Ваша стратегия Илья?
--- Вообще говоря, можно было аккуратно доказать, что существует способ делать такое для любой перестановки.
Что Вы этим имели ввиду? Что существует стратегия для любого количества мудрецов, например для 101?
> Если видоизменить задачу так, что всего 101 мудрец, из них 51 одного цвета, 50 другого, какова будет Ваша стратегия Илья?
УдалитьЕстественно, если поменять остаток от деления количества мудрецов на четыре, то задача и её решение меняется (всё становится менее красивым).
Я вижу примерно такое решение:
С теми, кто видит ситуацию 49+51 всё понятно (их будет ровно 50). Разберёмся с 51 мудрецом, которые видят 50+50. Можно показать, что более 25 из них не смогут гарантированно называть свой цвет. Тогда предъявим решение для 25. Пусть каждый мудрец знает свой номер (число от 0 до 100). Тогда мудрец, чётность которого совпадает с чётностью наблюдаемой им перестановки, называет первый цвет, а остальные - второй.
> Что Вы этим имели ввиду?
Что можно было доказать существование алгоритма для задачи про 99 мудрецов, а не предъявлять этот алгоритм. В некоторых задачах (как и в этой) придумать решение может быть даже проще, чем доказать, что его можно построить. Но бывают задачи, для которых так и не удаётся найти чего-то более удобного и естественного, чем алгоритм построения очень большой таблицы, по которой должны ориентироваться мудрецы.
--- Можно показать, что более 25 из них не смогут гарантированно называть свой цвет.
УдалитьТогда оставшихся менее 25, а не ровно 25. Или здесь очепятка?
---Что можно было доказать существование алгоритма для задачи про 99 мудрецов, а не предъявлять этот алгоритм.
Если имеется конструктивное доказательство в виде готового алгоритма, то зачем далее теоретизировать? - Не понимаю. Ладно, думаю не важно, забудьте.
> --- Можно показать, что более 25 из них не
Удалить> смогут гарантированно называть свой цвет.
> Тогда оставшихся менее 25, а не ровно 25. Или здесь очепятка?
Да нет, 25 смогут, а более 25 не смогут.
> Если имеется конструктивное доказательство в виде
> готового алгоритма, то зачем далее теоретизировать?
А если не имеется готового алгоритма, то иногда достаточно предъявить способ его построить (само построение может быть невероятно ресурсоёмким).
--- Пусть каждый мудрец знает свой номер (число от 0 до 100). Тогда мудрец, чётность которого совпадает с чётностью наблюдаемой им перестановки, называет первый цвет, а остальные - второй.
ОтветитьУдалитьА откуда у Вас Илья гарантия, что Вы сможете обеспечить равное количество совпадений и несовпадений четности номеров мудрецов и четности номеров перестановок.
Условно назовем красными тех кто видит 50\50.
Возьмем например следующий маргинальный расклад. Все те кто в будущем станет красными получили нечетные номера по считалочке до рассаживания. До кучи они еще и расселись по порядку. До кучи им ещё и шляпы надели строго по порядку: на нечетных красные, а на четных синие.
В таком случае слева\справа почти каждого красного почти всегда будут синие. Найдется только два красных (номер 1 и номер 101) слева\справа которых есть и красный и синий.
Как Вы в таком случае занумеруете перестановки, чтобы ровно половина из тех из них и только тех из них, которые видны красным, были нечетными.
Да, похоже, я тут погорячился (не надо учитывать чётность мудреца). Но это детали. И это очень правильно, что Вы стараетесь проверить потенциальное решение на крайних случаях! Это очень хорошая техника для отсечения неудачных гипотез.
Удалить> Как Вы в таком случае занумеруете перестановки?
Можно прочитать, например, в википедии, что такое чётность перестановки.
Занумеровать можно всё что угодно и как угодно. Вопрос был о другом. Есть ли у Вас решение для случаев 1+4n мудрецов? - 5, 9, ... 101 и т.д. По Вашим ответам я этого не понял.
Удалить> Занумеровать можно всё что угодно и как угодно.
УдалитьЭто верно. И я предъявил один из способов в ответ на Ваш вопрос.
> Есть ли у Вас решение для случаев 1+4n мудрецов?
Гм. Я думаю, что решение есть. Например, для 101 мудреца мы можем достигнуть результата в 50+24 правильных ответов следующим образом:
- если видим ситуацию 51+49, то называем цвет, которого меньше среди всех 100 человек, (они дадут ровно 50 правильных ответов)
- а если видим ситуацию 50+50, то называем тот цвет, которого меньше среди 49 человек, сидящих справа (они дадут от 24 до 26 правильных ответов).
Когда будет время, подумаю, можно ли поднять оценку с 24 до 25.