Логические загадки [ Которые любят задавать на собеседованиях ]

Предлагаю выкладывать задачки и загадки, которые вам встречались, и имеют вполне логическое и нетривиальное решение...

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

Начну, добавив от себя несколько загадок....

1)Условие:
Пролив, лодка
в лодку помещается 2 бога
1 бог - быстрый, переправляется за 1 час
2 бог - ловкий, за 2 часа
3 бог - толстый, за 5 часов
4 бог - неуклюжий, за 10 часов
лодка идет по времени самого медленного бога (т.е. если посадить 1 и 4 - время в пути 10 часов)
всем надо переправиться за 17 часов

2)Условие:
Есть 8 монет и весы (с чашечками, которые показывают либо равенство, либо перевес). Среди монет есть одна фальшивая, причем неизвестно, фальшивка тяжелее или легче настоящих. Необходимо за 3 взвешивания определить фальшивую. (реально задачи имеет решение и при 13 монетах, но на собеседованиях такое не спрашивают )

3)Даны два битфордовых шнура. Длина их может быть разной. Горение каждого из шнуров - ровно 1 час. Горение неравномерно, т.е. например половина может сгореть за пять минут, а другая за 55 минут.
Задача: Засечь время в 45 минут с помощью этих шнуров.

Сообщение отредактировал(а) Виталий - 23.03.2005 - 22:21

Первая очень простая, вторую решать лень - сколько их прорешал за жизнь, а вот третья понравилась - забавная и нетривиальная. Решение очень красивое!

Задача с собеседования: чем туман отличается от пара?

Вот еще задачка:
4)Вы стоите на первом этаже небоскрёба с 100 этажами. Вы имеете два хрустальных шара, и Вам говорят, что эти хрустальные шары разрушатся, если Вы бросите их из окна с одного из этажей. Выбрасывание шара из окна рассчитывает как попытка, и Вы не можете заменить разрушенные шары. Ваша задача состоит в том, чтобы узнать самый низкий этаж, с которого Вы можете выбросить хрустальные шары так, чтобы они были разрушены в минимальном возможном числе попыток.

Задача 1 - скучная, обычные перебор вариантов, после того, как становится понятно, что не проходит самый тревиальный.
Задача 2 - стандартная задача на взвешивание, меняешь монеты и анализируешь больше-меньше.
Задача 3 - Решение вроде видится, но хочется уточняющий вопрос, можно ли поджигать шнур не с одного конца и сохранятся ли тогда временные свойства.
Задача Waxa - решение даже близко не видно, нужны уточнения, под туманом и паром, что подразумевается: физический смысл, видимая составляющая...
Задача 4 Нужно уточнить условие правильно ли я понял, что начиная с некоторого этажа шары начинают разбиваться, а до него не разбиваются. Пока видно 2 стратегии кидания шаров и выигрышность зависит от того, где будет находится эта граница (если есть)

Можно! Сохраняются!

Правильно! Нужно найти этот этаж за минимально возможное число попыток!

5)Вы на острове, на котором два города - лжецов и праведников. Лжецы всегда лгут, праведники наоборот. Города друг для друга открыты и население ходит друг к другу в гости.
Каким одним вопросом вы можете узнать, в каком вы сейчас городе?
ПРИМЕЧАНИЕ: И ЛЖЕЦЫ И ПРАВЕДНИКИ НА ЭТОТ ВОПРОС ОТВЕЧАЮТ - "ДА" ИЛИ "НЕТ". И ОТВЕЧАЮТ В ТОМ СЛУЧАЕ ЕСЛИ ЗНАЮТ ОТВЕТ.

Сообщение отредактировал(а) Виталий - 18.03.2005 - 17:55

Решение первое. Солнечное.

Для решения этой задачи в солнечный день поджигаем первый шнур, а второй подвешиваем вертикально. Отмечаем тень шнура на земле. Когда первый шнур догорит, отмечам новое положение тени второго шнура. Находим биссектриссу полученного угла, и делим угол между биссектриссой и одним из лучей пополам. Таким образом получаем 3/4 угла. Отмеряем этом угол от последнего луча и смотрим, когда тень достигнет этой отметки - это будет 45 минут.

Решение второе. Кровавое.

Поджигаем 1-й шнур и засекаем свой пульс. Когда первый шнур догорит, полученное число ударов сердца умножаем на 3/4. Теперь можно отмерить 45 минут с помощью подсчета ударов сердца. 2-й шнур понадобится для того, чтобы во время этой процедуры отгонять комаров и мух.

Решение третье. Коммерческое.

Идем на базар и продаем оба шнура. Покупаем часы...

Решение четвертое. Террористическое.

Идем к ближайшей воинской части и поджигаем оба шнура одновременно. Засекаем время появления солдат (можно с помощью пульса). Результат умножаем на 60.

Решение пятое. Статистическое.

Нарезаем оба шнура на 100 равных частей. Поджигаем 75 из них по очереди.
Повторяем процедуру. Время - усредняем.

Решение шестое. Домостроевское.

Сплетаем из обоих шнуров кнут. Зовем кого-нибудь провинившегося из домочадцев и вешаем ему на грудь табличку "время 45 минут". Засекаем его.

Решил задачу 2 и 5. Решение послано Виталию. 5 - ну очень просто и красиво!

Берем 1-й хрустальный шар и смотрим в него, заглядывая в будущее, в котором мы каждый раз поднимаемся на следующий этаж и сбрасываем 2-й шар. Находим в будущем тот момент, когда 2-й шар разбивается. Теперь идем на этот этаж и с первой попытки разбиваем 1-й шар.

И такое задают на собеседовании? И сколько времени дают на это?
1. Знал решение раньше
2. Задача с монетами уже была на форуме и даже с решением.
3. Про шнур решил с подсказки про поджигание с обоих концов
4. Я так понимаю что нужно найти минимальный этаж за минимальное количество попыток при этом разбив не более 2 шаров? Или именно 2 шара нужно разбить с минимальной высоты
5. Спросить очевидное для всех

6. Пар вроде как прозрачен

Но чесно говоря давать задание про монеты на собеседовании это изврат

А если не из окна, а с пожарной лестницы? Если выбрасывание с пожарной лестницы не считается за попытку, то мы поднимаемся по пожарной лестнице, сбрасывая 1-й шар на каждом этаже, пока он не разобьется. Замечаем этот, этаж, заходим в дом, поднимаемся на этот этаж и с первой попытки разбиваем 2-й шар. Так?

Про шнур-то подскажите кто-нибудь...
И про Богов что-то не получается никак...

A фиг его знает хитрая задачка какая то Можно сбрасывать через два если разобъётся то спускаемся на два этажа ниже и сбрасываем последний. Разбился это тот этаж и есть. Если нет то поднимаемся на один выше и пробуем.

И так есть подсказка про поджигание с двух концов. Ну уж дальше то совсем просто

Пробуй ещё. В крайнем случае перебором решай

Узнать самый низкий этаж.
Видимо, это первый. Ниже нет. И бросать ничего не надо.

Впрочем, надо. Чтобы вообще понять - разобьется или нет.

решил первую! Красота-а-а...
Блин, третья - ну никак...

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

Кстати про бикфордовы шнурки есть ещё 2 решения задачи.
1. Позволяет обойтись одним шнурком!!!
2. Позволяет оставить от шнурка именно 45 минут

Правда нсколько страдает точность в первом случае. Зато второй точный если считать время на поджигание =0

Кстати тута этого добра много http://www.arbuz.uz/w_time.html

4) Уточнение! Найти наименьший этаж, с которого шары бьются, причем у нас есть только 2 шара. Соответственно за наименьшее число попыток!

Первые 3 задавали на собеседованиях мне лично!!! Причем говорили, если знаю ответ, то сразу признавайся!
4 и 5 Сказали знакомые!!!

Ну так про шары я же сказал кидать через 2 этажа до тех пор пока не разобъётся (1,4,7...) далее после того когда разбился кидаем с N-2 этажа если разбился это он и есть если не разбился кидаем с N-1 если разбился это он и есть если не разбился то это N.
Так?

А мое предложение скидывать с пожарной лестницы?
Или глядеть через один из шаров в будущее ?

Про шарики. Кинуть с первого. С 3-его. 7-го. 15-го... Пока не разобьется. То есть, шаг увеличивается вдвое с каждым броском.
Второй кидать последовательно с предыдущего покиданного, с которого не разбивался.
Эт ничего, что задачка решена в общем виде?

что-то я не понял, дальше будет 30 60 100? А если на 60 не разобется. а на 100 разобется? Итого 40 + 6 попыток?
Можно кидать например через каждые 10... 20 30...
итого 19 попыток, но можно еще лучше....

Сообщение отредактировал(а) Виталий - 22.03.2005 - 17:46

Беседуют два математика.
Первый (П) спрашивает Второго, есть ли у него дети.
Второй (В) говорит, - Конечно. У меня трое детей.
П - А сколько им лет?
В - Сумма их возрастов равна числу окон в этом доме, а произведение – 36.
Первый математик посмотрел на дом, подумал и говорит: "Этой информации недостаточно".
В - Да, конечно, я совсем забыл: младший сын-рыжий.
Сколько лет детям (каждому) второго математика?

Ответ ниже (надо выделить):

Сообщение отредактировал(а) Пересвет - 23.03.2005 - 10:07

Почти загадка:

Глупый пингвин робко прячет тело жирное в утесах.
Глупый пингвин... Ну допустим... Прячет тело...??? Это ново,
Это даже детективно.
Чьё же тело прячет пингвин глупый жирное в утесах?
Может он кого-то шлепнул или ревностью замучил?
Мне чего то не понятно. Пингвин этот - он же глупый, он же робкий.
Или только прячет робко??....
Он вообще-то прячет тело, а не "робко", но в утесах.
ТЕЛО жирное - в утесах будет спрятано надежно!!!!
Интересно все же чьё же тело пингвин прячет в камни?
Он наверно не специально, А! - у него такое хобби. Он кого нибудь замучит,
а потом в утес запрячет.
Сколько ж тел лежит в утесах, робко спрятанных пингвином???...
Этот пингвин он чего же? Глупый прямо от природы?
Или он в утесах спятил - постоянно тело пряча???
Хорошо - с пингвином ясно, но не ясно: Чьё же тело?
Робко пингвин прячет в скалах.?
Это в принципе не важно, потому что "глупый пингвин"
сам по-моему не знает, чьё он тело робко прячет!
Просто прячет... Он же глупый. !
!!! П И Н Г В И Н З А Н Я Т !!!!!
Он же прячет, хоть и робко, но в утесах...
И вообще не наше дело лезть с вопросами к пингвину!!!!

Примерно так.
Я только идею кинул. Что шаг не обязан быть постоянным.
Кстати, шаг, равный корню из числа этажей - вполне может быть оптимальным. Для двух шаров.

Сообщение отредактировал(а) Афа - 23.03.2005 - 20:10

Буду публиковать решения скрытым текстом! Спасибо Пересвету за идею!
Новая задачка, но боюсь что не с собеседования!

6)Стоит человек, смотрит на портрет.
Его спрашиваю, кто изображен на портрете?
Он отвечает: Я рос один, но все же отец того, кто изображен на портрете - сын моего отца.
Кто изображен на портрете?

7)В темной комнате стоит шкаф, в ящике которого лежат 24 красных и 24 синих носка. Сколько минимально носков следует взять из ящика, чтобы из них заведомо можно было составить по крайней мере одну пару носков одного цвета?

Про шары ответ 14?

Горение неравномерно, т.е. например половина может сгореть за пять минут, а другая за 55 минут. Т.е. поджигание в середине нам ничего не дает!

Теперь у других есть подсказка, к чему стремится!!

Понятно, что шаг первого шара не должен быть постоянным, поскольку функция вида 100/n+n-1 дает минимум при шаге (n) = 10 и при числе попыток равном 19.
Но почему Вы решили, что шаг (зависящий от номера попытки) должен быть нелинейным???

Горение неравномерно, т.е. например половина может сгореть за пять минут, а другая за 55 минут. Т.е. поджигание в середине нам ничего не дает!

Он прав. Его вариант полностью работоспособен. Ты зря сопротивляешься. Именно его я и имел в виду когда можно оставить кусок на 45 минут. Тот шнурок который горит с 4 концов сгорит в четверо быстрее. Ты прочти внимательно там поджигается середина того который остался как только сгорит один кусок.

Согласен, что при равномерной пропитке шнура на каком-нибудь малом участке такое возможно , но если шнур пропитан так, что при сложении пополам, кусок слева всегда горит быстрее куска справа? Это реально при линейной пропитке шнура! Т.е. потребуется бесконечное число поджиганий, т.к. шнур слева горит быстрее и всегда будет оставаться кусочек справа, который придется бесконечно поджигать

Вот задачи с собеседования (источник - анекдот.ру)

1. Как положить слона в холодитьник?

2. Как положить бегемота в холодильник?

3. Лев собрал всех зверей на совет. Один из них не явился. Кто это?

4. Река Амазонка кишит крокодилами. У вас нет ни каноэ, ни каких других транспортных средств. Мостов тоже поблизости нет. Как перебраться на другой берег?

А почему тогда река Амазонка кишит крокодилами, если они у льва на совете? Река не должна в это время кишеть крокодилами....

Обычно кишит. Согласен, надо было уточнить.

Можно заменить на: река Амазонка кишела крокодилами....

Смысл получается двоякий и все - корректно.

Это предположение. Строго говоря - неправильное. Скорее всего, шаг с увеличением номера пробы должен уменьшаться.
Например, так.
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100.
Тогда за 14 ходов получим ответ.

Что-то я не догоняю: если 1-й шар разбился сразу на 14-м этаже, что тогда?
У тебя есть 13 этажей и всего 1 шар...

Именно. И есть 13 попыток. Последовательно пробуя этажи. С первого.

PS. Линейное уменьшение шага из лени искать более красивую функцию. И так нормально сходится.

А... все, теперь понял! И все же, зная прочность хрусталя, размеры шара и скорость начального броска можно решить задачу с ОДНОЙ попытки.

Вернее даже БЕЗ попыток.

Сообщение отредактировал(а) Governor - 25.03.2005 - 13:23

Ага именно так. Но про время на поджигание ни слова не сказано так что можно.

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