Как сдвинуть гору Фудзи

Ваш нетерпеливый интервьюер некоторое время будет сидеть спокойно, пока вы начертите таблицу с номерами с первого по десятый. Сделайте это и делайте отметку в клетке, относящейся к данному шкафчику, если положение его дверцы изменилось. Например, в первом цикле все 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 = 3x3). Это очень привлекательная закономерность.

Вы понимаете, почему открытыми остались только те шкафчики, номера которых — это квадраты какого-то числа? Вы столько раз меняете положение дверцы шкафчика, сколько есть множителей в числе, соответствующем его номеру, а эти множители — парные. Например, двенадцать — это 1х12, или 2x6, или 3x4. Поскольку есть три способа разбиения этого числа на пары сомножителей, общее число сомножителей — шесть. Это значит, что положение дверцы этого шкафчика изменится шесть раз. Единственный способ, которым число может избежать четного количества сомножителей, — это такая ситуация, когда его можно представить как пару из двух идентичных сомножителей. Например, девять можно представить как 1 х 9 и также как 3x3. Это дает только три различных сомножителя (1, 3 и 9). Только те шкафчики, номер которых — это квадрат какого-то числа, будут открываться/закрываться нечетное количество раз, и только их дверцы останутся открытыми.

Такие числа в первой сотне это: 1, 4, 9, 16, 25, 36, 49, 64, 81 и 100. Ответ на задачу: открытыми будут десять шкафчиков.

У вас есть два куска бикфордова шнура…

В более простой версии этой головоломки, которую также используют в интервью, спрашивают, как отмерить тридцать минут при помощи тех же бикфордовых шнуров. Поскольку она легче, с нее и начнем.

Возможностей немного: если вы подожжете оба шнура, вы не узнаете, сколько прошло времени, пока огонь не добежит до конца, а это будет шестьдесят минут. Никакого прока.

Обратите внимание на то, что вы можете найти середину длины каждого из шнуров без линейки, просто сложив их пополам. Но если вы подожжете любой шнур в его середине, вы также ничего не узнаете, потому что он горит неравномерно, следовательно, огонь доберется до его концов не одновременно. Хотя сумма времени, за которое сгорают обе половины, — шестьдесят минут, вам это никак не поможет. Если взять предельный случай, то может оказаться, что правая половина шнура горит сверхбыстро — всего одну минуту, а левая, напротив, сверхмедленно — целых пятьдесят девять минут. Это не поможет вам узнать, когда прошло тридцать или сорок пять минут.

Исчерпывает ли это все возможности? Нет. Умная идея — положить два шнура крест-накрест, в форме буквы X. Положите их так, чтобы они пересекались в середине длины каждого из шнуров, прикасаясь друг к другу. Тогда, если вы подожжете один из концов буквы X, огонь доберется до середины, а дальше пойдет сразу в трех направлениях. Все, чего мы добьемся таким способом — второй шнур начнет гореть с середины своей длины (но мы уже знаем, что это нам ничего не дает), и мы не будем знать, сколько времени пройдет (то есть за какое время огонь доберется до пересечения). Что в лоб, что по лбу!

Исчерпаны ли все возможности? Нет: вы можете поджечь бикфордов шнур сразу с обоих концов.

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

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