Занимательные задачки

Есть такая занимательная штука — этические уравнения. Она очень занимательна, когда не касается лично тебя и не приходится их решать в реальности. Приведу известный пример из истории:
Во время второй мировой войны у немцев была шифровальная машина «энигма», которая во всем мире считалась неподдающейся для взлома. Англичане смогли расшифровать сообщение о готовящейся массированной бомбардировке одного английского города. Массовая эвакуация населения подсказала бы немецким шпионам, что код раскрыт и в далнейшем союзные войска остались бы без ценной развединформации. Это могло бы изменить расклад сил и возможно изменило бы результат войны. Английский премьер-министр принимает решение не эвакуировать людей, в результате чего погибли десятки тысяч его соотечественников. Именно такое этическое уравнение и пришлось решать одному человеку. Главный показатель этического уравнения — человек будет чувствовать свою вину при любом раскладе.

Сейчас некоторые интернет-провайдеры США собираются внедрить тарификацию по трафику на тарифных планах широкополосного доступа. В частности, провайдер Time Warner Cable внедряет тарифный план за $15 в месяц с лимитом 1 ГБ и дополнительной оплатой по $2 за каждый гигабайт сверх положенного. Журнал Wired решил наглядно показать, насколько это маленький лимит. Они объявили конкурс среди своих читателей на наиболее быстрый способ потратить месячный лимит трафика, то есть один гигабайт.

Один гигабайт — это просто смехотворный лимит для широкополосного интернета. На самом деле потратить его можно буквально за полдня даже на самом низкоскоростном тарифе Time Warner со скоростью 786 Kbps.

Читатели Wired уже высказали несчастным пользователям планов с тарификацией несколько предложений, в том числе организовать у себя на ПК раздачу торрентов, сервер Tor, запустить Windows Update, поднять веб-сервер, снять пароль с домашней точки доступа Wi-Fi, или сделать всё это одновременно. Страшно представить, какой месячный счёт придёт смельчакам, решившим проверить эти вредные советы на практике.

Ещё одна задача про узников. На этот раз не такая теоретическая.

Есть 30 узников, пронумерованных от 1 до 30. Каждый знает все номера, в том числе свой. У них есть время на обсуждение алгоритма. Дальше их по одному заводят в комнату, где есть 30 пронумерованных коробок. В каждой коробке по одному ключу с номером какого-то узника (номер коробки и номер ключа в ней могут быть различными). Ключи по коробкам распределены совершенно случайно (т.е. все перестановки ключей в коробках равновероятны). Каждый узник по очереди открывает 15 коробок и смотрит, какие в них ключи, причём, открывая очередную коробку, он может сначала посмотреть, какой в ней ключ, а потом решить, какую открывать следующей. Если в одной из этих 15 коробок оказался ключ с его номером, то его отпускают, если нет — расстреливают. Комната и все коробки в ней после этого приводятся в изначальное состояние, т.е. следующие узники не получают никакой информации о том, что было с предыдущим узником.
Придумайте алгоритм, чтобы с вероятностью не меньше 30% выжили все узники.

PS Можно использовать калькулятор.

UPD Решение в комментах.

Рассказали мне недавно супер-задачу, потребовалось несколько дней чтобы решить.

Есть бесконечно много узников (счётное число), пронумерованных натуральными числами. Каждый узник знает все номера, в том числе свой. Узники умеют бесконечно быстро думать, и у них бесконечно много памяти. Сначала у них есть время на обсуждение алгоритма.
Их выстраивают по порядку, так что первый смотрит в спину второго, второй в спину третьего и т.д. На них одновременно надевают колпаки двух цветов. Каждый узник видит, какие колпаки надеты на узниках с большими номерами (первый видит все колпаки, кроме своего, второй — все, кроме своего и первого и т.д.). Никакой информацией они уже не обмениваются. Дальше каждый из них должен одновременно со всеми сказать, какой на нём колпак. Кто не угадает — того расстреливают. Как сделать так, чтобы лишь конечное число узников расстреляли?

PS Не хватает кармы, чтобы переместить в блог «Занимательные задачки». Спасибо за карму, перенёс в блог «Занимательные задачки».

UPD Решение в комментах.

В обсуждении спонтанно родилась задачка, показалась интересной:

Огромный сервис выполняет запросы, результаты которых кешируются. Выполнение незакешированного запроса в десятки тысяч раз дольше, чем закешированного. Однажды что-то слегка испортилось, и процент попаданий в этот кеш упал с 99% до 98%.

Раньше сервис работал на 100 абсолютно одинаковых серверах. Сколько серверов потребуется теперь?

PS: задача не совсем строго сформулирована, но это не должно сильно мешать её решить :)

Старая боянистая задача про 12 монет и 3 взвешивания (только на Хабре она решалась здесь и здесь) может быть решена так же для 13-ти монет, при условии, что определять тяжелее или легче эта фальшивая монета — не надо (здесь подробно описано это решение, на основании троичной системы).

Но подобной модификации я еще не встречал. Задача решается для 14 монет, если одной (15-той) вы можее пользоваться во взвешиваниях как точно «настоящей».

Условие задачи с модификацией:

Есть 14 монет. Одна из них фальшивая, но неизвестно, тяжелее она или легче остальных. Также есть точные ювелирные весы с двумя чашечками, которые могут быть либо уравновешены, либо нет, в зависимости от того, какие монеты вы положите на каждую из сторон.
Необходимо использовать три, и только три взвешивания. За эти три взвешивания нужно определить, какая из 14-ти монет является фальшивой.

Тяжелее или легче монета — определять не надо.
В помощь Вам дана «правильная» 15-тая монета, которую Вы можете испльзовать во взвешиваниях зная, что она точно «правильная».

Лет десять назад, когда интернет был диковинкой, я мошенничал тем, что участвовал в различных теле- и радиовикторинах, используя свой доступ в сеть. То есть не знал ответы на вопросы, а просто очень быстро умел находить их в интернете. Что позволило мне несколько раз выиграть билеты в кино, пару книжек и компакт-дисков, и разок появиться на местном телевидении. Все эти навыки пригодились в жизни — я и сейчас по просьбам друзей нахожу в Сети требуемое. «Если оно есть в интернете, говорю я им, то я это вам найду». Впрочем, не сочтите это за хвастовство. Уверен, что многие умеют быстро находить любую требуемую информацию.
И вот в связи с этим мне подумалось как-то: а почему бы не сделать хитроумных задачек в стиле, скажем, «Своей игры» или «Что? Где? Когда?», но специально для тех, кто любит и умеет искать в интернете.
И я начал сочинять такие задачки. Кому-то из моих знакомых они не понравились вовсе, кто-то почесал репу и остановился на середине пути. А кому-то понравилось, и они потратили несколько минут (или часов) своего драгоценного времени на разгадывание этих головоломок.
Если у вас есть свободное время, есть навыки поиска информации и вы хотите попробовать свои силы — попробуйте разгадать несколько таких задачек.
Всё, что для этого нужно — базовые знания, Google, Wikipedia и другие ваши любимые источники информации.
Задачки можно разгадывать сразу с хвоста, опустив начало. Я бы рекомендовал всё же разгадывать последовательно, от начала до конца. Тогда разгадывание может оказаться более интересным. Потому как здесь цель — не скорость и не точность лишь финального слова, а раскрытие всей цепочки целиком.

Изобретатель знаменитой логической игрушки в виде кубика венгерский скульптор и профессор архитектуры Эрно Рубик презентует свою новую логическую игрушку, сделанную в виде шара.

Решил развеять последний поток задач на искусство ассемблера и вернуться к логике и наблюдательности.

Бабушка несла яйца. Какой-то барин ей их разбил и спросил, сколько было яиц, чтобы заплатить. Бабушка сказала, что не знает, но она пыталсь разделить их на 2,3,4,5,6,7 и 8 кучек, но всегда оставалось одно яйцо! Внимание, вопрос: зачем она пыталась их разделить? (решать устно, без всяких экселей, маткадов, калькуляторов).

Ответ должен быть аргументированным и заскринен белым (as usual).

UPD: Верный ответ — первым же постом. Одно яйцо математически конечно тоже верный результат, но физически — нет, ну не бывает же пустых кучек, в самом деле :)

Задача #2 «Позитивные автоматы»

Для тех, кто не хочет читать:

Найти значение выражения: |x — |y||
X, Y — любые целые ( и отрицательные тоже )

Ограничение: нельзя пользоваться sub, dec… и любое другое вычитание, нельзя пользоваться регистрами флагов и бинарными операциями. (в частности сдвигами)
Все что у вас есть: je, cmp (нельзя смотреть флаги), jmp, inc, mov. (я же сказал, немного)

Для того, что бы лучше разобраться в задаче:

Есть такая замечательная штуковина, называется:
Машина с неограниченными регистрами (МНР)
Итак, зачем это? Лично для меня — расшевелить мозги.

Теперь попробуем в деле!

Задача #1 «О Квадрантах»

Итак сразу к делу: как-то когда я занимался ассемблером у меня в лабораторной работе попалась очень простенькая задача, ее текст: Найти квадрант окружности ( номер ее четверти) по координатам точки, которая вводится с клавиатуры. Все было бы ничего…

Буквально несколько минут назад оставалось 1234,56789 часов до наступления судьбоносной даты — 1234567890 секунд по юнихтайму :)

Конкурс завершен, ниже оригинальное содержание, под ним — ответы

Добрый вечер харбаюзеры и хабраюзерши. Особый привет гостям, читающим хабр но не имеющим на нем регистрации.
Почему? Каждый день на хабре регистрируется 5-10 новых людей, я уверен что желающих намного больше, но нло не так щедро на инвайты, как многим бы хотелось.

Сегодня, у вас есть шанс получить себе инвайт на хабр! Но, все будет не так просто.

Накопал на баше задачку, и решил ее с небольшими изменениями предложить вам:

Штирлиц должен отправить важное сообщение по в Центр.
Сообщение состоит из 4 бит информации, а общий размер передачи в центр составляет 7 бит.
Противник не дремлет, и при отправке возможны диверсии.
Любой бит информации (но только один) может быть испорчен.
Как должен Штирлиц закодировать информацию, чтобы в Центре гарантированно смогли прочитать сообщение при возможном искажении любого одного бита?

upd: И подскажите возможно ли это в принципе.

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

Лжюзер goblin_gaga у себя в жж запостил задачку.
Мне она понравилась, поэтому предлагаю к решению хабрасообществу под конец рабочего дня. Благо не сложная, но вполне интересная. Подход в подобных задачах обычно един, но тут подкупает закрученная формулировка. Признаюсь, я сам немало времени потратил на понимание сути написанного :)

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

Вопрос: Кто вы, где и чем занимаетесь?

UPD.
источник (осторожно! правильный ответ инсайд)

UPD Ворнинг, почти правильный ответ в комментах

Есть одна интересная задача, которую нам с друзьями задали на одной из посиделок — мы бились над ней почти всю ночь, и смогли придти к правильному ответу. Задача, на мой взгляд, очень интересная. Представляю ее вниманию хабрасообщества...

Самолет (реактивный или винтовой) стоит на взлётной полосе с подвижным покрытием (типа транспортёра). Покрытие может двигаться против направления взлёта самолёта, то есть ему навстречу. Оно имеет систему управления, которая отслеживает и подстраивает скорость движения полотна таким образом, чтобы скорость вращения колёс самолёта была равна скорости движения полотна.

Вопрос: сможет ли самолёт разбежаться по этому полотну и взлететь?

P.S. Если есть знающие решение — не постите ответ хотя бы пару дней — дайте другим подумать.

Задача особенно актуальная в условиях финансового кризиса и для работников налоговых органов, хотя и создана в 18 веке.
Двое, Андрей и Фёдор, обмениваются деньгами (с целью уйти от налогов). Сначала Андрей отдал часть своих денег Фёдору, потом Фёдор Андрею, затем опять Андрей Фёдору и, наконец, Фёдор отдал Андрею деньги в последний раз, и после этой передачи у каждого стало по 160 рублей. Количество передаваемых денег всякий раз было равно количеству денег у получавшего их.
Сколько денег у Андрея и Фёдора было первоначально?
PS поскольку задача сама по себе не сложная, то предполагается решение её в уме в максимально короткий срок, поскольку именно такие решения зачастую приходится принимать в условиях финансового кризиса.

Эта задача была сформулирована в 1971 году и до сих пор остается нерешенной. За доказательство утверждения P=NP или за доказательство его опровержения Математическим институтом Клэя назначена премия в 1 миллион долларов США. Если все-таки окажется, что P=NP, то это даст возможность быстро и эффективно решать множество трудноразрешимых на данный момент задач.

Так в чем же все-таки суть проблемы?

Прочёл статью Полезные билетики и вспомнил далёкий 1999 год, когда где-то в каком-то журнале отыскал, как мне показалось, довольно занятную задачку. Сразу оговорюсь, что условие схоже с вышеупомянутой статьёй, однако есть нюансы. Смысл её

Уже больше недели хожу пешком и катаюсь на общественном транспорте, проездные билеты не продают после 5-го числа, поэтому приходится каждый раз при посадке оплачивать проезд. А что чаще всего делают школьники и студенты (а часто даже взрослые люди, каждый день наблюдаю) с билетом первым делом? Проверяют его на принадлежность к так называемым «счастливым», чтобы потом положить к себе в коллекцию, а может даже «по-тихому» съесть для верности. А может просто выкинуть :)



В любом случае, это какое-никакое развлечение и повод для радости. И что-то детство в одном месте у меня заиграло, стало интересно, какова вероятность получить «счастливый» билет? Сколько всего «счастливых» билетов?

Помню, что в школе даже кто-то делал исследовательскую работу (или что-то в этом роде, не суть), мы пытались выводить формулы, рисовать графики и прочее.

Но, поскольку мощность наших компьютеров зачастую позволяет идти неоптимальным путем (с точки зрения математики), то решил не заморачиваться выводом формул.