Category: эзотерика

Category was added automatically. Read all entries about "эзотерика".

77
  • flaass

задача про экстрасенса - верхняя оценка

Вот небольшая комбинаторная задачка про деревья, для которой нетрудно найти полное решение.

Рассмотрим корневое дерево высоты n (то есть, расстояние от корня до любого листа дерева равно n). Предположим, что каждое ребро раскрашено в белый или черный цвет, и выполняются вот такие свойства:
- из каждой вершины в следующий уровень выходит не более p черных и не более q белых ребер;
- на каждом пути от корня к листу встречается не более k белых ребер.
Вопрос: чему равно m(n,k) - наибольшее возможное число листьев?
Collapse )
Спрашиваете, при чем тут экстрасес?
Вот в этой записи у себя я фактически доказал такую теорему:

Теорема. Положим p=2, q=6. Если m(n,k) строго меньше числа возможных расположений мастей в колоде из n карт, то любая стратегия служителя с экстрасенсом может привести к тому, что экстрасенс ошибется более k раз.

На самом деле там это доказано для более общей ситуации: когда карты имеют b мастей, и служитель может оставлять на рубашках одну из a различных пометок, a < b. (При этом надо взять p=a, q=a(b-1).)

Арифметика и подробные объяснения - на потом, убегаю...
77
  • flaass

Экстрасенс - сводка.

Задачка.
Решения и обсуждения. - даны простые способы, как угадать 23 и 24 карты, и сложный - как угадать 25 (и похоже, не все собеседники еще убедились, что 25 возможно).

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

И по-прежнему никаких следов верхних оценок...
77
  • flaass

решение про экстрасенса

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

Collapse )

Рассказал бы и про 24, но раз кто-то может 25 - зачем корячиться? :)
77
  • flaass

задачка с олимпиады

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

Если больше половины - уже неплохо.
А сам я не могу больше двух третей.