Переключатели

[Робинзон]

0. На входе на платформу "9 ³/₄" расположены 2015 переключателей, каждый из которых может иметь два состояния: ON и OFF. Разрешается за один рубль переключить или три произвольных соседних переключателя, или одну пару крайних переключателей (либо 1й и 2й, либо 2014й и 2015й). Докажите, что за конечное число таких операций можно все переключатели поставить в состояние  ON.

1.В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу на следующих условиях:
«В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON и OFF («вкл.» и «выкл.»). Каждую ночь я буду приводить в эту комнату ровно одного заключенного (выбирая его абсолютно случайно) и через некоторое время уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен понять, что в комнате побывали все заключенные, и сообщить об этом. Если он окажется прав — всех отпустят, если ошибется — все вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные, причем каждого будут приводить туда неограниченное число раз».

После этого заключенным разрешили собраться и обсудить стратегию действий, а потом развели обратно по камерам.
Могут ли заключенные гарантированно выйти на свободу, и если да, то как им этого добиться?

2. На входе в налоговую есть 2014 переключателей, каждый из которых может иметь два состояния: ON и OFF («вкл.» и «выкл.»), но по внешнему виду нельзя определить, в каком состоянии находится переключатель. За один рубль разрешается переключить какой-то один переключатель. Вход откроется, если ровно 1008 переключателей окажутся в состоянии ON, а остальные - в OFF. Какое наименьшее количество денег необходимо, стобы наверняка попасть в налоговую?

[RaiN]

Показать скрытый текст

1. Не знаю, можно ли считать подобный выход гарантированным, если нельзя гарантировать время выполнения.
Пусть есть n заключенных. Им надо выбрать одного главного.

Поведение обычного (не главного) заключенного:
Если выключатель выключен и этот заключенный ни разу его не включал, то он его включает. Если выключатель включен, либо заключенный уже включал его до этого, то ничего не делает.

Поведение главного:
При заходе в комнату смотрит, включен ли выключатель. Если выключен, ничего не делает. Если включен, то он его выключает и записывает себе, что в комнату зашел один новый заключенный.
В тот момент, когда он поймет, что заходили все n-1 заключенных, он говорит что все были.

[RaiN]

Показать скрытый текст

2. Если я не могу определить состояние выключателя ни до, ни после переключения, то я вижу единственную стратегию, которая может привести к результату - по очереди менять состояние всех выключателей слева-направо, каждый по одному разу. Надо только доказать, что в этом случае я приду к нужному результату. И определить, через сколько я к нему гарантированно приду.

Допустим в начальном состоянии k выключателей включены, тогда (2014 - k) выключены. Если я по очереди буду менять состояние всех выключателей, то я пройду через все состояния между "k включено" и "(2014 - k) включено".
В какой-то момент мы обязательно окажемся в состоянии "1007 включено", назовем его Середина.

Если в начальном состоянии мы не находимся в Середине, то состояние "1008 включено" тоже будет пройдено, это будет либо то, в которое мы придем из Середины, либо то, в которое мы выйдем из Середины. Перепрыгнуть через него мы не сможем.

Рассмотрим вариант, когда в начальном состоянии 1007 включено. То есть начальное состояние - Середина.
1) Если первый выключатель в начальный момент выключен, то на первом же ходе получаем искомое состояние.
2) Первый выключатель включен. Тогда самом худшем случае при смене всех выключателей мы не получим искомое состояние, а придем в состояние Середины. Такое будет например для чередования (ON OFF ON OFF ON OFF ...). В этом случае мы знаем, что первый выключатель в начальный момент времени был в состоянии ON, иначе бы мы получили искомое состояние на первом же шаге. Раз в начале он был в ON, значит сейчас в OFF. И если сейчас мы его нажмем - получим искомое состояние.
Итого максимум 2015 рублей.


Не исключено, что я неправильно понял условие задачи. Если так, то попробую решить после уточнений)

[Робинзон]

RaiN, если любой из ваших алгоритмов за конечное время, но всегда достигает цели, то можете считать задачу решённой.