31 июл. 2011 г.

Интересное в феврале 2010

Добрый день.

Полтора года назад был весьма насыщенный месяц:

- блогу исполнилось два года (значит, сейчас уже 3.5 :). В той заметке приведена забавная статистика: доля читательниц в какой-то момент сократилась с 35% до 12%. Для сравнения: сейчас 20-25% читателей представляют прекрасный пол.

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

- В век интернета может казаться, что всевозможные википедии, викиучебники и электронные лекции могут заменить учителей. Кстати, в какой-то мере это справедливо (если есть мотивация, то можно многое выучить, сидя в районной библиотеке). Но если хочется учиться эффективнее, то может пригодиться хороший учитель. А что это значит? Чтобы ответить на этот вопрос, я написал заметку «В чём мастерство учителя?»

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

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

Хорошего дня!

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

29 июл. 2011 г.

Бег и травмы суставов

Последние недели мне попадалось очень много людей, решивших занять своё летнее время бегом. Эта мода хорошо распространилась в Европе и США, а теперь потихоньку захватывает и Россию. В самом деле, почему бы не развивать своё сердце и лёгкие, бегая по утрам?

А вот почему: бег по асфальту не физиологичен.
- Долгие сотни тысяч лет человек бегал по земле, а не не по жёсткой поверхности, поэтому его суставы не имели повода приспособиться к частым и сильным ударам.
- Долгие сотни тысяч лет человек с детства имел большую нагрузку на связки и суставы, но при этом имел меньший запас жира (относительно своей массы), так как необходимо было много двигаться. А сейчас суставы изначально слабенькие, а типичный вес начинающего бегуна нередко зашкаливает (что частенько и приводит его к мысли о занятии спортом).
- Профессиональный бегун старается «не трясти своим центром масс», чтобы сэкономить энергию и направить её на поддержание высокой скорости. Начинающий же бегун движется на низкой скорости, постоянно подбрасывая свою массу вверх, а потом с грохотом приземляясь на тонкие кости и хилые суставы ног.

Вроде бы красиво выглядит парк, наполненный молодёжью, бегающей по асфальтированным дорожкам. Возникает приятное ощущение, что «люди думают о своём здоровье, о своём будущем». Но проблема в том, что через 10 лет многие из этих людей будут медленно и осторожно ходить от одного врача к другому, а о беге и прыжках забудут навсегда.

И что теперь, не бегать? Конечно, бегать, если хочется. Только надо выбрать подходящее место: мягкую тропинку в лесу/парке или пляж. Кто-то скажет, что по песку бегать сложнее. А разве бегом занимаются, чтобы было проще? Плюсы от бега по пружинящей поверхности перевешивают все минусы, поэтому стоит потратить чуть-чуть времени на дорогу до леса, пляжа или парка. И лучше бегать не в тоненьких кедах, а в нормальных беговых кроссовках. Кстати, профессиональных бегунов тренеры гоняют не по стадиону, а по лесным дорожкам.

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

Если велосипедист:
1) не забывает регулярно пить (чтобы «смазка» поступала в колени),
2) не опускает количество полных оборотов педалями ниже 60 в минуту (так мы защищаемся от чрезмерных нагрузок на суставы, ибо никакого сердца и лёгких не хватит, чтобы в таком темпе ехать на высокой передаче в крутую гору, например),
то всё должно быть хорошо (во всяком случае, если ездить не более 100 километров в день). Ну а если станете ездить больше, то начнут играть роль и другие факторы, но к тому времени вы о них прочитаете на специализированных ресурсах.

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

Хороших выходных и приятного лета!

24 июл. 2011 г.

Кто пылесосит по ночам?

Представьте, что каждую ночь вы слышите не стук перфоратора, не уроки игры на пианино, не весёлую пьянку (потому что живёте в хорошем доме, жильцы которого отличаются повышенной вменяемостью), а... работающий пылесос. Вроде бы никто новый в дом не вселился, но почему-то один из соседей внезапно начал пылесосить каждую ночь примерно с 2:00 до 2:30. Нельзя сказать, что это нестерпимо громко, так как спать особо не мешает. Но интригу-то создаёт! Как тут спокойно уснёшь, если шесть месяцев каждую ночь повторяется одна и та же загадка — что они делают пылесосом по ночам? А через полгода всё прекратилось, как будто и не было ничего. И даже не понятно, кого спросить о причине странных ночных звуков.

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

Ну а если вы любите ясные формулировки, не подразумевающие нескольких толкований, то следующая математическая часть заметки для вас. Вернёмся к последней задачке об общей цели группы людей. Напомню, что вопрос был в том, с какой вероятностью группа из 2N человек побеждает в игре, если все люди умные и умеют договариваться. Другими словами, надо предъявить функцию P(N), которая описывает вероятность победы группы, а также доказать, что группа не может действовать лучше.

В самой заметке мы доказали, что P(1) = 1/2. Более того, для N>1 очевидно, что P(N) <= 1/2 (так как первый игрок не может обеспечить вероятность выше, чем 1/2, а остальные игроки выше 100% тоже не прыгнут.

Легко понять, что P(N) >= 1/2^(2N), так как каждый игрок, если будет действовать случайным образом, вытянет свой номер с вероятностью 1/2, а всего участников 2N. Так мы сделали оценку снизу.

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

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

Определим функцию вероятности победы P(N, S), где S — стратегия группы из 2N игроков:
P(N, S) = W(N, S) / C(N).
В этой формуле W(N, S) — это количество побед для группы из 2N человек, пользующихся стратегией S, на всех возможных входных данных (наборах табличек в коробочках). А C(N) — это количество всех возможных входных данных (т.е. количество способов поместить 2N разных табличек в 2N разных коробочек). Здесь мы исходим из того, что размещение табличек по коробочкам является полностью случайным (т.е. мы можем считать, что все эти элементарные события равновероятны).

Как определиться C(N)? Очень легко — C(N) = (2N)! (т.е. 2N(2N-1)(2N-2)(2N-3)...3*2*1). Это одна из первых формул, которую доказывают студенты, начинающие заниматься комбинаторикой.

А как определить W(N, S)? Простейший способ — честно посчитать. Надо всего лишь проверить для всех перестановок, позволяет ли стратегия S выиграть всей группе (за каждый случай победы надо увеличивать W на единицу).

Давайте, например, разберёмся с этой задачкой для N=2 (раз уж с N=1 мы всё поняли в прошлой заметке):
C(2) = 4! = 24. Действительно, у нас есть следующие 24 перестановки табличек в коробочках:
1234,
1243,
1324,
1342,
1423,
1432,
...
...
4312,
4321.

Теперь для каждой стратегии S, которую мы хотим проверить, надо попробовать её применить на всех 24 возможных входных данных. Соответственно, вероятность P(2, S) = W(2, S) / 24.

Зачем все эти сложности? Во-первых, далеко не все задачи получается решить сразу в общем виде. Часто бывает эффективно поиграть с частными случаями, чтобы лучше понять суть. Во-вторых, в теории вероятностей есть масса тонкостей, поэтому очень легко допустить ошибку в рассуждениях (особенно, если не иметь регулярной практики решения вероятностных задач). А предложенный подход хоть и требует аккуратности при переборе случаев, но позволяет избавиться от ошибок в рассуждениях о вероятностях, что на начальном этапе очень нужно.

Далее, имея в руках какие-то надёжно насчитанные равенства и неравенства, можно будет увереннее продвигаться в решении этой задачки. Предлагаю в комментариях к этой заметке добить случай N=2, чтобы в скором времени попробовать ответить на вопрос: если N стремится к бесконечности, то P(N) стремится к нулю? И если не к нулю, то к чему?

Пользуясь случаем, удивлюсь малому количеству ответов к задачке о выворачивании кубика. Что случилось? Вы не пьёте молоко и соки? Или не имеете ножниц, бумаги и скотча? ;) Задачка же хорошая! А пропадает почему-то...

Хороших выходных!

12 июл. 2011 г.

Общая цель

Добрый день!

В задачах о взаимодействии игроков бывают разные цели:
1) индивидуалистическая (максимизировать вероятность собственной победы),
2) бухгалтерская (максимизировать суммарный выигрыш всех игроков),
3) бескомпромиссная (максимизировать вероятность того, что все победят),
4) конкурентная (максимизировать количество тех, у кого результат будет хуже собственного),
5) ...

Классификаций, конечно, бывает много, но они нам сейчас и не нужны. Впрочем, для ясности приведу примеры (возможно, не самые удачные, но короткие, что важнее):
1) шахматная партия — индивидуалистическая игра,
2) задача о составлении расписания или настройке светофоров — бухгалтерская игра (максимизируем комфорт для всех участников),
3) взаимное кредитование стран — бескомпромиссная игра (если один «проиграет», то и остальные полетят вниз),
4) шахматный турнир — конкурентная игра (стараемся подняться как можно выше).

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

Предлагаю одну из задачек о бескомпромиссной игре, в которой участники обязаны думать друг о друге (т.е. у них есть общая цель, а индивидуальная победа невозможна по условию):
Бесчеловечный тиран пронумеровал 2N человек числами от 1 до 2N, заготовил 2N коробочек, пронумерованных от 1 до 2N, произвольным образом поместил в каждую коробочку ровно одну табличку с числом от 1 до 2N. Другой бы на этом остановился, но этот был очень бесчеловечным! Он запер всех людей в одной комнате, а все коробочки с бумажками в другой. Но не просто так запер, а объявил, что все люди будут заходить по одному в комнату с коробочками, чтобы заглянуть ровно в N штук, ничего не перекладывая. Естественно, состояние комнаты перед входом каждого участника делают исходным (все коробочки закрыты, ничего не сдвинуто и так далее), а игроки никак не могут общаться после того, как первый зашёл в комнату.

Цель людей — договориться действовать таким образом, чтобы максимизировать вероятность того, что каждый человек откроет коробочку, в которой лежит табличка с его номером. Другими словами, выигрыш каждого возможен только тогда, когда выигрывают все. А если хоть один участник свой номер не найдёт, то их всех заберёт паром из задачки про остров без зеркал. Этого никто не хочет, поэтому все будут стараться :)

Второй вопрос: с какой вероятностью умные люди будут выигрывать в этой игре?


Для начала давайте рассмотрим крайний случай — N=1. У нас есть два участника и две коробочки. В одной коробочке номер одного, в другой — номер второго. Каждый из них может открыть только одну коробочку, поэтому они должны договориться о том, что откроют разные (так как выиграть могут только при условии, что оба увидят свои номера в коробочках). Сначала заходит первый — он может открыть любую коробку (с вероятностью 1/2 в ней он увидит свой номер). Если игроки хорошо договорились, то второй участник вскроет вторую коробку с вероятностью 100%. Соответственно, для N=1 ответ такой:
1) игроки должны договориться, что первый открывает первую коробочку, а второй — вторую (или наоборот),
2) если они так поступят, то выиграют с вероятностью 50%.

Это был простой случай, чтобы лучше понять условие. А теперь приглашаю решить задачу для N>1.

Хорошего дня!

P.S.
Поздравляю всех с победой мужской волейбольной команды России в Мировой лиге 2011! Кстати, наша сборная показала высокий уровень командной игры, что прямо относится к теме этой заметки. Было видно, что каждый игрок понимал, что важно максимизировать не количество мячей, эффектно забитых своими руками, а вероятность победы команды в матче/партии.

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний