knop: (qr)
...то при любом собеседовании на должности, требующие математических способностей хотя бы в минимальной степени, соискатели получали бы у меня следующую задачку.

Придумайте, как можно организовать такой фокус.
Помощник фокусника просит одного из зрителей написать на доске в ряд N цифр. Затем помощник фокусника стирает одну из них и покидает помещение. После этого появляется фокусник. Глядя на оставшиеся цифры, фокусник безошибочно отгадывает, какая цифра была стёрта.
(Фокусник и его помощник заранее выбирают число N так, как им удобно; фокусник видит, на каком месте стояла стёртая цифра. Любые способы скрытой коммуникации, кроме явно оговоренных в задаче, запрещены.)

Ну что, хотите рискнуть? Комменты скрыты.

8.12. Раскрываю все комменты.
knop: (uzel)
Для прохождения теста тысячу мудрецов выстраивают в колонну. Из колпаков с номерами от 1 до 1001 один прячут, а остальные в случайном порядке надевают на мудрецов. Каждый видит только номера на колпаках всех впереди стоящих. Далее мудрецы по порядку от заднего к переднему называют вслух целые числа. Каждое число должно быть от 1 до 1001, причем нельзя называть то, что уже было сказано. Результат теста – число мудрецов, назвавших номер своего колпака. Мудрецы заранее знали условия теста и могли договориться, как действовать.
а) Могут ли они гарантировать результат более 500?
б) Могут ли они гарантировать результат не менее 999?

[Задача, которая прошлым летом принесла мне море удовольствия. Автор поначалу придумал не пункт б), а намного менее точный результат, и мы с ним последовательно дорешали ее до нынешнего вида.]

Комменты скрыты. Обязательно подумайте над этой задачкой, если вы ее еще не видели (она была на весеннем ТурГоре этого года).
Кстати, благодаря ей на problems.ru наконец-то появился отдельный раздел "Кооперативные алгоритмы":
http://problems.ru/view_by_subject_new.php?parent=1899
knop: (uzel)
Для тех, кто не в курсе: иногда я что-то из задач и головоломок пишу не в ЖЖ c автокопией в Тви, ВК и FB, а в блог на платформе Blogger: http://blog.kknop.com/

В частности, относительно свежие записи там -
"50+49" http://blog.kknop.com/2013/03/5049.html
и разрезалка - http://blog.kknop.com/2013/03/blog-post.html

Комментировать можно или там, или здесь, и даже в обеих местах сразу.
knop: (uzel)
Алексей с друзьями, взявшись за руки, встали вдоль Садового кольца в одиночные пикеты. У Алексея есть белая ленточка, которую он может передать любому из своих соседей по пикету (вправо или влево). Те, в свою очередь, могут сделать с лентой то же самое. Может ли Алексей разработать такой алгоритм передачи ленты, чтобы по его завершении каждый участник пикета точно знал две вещи:
1) что алгоритм действительно завершен
2) какое именно количество людей находится в пикете
[Ни Алексей, ни кто-либо из его друзей не могут регулировать время передачи ленты, однако каждый старается передать ленту согласно алгоритму как можно быстрее. Все участники пикета обладают памятью, а также умеют складывать и умножать целые числа. Садовое кольцо - действительно кольцо.]
.
knop: (uzel)
См. http://elementy.ru/problems/499

Для моих давних читателей - не открытие, но решение и послесловие будут достаточно интересными.
А для остальных - попробуйте порешать
knop: (Default)
Хорошо известна следующая классическая задача: расставить 7 гномов в хоровод (длины 7) шесть раз так, чтобы каждый побывал правым соседом каждого другого ровно по одному разу.
(Решается она как угодно. Например, если гномы и хороводы перенумерованы, то в i-м хороводе правым соседом гнома j ставим гнома с номером j+i (mod 7).)

А вот как разумно рещить такую задачу: расставить 7 гномов в хоровод длины 6 семь раз так, чтобы каждый побывал правым соседом каждого другого ровно по одному разу, и еще один раз постоял в центре хоровода?

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

Комменты скрыты на несколько дней.
knop: (qr)
Несмотря на то. что мудрецы уже не раз демонстрировали не только преданность султану, но и незаурядную смекалку, нехороший султан решил устроить им еще одно испытание...

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

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

а) Как им действовать (в смысле, какой должна быть предварительная договоренность между ними), чтобы повысить шансы своей команды на прохождение теста?
б) Можно ли сделать эту вероятность больше, чем 9999/10000 ?
в)* Какова оптимальная стратегия?

Комменты будут скрываться.
knop: (Default)
Зритель выкладывает по кругу 4 (различных) туза картинками вверх и переворачивает один из них (вверх рубашкой). В этот момент подходит помощник фокусника, переворачивает одного из двух тузов, соседних с уже перевёрнутым, и уходит. После этого зритель подзывает фокусника.
Тот видит два открытых туза и определяет, в каком порядке лежат перевернутые.

Разумеется, помощник с фокусником никак не жульничают. Как же им удаётся проделать такой фокус?
knop: (Default)
В выходные мне напомнили о такой замечательной информационной задаче:

Секретный код к любому из сейфов ФБР - это натуральное число от 1 до 1700. Двое шпионов узнали по одному коду каждый и решили обменяться информацией. Согласовав заранее свои действия, они встретились на берегу реки возле кучи из 26 камней. Сначала первый шпион кинул в воду несколько камней, потом - второй, потом опять первый и так далее до тех пор, пока камни не кончились. После этого шпионы разошлись. Каким образом могла быть передана информация? (Шпионы не сказали друг другу ни слова.) (Авторы - Дмитрий Челкак и Константин Кохась, СПбМО 2002, отборочный тур, 10 класс)

Комменты пока скрыты, можно порешать.

PS. Открываю большинство комментов. Правильных решений несколько, они могут быть описаны по-разному...
knop: (Default)
Есть старая (можно, сказать, классическая) задача о неверных мужьях. Я процитирую ее по замечательной книге Уильяма Паундстоуна "Как сдвинуть гору Фудзи".

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

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


Я надеюсь, что ответ на нее известен всем заинтересованным читателям моего ЖЖ.
Речь пойдет не о ней, а о ее вариации. Во-первых, пусть это будет большой город, а не маленькая деревня. Во-вторых, вовсе не обязательно, чтобы все мужья были неверными. Тем не менее, основное условие по-прежнему выполнено: (1) каждая жена точно знает факт неверности всех неверных мужей, кроме своего собственного, (2) понимает, что все остальные женщины тоже обладают знанием (1), ..., (N+1) понимает, что все остальные женщины обладают знанием (N), ...

Главное изменение условия - нетерпеливость королевы. Она не хочет ждать столько дней, сколько неверных супругов подлежит наказанию! Поэтому по ее указанию все жены получают ружья с патронами и набор инструкций, как им действовать. В частности, инструкции разрешают женам стрелять не только в супруга, но и в воздух. Для определенности будем считать, что все выстрелы происходят ровно в 0:00 по местному времени. За какое наименьшее число ночей может свершиться правосудие при таких условиях?

(Эта версия взята из одной научной статьи 1986 года.)
Комменты скрыты.

4.08.2010. Раскрываю комменты, читайте. Правильные ответы есть, неправильные тоже есть.
Какой именно ответ правилен, я пока не пишу. На всякий случай...
knop: (Default)
Сегодня зачитался одним форумом с задачками и - как там это было у Жванецкого - "народ сказал АХ и дружно проехал свою остановку". (Игорь, спасибо!!)

Несколько дней назад через [livejournal.com profile] alexey_ustinov узнал еще одну версию задачи-фокуса с закрыванием карт.

Итак, зритель пишет по кругу N цифр. (Каждая цифра - от 0 до 9). Помощник фокусника стирает одну из них. После этого в аудиторию заходит фокусник, задача которого - гарантированно правильно определить стертую цифру. При каком наименьшем N этот фокус удастся?

(Дополнительный вопрос: существует ли какая-нибудь "естественная" стратегия фокусника с помощником, не требующая запоминания таблицы размера 10^n или сравнимого с этим?)

Комменты скрыты.
knop: (Default)
Ойййо. Как же я пропустил, насколько интересно и дотошно покопались индусы в моей задаче.

S. Aravamuthan , S. Lodha, Coloring Codes for Hats-on-a-line, The Electronic Journal of Combinatorics, 13 (1), Mar. 2006.
http://www.combinatorics.org/Volume_13/Abstracts/v13i1r21.html
(там есть pdf и ps). А еще - заметка для себя - посмотреть различия между опубликованным текстом и тем, что лежит на странице у одного из авторов.
http://121.241.184.234:8000/pdf/SRL/aravamuthan_ccfh_2006.pdf

(Да, чтоб два раза не вставать. Вот ссылочка оттуда на коллекцию, в которой упомянуты разные головоломки о мудрецах и шляпах. http://www.cs.cmu.edu/puzzle/puzzle15.html
и решение http://www.cs.cmu.edu/puzzle/solution15.pdf. И чтоб трижды не вставать, еще одна забавная задача о шляпах -- http://www.cs.cmu.edu/puzzle/puzzle27.html, решение http://www.cs.cmu.edu/puzzle/solution27.pdf)
knop: (Default)
Среди всех разнообразных версий я, кажется, еще ни разу не упоминал у себя такую вот классику:
10 мудрецам пишут на лбы натуральные числа от 1 до 10 (не обязательно различные). Каждый видит все числа, кроме своего. По сигналу Короля каждый мудрец должен записать на бумажке предсказание числа, которое написано на лбу у него самого. Если хотя бы один из мудрецов предскажет правильно - все спасены, иначе всех их казнят.
Задача традиционна: придумать коллективную стратегию, гарантирующую спасение.

А вот теперь - свежее дополнение к этой классике, прочитанное все у того же P.Winkler.
Пусть все надписи на лбу сделаны красной краской, один из мудрецов - зеленокожий Шрек, а еще один - дальтоник, не различающий красный и зеленый цвета. (Иначе говоря, все мудрецы видят надписи на лбах у всех остальных, кроме одного, который видит надписи только у 8 из 9 остальных.) Докажите, что при таких условиях у мудрецов не может быть гарантированной спасительной стратегии.

Скрывать ли комменты? Даже не знаю. Пусть пока будут скрыты...
knop: (Default)
Прочитал версию, которой раньше не знал.

На лбу каждого из N мудрецов написали произвольное действительное число; кроме этого каждому из них выдали одну черную и одну белую варежку. Каждый из них видит все остальные числа, кроме своего, и имеет возможность надеть на одну руку одну варежку, а на другую - другую. (Все надевания варежек должны произойти одновременно, всякое общение между мудрецами запрещено.) Цель мудрецов - надеть варежки так, чтобы после того как всех мудрецов построят в шеренгу в порядке возрастания написанных на их лбах чисел и попросят всех соседей взяться за руки, каждая белая варежка взялась за белую, а каждая черная - за черную.

Помогите мудрецам справиться с этой непростой задачей...
knop: (Default)
Все-таки пока скрою комменты, чтобы не ломать кайф решающим. Буду открывать то, что будет не очень близко к правильности...

Эта задача (как мне кажется) достаточно известна. Кто ее знает, просьба в дискуссию не включаться...

knop: (Default)
Первая задача из этих самых brainteasers, которая меня тогда "вставила" по полной программе.
В том числе и по затраченному на нее времени.

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

knop: (Default)
Продолжу публиковать старые brainteaser'ы. Как следует из указанного уровня, первая задача чуть полегче, вторая - потяжелее.

Первая:


Вторая:


Комменты скрываются поримерно на 4-5 дней.

PS. Комменты раскрыты. Решение второй задачки я опубликую отдельным комментом.
knop: (Default)
Это продолжение задачки, комменты к которой я только что раскрыл. Смотрите метку brainteasers



Комменты пока скрыты, дам только небольшую подсказку: для 4 игроков улучшения не бывает (ухудшения, впрочем, тоже - они выигрывают в 3/4 всех случаев, то есть в 12 из 16). Первое улучшение достижимо для 5 участников: 25/32.

(Для математиков: докажите, что 26/32 недостижимо).
knop: (Default)
Именно в этой формулирровке - жуткий "баян", хотя еще лет 15 назад баяном не была. Очень яркий пример задачи, интернет-популярность которой многократно затмила известность того бумажно-книжного источника, в котором она встретилась изначально.



P.S. Для тех, кто раньше встречался с этой задачей, предлагаю порешать одну из следующих версий.
Задача о пяти шляпах
Пять человек, шляпы трех цветов. Требуется отыскать оптимальную стратегию.
Задача о четырех шляпах
Четыре человека, шляпы трех цветов. Требуется отыскать оптимальную стратегию.
(Подсказки, которые здесь стояли раньше, по-видимому, неверны. Я их убрал.)

PPS. 2 мая. Я раскрыл комментарии и поместил продолжение задачи (про большую компанию).

April 2017

S M T W T F S
      1
234567 8
9101112131415
16171819202122
23242526272829
30      

Syndicate

RSS Atom

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 23rd, 2017 11:08 am
Powered by Dreamwidth Studios