Решения:
1) а) Выделяем одного человека, который будет считать (считающий), сколько людей зашло. Если заключенный (не считающий) заходит в комнату, и лампа выключена, он ее включает. Так он делает ровно один раз, и в дальнейшем лампу не трогает. Если считающий заходит в комнату, и лампа включена, он понимает, что еще один человек побывал в комнате, и выключает лампу. И того, считающий ответит, что все были, когда 99 раз выключит лампу.
б) Проблема в том, что если лампа изначально включена, то считающему надо выключить лампу на 99, а 100 раз. А если выключена, то 99. То есть мы можем ошибиться на единицу. Решение - сделать так, чтобы эта единица не играла роли. Каждый заключенный включает лампу не один раз, а два. И 198 раз увидев включенную лампу, считающий знает, что все побывали в комнате (если лампа изначально была включена, то какой-то человек включит лампа не 2 раза, а один; но тем не менее побывает).
2) Включенная лампа несет в себе какую-то информацию, а выключенная - не несет никакой. Поскольку порядок случаен, то любая последовательность эльфов встретится хотя бы раз, но неизвестно, когда. Рано или поздно у нас встретится последовательность эльфов (и встретится бесконечно много раз), когда они идут подряд (первый, второй, ... , сотый). И тогда первый включит лампу, если количество прошедших от начала часов делится на 100. Второй оставит лампу включенной, если она была включена к его приходу, и количество прошедших часов дает при делении на 100 остаток 1 (так он узнает, что перед ним был именно первый). И так далее.
3) Коротко и с понятиями из алгебры: у нас есть перестановка, в ней есть не более одного цикла длины больше 50. Если он есть, разрубаем его пополам. Перемещаемся по полученным циклам.
Подробнее: Все имена можно пронумеровать от 1 до 100, и теперь считать, что у нас в ящике лежит не имя, а соответствующее число. Заключенный заходит, открывает ящик со своим номером, и видит там некоторое число K. Если K равно его номеру, все счастливы. Иначе он открывает ящик с номером K, и снова смотрит на число. Рано или поздно он встретит ящик со своим номером. Это должно быть интуитивно понятно, но если это вкратце доказать, то эта последовательность не может зациклиться, не придя в начальный ящик (потому что тогда какой-то номер встречается более одного раза). А зациклиться она должна, потому что ящиков конечно. В итоге у нас образуетя цикл - начав с какого-то ящика цикла, мы когда-нибудь придем в него. Каждый ящик принадлежит одному циклу (причем тому же циклу принадлежат те ящики, которые мы посетим, начав с него в описанном алгоритме).
Единственная проблема - эта последовательность может быть довольно длинной - вплоть до 100. И тут как раз и приходит на помощь первый заключенный - он переставляет два ящика так, чтобы цикла длины больше 50 не было. [Пронумеруем ящики в цикле в порядке, в котором мы посетим ящики, начав с некоторого из них] То есть делает так, чтобы 50-й ящик в цикле указывал на первый элемент цикла, а последний - на 51-й в цикле. Для этого надо просто поменять 50-й и последний ящик в цикле местами.
4) Пусть количество неверных жен равно k. Основное замечание - если жена визиря неверна, то он спал с k женами, а если верна - с (k+1) (все неверные, плюс его жена).
В первый день рассуждает визирь так - неверных жен не меньше 5. Если он спал с 5 женами, то он знает, что его жена неверна, и убивает ее. Однако этого не произошло, никто не умер, значит неверных жен не меньше 6 (и теперь визири знаюи и это).
Аналогично во второй день узнаем, что неверных жен не меньше 7.
В третий день по той же логике кто-то умирает. Это значит, что кто-то спал ровно с 7 женами, и понял, что его жена неверна. Те же, кто спал с 8 женами, в конце дня узнают, что кто-то убит, и значит неверных жен 7, и значит его жена верна.
И того, всего 7 неверных жен.
1) а) Выделяем одного человека, который будет считать (считающий), сколько людей зашло. Если заключенный (не считающий) заходит в комнату, и лампа выключена, он ее включает. Так он делает ровно один раз, и в дальнейшем лампу не трогает. Если считающий заходит в комнату, и лампа включена, он понимает, что еще один человек побывал в комнате, и выключает лампу. И того, считающий ответит, что все были, когда 99 раз выключит лампу.
б) Проблема в том, что если лампа изначально включена, то считающему надо выключить лампу на 99, а 100 раз. А если выключена, то 99. То есть мы можем ошибиться на единицу. Решение - сделать так, чтобы эта единица не играла роли. Каждый заключенный включает лампу не один раз, а два. И 198 раз увидев включенную лампу, считающий знает, что все побывали в комнате (если лампа изначально была включена, то какой-то человек включит лампа не 2 раза, а один; но тем не менее побывает).
2) Включенная лампа несет в себе какую-то информацию, а выключенная - не несет никакой. Поскольку порядок случаен, то любая последовательность эльфов встретится хотя бы раз, но неизвестно, когда. Рано или поздно у нас встретится последовательность эльфов (и встретится бесконечно много раз), когда они идут подряд (первый, второй, ... , сотый). И тогда первый включит лампу, если количество прошедших от начала часов делится на 100. Второй оставит лампу включенной, если она была включена к его приходу, и количество прошедших часов дает при делении на 100 остаток 1 (так он узнает, что перед ним был именно первый). И так далее.
3) Коротко и с понятиями из алгебры: у нас есть перестановка, в ней есть не более одного цикла длины больше 50. Если он есть, разрубаем его пополам. Перемещаемся по полученным циклам.
Подробнее: Все имена можно пронумеровать от 1 до 100, и теперь считать, что у нас в ящике лежит не имя, а соответствующее число. Заключенный заходит, открывает ящик со своим номером, и видит там некоторое число K. Если K равно его номеру, все счастливы. Иначе он открывает ящик с номером K, и снова смотрит на число. Рано или поздно он встретит ящик со своим номером. Это должно быть интуитивно понятно, но если это вкратце доказать, то эта последовательность не может зациклиться, не придя в начальный ящик (потому что тогда какой-то номер встречается более одного раза). А зациклиться она должна, потому что ящиков конечно. В итоге у нас образуетя цикл - начав с какого-то ящика цикла, мы когда-нибудь придем в него. Каждый ящик принадлежит одному циклу (причем тому же циклу принадлежат те ящики, которые мы посетим, начав с него в описанном алгоритме).
Единственная проблема - эта последовательность может быть довольно длинной - вплоть до 100. И тут как раз и приходит на помощь первый заключенный - он переставляет два ящика так, чтобы цикла длины больше 50 не было. [Пронумеруем ящики в цикле в порядке, в котором мы посетим ящики, начав с некоторого из них] То есть делает так, чтобы 50-й ящик в цикле указывал на первый элемент цикла, а последний - на 51-й в цикле. Для этого надо просто поменять 50-й и последний ящик в цикле местами.
4) Пусть количество неверных жен равно k. Основное замечание - если жена визиря неверна, то он спал с k женами, а если верна - с (k+1) (все неверные, плюс его жена).
В первый день рассуждает визирь так - неверных жен не меньше 5. Если он спал с 5 женами, то он знает, что его жена неверна, и убивает ее. Однако этого не произошло, никто не умер, значит неверных жен не меньше 6 (и теперь визири знаюи и это).
Аналогично во второй день узнаем, что неверных жен не меньше 7.
В третий день по той же логике кто-то умирает. Это значит, что кто-то спал ровно с 7 женами, и понял, что его жена неверна. Те же, кто спал с 8 женами, в конце дня узнают, что кто-то убит, и значит неверных жен 7, и значит его жена верна.
И того, всего 7 неверных жен.
Я накосячил в месте:
"каждая жена либо не изменяла своему мужу никогда, либо изменяла со всеми остальными визирями (муж об этом не знает)"
Я хотел сказать, что муж не знает, изменяла ли его жена. О том, что жены изменяют либо ни с кем, либо со всеми, визирям известно.
"каждая жена либо не изменяла своему мужу никогда, либо изменяла со всеми остальными визирями (муж об этом не знает)"
Я хотел сказать, что муж не знает, изменяла ли его жена. О том, что жены изменяют либо ни с кем, либо со всеми, визирям известно.