Название: Переключатели
Отправлено: Робинзон от Январь 25, 2015, 13:15:55
0. На входе на платформу "9 3/4" расположены 2015 переключателей, каждый из которых может иметь два состояния: ON и OFF. Разрешается за один рубль переключить или три произвольных соседних переключателя, или одну пару крайних переключателей (либо 1й и 2й, либо 2014й и 2015й). Докажите, что за конечное число таких операций можно все переключатели поставить в состояние ON.
1.В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу на следующих условиях:
«В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON и OFF («вкл.» и «выкл.»). Каждую ночь я буду приводить в эту комнату ровно одного заключенного (выбирая его абсолютно случайно) и через некоторое время уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен понять, что в комнате побывали все заключенные, и сообщить об этом. Если он окажется прав — всех отпустят, если ошибется — все вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные, причем каждого будут приводить туда неограниченное число раз».
После этого заключенным разрешили собраться и обсудить стратегию действий, а потом развели обратно по камерам.
Могут ли заключенные гарантированно выйти на свободу, и если да, то как им этого добиться?
2. На входе в налоговую есть 2014 переключателей, каждый из которых может иметь два состояния: ON и OFF («вкл.» и «выкл.»), но по внешнему виду нельзя определить, в каком состоянии находится переключатель. За один рубль разрешается переключить какой-то один переключатель. Вход откроется, если ровно 1008 переключателей окажутся в состоянии ON, а остальные - в OFF. Какое наименьшее количество денег необходимо, стобы наверняка попасть в налоговую?
Название: Re: Переключатели
Отправлено: RaiN от Январь 26, 2015, 15:33:18
Показать скрытый текст
1. Не знаю, можно ли считать подобный выход гарантированным, если нельзя гарантировать время выполнения.
Пусть есть n заключенных. Им надо выбрать одного главного.
Поведение обычного (не главного) заключенного:
Если выключатель выключен и этот заключенный ни разу его не включал, то он его включает. Если выключатель включен, либо заключенный уже включал его до этого, то ничего не делает.
Поведение главного:
При заходе в комнату смотрит, включен ли выключатель. Если выключен, ничего не делает. Если включен, то он его выключает и записывает себе, что в комнату зашел один новый заключенный.
В тот момент, когда он поймет, что заходили все n-1 заключенных, он говорит что все были.
Название: Re: Переключатели
Отправлено: RaiN от Январь 26, 2015, 15:41:15
Показать скрытый текст
2. Если я не могу определить состояние выключателя ни до, ни после переключения, то я вижу единственную стратегию, которая может привести к результату - по очереди менять состояние всех выключателей слева-направо, каждый по одному разу. Надо только доказать, что в этом случае я приду к нужному результату. И определить, через сколько я к нему гарантированно приду.
Допустим в начальном состоянии k выключателей включены, тогда (2014 - k) выключены. Если я по очереди буду менять состояние всех выключателей, то я пройду через все состояния между "k включено" и "(2014 - k) включено".
В какой-то момент мы обязательно окажемся в состоянии "1007 включено", назовем его Середина.
Если в начальном состоянии мы не находимся в Середине, то состояние "1008 включено" тоже будет пройдено, это будет либо то, в которое мы придем из Середины, либо то, в которое мы выйдем из Середины. Перепрыгнуть через него мы не сможем.
Рассмотрим вариант, когда в начальном состоянии 1007 включено. То есть начальное состояние - Середина.
1) Если первый выключатель в начальный момент выключен, то на первом же ходе получаем искомое состояние.
2) Первый выключатель включен. Тогда самом худшем случае при смене всех выключателей мы не получим искомое состояние, а придем в состояние Середины. Такое будет например для чередования (ON OFF ON OFF ON OFF ...). В этом случае мы знаем, что первый выключатель в начальный момент времени был в состоянии ON, иначе бы мы получили искомое состояние на первом же шаге. Раз в начале он был в ON, значит сейчас в OFF. И если сейчас мы его нажмем - получим искомое состояние.
Итого максимум 2015 рублей.
Не исключено, что я неправильно понял условие задачи. Если так, то попробую решить после уточнений)
Название: Re: Переключатели
Отправлено: Робинзон от Январь 26, 2015, 20:39:19
RaiN, если любой из ваших алгоритмов за конечное время, но всегда достигает цели, то можете считать задачу решённой.
|