Логические задачи
      NazVa.net

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

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

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

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


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

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

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

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

34,5 л.

Возьмем за отправную точку какую-нибудь чашку 0,5 л, стояющую после чашки в 1 л.
Человек с ней льет себе. Справа от него льет себе. И так далее. До первой кружки в 1л. Человек с литровой кружкой льет себе. А вот следующие за ним до следующей литровой (включительно), льют предыдущему. Итого получим 1 налитую литровую, одну пустую литровую и мы в начальном положении. Повторяем до окончания кружек. Получим 5 полных литровых, 5 пустых литровых, остальные полные.

Для n>4 - получается развертка ходов коня всегда больше 180 градусов. А значит относительно каждого коня обязательно будет как минимум 1 конь левее и один конь правее. То есть доска должна быть бесконечна.

Очевидно, что больше чем 30 человек не напьется из-за ограничения по общему количеству чая: 25*0.5 + 5*1 = 35*0.5
Каждый, у кого чашка 0.5 литра, наливает чай себе.
Чашки по литру находятся рядом. Первый наливает себе, второй - первому. Третий - себе, четвертый - третьему. И т. д.

a[n] = a[n-1]/a[n-2];
a[n-1] = a[n-2]/a[n-3];
Следовательно:
a[n] = 1/a[n-3];
a[n] = 1/a[n-3] = a[n-6] = a[n-12] = ...
a[100] = a[100-6] = ... = a[100-96] = 1/a[100-99] = 1/7;

Не обоснована.
Пусть есть 6 обществ, с номерами от 1 до 6. И люди с именами a, b, c, d, e.
Каждый состоит в таком списке обществ:
a : 1 2 3 4 5 6
b : 2 3 5 6
c : 1 2 3
d : 4 5 6
e : 1 4

После ссылки "a" будет 6 обществ по 2 человека.
После ссылки "b" останется 2 общества: 1 и 4, причем "e" окажется в обоих и будет сослан следующим.
Хотя изначально был в наименьшем количестве обществ.

n=4, все враги.
Доказательство от противного:
Рассмотрим задачу в виде графа. Каждая вершина - рыцать. Если между двумя вершинами есть ребро - они друзья. Нет - враги. У каждого рыцаря 3 врага, а значит (n-4) друзей. (n-4)>0.
Пусть одна вершина - Вася. Проведем для него эти (n-4) ребер. Если хоть какие-то двое из этих друзей не соединены между собой - то они враги. Получается, что враг друга Васи - друг Васи. Этого быть не может. Значит друзья - полный граф.
Остаются отдельные 3 вершины, не связанные с остальными. Ни от кого из них (n-4) ребер провести нельзя, значит при n>4 задача не решается.
Для n<4 не найдется 3-х врагов.

По-моему указатели на лестнице выглядят так:
>>>>>><<<<<<
То есть снизу вверх n/2 указателей вверх, потом n/2 указателей вниз. Если n нечетно, указателей вверх на 1 больше. Вася стоит на последнем указателе вверх.
Доказательства пока не придумал, к сожалению.
Количество ходов (1+n)/2*n

Система:
Ax = b;
A:
( -1,  1/N, 1/N, ..., 1/N )
( 1/N,  -1, 1/N, ..., 1/N )
...
( 1/N, 1/N, 1/N, ...,  -1 )

b - вектор, содержащий проигрыши (для выигрышей отрицательные числа)
Полученный x - вектор, содержащий количество песка для каждого пирата, которое он должен отдать.