Йо_Бё обратиться по имени
Воскресенье, 15 Января 2012 г. 23:21 (ссылка)
Поехали парни (содрал в сообществе, ответов не знаю)
1.
Имеется 8 с виду одинаковых монет. Одна из них фальшивая и известно, что она легче настоящей. Как с помощью всего лишь двух взвешиваний найти фальшивую монету? В Вашем распоряжении только лабораторные весы, которые показывают только больше-меньше.
2.
В компании, состоящей из двух мужчин и двух женщин, каждый человек болен своей венерической болезнью (пофантазируйте на тему какими именно). Эти мужчины и женщины принимают решение заняться сексом, каждый мужчина с каждой женщиной по очереди. На всю компанию у них есть два презерватива.
Вопрос: как партнёрам обезопасить все четыре сексуальных акта? Сексом без презерватива партнёры заниматься не могут, т.к. болезни у всех разные и заразные.
Это,конечно, не из собеседований, но подобные задачки ,только с более приличным содержанием, там тоже бывают.
3.
Задача о преступниках
Суд приговорил десять преступников к наказанию.
1. Каждый из них будет сидеть в отдельной камере, не имея возможности общаться с остальными заключенными.
2. Ежедневно утром, начиная с первого дня заключения, одного из них будут отводить в карцер, а вечером того же дня возвращать назад в камеру.
3. В карцере есть лампочка, которую находящийся в карцере заключенный сможет включать и выключать. Надзиратели должны тщательно следить за тем, чтобы сидящие в карцере не оставляли друг другу никаких посланий. При этом надзиратели сами не будут ни включать, ни выключать лампочку.
4. Заключение закончится в тот день, когда кто-то из осужденных сообщит надзирателю о том, что каждый из десяти преступников побывал в карцере хотя бы один раз. Если это окажется правдой, то все десять преступников будут отпущены на свободу, в противном случае — их казнят.
5. До начала заключения преступникам разрешено собраться вместе и разработать план действий, позволяющий им покинуть место лишения свободы в соответствии с правилами задачи.
6. Заключенным не известен порядок, в котором будут они сидеть в карцере, но им сообщили, что согласно плану надзирателей:
каждый заключенный побывает в карцере;
после выхода из него заключенный вновь попадает туда через конечное число дней.
7. Предполагается, что ни один из преступников не может ни освободиться, ни умереть иначе как в результате того, что кто-то из заключенных сообщит надзирателю о факте пребывания в карцере каждого преступника.
Необходимо предложить такой алгоритм поведения преступников, который позволит им выбраться из тюрьмы за конечное время без риска быть казненными.
Эта задача довольна известная, мне её в Яндексе на собеседовании предлагали, я не смог решить. Ну и собеседование не прошёл.
4.
Пожалуй, последняя на сегодня, а то м так многабукф.
Эта задачка часто даётся при собеседованиях в разные ИТ-компании. Она довольно несложная, в общем-то.
Посадил людоед сотню гномиков в тюрьму, каждого пронумеровал и поставил условия:
— Завтра каждый из вас по одному будет заходить в специальную камеру, где будет лежать сотня пронумерованных конвертов. В каждом конверте — какой-то номер (просто все цифры от одного до ста, разложенные по конвертам случайным образом). Каждый из вас будет иметь право открыть ровно 50 конвертов, чтобы найти свой номер. Если все вы найдете свои номера — освобожу. Если хотя бы один ошибется — съем всех.
Гномики после обсуждения общей стратегии больше никак общаться не смогут и вообще друг друга не увидят. Конверты после каждого гномика закрываются обратно, так что входящий в камеру гномик не имеет никакой информации о том, что нашли или не нашли другие гномики и какие конверты они открывали.
Гномикам надо придумать стратегию как искать свой номер, чтобы найти. Если открыть просто наугад 50 из 100 конвертов, то вероятность найти свой номер — 1/2. Учитывая, что гномиков сто штук, то их общие шансы при случайной стратегии оказываются равны 1/2100, что совсем уж мало. Надо поэтому придумать какую-то альтернативную стратегию.