Задачки

Здесь собраны наиболее заинтересовавшие меня околоматематические задачки.

1. Однажды, король решил устроить испытание для своих визирей. Он объявил: "Завтра вы все соберетесь в тронном зале. Вам на головы наденут колпаки одного из семи цветов, но так, что вы не сможете видеть какой колпак на вас. Потом я буду по очереди спрашивать у каждого какой на нем колпак. Если ошибутся хотя бы двое, все будут обвинены в невежестве и казнены!" Как спастись визирям?
2. Усложнение предыдущей задачи. "...соберетесь в тронном зале и будете построены в колонну (для невоеннообязанных: это, в отличие от шеренги, носом в затылок) так что каждый будет видеть только тех, кто стоит впереди него ... Опрос начнется с последнего (с того, кто видит всех)"
3. Однажды, начальник тюрьмы собрал всех заключенных и заявил: "Чего-то хочется развлечься. Развлекаться я буду так: завтра всех рассажу по одиночным камерам и буду водить к себе в кабинет по одному (это не значит, что водить начну завтра - может и через месяц). В кабинете у меня есть две лампочки. Войдя, каждый человен должен выбрать одну из них и включить/выключить. Ровно одну. Каждый человек. В любой момент любой может сделать заявление: "В Вашем кабинете уже точно побывали все заключенные". Если он окажется прав — все свободны, если неправ - все будут казнены. Я вам гарантирую, что если эта фраза никогда не будет произнесена, то каждый человек побывает в комнате бесконечно много раз — я играю честно". Что делать заключенным?
4. Для любой последовательности функций (R → R) существует 3 функции, в виде композиции которых можно представить все функции последовательности.
5. На острове живут лжецы и правдолюбцы. Лжецы всегда говорят неправду, правдолюбцы всегда говорят правду. На остров приехал новый губернатор, и он решил с помощью переписи выяснить кто из его подданных лжец, а кто правдолюбец. Перепись происходит так. К губернатору приглашается какая-нибудь группа островитян. Все пишут сколько лжецов среди присутствующих (кто что написал известно) и расходятся. Какое минимальное количество дней придется устраивать перепись?
6. У входа в пещеру с сокровищами стоит бочка с 4 дырками по кругу в крышке. В каждой дырке можно нащупать селедку хвостом вверх или вниз. Али-Баба может просунуть руки в любые две дырки, определить положение селедок под ними и, если хочет, перевернуть одну или обе по своему усмотрению. Когда хвосты всех четырёх селедок окажутся направленными в одну сторону, дверь в пещеру откроется. Однако, после того, как Али-Баба вытаскивает руки, бочка некоторое время с дикой скоростью крутится, так что Али-Баба не может определить, куда именно он совал руки раньше. Как Али-Бабе открыть дверь?
7. Все было прекрасно в государстве, которым правил мудрый султан. Одно лишь обстоятельство беспокоило султана - жены его десяти визирей. Некоторые из них были неверны, причем, если жена визиря начинала "гулять", то изменяла ему со всеми мужиками Багдада от стражника до визиря. Непорядок. Султан приказал каждого визиря со своей женой посадить в отдельную камеру. И приказал убить своих жен, если они неверны. И сказал, также, что всех выпустят, как только неверные жены будут убиты. После первой ночи султан послал слугу посмотреть, выполнен ли его приказ. Слуга вернулся и сказал: "Не все неверные жены убиты". После второй ночи слуга вновь пошел проверить и вернулся с тем же сообщением. После третьей и четвертой ночи все повторилось. А после пятой ночи пришел слуга к султану и сказал "Все неверные жены убиты". Как определили неверных жен визири? Сами жены, конечно, ничего не рассказывали. Стены камер звуко-видео-стуко-пыле-влаго-запахонепроницаемые. Слуга заходил, молча смотрел на узников и молча выходил.
8. Фея Флорентина плавает в бассейне. Она решила проплыть вдоль бассейна туда и обратно n раз. Каждый раз, вернувшись на старт, она считает какую долю тренировки уже завершила k/n, где k — число кругов, которые она уже проплыла. Если k — составное число, то эта дробь сократима (она может сократиться и при простом k) Какое наибольшее число n имеет это свойство?
9. Некто вычислил произведение чисел от одного до 100. 1×2×3× ... ×100. Затем подсчитал сумму цифр этого числа, затем сумму цифр полученного и так далее. Наконец, получилось однозначное число. Какое? Это простая задачка. Вот другая интересная задачка: ...Наконец, получилось двузначное число. Какое?
10. Имеется 12 монет, из которых одна — фальшивая. Необходимо за 3 взвешивания на весах без делений найти её и определить легче она настоящих монет или тяжелее.
11. Заяц и черепаха бегут по отрезку [0; 1]. В каждой точке скорость Зайца была выше скорости черепахи (когда она пробегала эту точку). Могла ли черехаха финишировать раньше?
12. Сколько цифр в числе 2¹⁰⁰?