Самый большой стол

Добрый день.

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

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

Вопрос: стол какой максимальной площади можно занести в кабинет Дяди Васи?

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

(Интересно, что источник предлагает хитрое, но неправильное решение, в чём честно сознаётся в комментариях. Будьте осторожны, переходя по этой ссылке, так как там есть хорошая идея, до которой гораздо приятнее дойти самостоятельно)

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

Да, и ещё: завтра (в пятницу, 29 июня 2012 в 20.00 Москвы) состоится очередной (и последний в этом сезоне) турнир по игре «Банальности» (подробнее). Не пропустите интересную игру! Вы можете попробовать сыграть с роботами на сайте, чтобы почувствовать, в чём смысл.

По поводу самого большого стола: легко предложить решение с площадью 3, несложно доказать, что площадь 9 недостижима. А до какой степени вам удалось сблизить эти границы?

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

Маловероятное событие

Добрый день!

Можно потратить много денег, чтобы показать мне Филиппа Киркорова на лошади, поющего песню Сергея Шнурова «Ленинград» (вероятность того, что я окажусь в кафе именно тогда, когда местный телевизор исполнит это безумие, крайне мала, но ОНИ воспользовались своим шансом). А можно с весьма скромным бюджетом и совсем без лошади создать весёлый и просветительский клип «Грибок стопы» (угадайте, о чём), самый популярный комментарий к которому «I really do like this music, even don't knowing the text».

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

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

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

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

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

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

Для случая k=1 всё достаточно просто: если известно, что шляпы бывают только одного цвета, то именно его надо называть. С вероятностью 100% ответ будет правильным, поэтому мудрецы пройдут тест. Остаётся найти решение для случая k>1. Будьте осторожны, читая источник задачки, так как там в комментариях уже всё подсказано.

Чем мне нравится эта задача? А тем, что кажется, что она не имеет разумного решения. Судите сами: первый отвечающий (который видит перед собой 99 шляп) ничего не знает о цвете своей шляпы. Поэтому он, не имея права назвать какой-то цвет (если назовёт, то с вероятностью 1-1/k все проиграют), вынужден сказать «пас». Но у второго совершенно такая же ситуация: он видит перед собой 98 шляп, он заранее знал, что первый скажет «пас», поэтому он тоже вынужден говорить «пас». И так далее. Возникает иллюзия, что выиграть невозможно. И тем интереснее догадаться, как же действовать мудрецам.

И ещё одна мысль на сегодня: раньше, объясняя метод математической индукции, я часто показывал задачку о триминошках (и её изящное решение). Обычно такого типа задачка гораздо лучше проясняет ситуацию для ученика. Во всяком случае, это всё куда нагляднее, чем стандартные задачки на делимость (главное, не слишком сбить с толку задачкой о лошадях). Если вам близка эта тема, то рекомендую заметку про Ханойскую башню (там в комментариях полезное дополнение к основному тексту).

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

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

День равновесия

Ну вот, опять Пасха на воскресенье выпала.
©Уже не понятно, кто первый сказал

Добрый день!

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

Например, можно отмечать каждый тысячный день жизни. Это, конечно, чуть реже, чем традиционный день рождения, но даты получаем более разнообразные (хотя бы не всегда одно время года будет за окном). Людям, имеющим отношение к IT-области, естественно было бы отмечать каждый 1024 день своей жизни. А если не терпится, то каждый 256 день, тогда даже выйдет чаще, чем традиционную «днюху». Как определить возраст в днях? Наверное, каждый начинающий программист в процессе обучения написал программку, переводящую даты из одного формата в другой — это полезное упражнение.

А ещё интереснее отмечать что-то нерегулярное. Я придумал день равновесия (напишите, пожалуйста, где уже читали о такой задумке):
- день малого возрастного равновесия: сумма возрастов жены и одного из детей совпала с возрастом мужа (или наоборот, если жена старше) — можно отмечать столько раз, сколько будет детей,
- день среднего возрастного равновесия: сумма возрастов детей совпала с возрастном одного из родителей (этот повод может возникнуть аж 2 раза, если супруги родились не в один день),
- день большого весового равновесия: сумма весов детей совпала с суммой весов родителей,
- день малого детского равновесия: количество внуков совпало с количеством детей,
- день среднего детского равновесия: среднее количество детей у каждого ребёнка совпало с количеством собственных детей (т.е. количество внуков совпало с квадратом количества детей),
- день большого возрастного равновесия: сумма возрастов детей совпала с суммой возрастов супругов,
и т.д.

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

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

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

Хорошего дня! И пусть у вас будет больше радостных событий!

Адреса wiki-статей без процентов

Добрый день.

Сегодня я сознаюсь, почему со страниц блога так много ссылок на страницы английской википедии, хотя всё то же самое можно найти и в русской. Ответ очень простой — было некогда разобраться, как ставить ссылки на русскую вики (серьёзно, я делал несколько подходов по 5 минут, но не находил простого способа).

Почему же я не спросил у коллективного разума интернет-знания? Бывают такие вопросы, ответ на которые почти невозможно получить с помощью поисковой машины. Википедия так популярна, что очень трудно найти текст вне википедии, если указал слово «wiki» в своём поисковом запросе. Это как пытаться узнать, выпустила ли свежий альбом «Music» группа «MP3». Ну или сейчас я расскажу, в чём была проблема, а вы покажете, как надо было искать на неё ответ — тоже полезно будет.

Вот представьте, что вам надо сослаться на какую-то статью русской википедии (или любую другую страницу, в адресе которой есть кириллица). Как это сделать?

Кажется, что очень легко:

• открываем нужную страницу википедии,
  
• копируем в буфер обмена адрес этой страницы из адресной строки браузера,
  
• вставляем куда угодно.
  

Попробуйте. У меня всегда получалось что-то такое: «http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BF%D0%B5%D0%BA%D0%B0%D1%80%D1%8F» А хотелось-то увидеть короткую и понятную строчку «http://ru.wikipedia.org/wiki/Преобразование_пекаря» (я честно перепробовал несколько браузеров, поискал решение в сети, но это не помогло). Согласитесь, второй адрес куда яснее и удобнее!

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

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

Итого:

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

Успехов!

Общее у ЕГЭ и ГАИ

Добрый день.

Два человека независимо рассказали мне следующую историю (каждый о себе):

1) Перед сдачей экзамена на получение водительских прав они внимательно изучили правила дорожного движения;

2) Когда сдавали тест на компьютере, получили негативную оценку, но решили разобраться, так как были уверены в своей правоте;

3) Во время общения с живым инспектором получили следующий ответ: «Да, с точки зрения ПДД вы ответили правильно, но это же компьютерный тест, к нему надо готовиться по билетам!».

Далее был естественный диалог:
— Мы ездить должны по ПДД или по билетам?
— Ездить надо по ПДД. А экзамен сдавать по билетам! Выучите уже их, это же не так сложно. Я не могу ничего сделать, так как программа выдала результат «не сдал». Не я же её сделал.

Мне это напомнило обычные ляпы в ЕГЭ первых лет. Там встречались вопросы, на которые правильным считался неправильный ответ (иногда из-за спешки при подготовке заданий, а иногда по причине разного взгляда на один и тот же вопрос в школьных и вузовских учебниках). Из-за этого более подготовленные школьники набирали на подобных заданиях меньше баллов, чем слабые, так как сильные школьники давали один и тот же ответ (правильный, с точки зрения изучаемой науки), а слабые с вероятностью 25% угадывали ответ, который считывался правильным. Впрочем, какие-то положительные движения есть и в этой области (например, тесты для девятиклассников (ГИА) оказались куда приятнее, чем можно было ожидать, ведь в них вернулась геометрия, которую в ЕГЭ до этого задвинули довольно далеко).

Аналогичные ляпы были и с тестами IQ: в первых классических изданиях встречались логические ошибки (кстати, их иногда переиздают и в наше время). Получается, что iq-тест не столько измерял способность испытуемого логически мыслить, сколько сходство логических ошибок испытуемого с ошибками авторов теста.

А какие вам известны случаи несоответствия теста тому, что он должен проверять?
Сталкивались ли вы с подобными особенностями в ГИБДД, школах, вузах или ещё где-то?
Победили ли несправедливость для всех? Добились правды только для себя? Смирились?

Разные ссылки #1

Добрый день!

Несколько дней назад я вернулся к нормальному интернету, разобрался со срочной почтой, отреагировал на комментарии, появившиеся в блоге за последние две недели, уменьшил количество непрочитанных записей в Google reader'е до 500, а теперь пришло время делиться найденным.

У меня получился такой список:

• Русский язык в котах. Можно в грубой форме требовать соблюдать правила русского языка, можно высмеивать неграмотность, а можно создавать приятные учебные пособия, которые в мягкой и весёлой форме решат ту же задачу (предлагаю неплохой пример справа, по ссылке есть больше, а у автора — ещё больше).
  
  
• Как сделать электродвигатель за 15 минут — замечательная тема не только для урока физики (материал статьи можно рассматривать как лишний повод для интересного общения с сыном, например),
  
  
• Название «Механическая модель коллайдера» после предыдущего может показаться шуткой, но интрига состоит в том, что всё серьёзно (у Игоря Иванова нередко так бывает),
  
  (кстати, если вам нравятся простые и интересные физические опыты, то рекомендую Новый канал Simple-Science — простые опыты и эксперименты)
  
  
• Предлагаю цитату из заметки «О возвращении к среднему»: «Представьте, что потоку из сотни студентов дают написать сложный экзамен по математике, и оценки за него выставляют по 100-бальной шкале. Давайте выпишем имена тех, кому выставили 10% худших оценок, и тех, кому достались 10% лучших. На следующий день всему потоку дают еще один экзамен, на ту же самую тему и той же сложности, но задачки другие. Теперь сравним оценки, которые получили студенты в первый день и во второй.
  
  Мы увидим, что почти всегда в среднем наихудшие ученики в первый день повысили свои оценки на второй день, а наилучшие, наоборот, снизили. Не у каждого ученика так будет, но в среднем выйдет так. Почему?» (если вам ещё не знаком этот эффект, то рекомендую сначала подумать, а уже потом читать рассуждение по ссылке выше),
  
  
• Блог «Бред программиста» понравился мне всем, но очень быстро «прочитался». Удивительно, как автору удалось зацепить меня несколькими совершенно разнородными темами. Оказалось, что про некоторые из этих вопросов я когда-то недавно думал, где-то решал похожие проблемы... Если честно, в какой-то момент мне показалось, что я читаю свой же блог, только не помню, когда всё это написал. У вас такое бывало?
  
  
• О переменах без перемен — Александр Привалов о больной теме предопределённости и о будущем нашего образования.

А знаете, какая заметка является самой посещаемой на этом блоге последние недели? «Как взрослому освоить велосипед»! Видимо, лето уже основательно началось, в пробках стоять никто не любит, а радоваться езде на велосипеде — это же совсем другое дело. Приветствую всех освоивших и осваивающих велосипед!

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

Интересное в мае 2010

Добрый день.

Два года назад мы говорили о физике и случайностях:

- В одной заметке того месяца мы сформулировали задачу о растворении пружины в кислоте, а уже в следующей постарались понять, куда же «девается» энергия. Хоть эту задачу и можно отнести к классическим и общеизвестным, споры о ней, наверное, не утихнут никогда. И объяснить это очень легко — гораздо проще иметь своё мнение, основанное на «здравом смысле и физике за 8 класс», чем разобраться в проблеме.

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

- Ещё в мае мы вспомнили «парадокс лжеца» (полезное упражнение для всех, кто его ещё не победил), а также подумали о том, как можно было бы понимать постоянное усложнение мозга (и какого досадного сценария для человечества тут можно было бы опасаться).

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

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