Сегодня мы будем решать достаточно сложную задачу, которая называется 100 дверей. Всего есть 100 дверей, расположенных в один ряд. Все они изначально закрыты. Человек проходит вдоль этого ряда 100 раз, и в каждом проходе изменяет состояние некоторых дверей.
Изменение состояния означает, что если дверь была закрыта, то он ее откроет, а если она была открыта, то наоборот закроет.
Каждый раз, проходя вдоль ряда, человек выбирает двери, состояние которых он изменит, руководствуясь следующей логикой. Во время первого прохода он изменит те двери, номер которых кратен единица. Это означает, что он изменит каждую из 100 дверей. И так как все двери изначально были закрыы, то после первого прохода они станут открытыми. Во время второго прохода человек изменит состояние дверей, номер которых кратен двум. Во время третьего прохода он изменит состояние тех дверей, номер которых кратен трём, то есть двери номер 3, 6, 9, 12 и так далее.
Вопрос - сколько шкафчиков будут находиться в открытом состоянии после 100-го прохода?
Во время четвертого прохода будут изменены двери с номером кратным 4. И так человек проходит 100 раз, изменяя состояние тех дверей, номер которых кратен номеру прохода. Вопрос заключается в том, чтобы определить какие из дверей останутся открытыми после сотого прохода. И помните, что изначально все двери были закрыты. Это сложная задача, и чтобы ее решить, нам нужно тщательно проанализировать происходящее и записать наши наблюдения. Для примера, давайте выберем случайную дверь и посмотрим, что с ней будет происходить. Допустим, это будет дверь номер 50. Человек будет выбирать данную дверь в проходах номер 1, 2, 5, 10, 25 и 50. Потому что 50 делится на целых на любое из этих чисел. Иными словами, 1, 2, 5, 10, 25 и 50 это множители двери номер 50. Изначально эта дверь была закрыта. В первом проходе человек откроет эту дверь. Во втором проходе он ее закроет. Во время пятого прохода он ее снова откроет. На десятом проходе обратно закроет. Во время 25 прохода дверь будет открыта. И наконец, во время 50 прохода человек закроет эту дверь. Какой вывод мы можем сделать из увиденного? Если у номера двери имеется четное количество множителей, то после 100 проходов она будет закрыта.
В данном случае дверь номер 50 имеет 6 множителей. Это четное число и соответственно дверь в конечном счете оказалась закрыта. Если же количество множителей у номера двери нечетное, то она будет открыта после 100 проходов. Итак, нас попросили отыскать такие двери, которые после всех проходов окажутся открытыми. Таким образом, нам нужно определить, какие из дверей имеют нечетное число множителей. Один из способов этого достичь, это вручную для каждого номера выписать все множители и определить номера с их нечетным количеством. Однако, это не самый разумный способ. Умный способ проанализировать паттерны распределения множителей и сделать вывод, который приведет нас к правильному ответу. Давайте еще раз посмотрим, например, с дверью номер 50.
Множители данной двери 1, 2, 5, 10, 25, 50. Если нарисовать линию по центру, то мы увидим 3 множителя с левой стороны и 3 множителя с правой стороны. Произведение крайнего слева множителя и крайнего справа множителя равно 50, то есть равно номеру самой двери. Произведение второго слева множителя и второго справа множителя, то есть 2 и 25, также дает результат равный 50. Аналогично, произведение третьего слева и третьего справа множителей будет равно 50. Это был пример с четным количеством множителей. А теперь представим, что у некой двери нечетное количество множителей. Например, дверь номер x имеет 5 множителей m1, m2, m3, m4 и m5. Проведем линию по центру. m1 умноженное на m5 даст нам результат равный номеру двери, то есть x. m2 умноженное на m4 даст нам тот же результат.
И множитель m3 остался в одиночестве посередине. Но мы знаем, что m3 тоже является множителем x, а значит он точно может быть умножен на какой-либо из представленных множителей, чтобы получилось значение равное x. Однако, у каждого из других множителей уже есть пара и они не подходят. Таким образом, единственный подходящий множитель это и есть сам центральный множитель, то есть m3 умноженное на m3 даст нам результат равный номеру двери, то есть x. А что получается, когда число умножается на само себя? Правильно, получается идеальный квадрат.
И мы можем сделать вывод, что все номера дверей, которые являются идеальными квадратами, имеют нечетное число множителей. Давайте быстро проверим некоторые из них. Число 36 это идеальный квадрат и у него есть 9 множителей, центральный множитель равен 6 и умножение 6 на 6 даст нам результат равный 36. Аналогично число 16 – это идеальный квадрат и у него 5 множителей, центральный множитель равен 4 и 4 на 4 дает нам 16. Итак, это двери, у которых номер является идеальным квадратом и соответственно они останутся открытыми после 100 проходов.
Еще куча интересного на моём дзене!
7 мега-проектов СССР которые были заброшены (технологии которые мы потеряли)
Дефицит в СССР как это было на самом деле?
Реальная правда о второй мировой войне. Ложь в которую мы верим!
Что будет если вулкан Эльбрус начнёт свое извержение?
