Это одно из тех абсолютно не соответствующих здравому смыслу решений, которые убеждают многих людей в абсурдности логических головоломок. Если бы пираты формировали коалиции на основе дружеских отношений (что и происходит в телешоу «Последний герой»), все эти рассуждения оказались бы бессмысленными. Но даже если не принимать в расчет возможные дружеские коалиции, решение все равно выглядит сомнительным. Вы можете поверить, что пираты (или наркоторговцы, мафиози, какие-нибудь другие бесчестные эгоисты) спокойно проголосуют за схему, которая вам дает девяносто девять монет, а они получают или одну монетку, или вообще ничего? Да остальные четверо сначала вас застрелят, а уже потом станут заниматься дедукцией.
Эту головоломку использует компания Fog Creek Software из Нью-Йорка. По этому поводу в одной из интернет-конференций появилось сообщение: «Готов поклясться, что генеральный директор Fog Creek загребает 98 процентов прибылей этой компании. Реальная причина, по которой в ней задают этот вопрос, – желание найти смиренных овечек, готовых с этим мириться, если получат какое-нибудь математическое объяснение»».
? В одной из школ есть такой ритуал в последний день занятий…
Первая вещь, которую необходимо понять, – эта головоломка просто обязана быть проще, чем она кажется на первый взгляд. Ваш интервьюер слишком занят, чтобы сидеть и ждать, пока вы пройдете все сто шагов. Должен быть какой-то трюк, который позволит упростить решение, и ответ должен быть относительно простым. Или все 100 шкафчиков должны остаться открытыми, или ни один из них, или должна отыскаться какая-то закономерность, которая позволит легко решить, сколько будет открытых шкафчиков.
Ваш нетерпеливый интервьюер некоторое время будет сидеть спокойно, пока вы начертите таблицу с номерами с первого по десятый. Сделайте это и делайте отметку в клетке, относящейся к данному шкафчику, если положение его дверцы изменилось. Например, в первом цикле все 100 шкафчиков будут открыты. И вы поставите в таблице соответствующие отметки.
Во втором цикле вы поставите отметки в клетках с четными номерами 2, 4, 6, 8 и 10. Продолжите это до десятого цикла (если бы вы продолжили это делать до 20, 30, 40 и т. д. – у вас получилась бы полная таблица). После десяти циклов ваша таблица будет выглядеть так:
И следующие циклы никак не повлияют на первые десять шкафчиков – ведь во время одиннадцатого цикла будет меняться положение дверец только шкафчиков номер 11, 22, 33… Таким образом, составленная вами таблица для первых десяти ящиков окончательная. Поскольку в начале шкафчики были закрыты, то все шкафчики, положение дверец которых изменилось нечетное количество раз, останутся открытыми, а если положение менялось четное количество раз, шкафчики будет закрытыми.
Это означает, что после 100 циклов шкафчики 1, 4 и 9 останутся открытыми, а все остальные закрытыми. 1, 4 и 9 – это точные квадраты, то есть числа, умноженные сами на себя (1 = 1 × 1; 4 = 2 × 2; 9 = 3 × 3). Это очень привлекательная закономерность.
Вы понимаете, почему открытыми остались только те шкафчики, номера которых – это квадраты какого-то числа? Вы столько раз меняете положение дверцы шкафчика, сколько есть множителей в числе, соответствующем его номеру, а эти множители – парные. Например, двенадцать – это 1 × 12, или 2 × 6, или 3 × 4. Поскольку есть три способа разбиения этого числа на пары сомножителей, общее число сомножителей – шесть. Это значит, что положение дверцы этого шкафчика изменится шесть раз. Единственный способ, которым число может избежать четного количества сомножителей, – это такая ситуация, когда его можно представить как пару из двух идентичных сомножителей. Например, девять можно представить как 1 × 9 и также как 3 × 3. Это дает только три различных сомножителя (1, 3 и 9). Только те шкафчики, номер которых – это квадрат какого-то числа, будут открываться/закрываться нечетное количество раз, и только их дверцы останутся открытыми.
Такие числа в первой сотне это: 1, 4, 9, 16, 25, 36, 49, 64, 81 и 100. Ответ на задачу: открытыми будут десять шкафчиков.
? У вас есть два куска бикфордова шнура…
В более простой версии этой головоломки, которую также используют в интервью, спрашивают, как отмерить тридцать минут при помощи тех же бикфордовых шнуров. Поскольку она легче, с нее и начнем.
Возможностей немного: если вы подожжете оба шнура, вы не узнаете, сколько прошло времени, пока огонь не добежит до конца, а это будет шестьдесят минут. Никакого прока.
Обратите внимание на то, что вы можете найти середину длины каждого из шнуров без линейки, просто сложив их пополам. Но если вы подожжете любой шнур в его середине, вы также ничего не узнаете, потому что он горит неравномерно, следовательно, огонь доберется до его концов не одновременно. Хотя сумма времени, за которое сгорают обе половины, – шестьдесят минут, вам это никак не поможет. Если взять предельный случай, то может оказаться, что правая половина шнура горит сверхбыстро – всего одну минуту, а левая, напротив, сверхмедленно – целых пятьдесят девять минут. Это не поможет вам узнать, когда прошло тридцать или сорок пять минут.
Исчерпывает ли это все возможности? Нет. Умная идея – положить два шнура крест-накрест, в форме буквы Х. Положите их так, чтобы они пересекались в середине длины каждого из шнуров, прикасаясь друг к другу. Тогда, если вы подожжете один из концов буквы Х, огонь доберется до середины, а дальше пойдет сразу в трех направлениях. Все, чего мы добьемся таким способом – второй шнур начнет гореть с середины своей длины (но мы уже знаем, что это нам ничего не дает), и мы не будем знать, сколько времени пройдет (то есть за какое время огонь доберется до пересечения). Что в лоб, что по лбу!
Исчерпаны ли все возможности? Нет: вы можете поджечь бикфордов шнур сразу с обоих концов.
Скорость, с которой движется огонь, сама по себе для нас не важна, и огоньки, двигающиеся с двух концов шнура навстречу друг другу, совсем не обязательно встретятся в середине, но где-то они обязательно встретятся. Когда они встретятся, это будет означать, что каждый из них горел время, равное половине от шестидесяти минут, то есть тридцать минут.
Отлично! Это решение для более легкой версии задачи, которое также позволит нам решить и 45-минутную версию. Итак, поджигая один из шнуров с обоих концов, мы можем отмерить тридцать минут. Если бы нам удалось при помощи второго отрезка шнура отмерить еще пятнадцать минут, мы бы решили головоломку.
Мы уже знаем, что можем уменьшить вдвое время горения любого отрезка шнура, поджигая его одновременно с двух концов. Если бы у нас был отрезок, сгорающий за тридцать минут, мы могли бы поджечь его с обоих концов в тот самый момент, когда догорел бы первый шестидесятиминутный отрезок, подожженный с двух концов. Это как раз и дало бы нам недостающие пятнадцать минут, и мы бы получили искомые сорок пять минут.
