Сегодня знакомый предложил задачу, процесс решения которой понравился. Прошу сильное не пинать, если баян )) Итак...
На фабрике работает один миллион рабочих, каждому из которых руководство выделило по персональному ящику. Вечером рабочий день заканчивается, и рабочие идут к своим ящикам, которые пронумерованы с 1 до 1`000`000, складывают в них свои вещи и отправляются домой на заслуженный отдых. Ближе к полуночи из старых цехов, домен, чердаков и т.д. появляются ровно один миллион привидений, решивших немного пошалить. Все они также пронумерованы от 1 до 1`000`000 )) Привидения действуют следующим образом:
1. Первое привидение открывает все ящики наших работяг (т.к. к сожалению, денег на замки для ящиков начальство не предоставило)
2. Привидение с порядковым номером на «груди» «2» закрывает все ящики, номера которых делятся на 2, т.е. закрывает ящики 2, 4, 6, 8 и т.д.
3. Третье привидение с порядковым номером, как мы все догадались, «3» изменяет состояние всех ящиков, которые делятся на 3. Т.е. если номер ящика делиться на 3 и был закрыт, то оно открывает его, если этот ящик был открыт – закрывает. Например, на этом шаге будут закрыты ящики: 3, 9 и открыт ящик за номером 6 и т.д.
N. Все последующие привидения с 4 по 1`000`000-е действую по тому же алгоритму, т.е. изменяют состояние ящиков, порядковые номера которых делятся на их порядковый номер.
Привидения действую быстро и бесшумно до самого утра, пока все не внесут свою лепту в процесс открывания/закрывания ящиков. И вот к утру последнее 1`000`000 привидение изменяет состояние единственного ящика, и все привидения исчезают каждое по своему углу.На утро приходят рабочие и обнаруживают, что часть ящиков открыта, а часть закрыта.
1. Сколько ящиков открыто/закрыто?
2. Как доказать, что именное указанное количество будет открыто/закрыто, без просчета каждого шага?
