Как сдвинуть гору Фудзи? Подходы ведущих мировых компаний к поиску талантов | страница 175

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

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