Стратегическая свобода

[Nadir Zaitov]

Опять же задачка с собеседований. Так что дайте себе времяне более 20 минут на решение. В тюрьму поступили 23 заключенных, их встретил начальник тюрьмы и сказал:

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

В тюрьме есть комната с двумя переключателями, обозначенными "A" и "B", каждый из переключателей может быть в положении "ON" и "OFF", я не скажу вам, в каком они сейчас положении. Переключатели ни к чему не подключены.

С завтрашнего дня, время от времени, когда мне захочется, я буду выбирать одного из вас случайным образом, и отводить в комнату с переключателями. Заключенный должен выбрать один из двух переключателей и изменить его положение. Он должен обязательно переключить один из переключателей, он не может переключить оба. Затем он будет возвращен в камеру.

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

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

Какая стратегия поможет заключенным выбраться на свободу?

Закручено. Заключенных 23, выключателей 2. Позиций 4. Вроде б кодировать никак не удается, а надо!

[Shuhrat Ismailov]

дайте себе времяне более 20 минут на решение. У меня двадцать минут только на прочтение ушло.....О решении вообще не говорю...

[Nadir Zaitov]

У меня двадцать минут только на прочтение ушло.....О решении вообще не говорю...А у меня 20 минут на решение вообще ничего не дало. Не любить мне дочку Собчака (с) Не работать мне в Интеле.

[Shuhrat Ismailov]

Не работать мне в Интеле.
Кому-то из-за своеобразного мышления такие задачи нравятся и легко даются .
В Интеле задачи из Рудина не дают, тогда были бы Вы там непременно.

[Nadir Zaitov]

Да, кстати!
Отгадка у задачки весьма заумная и в моем понимании дебильная.
Мне решение очень не понравилось. Я в своих размышлениях дошел до очень близкого решения, однако оно не позволяло дать характеристику для всех 23 заключенных. Решение предложенное авторами задачи оказалось таким утомительным для реализации, что вполне вероятно заключенных скормили бы крокодилам просто так... от того, что запарились.

[0zz]

Можно ли согласно фразе "Если хватит времени" предположить, что все будет происходить в течении одного дня? Если так, то ответ очевиден - весь день играть в эту клоунаду, а после полуночи любому объявить об окончании игры.

Если время не ограничено, то все равно продолжать щелкать, до тех пор пока начальнику тюрьмы не надоест. Ведь крокодилам их скормят только если они ошибутся, верно?

[Nadir Zaitov]

Можно ли согласно фразе "Если хватит времени" предположитьВремя не ограничено.
Если время не ограничено, то все равно продолжать щелкать, до тех пор пока начальнику тюрьмы не надоест. Ведь крокодилам их скормят только если они ошибутся, верно? И выйдут на свободу, только если угадают наверняка!

[Nadir Zaitov]

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

[insider]

мне кажется, 23 - это 23 часа в сутки. Надо это както связать. 23-закл. должен сказать что, все побывали в комнате. Надо толко придумать протокол общения :)

[Наташа]

Выбирается 1 человек, который имеет право выключить выключатель А, если он включен, а если же он выключен то переключает выключатель Б. Все остальные имеют право только 1 раз включить выключатель А в остальных случаях они его не трогают....:) Вот сколько раз выключит избранный товарищ выключатель А столько человек и побывало уже в комнате...:)

[Химера]

Наташа,
Единственная загвоздка. Первоначально положение выключателя "А" неизвестно, и заключенный не знает первый он попал в комнату или нет. То есть если первоначально "А" включен, то может образоваться лишний посетитель. За этим исключением решение рабочее.

[Nadir Zaitov]

Выбирается 1 человек, который имеет право выключить выключатель А, если он включен, а если же он выключен то переключает выключатель Б. Все остальные имеют право только 1 раз включить выключатель А в остальных случаях они его не трогают.... Вот сколько раз выключит избранный товарищ выключатель А столько человек и побывало уже в комнате... За этим исключением решение рабочее. Что-то в этом роде в оригинале:
Пусть выключатель "B" будет использоваться для подсчета. Нужно выбрать одного заключенного, который будет вести подсчеты. Положение "ON" выключателя "B" будет означать "Да! Я уже был в этой комнате!". Если заключенный входит в комнату, и выключатель "B" находится в положении "OFF", и заключенный никогда не изменял положение этого выключателя прежде, то он переключит его, чтобы пометить что он уже был в комнате. Если он входит в комнату, и выключатель "B" находится уже в положении "ON", то заключенный не меняет его положения, он переключит выключатель "A", он не должен трогать выключатель "B", поскольку он указывает тому кто считает, что кто-то побывал в комнате впервые, а также указывает на то что считающий заключенный еще не учел появление в комнате нового человека.
Каждый раз, когда считающий зэк заходит в помещение и видит что выключатель "B" в положении "ON", он мысленно добавляет к количеству подсчитанных единицу, и сбрасывает "B" в "OFF", что дает возможность следующему впервые посетившему отметиться.
Когда считающий зек обнаружит что выключатель "B" 22 раза был в положении "ON" (сам себя с помощью переключателя он считать не должен), это будет означать, что все были в комнате хоть раз.
Эта замечательная стратегия позволит им отправиться на корм крокодилам лишь в части случаев, ведь они не знают в каком положении был счетный переключатель изначально. Чтобы гарантированно избежать встречи с зубастыми, им нужно дважды отметиться в комнате, когда считающий заключенный досчитает до 44, это будет означать что каждый был в этой комнате по крайней мере один раз, независимо от начального положения "B".
Тут явные несколько проблем с объемом работы.

1) Процесс может никогда не закончиться, достаточно мне зека №1 (того самомго счетчика) не заводить в эту комнату столько раз, сколько нужно. Т.е. свобода не гарантирована.

2) При "равномерном" распределении визитов, минимальное количество раз, которое должен зайти каждый заключенный в комнату - 44 раза (так как нужный нам заключенный №1 именно столько раз в комнату и зайдет). В среднем нужно будет зайти еще в 2 раза чаще, так как нужный человек может зайти 2 раза между вами и вы 2 раза до того, как зайдет нужный человек.
Таким образом при равномерном распределении вероятности выбора нужно 88*23 раза в среднем побывать в комнате, т.е. где-то в среднем 2000 посещений и переключений тюремному выключателю придется выдержать.

3) Наконец... и с этого нужно было начать, что если на Intel пускают специалистов, которые дают такие трудоемкие решения, то понятно, откудова у Интел такой запас повышения производительности.

[Shuhrat Ismailov]

Тут явные несколько проблем с объемом работы.
откудова у Интел такой запас повышения производительности.
Наверное с детства.
В 2003 году на московской олимпиаде девятиклассникам предлагалось разобрать случай для 100 узников.

Условие
В тюрьму поместили 100 узников. Надзиратель сказал им:
"Я дам вам вечер поговорить друг с другом, а потом рассажу по отдельным камерам, и общаться вы больше не сможете. Иногда я буду одного из вас отводить в комнату, в которой есть лампа (вначале она выключена). Уходя из комнаты, вы можете оставить лампу как включенной, так и выключенной.

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

Придумайте стратегию, гарантирующую узникам освобождение.
Решение

Узники выбирают одного определённого человека (будем называть его "счётчиком"), который будет считать узников по такой системе: если, приходя в комнату, он обнаруживает, что свет включён, то он прибавляет к уже посчитанному числу узников единицу и выключает свет, если же свет не горит, то он, ничего не меняя, возвращается обратно в свою камеру. Каждый из оставшихся узников действует по такому правилу: если, приходя в комнату, он обнаруживает, что свет не горит, и он до этого ни разу не включал свет, то он его включает. В остальных случаях он ничего не меняет. Когда число посчитанных узников становится равным 99, "счётчик" говорит, что все узники уже побывали в комнате.

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

Остаётся доказать, что каждый из 99 узников включит свет. Предположим, что это не так - свет будет включён менее 99 раз. Тогда, начиная с некоторого дня n, свет включаться не будет. Так как никакой заход в комнату не будет для счётчика последним, он побывает в комнате после этого дня (например, на m-й день, m>n). Если свет при этом горел, он его выключит. Значит, начиная с (m+1)-го дня свет будет всё время выключен. Рассмотрим узника, который свет ещё ни разу не зажигал. Так как и для него никакой заход в комнату не последний, он побывает в комнате после m-го дня. Но тогда он должен включить свет - противоречие.

[Nadir Zaitov]

И не волнуйтесь, что кого-нибудь забудут - если будете молчать, то все побываете в комнате, и ни для кого никакое посещение комнаты не станет последним.Однако, если хватит времени, каждый из вас успеет побывать в комнате с переключателями.Почувствуй разницу (с). HR обязан был что-то да напортачить.
Кстати, идея убрать один выключатель и разрешить узника ничего не делать и есть ключевая в решении. Согласитесь, насколько красивее и лаконичнее выглядит задача для школьников!

[Химера]

Наконец... и с этого нужно было начать, что если на Intel пускают специалистов, которые дают такие трудоемкие решения, то понятно, откудова у Интел такой запас повышения производительности.
Скорее наоборот. Требуется запас производительности, под который берут головастых инженеров. А все из-за того что в программеры берут кого угодно. Как где-то постанули "раньше на 128к на Луну летали в автоматическом режиме, а сейчас чтобы зарплату бухгалтерия посчитала нужно 128Гб памяти" (вероятно имеется ввиду 1С на виндовом терминальнике)

[Nadir Zaitov]

Скорее наоборот.Должно быть наоборот, но сама задача, если она действительно задавалась в Intel на собеседовании, решается только при избыточной затрате сил (куда это годится - в среднем 88 раза заходить в комнату, чтоб подтвердить, что он там был) и без гарантированного результата (условия задачи не полные). Те, кто бы дал такое решение, не умеют воспринимать реальность и реальные потребности в ресурсах. Кстати, понятие алгоритм предполагает понятие конечности цикла. У Шухрата в решении есть это понятие.

[insider]

Виртуальная модель задачи


import java.util.Random;

/**
* Created by IntelliJ IDEA.
* User: uforum
* Date: Aug 19, 2010
* Time: 9:24:02 AM
* To change this template use File | Settings | File Templates.
*/

class Sostoyanie{
boolean A_ya_tut_byl = false;
boolean B_delat_nechego = false;
public Sostoyanie(boolean A_ya_tut_byl,boolean B_delat_nechego){
this.A_ya_tut_byl = A_ya_tut_byl;
this.B_delat_nechego = B_delat_nechego;
}
}

class Tyurma {
Sostoyanie perekl = new Sostoyanie(true,true);
Zaklyuchenny[] kamery;
int[] realschet;
public Tyurma(int skolka){
System.out.println("Strajnik: V turme "+skolka+" zakluchenix.");
System.out.println();
kamery = new Zaklyuchenny[skolka];
realschet = new int[skolka];
for(int i=0;i<skolka;i++){
kamery[i] = new Zaklyuchenny(i+1);
realschet[i]=0;
}
}
boolean uveren = false;
public Zaklyuchenny vybor(){

int nomer = new Random().nextInt(kamery.length);

//while(nomer==5){
// nomer = new Random().nextInt(kamery.length);
//}

Zaklyuchenny izbran = kamery[nomer];
realschet[izbran.nomer-1]++;
uveren = izbran.zashel(perekl);
return izbran;
}
public String toString(){
return "Perekluchatel: A="+perekl.A_ya_tut_byl+", B="+perekl.B_delat_nechego;
}
public boolean proverka(){
System.out.println("Strajnik: Shas proverim ...");
for(int i=0;i<realschet.length;i++){
System.out.println(" N "+(i+1)+" bil "+realschet[i]+" raz.");
}
for(int i=0;i<realschet.length;i++){
if(realschet[i]==0){
System.out.println("Strajnik: Krokodili jdut !!!");
return false;
}
}
System.out.println("Strajnik: Svoboda !!!");
return true;
}
}

class Zaklyuchenny{
int nomer = 0;
int schet = 0;
Sostoyanie[] pamyat=new Sostoyanie[0];

public Zaklyuchenny(int nomer){
this.nomer = nomer;
}
public boolean zashel(Sostoyanie pereklyuchatel){
if(pamyat.length==0){
if(pereklyuchatel.A_ya_tut_byl==true){
pereklyuchatel.A_ya_tut_byl=false;
}else{
pereklyuchatel.B_delat_nechego= !pereklyuchatel.B_delat_nechego;
}
}else{
if(pereklyuchatel.A_ya_tut_byl==pamyat[pamyat.length-1].A_ya_tut_byl&&pereklyuchatel.B_delat_nechego==pamyat[pamyat.length-1].B_delat_nechego){
if(pereklyuchatel.A_ya_tut_byl==false){
pereklyuchatel.A_ya_tut_byl=true;
}else{
pereklyuchatel.B_delat_nechego= !pereklyuchatel.B_delat_nechego;
}
}else{
schet++;
if(pereklyuchatel.A_ya_tut_byl==false){
pereklyuchatel.A_ya_tut_byl=true;
}else{
pereklyuchatel.B_delat_nechego= !pereklyuchatel.B_delat_nechego;
}
}
}
Sostoyanie[] s = new Sostoyanie[pamyat.length+1];
System.arraycopy(pamyat,0,s,0,pamyat.length);
s[s.length-1] = new Sostoyanie(pereklyuchatel.A_ya_tut_byl,pereklyucha tel.B_delat_nechego);
pamyat = s;
if(schet>23){
return true;
}
return false;
}
public String toString(){
return "Zakluchenniy: N "+nomer+", schet: "+schet;
}
}

public class Svoboda {
public static void main(String[] args){
Tyurma t = new Tyurma(23);

t.perekl.A_ya_tut_byl = new Random().nextBoolean();
t.perekl.B_delat_nechego = new Random().nextBoolean();

System.out.println(t);

while(true){
try {
Thread.sleep(10);
} catch (InterruptedException e) {
//e.printStackTrace(); //To change body of catch statement use File | Settings | File Templates.
}
Zaklyuchenny z = t.vybor();
System.out.println(z);
if(t.uveren){
System.out.println(" Ya uveren !!!");
System.out.println();
t.proverka();
System.exit(0);
}
System.out.println(t);
}
}
}



при запуска программы всегда получается свобода, т.к. генератор случайных чисел (ГСЧ) (имеет равномерное распределение) дает всем шанс. т.к. надзиратеь не мыслит как ГСЧ, то все таки от него и зависит "свобода" или "крокодилы". он может специально не вызвать хотя бы одного узника ...

вывод программы
http://uforum.uz/attachment.php?attachmentid=2886&stc=1&d=1282192891

[Nadir Zaitov]

вывод программыА по человечески? Сколько раз заключенные заходили в комнату?

[insider]

вывод программыА по человечески? Сколько раз заключенные заходили в комнату?

В конце есть


Strajnik: Shas proverim ...
N 1 bil 48 raz.
N 2 bil 40 raz.
N 3 bil 53 raz.
N 4 bil 34 raz.
N 5 bil 37 raz.
N 6 bil 38 raz.
N 7 bil 36 raz.
N 8 bil 37 raz.
N 9 bil 36 raz.
N 10 bil 37 raz.
N 11 bil 51 raz.
N 12 bil 31 raz.
N 13 bil 33 raz.
N 14 bil 35 raz.
N 15 bil 38 raz.
N 16 bil 51 raz.
N 17 bil 36 raz.
N 18 bil 33 raz.
N 19 bil 31 raz.
N 20 bil 43 raz.
N 21 bil 39 raz.
N 22 bil 39 raz.
N 23 bil 43 raz.

[Nadir Zaitov]

if(schet>23){ return true; }У Вас считается вариант, что каждый 2 раза побывал? Должно быть 44, а не 23! Вот в чем прикол. При 23 не гарантируется выход из тюрьмы :) Нужно 2 прохода. Начальное положение выключателей неизвестно, помните? Вот тогда и получится в среднем 87,5 прохода на каждого!

[insider]

if(schet>23){ return true; } У вас считается вариант, что каждый 2 раза побывал? Должно быть 43, а не 23! Вот в чем прикол. При 23 не гарантируется выход из тюрьмы :) Нужно 2 прохода.

не знаю, мне даже и 5 хватало (за счет ГСЧ)

[Nadir Zaitov]

за счет ГСЧА если бы ГСЧ случайно не выбирал бы одного и того 1-го вообще? И еще: откудова и кто дал в счете 23! Счет начинался с 1 или с нуля? Если с нуля, то макимум должно было быть 22 (если счетчик как-то себя не считал). :).

[insider]

при уменьшении этого числа вероятность попасть к крокодилам увеличивается (, но выигриш во времени),
а при увеличении, уменьшается :)

[Nadir Zaitov]

а при увеличении, уменьшаетсяТак ясен пень!
Вам же нужно гарантированно! Я и говорил, что избыточность тут "в среднем" страшная! Так ни одна система работать не должна, другое дело, что если надо, то лучше сделать по-другому.