Задача про басмачей и товарища Сухова.

[Veidali 259]

Поймал как-то товарищ Сухов в песках Каракумов банду басмачей. И стал перед ними речь держать:

Так мол и так, сидеть вам товарищи басмачи предстоит долго. Сегодня вечером вас разведут по зинданам и общаться вы друг с другом больше не будете. (Для одаренных поясню - общаться нельзя никакими способами - перестукиваться, дрессированых мышей с записками отправлять и т.д.)

Но! Как завещал товарищ Ленин - учиться, учиться и еще раз учиться. Петруха будет водить басмачей в библиотеку, в которой всего 2 книги (например синяя и вторая ). Обе лежат на столе. Каждый басмач за время посещения должен взять со стола одну книгу и, уходя, перевернуть ее (т.е. если до его прихода титульный лист был наверху, то после ухода он будет внизу и наоборот)

При этом графика посещений нет - Петруха водит басмачей в случайном порядке и нерегулярно. Может за один день 10 человек по очереди отвести, а может неделю никого не водить.

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

За порчу имущества библиотеки - смертная казнь (книги нельзя рвать, пачкать и т.д.)

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

У басмачей есть время совещаться до вечера, пока их не развели по зинданам.

 

Вопрос - как они должны действовать, чтобы гарантированно выйти на свободу?

Число бандитов не принципиально. Допустим их 10 (но решение должно работать и для 20 человек)

[Evtanazia 2 258]

Это на сообразительность... Это не для меня(я тугодум).

[Veidali 259]

Подобные задачи на ТРИЗе решать дают. Ну и некоторые айтишные конторы любят на собеседованиях задачи на логику давать.

[Storm 31 012]

Да, есть такое - куча таких задач, там Роберт, Джозеф и пр.

белые сидят в затылок друг другу, им перо показывают и пр.

бинарная логика + еще всякие умные слова.

[Stan 0]

Есть такая идея:

Каждый басмач проделывает следующее: при первом посещении берет синию книгу и переворачивает ее. При следующем посещении переворачивает ее обратно.

Если басмач пришел и видит, что синяя книга перевернута, то он ее не трогает, а переворачивает другую книгу.

Таким образом они смогут подсчитать, сколько раз в обе стороны перевернули синию книгу. И когда количество раз будет равно количеству басмачей (минус 1), последний придет и скажет, что все уже тут побывали.

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

Пример для трех:

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

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

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

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

 

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

Edited 11.06.2008 09:09 by Stan

[Veidali 259]

Ничерта не понял, что вы имели в виду с вашей идеей.

 

Пример для трех:

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

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

В условии задачи про начальное положение книг ничего не сказано.

 

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

Сами понимаете, что условие неверное, зачем его предлагаете?

Хотя дельные мысли там есть, но вы ушли в неправильном направлении.

 

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

А если стол круглый? Или треугольный? Число басмачей ничем неограничено. А если стол размером 30х30 см? По миллиметрам будут книгу двигать?

 

В общем оба ваши варианта не подходят.

[Stan 0]

Да я так, после обеда морально отдыхаю А то от работы голова кругом идет

 

Тогда есть еще одна идея:

Есть синяя книга и другая.

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

И есть только один басмач-считальщик, только он имеет право переворачивать синюю книгу лицевой стороной кверху.

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

Считальщиком может быть любой из них.

А вот как он просигнализирует о том, что побывал уже там и может начинать отсчет, пока в голову не пришло.

[Deja_VU 3 243]

К тому же переворачивать с лицевой стороны на тыльную можно разными способами: переплет справа-налево, переплет всегда с одной стороны, по часовой стрелке, против и т.д.

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

[Veidali 259]

Ага. Только вот по условию мы не знаем начального положения книги.

Но мыслишь верно.

[Stan 0]

Ага. Только вот по условию мы не знаем начального положения книги.

Но мыслишь верно.

Да, вот в этом пока и загвоздка, что начальное положение книг может быть любым и они его не знают

[Veidali 259]

К тому же переворачивать с лицевой стороны на тыльную можно разными способами: переплет справа-налево, переплет всегда с одной стороны, по часовой стрелке, против и т.д.

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

Нужен четкий алгоритм, а не "они как-нибудь обговорят".

А если их 100 человек? 100 положений книги будете придумывать?

[Deja_VU 3 243]

Нужен четкий алгоритм, а не "они как-нибудь обговорят".

А если их 100 человек? 100 положений книги будете придумывать?

 

Каков привет - таков ответ!

Задавай тогда конкретные условия задачи, а не "допустим 10, а может быть и 20".

[Алекс 1 852]

Каков привет - таков ответ!

Задавай тогда конкретные условия задачи, а не "допустим 10, а может быть и 20".

Тут ты не прав Это называется найти решение для общего случая

[Veidali 259]

Шторм, условие задачи читай внимательно - "Число бандитов не принципиально".

 

Стэн на полпути к решению уже.

Edited 11.06.2008 10:03 by Veidali

[Deja_VU 3 243]

Тут ты не прав Это называется найти решение для общего случая

 

Согласен

[cduz 0]

Решение этой задачки в случае, если их водят по одному в день, и водят каждый день - проще, чем в заданных условиях. Если бы их водили раз в день и каждый день, строго по одному, тогда алгоритм такой: басмачи договариваются, что тот из них, который попал в зиндан в первый день, становится "учетчиком", и действует так: он, в первое свое посещение, обязательно оставит синюю книгу лицом вверх. Если она уже лицом вверх, он ее не трогает. Затем, все остальные басмачи, действуют так: каждый из них, ТОЛЬКО ОДИН РАЗ ЗА ВСЕ ВРЕМЯ ПРЕБЫВАНИЯ В ПЛЕНУ, увидев синюю книгу лицом вверх, переворачивает ее лицом вниз. И делает это ТОЛЬКО ОДИН РАЗ. Все остальные разы он тупо читает вторую книгу и делает с ней что хочет. Книга так и пролежит лицом вниз до следующего появления учетчика. Учетчик же, каждый раз возвращаясь в зиндан, когда-нибудь увидит синюю книгу перевернутой лицом вниз. Это означает, что один из ранее не переворачивавших книгу басмачей побывал в библиотеке. Он снова переворачивает книгу лицом вверх и уходит. И так до тех пор, пока учетчик не перевернет книгу 9 раз, не считая самого первого раза. После этого он смело может заявить, что каждый из его товарищей успел побывать в библиотеке.

 

В данном же случае ситуация усложняется тем, что басмачей могут водить нерегулярно, т.е. никто не может с уверенностью сказать, что он пришел в зиндан самым первым, чтобы стать учетчиком. Поэтому учетчика они выбирают заранее, и этот учетчик делает те же самые действия, и остальные действуют по тому же самому алгоритму, с одним изменением в алгоритме: каждый басмач, не являющийся учетчиком (а учетчик выбран заранее), переворачивает книгу ДВА РАЗА. Т.е. впервые увидев синюю книгу лицом вверх, он ее переворачивает лицом вниз. В следующий раз, когда он ее, синюю книгу, увидит лицом вверх, он снова переворачивает ее лицом вниз. И больше он ее не трогает. Учетчик же на семнадцатый раз, когда он видит синюю книгу лицом вниз (он может на самом деле быть восемнадцатым, в силу неуверенности в том, кто первым попал в библиотеку и какое было положение синей книги), точно может быть уверен, что каждый из девяти коллег как минимум один раз был в библиотеке, и потребовать, чтобы их выпустили.

 

Вот как-то так.

Edited 11.06.2008 11:30 by cduz

[Stan 0]

В данном же случае ситуация усложняется тем, что басмачей могут водить нерегулярно, т.е. никто не может с уверенностью сказать, что он пришел в зиндан самым первым, чтобы стать учетчиком. Поэтому учетчика они выбирают заранее, и этот учетчик делает те же самые действия, и остальные действуют по тому же самому алгоритму, с одним изменением в алгоритме: каждый басмач, не являющийся учетчиком (а учетчик выбран заранее), переворачивает книгу ДВА РАЗА. Т.е. впервые увидев синюю книгу лицом вверх, он ее переворачивает лицом вниз. В следующий раз, когда он ее, синюю книгу, увидит лицом вверх, он снова переворачивает ее лицом вниз. И больше он ее не трогает. Учетчик же на семнадцатый раз, когда он видит синюю книгу лицом вниз (он может на самом деле быть восемнадцатым, в силу неуверенности в том, кто первым попал в библиотеку и какое было положение синей книги), точно может быть уверен, что каждый из девяти коллег как минимум один раз был в библиотеке, и потребовать, чтобы их выпустили.

хехехе

точно

по два раза

когда в 18 раз увидит, то все, конец

[Storm 31 012]

При чем тут ШТОРМ ?

я что такого сказал , что мне надо внимательно читать ?

Да и до стена мне нет дела вовсе, на полпути он, или заблудился.

решал такие задачи уже, посему неинтересно, типичные они все.

[cduz 0]

хехехе

точно

по два раза

когда в 18 раз увидит, то все, конец

 

В том-то и дело, что 18-го раза может и не быть. Если первым вошел не учетчик, и синяя книга была лицевой стороной вверх, он перевернет ее лицом вниз, то учетчик так и не узнает, переворачивали книги до него или нет. И "восемнадцатого" раза для него так и не наступит, потому что все уже по два раза перевернули и больше не трогают. Потому и нужно договариваться на по два раза, что ответ можно дать на 17-м переворачивании (которое на самом деле может оказаться 18-м, но это уже не важно).

Edited 11.06.2008 14:04 by cduz

[Veidali 259]

В данном же случае ситуация усложняется тем, что басмачей могут водить нерегулярно, т.е. никто не может с уверенностью сказать, что он пришел в зиндан самым первым, чтобы стать учетчиком. Поэтому учетчика они выбирают заранее, и этот учетчик делает те же самые действия, и остальные действуют по тому же самому алгоритму, с одним изменением в алгоритме: каждый басмач, не являющийся учетчиком (а учетчик выбран заранее), переворачивает книгу ДВА РАЗА. Т.е. впервые увидев синюю книгу лицом вверх, он ее переворачивает лицом вниз. В следующий раз, когда он ее, синюю книгу, увидит лицом вверх, он снова переворачивает ее лицом вниз. И больше он ее не трогает. Учетчик же на семнадцатый раз, когда он видит синюю книгу лицом вниз (он может на самом деле быть восемнадцатым, в силу неуверенности в том, кто первым попал в библиотеку и какое было положение синей книги), точно может быть уверен, что каждый из девяти коллег как минимум один раз был в библиотеке, и потребовать, чтобы их выпустили.

 

Вот как-то так.

Дец как мало.

Маладец!

 

Именно поэтому, когда Стэн предложил переворачивать 1 раз я сказал что он на полпути.

:-)

 

В том-то и дело, что 18-го раза может и не быть. Если первым вошел не учетчик, и синяя книга была лицевой стороной вверх, он перевернет ее лицом вниз, то учетчик так и не узнает, переворачивали книги до него или нет. И "восемнадцатого" раза для него так и не наступит, потому что все уже по два раза перевернули и больше не трогают. Потому и нужно договариваться на по два раза, что ответ можно дать на 17-м переворачивании (которое на самом деле может оказаться 18-м, но это уже не важно).

Нет. Он обязательно должен дождаться 18-го раза

Возможная ситуация:

1 раз книга лежала неправильно - он ее посчитал.

Потом 8 зеков зашли по 2 раза и он их постчитал, всего получится 17 раз.

Поэтому ему надо дождаться 18-го, раза чтобы гарантировать результат

 

При чем тут ШТОРМ ?

я что такого сказал , что мне надо внимательно читать ?

Ты сказал что тебе непонятно из условия сколько там басмачей, то ли 10, то ли 20.

Я тебе показал, что в условии сказано о том, что басмачей может быть сколько угодно, алгоритм от этого не должен зависеть.

 

Да и до стена мне нет дела вовсе, на полпути он, или заблудился.

решал такие задачи уже, посему неинтересно, типичные они все.

Интересная позиция. То пытаешься решать, какие-то ответы предлагаешь, а то вдруг в кусты, "мне, мол, не интересно".

[Dishenzo 7 817]

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

[zero_73 3]

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

Ржачь. Еще одно решение тогда. Все читают эти две книги. по очереди пересказывают и выходят на свободу. :mellow:

[Veidali 259]

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

Кто и кого будет спрашивать? Петруха - басмачей? Или товарищ Сухов?

Им пофигу как книги лежат.

А басмачи друг с другом общаться не могут (прочитайте условие)

[Dishenzo 7 817]

А книгу можно оставлять открытой?

 

 

Кто и кого будет спрашивать? Петруха - басмачей? Или товарищ Сухов?

Им пофигу как книги лежат.

А басмачи друг с другом общаться не могут (прочитайте условие)

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

[cduz 0]

Нет. Он обязательно должен дождаться 18-го раза

Возможная ситуация:

1 раз книга лежала неправильно - он ее посчитал.

Потом 8 зеков зашли по 2 раза и он их постчитал, всего получится 17 раз.

Поэтому ему надо дождаться 18-го, раза чтобы гарантировать результат

 

В предложенном мной варианте он первый свой заход не считает независимо от того как лежала книга. Потом считает 17 раз.