Неутомимые гномики

Изображение пользователя Gregory Frenklach.

Эту задачу давали при приёме на работу в некоторые hi tech компании.
Имеется, скажем, миллион (можно и больше) свечек.
Проходит первый гномик и зажигает каждую свечку.
Проходит второй гномик и тушит каждую вторую свечку.
Проходит третий гномик и либо тушит каждую третью свечку - если она горит, либо зажигает - если она не горит.
Проходит четвёртый гномик и делает то же самое, но с каждой четвёртой свечкой.
И так далее пока миллионный гномик не потушит (или не зажжёт) последнюю свечку.
Свечки могут гореть вечно. Это я на всякий случай, чтобы никто не сказал, что какие-нибудь свечки (например, первая) могут полностью догореть...
Сколько свечек останется гореть, когда гномики закончат свою работу?
Замечу, что в этой задаче интересно не столько само решение сколько его (решения) ход и/или обоснование.
Успехов...

Форумы: 

Re: Неутомимые гномики

Что-то в этом духе было у Перельмана. и нас, помнится, натаскивали на это дело классе этак в 9-10. Там, правда, было сильно более советски-пионерски.

Поискать первоисточник?

Re: Неутомимые гномики

Изображение пользователя Gregory Frenklach.

Неужели никто даже не попытается?

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

Re: Неутомимые гномики

Опять воспользовался тем же способом решения, что и в задаче про черепах.

Берешь частный случай. Рисуешь рисунок и считаешь. Потом обобщаешь. Потратил времени 15 минут.

При 10 свечках гореть остануться 3.

При 20 останется 4.

При 30 останется 5.

При 40 останется 6.

Теперь обобщаем: при  N  свечках и гномиках (N - кратно 10) останется гореть 2+N/10 свечек, т.е при миллионе свечек останется гореть 100002 свечки, или, грубо, 100000, т.е десятая часть.

Re: Неутомимые гномики

Изображение пользователя Gregory Frenklach.

Ошиблись на несколько  порядков потому, что дальше всё меняется:

При 50 - 7;
При 60 - 7;
При 70 - 8;
При 80 - 8;
При 250 - 15;
При 1500 - 38;
При 150000 - 387;

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

Re: Неутомимые гномики

Изображение пользователя Gregory Frenklach.

Хочу предупредить, что ни ответа ни разбора хода решения не будет до тех пор, пока кто-нибудь не решит эту задачу.

Re: Неутомимые гномики

Gregory Frenklach wrote:

Хочу предупредить, что ни ответа ни разбора хода решения не будет до тех пор, пока кто-нибудь не решит эту задачу.

1 000 000 - 1000

7 08 2016 - 2661

Теперь давайте разбор ;-)

Re: Неутомимые гномики

Изображение пользователя Gregory Frenklach.

Гномики - это "множители" => чтобы свечка осталась гореть количество гномиков, "задержавшихся" у свечки должно быть нечётным.
Например, четвёртая свечка:
1-й зажёг, 2-й потушил, 4-й зажёг.
Какие числа имеют нечётное количество множителей? Почему?
Можно, конечно, было пойти длинным путём, взять, скажем 50 свечек и посмотреть, какие останутся гореть после "прохода" 50-ти гномиков. Номера свечек, оставшихся гореть дали бы идею, но это не очень "изящно".

Re: Неутомимые гномики

Изображение пользователя Gregory Frenklach.

Каждое из чисел, соответствующих номеру той или иной свечки может быть получено парой "можителей".
Таких пар может быть несколько, например, число 18 = 1 х 18 или 2 х 9 или 3 х 6.
Для определённых чисел в одной из пар "множителей" могут быть не два разных числа, а одно, умноженное само на себя (квадрат), например, число 16 = 1 х 16 или 2 х 8 или 4 х4. Поэтому у этих чисел общее число "множителей" нечётное, в отличие от остальных, у которых оно чётное.
Вот эти свечки с номерами, соответствующими числам с нечётным числом "множителей" (квадраты целых чисел) и останутся гореть.
Таким образом, для того, чтобы определить какое количество свечек останется гореть из миллиона (двух, трёх... десяти) надо извлечь из этого числа квадратный корень и оставить от значения корня только целую часть.

Теперь все силы на задачу с черепашками:)

Subscribe to Comments for "Неутомимые гномики"