Привычка не думать

Неправильный ответ

noreply@blogger.com (Илья Весенний) — Sun, 22 Jan 2012 22:34:44 PST

Добрый день.

Многие родители старательно проверяют совпадение ответов, полученных их детьми при выполнении домашних заданий, с ответами, опубликованными на последних страницах учебников. Это одна из причин того, что детям иногда важнее получить правильный ответ, чем разобраться в методах решения. Бывает даже, что для получения этого самого ответа ребята делают какие-то нелепые вычисления, которые не могут никак объяснить («подгоняют под ответ»).

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

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

Напомню задачку:
1. Дано количество шкатулок N и набор вероятностей p0, p1, ... pN (их сумма равна единице).
2. Кто-то определил количество призов (с вероятностью p0 должен быть ноль призов, с вероятностью p1 — один приз, ... с вероятностью pN — N призов), после чего поместил их в эти шкатулки (не более одного приза в шкатулку).
3. Якубович выносит поднос с N шкатулками, сообщает игроку все данные из первого пункта, а затем спрашивает, с какой вероятностью игрок обнаружит в случайно открытой шкатулке приз. Игрок вычисляет эту вероятность — получается P.
4. Когда игрок открыл случайную шкатулку, он обнаружил приз (повезло). Пока радостный игрок укладывал приз себе в карман, Якубович захлопнул пустую шкатулку, после чего перемешал шкатулки на подносе.
5. Теперь ситуация поменялась (на подносе призов стало на один меньше), поэтому игрок вновь вычислил вероятность того, что в случайной шкатулке будет приз — получилось Q.

Вопросы задачи состояли в том, чему равны P и Q, как они соотносятся между собой при разных ограничениях на набор pi.

Первое заблуждение, которое многие отстаивали — вероятность P всегда превосходит Q.

Объяснение приводилось примерно такое: «Если предположим что призов было k, то P = k/N, а Q = (k-1)/N. Из этого легко доказать, что Q < P». Мне это напомнило высказывание одной ученицы: «Так как в условии задачи не сказано, какая это трапеция, то можно считать, что она равнобедренная, тогда...». Да, иногда полезно бывает временно упростить условие задачи, чтобы лучше понять, с чем мы имеем дело. Но надо с большой осторожностью распространять результаты модифицированной задачи на исходную.

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

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

Рассмотрим второе заблуждение: Q = (p1*0 + p2*1 + p3*2 + ... + pN*(N-1)) / (N * (1 - p0)). Это неверный ответ, хотя многие были так рады, что легко избежали первого заблуждения, что не задумываясь попались в сети второго.

Обоснование было примерно следующим:
- после того, как один приз убрали, количество призов стало описываться новым набором q0, q1, ... qN,
-- q0 должно быть равным p1 (вероятность того, что сейчас призов ноль такая же, как раньше была вероятность того, что приз ровно один),
-- q1 должно быть равным p2 (вероятность того, что сейчас один приз такая же, как раньше была вероятность того, что призов ровно два),
и т.д.
-- qN равно нулю, так как призов сейчас не более N-1 (один уже вынули),
- но сумма q0+q1+...+qN должна быть 1, поэтому надо «отнормировать» (поделить все эти qi на (1-p0)).
- так мы получили набор вероятностей q0=p1/(1-p0), q1=p2/(1-p0), q2=p3/(1-p0)..., qN=0. Осталось только подставить эти qi в ранее полученную формулу для P.

В этом рассуждении содержится ошибка, поэтому мы получили неправильную формулу для вычисления Q. А раз так, то все следующие выводы могли быть ошибочными (редкие люди смогли правильно ответить на четвёртый вопрос о случае p0=p1=...=pN).

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

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

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

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

Требовать свое

noreply@blogger.com (Илья Весенний) — Tue, 17 Jan 2012 01:13:23 PST

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

Научный редактор журнала «Эксперт» Александр Привалов написал очередную статью об образовании. Мне кажется, с ней стоит ознакомиться каждому, кто растит или планирует растить детей в России.

Приведу несколько цитат.

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

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

Далее вспоминает о похожем и тоже очень важном пласте проблем: «... Стоит подчеркнуть: ничего уникального наш беглый анализ не обнаружил. Так, обернувшись на реформу здравоохранения, мы увидим всё то же самое: и отсутствие системности, и примат бухгалтерии, и беспардонное верховенство чиновника. И то же яростное нежелание слушать кого-либо, кроме самих себя. Вспомните: весной на Форуме медработников доктор Рошаль посмел — в присутствии самого премьера! — высказать несколько критических замечаний: что, мол, хорошо бы наконец обсудить концепцию развития здравоохранения; что не всё, мол, в порядке с врачебными кадрами и проч. Так заслуженного доктора чуть не сожрали («Да кто он такой, этот Рошаль! Да как он смеет! Да по чьему заказу, да на чью мельницу?») — и сожрали бы, кабы не чуть снисходительное заступничество Путина».

Но не всё так плохо. Цитата: «Сейчас в России, по дружным оценкам самых разных людей, от 10 до 15 процентов школ, где детей действительно учат. Дети там не только сдают какие угодно Минобру тесты, но и взаправду получают знания». Понятно, что этого мало. Но хорошо хоть остались такие места, в которых «хранится знание о том, как надо». Наша задача поддержать такие школы и те, которые к ним стараются тянуться. Тогда может их станет не 10-15, а уже 15-20 процентов.

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

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

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

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

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

Невозможное возможно!

noreply@blogger.com (Илья Весенний) — Thu, 12 Jan 2012 20:39:14 PST

Добрый день, дорогие любители теории вероятностей.

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

Итак, Якубович предлагаем нам поднос с N шкатулками (N — натуральное число больше единицы). В каждой шкатулке или находится приз, или вообще ничего нет. Другими словами, есть N шкатулок и сколько-то призов (не больше, чем N), причём в одной шкатулке не может лежать больше одного приза.

Далее состоялся важный диалог:
(Якубович) - Как вы думаете, с какой вероятностью в случайно выбранной шкатулке окажется приз?
(игрок) - Я не знаю, потому что не имею никакой информации о количестве призов в этих шкатулках.
(Якубович) - Верно! Но я сообщу эту информацию: с вероятностью p0 в шкатулках нет призов, с вероятностью p1 в шкатулках 1 приз, с вероятностью p2 — 2 приза и так далее.

Другими словами, игрок знает N (т.к. уже посчитал количество шкатулок на подносе) и только что узнал все вероятности p0, p1, p2 и так далее.

(игрок) - Теперь я могу посчитать. Вероятность того, что в случайно открытой шкатулке будет приз, равна P. (Чему равно P? Это первый вопрос из окончания заметки)
(Якубович) - Отлично. Открывайте шкатулку!

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

(Якубович) - Поздравляю с призом! Теперь, когда призов на подносе стало на один меньше, что стало с вероятностью того, что в случайно открытой шкатулке будет приз?

Тут я предлагаю читателю задуматься. В самом деле, если шкатулок осталось прежнее количество, а призов стало на один меньше, то кажется вполне естественным, что вероятность уменьшилась?.. Да? Точно? Уверены?

Тогда продолжаем наш разговор!

(Якубович) - Какая теперь вероятность найти приз в случайно выбранной шкатулке?
(игрок) - У меня есть все данные, чтобы её посчитать. Получилось Q. (Чему равно Q? Это второй вопрос.)
(Якубович) - Интересно у вас получилось! Выходит, что Q больше P? Вероятность выросла?
(игрок) - Да, она выросла.
(Якубович) - Ну тогда открывайте ещё одну шкатулку
...

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

Вопросы следующие:
1. Какую вероятность P назвал игрок, когда Якубович спросил его о вероятности нахождения приза в случайной шкатулке?
2. Какую вероятность Q назвал игрок после выигрыша, когда Якубович опять спросил его о вероятности нахождения приза в случайной шкатулке?
3. Может ли Q быть равным P? Может ли Q быть больше P? Приведите примеры или способ их построить.
4. Может ли Q быть равным P, если p0=p1=p2=...=pN? Может ли Q быть больше P, если p0=p1=p2=...=pN? Приведите примеры или способ их построить.
5. Почему нам кажется, что Q обязано быть меньше P?

Хорошей вероятностной пятницы!

Антисемейная комедия «О чём ещё говорят мужчины»

noreply@blogger.com (Илья Весенний) — Mon, 09 Jan 2012 02:26:35 PST

Добрый день!

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

Приходил мне такой спам от бездетных знакомых, являющихся единственными в семье, у которых родители тоже являются единственными в семье. Причём речь идёт об обеспеченных людях, которые не догадываются задать самим себе простой вопрос: если в России население убывает из-за того, что доходы от продажи сырья разворованы, то почему же богатые семьи такие маленькие? И тут мы плавно переходим к фильму «О чём ещё говорят мужчины».

Краткое содержание: четыре вполне состоятельных сорокалетних мужчины успели дать жизнь всего двум детям (из первого фильма мы знаем, что две дочки есть только у героя, которого играл Леонид Барац). А остальная их жизнь заполнена обманом близких им женщин, своих друзей и самих себя. Всё.

Это как в фильме «Ирония судьбы. Продолжение» — герои вроде бы выглядят как нормальные люди, но сами давно уже действуют по каким-то звериным правилам. Для них любая подлость выглядит допустимой, потому что они не имеют стыда. Это смотрится мерзко и неестественно.

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

В такие моменты я вспоминаю сериал «Бригада»: ловкие, умные, сильные, решительные и интересные люди притягивают, призывают подражать себе. В таких фильмах традиционно отсутствует столь же притягательный образ нормального человека. Почему-то именно жулики, обманщики, предатели и убийцы показываются выпуклыми и яркими. И не надо на это отвечать словами «люди же не идиоты, они не повторяют то, что видят по телевизору». Разные люди способны на разные действия.

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

Зачем это называть комедией? В моей голове Нонна Гришаева крепко связана с чистым юмором (как Татьяна Лазарева, например), поэтому я очень рад был осознать, что она не участвовала в этой пропаганде обмана близких. Мне приятно думать, что это из-за того, что она решила не сниматься в плохом фильме ни за какие деньги.

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

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

Зрителю должно быть противно ассоциировать себя с любым из героев этой ленты. Если бы фильм говорил что-то вроде «Вот таким неудачником можно стать, если жить, не подключая голову», то я бы поверил, что в этом и была цель авторов. Мол, зритель, пока молодой, посмотри, во что можно превратиться к сорока годам, не повторяй чужих ошибок. Но фильм не говорит, а кричит: «Живи именно так, потому что всё остальное — вообще не жизнь».

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

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

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

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

Начни вчера

noreply@blogger.com (Илья Весенний) — Sat, 31 Dec 2011 00:21:16 PST

Добрый день!

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

Список странных национальных особенностей можно продолжать долго... Но есть одна очень распространённая традиция, которая присуща почти всем народам — начинать что-то делать с первого января.

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

И этот самообман может работать не неделями, а месяцами. Иногда человек в августе позволяет себе говорить «вот с 1 января я с этим завяжу»... Видели такое?

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

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

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

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

Живите счастливо! И начните делать это не с 1 января, а хотя бы прямо сейчас (или даже со вчерашнего дня :)

До встречи в 2012 году!

Аукцион с камнями

noreply@blogger.com (Илья Весенний) — Sun, 25 Dec 2011 21:58:46 PST

Добрый день.

За новогодним столом бывает здорово поиграть в какую-нибудь весёлую игру. Например, можно устроить аукцион, в котором побеждает тот, кто сможет закодировать пару чисел из наибольшего диапазона. Здорово звучит?

Цитата из книги «Что делать, если вас не считают занудой»: «Встретив филологов или историков, расскажите им анекдот про марсианина. Обязательно объясните им, почему это смешно. Убедите их поделиться этим анекдотом с друзьями. Проконтролируйте, чтобы они правильно объяснили своим друзьям, почему этот анекдот смешной».

Но возвращаемся к нашему аукциону. Недавно Константин Кноп напомнил чудесную формулировку (осторожно, там в комментариях сказано уже слишком много!):

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

Мне в ней не нравятся две вещи:
- наших разведчиков назвали шпионами,
- задана граница 1700.

Поэтому давайте чуть-чуть переформулируем задачу:
- два человека знают целые числа из диапазона от 1 до N,
- они поочерёдно пишут на доске положительные целые числа, пока сумма всех записанных чисел не станет равна 26,
- давным давно они учились в одном классе, поэтому заранее договорились, как кодировать данные.

Вопросы:
1. Как они могли бы обменяться парой чисел при N = 1700?
2. Для какого максимального N вы можете придумать способ кодирования?

Эта задачка хороша тем, что когда кажется, что «ну уж дальше N увеличить невозможно», обязательно находится кто-то, кто опять смог поднять верхнюю границу :)

(Кстати, не так давно мы решали другую забавную школьную задачку, имеющую отношение к теории кодирования)

Хорошего начала предпраздничной недели!

Как считать вероятности?

noreply@blogger.com (Илья Весенний) — Mon, 19 Dec 2011 23:27:02 PST

Добрый день!

Неделю назад мы провели небольшой опрос на тему «Проще выиграть три раза из четырёх или пять раз из восьми?»

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

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

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

Короче, разных мнений много, но разводить демократию для выбора правильного ответа мы здесь не будем. Давайте сначала выясним примерный ответ, проведя эксперимент (на JS, как обычно):

<script type="text/javascript">
n = 100000;  nb3of4 = 0;  nb6of8 = 0;  nb5of8 = 0;
for (i = 0; i < n; i++) {
  nbWin = 0;
  for (j = 0; j < 4; j++)
    if (Math.random() > 0.5)
      nbWin++;
  if (nbWin == 3)
    nb3of4++;
  for (j = 4; j < 8; j++)
    if (Math.random() > 0.5)
      nbWin++;
  if (nbWin == 5)
    nb5of8++;
  if (nbWin == 6)
    nb6of8++;
}
document.write('pA = ' + nb3of4/n + ', pB = ' + nb6of8/n + ', pC = ' + nb5of8/n);
</script>

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

Это простая программа проводит 100000 следующих экспериментов:
сначала подбрасывает монетку четыре раза (и если три раза выпал «орёл», то увеличивает на один счётчик nb3of4), а потом подбрасывает её ещё четыре раза (и тут уже увеличивает на единицу nb5of8 или nb6of8, если победа была ровно пять или ровно шесть раз из восьми, соответственно). В последней строке программа выводит три искомых числа (отношение числа побед заданное число раз к общему количеству проведённых экспериментов).

У меня этот эксперимент дал следующие результаты:
  pA = 0.24865,
  pB = 0.10918,
  pC = 0.21898.

Вроде бы уже понятно, что вероятность события А больше В, а В больше Б, но как раз тут важно не остановиться, а понять, что означают эти числа. Давайте попробуем в первой строке программы заменить число 100000 на 10 (т.е. заметно сократим число экспериментов). У меня получались следующие результаты при n=10:
pA = 0.2, pB = 0, pC = 0.1,
pA = 0.2, pB = 0, pC = 0.5,
pA = 0.1, pB = 0.2, pC = 0.3,
pA = 0.4, pB = 0, pC = 0.2,
pA = 0.3, pB = 0.1, pC = 0.4.

Как видите, в первой и четвёртой строчках наша теория «pA > pC > pB» подтвердилась, а в трёх других строчках не подтвердилась. Что это означает? А это означает это, что мы провели эксперимент с низкой степенью достоверности.

Если вы читали результаты социологических опросов, то могли обратить внимание на примерно такую фразу: «Статистическая погрешность подобных опросов не превышает 3.4%». Люди, изучившие математическую статистику, знают, как вычислить вероятность того, что результаты опроса нескольких тысяч человек не слишком отличаются от результатов опроса всех граждан страны. Интуитивно мы понимаем, что по мнению 10 случайных опрошенных нельзя надёжно понять, что думают люди в стране, поэтому хотим увеличить число опрошенных. Проблема в том, что всех опросить почти невозможно (очень затратно), поэтому приходится искать компромисс.

Так и у нас с этой задачкой: если мы проводим всего 10 экспериментов, то вероятность получить правильный результат не очень высока. Преимущество же наше в том, что мы можем «опросить» всех, что позволит получить совершенно точный ответ.

Итак, кто же эти все? Это элементарные события. Мы можем перечислить все возможные равновероятные ситуации для нашей игры, а потом посчитать количество интересных. Например, если мы будем обозначать победу единицей, а поражение нулём, то список элементарных исходов для четырёх бросков монеты будет выглядеть так:
- 0000,
- 0001,
- 0010,
- 0011,
- 0100,
- 0101,
- 0110,
- 0111,
- 1000,
- 1001,
- 1010,
- 1011,
- 1100,
- 1101,
- 1110,
- 1111.

Поскольку монетка симметричная, а результаты предыдущих бросков не влияют на следующие, то все эти 16 ситуаций имеют равную вероятность. И так как в четырёх случаях из шестнадцати (выделенные строки) победа случается ровно три раза (три единички в строке), то и вероятность таких событий 4/16 = 0.25. Примерно это число мы и увидели в эксперименте при большом n.

Аналогично можно перечислить все расклады для 8 бросков монетки:
- 00000000,
- 00000001,
...
- 11111110
- 11111111.

Далее можно просто посчитать количество строк, в которых ровно 5 и ровно 6 единичек. Знатоки двоичной системы счисления уже давно поняли, что строк будет 2^8 = 256. Понятно, что работа была бы большая, но вполне выполнимая. Но давайте лучше найдём более простой способ посчитать число таких строк.

Начнём с «6 из 8». Нам проще будет посчитать, в каком количестве строк ровно два нуля (это то же самое, что и ровно 6 единиц). Первый нолик можно поставить на одно из восьми мест, а второй нолик — на одно из оставшихся семи мест. Получается, что два нолика можно разместить на восьми местах 8*7 способами. Надо только учесть, что каждый расклад мы посчитали дважды (сначала первый нолик левее второго, а потом на тех же местах второй нолик левее первого). Поэтому наш ответ надо ещё разделить на 2. Получается, что вероятность выиграть 6 раз из 8 равна 4*7/256 = 28/256 = 7/64 = 0,109375.

Теперь понятно, как посчитать число строк с пятью единичками на восьми местах. Будем считать, сколько у нас строк ровно с тремя нулями:
первый нолик можно поставить одним из 8 способов, второй — одним из 7 оставшихся способов, а третий — на одно из шести свободных мест. Получается 8*7*6 вариантов. Но здесь мы опять получили завышенную оценку, так как посчитали каждую возможную конфигурацию 6 раз (три нолика могут занять одни и те же позиции шестью способами: абв, авб, бав, бва, ваб, вба). Это значит, что наш ответ надо поделить на 6. Получается, что вероятность выиграть 5 раз из 8 равна 8*7/256 = 56/256 = 7/32 = 0,21875.

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

Дело в том, что в теории вероятностей ориентируется не так уж и много людей, но «применить здравый смысл» и «порассуждать о нормальном распределении» готовы очень многие (хоть и не готовы сформулировать определение нормального распределения). Я не спорю, иногда некорректные рассуждения приводят к верному ответу. Но надо помнить, что нередко правдоподобные о вроде бы очевидные мысли уводят от истины и мешают к ней вернуться. Поэтому я считаю правильным начинанием введение в ЕГЭ по математике одной простой задачки на теорию вероятностей. Это даёт надежду на постепенное движение к тому, что почти все школьники России будут легко справляться с элементарными вопросами о вероятностях.

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

Вероятность победы

noreply@blogger.com (Илья Весенний) — Sun, 18 Dec 2011 06:52:51 PST

Добрый день!

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

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

Я прошу вас написать в комментариях что-то вроде «вероятности Б и В одинаковы, а про вероятность А не знаю, но вроде бы должна быть меньше Б» (не это, а то, что подсказывает ваш здравый смысл).

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

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

UPD: опубликовано продолжение разговора.

Надёжная поломка

noreply@blogger.com (Илья Весенний) — Mon, 05 Dec 2011 01:53:20 PST

И даже если завтра появится телефон, аккумулятор
которого держит заряд 1000 лет, уже через месяц его придётся
поменять на новый, который держит заряд 2000 лет.

Добрый день!

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

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

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

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

Для одного гвоздя задачка решается элементарно.
Для N=2 многие уже решали в детском саду/начальной школе.
А как решить для N>2?
А можно ли решить так, чтобы длина верёвки не зависела от N экспоненциально?

Хорошего вам решения!

Почему я не люблю курильщиков?

noreply@blogger.com (Илья Весенний) — Sun, 18 Dec 2011 20:04:22 PST

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

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

Вроде бы не очень сложные навыки и мысли, так ведь?

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

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

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

Но причина неприязни есть! Один из важнейших недостатков курильщиков — они приносят прибыль производителям сигарет. Смешно звучит? Ну да, раз существуют, значит прибыльны. Беда в том, что если что-то приносит прибыль, то любой нормальный бизнесмен постарается прибыль увеличить или хотя бы поддержать. А как можно поддерживать сигаретный бизнес? Надо привлекать новых клиентов (вместо постепенно выбывающих). И эффективнее всего окучивать именно детей, потому что
- их проще обмануть разговорами о «крутости»,
- чем раньше начнут курить, тем больше прибыли принесут за свою жизнь.

Рекомендую прочитать на эту тему статью «ОАО «Детский табак». Саму статью цитировать здесь не буду, но советую ознакомиться с детскими текстами на промо-сайтах этих сигарет (например, smokingirl и kiss-club). На этих форумах дети прямо указывают, что им, например, 12 лет, после чего спрашивают совета (как обмануть учительницу, которая не только застукала ребёнка за курением, но и собирается позвонить родителям).

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

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

А почему вы любите или не любите курильщиков?

Три разнородные ссылки

noreply@blogger.com (Илья Весенний) — Sat, 19 Nov 2011 23:03:30 PST

Добрый день!

Сегодня в нашей традиционной рубрике «Три чего-нибудь» я предлагаю три ссылки.

1. В записи «Послесловие к самоссылающимся задачам» Константин Кноп предлагает перевод на русский язык хорошей подборки таких задачек. Прекрасный пример интересной и достаточно сложной задачки — восстановить все буквы в предложении «Это предложение содержит ___ слов(?), ___ ___ слог(?) и ____ ____ букв(?)» (вопросы в скобках означают одно из возможных окончаний).

Гораздо проще найти ответы на следующие вопросы (и куда интереснее подобные вопросы придумать самому):
- Чему равна площадь квадрата, периметр которого равен 16?
- Какой долей ведра являлась древнерусская мера объема «четверть»?
- Какова доля гласных в слове «половина»?

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

3. А в разборе «Про политику: строить vs. ломать» приводится анализ распространённых мифов о высказываниях/планах некоторых политиков. Мол, они все идиоты, которые ещё и нередко проговариваются о своих антинародных планах. Вырвать слова из контекста и растиражировать их через юмористические ресурсы — дело не очень сложное... Тем более, что «журналисту» достаточно эти слова просто выдумать. И происходит это по одной простой причине: очень многие не только не станут проверять правдивость сообщения, но и не вспомнят, что каждый месяц возникает несколько одинаковых новостных поводов об очередных страшилках вроде «вместо винтовок министерство обороны закупает бадминтонные ракетки». Опровержения всегда звучат тише агитационных материалов, поэтому желающие всегда имеют повод радостно наслаждаться ужасами, не нагружая зря мозг. И, что очень досадно, весь этот неконструктивный визг успешно вытесняет темы, которыми на самом деле надо заниматься.

Хорошего воскресенья!

Пробуй!

noreply@blogger.com (Илья Весенний) — Mon, 14 Nov 2011 01:49:50 PST

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

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

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

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

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

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

Чему нас учит эта задачка? Тому, что иногда надо попробовать решить, а не просто «читать условие». Первая попытка сразу указала нам, где надо менять. И внезапно оказалось, что менять мы можем единственным образом. Т.е. уже вторая попытка сразу привела нас к идеальному решению.

Теперь разберёмся с малярами и перчатками. Опять же, надо пробовать, а не бояться неведомого. У одной перчатки две стороны, а маляры испачканы четырьмя разными цветами, поэтому одной перчатки заведомо не хватит (надо как минимум две). А что можно сделать с двумя перчатками? Есть следующие варианты первого действия:

1) Надеть перчатки на руки маляров, идущих навстречу друг другу,
2) Обе перчатки надеть на руки маляров, идущих в одну сторону.

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

Если же мы пойдём по второму пути, то опять есть два варианта:

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

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

Опять же, мы просто рассмотрели все возможные варианты, пытаясь не потратить больше двух перчаток. Мы попробовали, мы честно расписали возможности. Часто этого достаточно. Безусловно, настоящие сложные задачи не позволят одолеть себя так легко. Но это не значит, что не надо развивать в себе способность справляться с простыми. Когда средние задачи покажутся вам простыми, тогда сложные покажутся средними :)

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

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

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

Исключения из исключений

noreply@blogger.com (Илья Весенний) — Thu, 10 Nov 2011 03:20:55 PST

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

За прошлый разговор с ним мы выбрали язык программирования (Javascript), определили задачу (преобразовать английское существительное из единственного числа во множественное), сделали простейшую систему тестирования (собрали небольшую тестовую базу вопросов-ответов из интернет-тестов) и начали реализовывать функцию, решающую задачу (пока эта функция просто добавляет «s» к любому слову).

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

Что же они сделали? Не очень много, но этим хочется поделиться:

1. Расширили тестовую базу в полтора раза (взяли примеры из википедии). В процессе этого расширения осознали, что надо слегка переделать тестовую систему, так как бывают слова, имеющие более одной формы множественного числа (например, можно писать и «volcanoes», и «volcanos»), а сейчас это никак не поддержано. Новая версия содержит 59 вопросов (и ответы на 27 из них считаются неправильными).

2. Гуманитарий рассказал, что о множественном числе существительного имеет смысл говорить, если это существительное является исчисляемым. Более того, невозможно без контекста определить, с исчисляемым ли существительным мы имеем дело. Например, «coffee» обычно считают неисчисляемым. Но если мы говорим не о кофе вообще, а о чашках кофе, то вполне можно говорить «two coffees» (как и «two cups of coffee»). Поэтому стоит добавить вывод предупреждения хотя бы для распространённых неисчисляемых существительных. Два заинтересованных человека показали высокую самостоятельность — они не только нашли в интернете список распространённых неисчисляемых существительных, но и написали функцию isUncountable(), определяющую, является ли существительное неисчисляемым:

function isUncountable(iNoun) {
    var aCommonUncountable = new Array(
        "water", "tea", "coffee", "milk", // Liquids
        "air", "oxygen", "hydrogen", "nitrogen" // Gases
        // etc
    );
    for (var i = 0; i < aCommonUncountable.length; i++)
        if (aCommonUncountable[i] == iNoun)
            return true;
    return false;
}

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

3. Ещё они очень захотели добавить несколько новых простых правил к нашей функции getPlural(). Например, надо научиться определять, оканчивается ли строка на «ch», «sh», «s», «z» или «x». В таких случаях почти всегда для получения множественного числа надо добавить «es». Реализация этой проверки позволила бы заметно продвинуться в улучшении качества результатов.

Тогда я рассказал ребятам о регулярных выражениях. Конечно, разговор был очень поверхностным. Сначала мы расширили нашу функцию, пользуясь методом substr() (т.е. для каждой строки проверяли, совпадают ли два её последних символа с «ch», совпадает ли её последний символ с «s» и так далее. А потом мы разобрались, как всё это многословное безобразие можно заменить одной строкой регулярного выражения:

function  getPlural(iSingular) {
    if (/ch$|sh$|x$|s$|z$/.test(iSingular))
        return iSingular + 'es';
    return iSingular + 's';
}

С этим дополнением программа стала выдавать неправильный результат на 22 тестах из 59. Стало лучше, но ещё есть куда двигаться, так как осталось ещё несколько правил, которые предстоит поддержать, да и исключения (слова вроде «woman» — «women») надо отдельно обрабатывать.

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

В прошлой заметке мы убедились, что нарисовать табличку 2 на 2 клетки очень легко, поэтому сейчас мы заполним эти клетки следующим образом

Singular: [поле ввода]
Plural: [результат работы функции]

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

<script type="text/javascript">

function getPlural(iSingular) {
  if (/ch$|sh$|x$|s$|z$/.test(iSingular))
    return iSingular + 'es';
  return iSingular + 's';
}

function writePlural() {
  document.getElementById("plural").innerHTML = getPlural(document.getElementById("singular").value.toLowerCase());
}

</script>

<table border=0>
  <tr><td>Singular:</td><td><input id="singular" onkeyup="writePlural()" value="test"></td></tr>
  <tr><td>Plural:</td><td><div id="plural">tests</div></td></tr>
</table>

(сохраните этот код в файл plural.html, после чего откройте браузером, чтобы проверить, как всё работает)

Как видите, в верхней правой ячейке таблицы мы поместили поле ввода (тэг input), из которого при изменении содержимого (на самом деле, при отпускании кнопок клавиатуры, так как используется обработчик onkeyup) вызывается наша новая функция writePlural(). Эта функция устроена очень просто — в нижнюю правую ячейку она записывает результат работы нашей функции getPlural(). Единственная тонкость — мы добавили перевод всех символов в нижний регистр (вызываем метод toLowerCase()), так как функция getPlural() пока не готова только к словам, записанным заглавными буквами.

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

На этом мы и остановились. Решили, что в следующий раз надо будет сделать следующее:
1) поддержать механизм слов-исключений в функции getPlural() («woman» — «women»),
2) добавить остальные правила построения множественного числа по единственному,
3) расширить тестирующий код для поддержки нескольких правильных ответов («volcanoes», и «volcanos»),
4) решить, как лучше всего использовать результат функции, определяющей, является ли существительное неисчисляемым (выводить подсказку/предупреждение?).

А как бы вы решали эту же задачу со школьниками?

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

Бессистемность

noreply@blogger.com (Илья Весенний) — Thu, 10 Nov 2011 03:20:32 PST

...Мы называемся школой танцев.
Но мы не учимся, мы танцуем...
(c) Михаил Щербаков

Добрый день.

1. Предисловие.

Одни люди настаивают на последовательном и системном обучении, критикуя любителей «салата» из разнородных навыков, а другие справедливо возражают, что от некоторых строгих учебников и уснуть можно, а спящий человек медленно учится. Кто же из них прав? Тут всё зависит от обучаемых.

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

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

2. Задача.

Можно было назвать эту заметку «Множественное число в английском языке и javascript». Или вот другое подходящее длинное название: «Регулярные выражения, js и английский язык в одном флаконе».

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

Итак, в нынешней серии заметок мы вспомним/узнаем следующие простейшие вещи:
1) правила формирования множественного числа существительных в английском языке,
2) создание простейшей таблички и формы в HTML,
3) элементарную работу со строками в Javascript,
4) подход к тестированию программного обеспечения.

Почему Javascript, а не какой-нибудь «продвинутый» язык? Да потому что Javascript сейчас есть почти в любом устройстве, умеющем открывать сайты. Поэтому каждый человек может мгновенно посмотреть на результат работы своей программы, написанной на коленке, не задумываясь об установке среды разработчика и прочих сложностях.

3. К делу.

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

— Что будем программировать?
— Не знаю.
— Что-нибудь уже писал на каком-нибудь языке?
— Только свою страничку в интернете на html. Но это же не язык программирования?
— Верно. Но хоть что-то. С Javascript что-то пробовал?
— Да, поставил код счётчиков и гостевой книги на свою страничку.
— Отлично. Давай выберем то, что было бы интересно сделать! Захватывающую игру написать будет трудно, поэтому предлагаю автоматизировать что-нибудь, что пока плохо получается делать головой. Есть такое на примете?
— Да, мы сейчас на английском прошли множественное число, а там столько правил и исключений! Как бы это всё понять?(да, конечно это было после 5 минут расспросов)

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

— Умеешь сделать простую табличку два на два?
— Запросто! Вот так:

<table>
<tr><td>left-top</td><td>right-top</td></tr>
<tr><td>left-bottom</td><td>right-bottom</td></tr>
</table>

— Отлично! Теперь давай учиться делать функции. Потом мы реализуем серьёзную функцию, которая будет преобразовывать существительные из единственного числа во множественное, но пока нам надо создать простую функцию-заглушку. Это нам нужно, чтобы научиться её тестировать.
— А как?
— Создай файл plural.html со следующим кодом, а потом открой его браузером

<script type="text/javascript">
function getPlural(iSingular) {
return iSingular;
}
document.write('Test: ' + getPlural('test'));
</script>

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

Уже через 15 минут у нас была табличка из четырёх десятков тестовых пар «fork-forks», «book-books» и так далее. Я объяснил, что такое массивы, как можно их описывать в Javascript, поэтому довольно скоро наш файл plural.html расширился функцией, проверяющей, совпадает ли ответ из теста с ответом нашей функции getPlural (а совпадать почти никогда не должно, потому что функция ещё ничего не делает). Конечно, пришлось многое показать и рассказать, но школьник попался толковый, поэтому вникал быстро. Скоро наша программа приобрела следующий вид:

<script type="text/javascript">
function getPlural(iSingular) {
  return iSingular;
}

function testPlural() {
  var aSingular = new Array("fork", "watermelon", "dress", "bridge", "book", "garage", "store", "pencil", "horse", "bay", "turkey", "Japanese", "coin", "staple", "fish", "key", "pepper", "wolf", "kitten", "foot", "sky", "oasis", "sit-in", "copy", "commando", "spy", "forget-me-not", "cloud", "watch", "factory", "man", "foot", "mouse", "woman", "tooth", "louse", "child", "ox", "goose");
  var aPlural = new Array("forks", "watermelons", "dresses", "bridges", "books", "garages", "stores", "pencils", "horses", "bays", "turkeys", "Japanese", "coins", "staples", "fish", "keys", "peppers", "wolves", "kittens", "feet", "skies", "oases", "sit-ins", "copies", "commandos", "spies", "forget-me-nots", "clouds", "watches", "factories", "men", "feet", "mice", "women", "teeth", "lice", "children", "oxen", "geese");
  var nbErr = 0;
  for (var i = 0; i < aSingular.length; i++) {
    if (aPlural[i] != getPlural(aSingular[i])) {
      nbErr = nbErr + 1;
      document.write('For the noun ' + aSingular[i] + ' the plural form must be ' + aPlural[i] + ', but getPlural() returned ' + getPlural(aSingular[i]) + '<br>');
    }
  }
  document.write('<b>Number of errors: ' + nbErr + ', number of tests: ' + aSingular.length + '</b>');
}

testPlural();
</script>

Как видите, большая часть этой программы — это таблица существительных (единственное число хранится в массиве aSingular, а множественное — в массиве aPlural). Дальше в цикле for проводится проверка для каждого элемента массива aSingular, совпадает ли ответ нашей функции getPlural() с эталонным ответом, хранящимся в массиве aPlural. Если не совпадает, то программа на единичку увеличивает счётчик ошибок nbErr.

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

— Отлично, программа работает. Но 37 ошибок из 39 — это очень много. Давай остановимся на более весёлой ноте. Как обычно образуется множественное число в английском языке?
— Добавляется «s».
— Верно! Давай научим нашу функцию хотя бы этому. Ты уже умеешь склеивать строки, поэтому всё можешь сам.
— Да, сейчас попробую. Там же всего одну строчку надо поправить

function getPlural(iSingular) {
return iSingular + 's';
}

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

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

Ну а я скоро опубликую продолжение этой истории.

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

Маляры и котлеты

noreply@blogger.com (Илья Весенний) — Thu, 13 Oct 2011 22:25:20 PDT

- Илья, где ты пропадаешь две недели?
- В глубоком-глубоком роуминге :)

Но я вернулся, почти всем ответил на почту и комментарии, а теперь, извините, поделюсь неприятным впечатлением от Питерского Пулково-1. Несколько лет я не был в этом дивном месте, поэтому успел подзабыть его бардак и грязь. Если бы номер гейта на билете соответствовал реальному номеру двери, от которой автобус повезёт к самолёту, если бы табло над гейтом правильно указывало номер рейса, то сотрудницы аэропорта не были бы вынуждены кричать: «Рейс ###, подходите сюда, а рейс ### отойдите, сейчас мы не вас сажаем. Да, мы знаем, что на табло сейчас указан ваш город, поэтому не читайте табло». Зачем я это пишу? Пару лет назад помогло же :) А пока, если меня спросят европейцы, через какую из столиц лучше влетать в Россию, то я однозначно назову Москву. Как минимум, в Москве работают лифты, хорошо светят лампочки и моют туалеты, а в Пулково-1 в тёмных коридорах неподвижно стоят грязные эскалаторы, о которых сразу забываешь, посетив уборную. Злые языки утверждают, что ремонта там не было со времён блокады Ленинграда.

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

1. Много лет назад у нас была задачка о хрупких шариках: Есть стакан с очень дорогими одинаковыми хрупкими шариками из очень прочного материала. И есть лестница с сотней ступенек. Какой минимум шариков придётся разбить, чтобы выяснить предельную высоту (число от 1 до 100 — бросаем со ступенек), с которой можно ронять шарики целыми (т.е. чтобы они не разбились)?

2. Старинная детская задачка о готовке звучит так: На одной сковороде может поместиться не более 2 котлет. Одна сторона котлеты жарится 1 минуту. За какое минимальное время можно пожарить три котлеты с 2-х строн.

3а. Два маляра столкнулись на дороге с другими двумя малярами. Этикет обязывает каждого из первой пары поздороваться с каждым из второй пары, но руки у каждого маляра испачканы в краске своего цвета. А так как маляры не хотят пачкать руки в краске другого цвета, то у них есть несколько чистых перчаток. Какое минимальное количество перчаток они будут вынуждены испачкать, чтобы поприветствовать друг друга?

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

(последние две задачки своевременно напомнил Антон, а я чуть-чуть поменял формулировки)

Пожалуйста, напишите в комментариях статус по этим задачкам примерно в таком виде:
   1. Помню, ответ x,
   2. Давно знаю, ответ y,
   3. а) тоже слышал, ответ z1, б) первый раз слышу, ответ z2.

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

Вспоминаем тригонометрию

noreply@blogger.com (Илья Весенний) — Thu, 29 Sep 2011 20:52:34 PDT

Почти все задачи, которые мы решаем в течение жизни, не являются настоящими. В каком смысле? Сейчас поясню.

Редкому человеку даётся шанс ответить на новый вопрос, от которого зависит дальнейшее развитие, например, человечества. Во-первых, необходимо справиться с огромным количеством учебных задач, чтобы подняться на уровень настоящих проблем. Это только в американских фильмах главный герой может «усилием воли» справиться с проблемой, о которой раньше никогда не думал. В реальной же жизни всё куда скучнее — необходимо очень долго и целенаправленно работать, чтобы продвинуться в изучении имеющих смысл, но ранее не исследованных постановок. Во-вторых должно очень повезти с задачей (окружающая среда должна натолкнуть на подходящую проблему), так как ответы далеко не на все вопросы а) возможны, б) нужны.

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

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

Если же в этот момент изучают тригонометрию, то тоже есть куда развернуться. В хороших школах учитель добивается не банального решения ограниченного набора типовых задачек, а понимания темы. Например, осваивая тригонометрию, не надо заучивать правила sin(-x)=-sin(x), не надо запоминать cos(0)=1 и так далее. А надо всего лишь разобраться с соответствием углов точкам единичной окружности, а тригонометрических функций точкам нескольких прямых. Если с этим разобраться, то все те «сложные для запоминания правила» станут простыми и естественными (и как будто сами «запомнятся»).

Но давайте на секундочку отойдём от игр с единичной окружностью, есть же ещё прямоугольный треугольник. В самом деле, слово тригонометрия образовано от двух греческих слов trigōnon «треугольник» + metron «измерять». В хороших школах кроме игр с единичной окружностью ещё обязательно играют с прямоугольным треугольником. Полезным бывает анализ функций arcsin(sin(x)), cos(arccos(x)), ctg(arctg(x)), cos(arctg(x)) и так далее. А для него стоит вспомнить определения тригонометрических функций острых углов: синусом/косинусом угла a называется отношение противолежащего/прилежащего катета к гипотенузе (в любом прямоугольном треугольнике, один из углов которого равен a).

Как, например, понять, как устроена функция sin(arctg(x))? Достаточно знать всего две вещи: теорему Пифагора и определение тригонометрических функций через отношение сторон в прямоугольном треугольнике. Давайте рассмотрим треугольник со сторонами 1, sqrt(n), sqrt(n+1). Синус верхнего угла в нём равен 1/sqrt(n+1), а тангенс того же угла равен 1/sqrt(n). Соответственно, sin(arctg(1/sqrt(n))=1/sqrt(n+1). Получается, что этой парой функций можно наезжать на 1/sqrt(n) сколько угодно раз, как бы увеличивая n под корнем — sin(arctg(sin(arctg(1/sqrt(n))))=1/sqrt(n+2) и т.д.

Что нам это даёт? Для задачки с тремя двойками нам как раз нужно было научиться увеличивать натуральное число на единицу произвольное число раз. Тут мы получили не совсем тот результат, но у нас ещё и не все двойки потрачены :)

В качестве n мы можем взять 2/2, тогда у нас останется одна двойка, чтобы получить x из 1/sqrt(x).

Так как 0 и 1 мы получать умеем ((2-2)*2 и (2/2)^2, например), то давайте разберёмся со всеми остальными натуральными числами:
2 = sin(arctg(2/2))^-2,
3 = sin(arctg(sin(arctg(2/2))))^-2,
4 = sin(arctg(sin(arctg(sin(arctg(2/2))))))^-2,
и так далее.

Опять же, этот результат совершенно не имеет значения для народного хозяйства. Но при освоении тригонометрии научиться оперировать такими «крокодилами» очень даже полезно. Хотите ещё полезнее? Тогда давайте откажемся от двух двоек — оставим только одну. Итак, задачка Московской математической олимпиады 2010 года за 10 класс: Можно ли, применяя к числу 2 функции sin, cos, tg, ctg, arcsin, arccos, arctg, arcctg в любом количестве и в любом порядке, получить число 2010? (спасибо автору, вовремя показавшему ссылку на эту задачу). На странице 28 документа с решениями приведён разбор. Как обычно, я рекомендую открывать его только после самостоятельного решения задачи.

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

Вспоминаем логарифмы

noreply@blogger.com (Илья Весенний) — Wed, 28 Sep 2011 21:54:17 PDT

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

Шаг первый — учимся делать хоть какой-то ход. В нашем случае всё просто: нужно было придумать какую-нибудь последовательность действий над тремя цифрами 2, чтобы получить натуральное число, которое ранее не было записано другими участниками аукциона.

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

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

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

Наличие унарных функций существенно меняет смысл игры. Если раньше надо было искать такие наборы действий, которые приводят к новому натуральному числу, то теперь достаточно взять самый большой результат конкурентов, после чего просто «наехать» на него факториалом. Получится натуральное число, которое ранее заведомо никто не получал.

Тут, правда, проявляется забавное ограничение: в правилах чётко сказано, что надо предъявить полученное натуральное число, если хочется сделать ход. Поэтому, например, ход (22²)! невозможен (так как в его записи почти 26 миллионов цифр, а такие длинные комментарии недопустимы на этом блоге). Но если говорить о строгой математической постановке, то, конечно, подход, например, с факториалами, полностью уничтожает аукцион.

Остаётся искусственно усложнить игру — научиться получать любое натуральное число (или понять, какие натуральные числа невозможно получить из трёх двоек). Ранее мы уже поняли, что если пользоваться только функциями от двух аргументов, то удастся получить натуральные числа из очень ограниченного набора. Это значит, что для получения произвольного натурального числа придётся применять произвольное число раз функции одного аргумента. А какие такие функции знает школьник? Перечислим их:

Факториал,
Квадратный корень,
sin, cos, tg, ctg,
arcsin, arccos, arctg, arcctg.

Давайте попробуем что-нибудь сконструировать из них. С факториалом ничего хорошего в голову не приходит (уж больно неудобная функция для точных действий), поэтому давайте разберёмся с квадратным корнем. Вот если мы N раз «наехали» квадратным корнем на 2, то какое число получится?
sqrt(sqrt(...(sqrt(2)...)) = 2^(1/(2^N)) (т.е. корень из двойки 2^N степени).

Что можно сделать с таким числом? Сразу чешутся руки применить к нему функцию log. Только как это лучше сделать? Можно взять логарифм по этому дикому основанию от двойки. Напомню, что логарифм числа b по основанию a определяется как показатель степени, в которую надо возвести основание a, чтобы получить число b.

Другими словами, из двух двоек, логарифма и N операций корня мы можем накрутить уже достаточно интересную конструкцию. Сколько корней мы поместим в основание логарифма, такую степень двойки и получим. Удобно? Не то слово! Из двух двоек мы научились получать 2^N (для произвольного натурального N).

Это уже очень хорошо. Но можно попробовать продвинуться дальше — попробовать вытащить из 2^N само число N. У нас же ещё осталась одна двойка, а логарифмом мы пользоваться не разучились, верно? Поэтому давайте «наедем» на это число 2^N функцией логарифм по основанию 2. Она как раз и вернёт нам N. Получается, что мы можем из трёх двоек, двух логарифмов и N квадратных корней получить произвольное натуральное число N.

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

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

Дорога в никуда

noreply@blogger.com (Илья Весенний) — Mon, 12 Sep 2011 04:20:31 PDT

Добрый день.

Давайте зайдём издалека. Вот почему многие люди знают, что 404 является кодом ошибки «Не найдено» в стандарте HTTP? Можно, например, задать любой поисковой системе вопрос «site:bash.org.ru/quote 404», чтобы увидеть цитаты с этим числом («сдал куртку в гардероб и получил номерок 404», «я понимаю, когда отдел ИТ отказывается устанавливать сервер в кабинете № 404», «До чего интернет довел - раньше люди боялись числа 666, теперь вздрагивают при виде числа 404» и так далее).

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

Забавно бывает в статье какой-нибудь ленты.ру или газеты.ру обнаружить ссылку на более раннюю их же статью (наверное, с близким по духу сюжетом), которая уже недоступна. Ну что за ~~идиоты~~ таланты?! Зачем каждый год менять формат адресов статей? Из-за этого ломаются все старые страницы, а лучше не становится. Мне регулярно в комментариях к старым заметкам пишут, что такая-то ссылка больше не работает. И тогда приходится редактировать свой старый текст (иногда удаётся найти новый адрес того материала, на который стояла ссылка, но чаще убираю, потому что уже не могу вспомнить, на что именно ссылался несколько лет назад). И это бывало с разными ресурсами: с новостными сайтами, с блогами, с интернет-магазинами (год назад Proball был спонсором конкурса, а с тех пор я уже несколько раз правил ссылку на главный приз, потому что они её постоянно меняли — теперь оставил только ссылки на главную страницу магазина).

К чему приводит эта манера из здоровой работающей страницы с полезным кому-то текстом/изображением делать ответ «404. Страница не найдена»? К тому, что ссылаться на чей-то материал хочется всё меньше, а скопировать его себе — всё больше. Давайте возьмём первую попавшуюся (не особенно популярную) историю о корявом переводе, которую легко найти по запросу «Кулверстукас и Крокодилас Генас». Гугл знает пару тысяч мест, куда её растиражировали! И если бы я захотел этой историей с вами поделиться, то я бы тоже не стал ставить ссылку ни на один из этих двух тысяч сайтов, так как в любой момент любой из таких адресов может смениться (плавали — знаем), из-за чего окажется, что уже я направляю вас в никуда.

Как решать это создателям сайтов? Да всё давно придумано (и нормальные администраторы сайтов так и делают): кроме ответа 404 есть же ещё ответ 301 («перемещено туда-то»). Другими словами, если владельцу сайта вдруг загорелось сменить адреса вида /2011/sent/12/ на /11/09/12/, то нет никакой сложности в организации 301-перенаправления со старых адресов на новые. И тогда люди, когда-то давно ~~сделавшие глупость~~ добавившие себе эту страничку в «Избранное» или поставившие на неё ссылку со своего сайта/блога, не окажутся внезапно у сообщения «Вам здесь не рады».

Дорога в никуда — это не только ссылка, установленная на несуществующую страницу. Дорога в никуда — это безудержное тиражирование текстов, изображений, видео- и аудиороликов. Объём данных, доступных для скачивания в сети, в тысячи раз превышает объём уникальных данных. Интернет давно стал свалкой (так как ценной информации всегда было относительно мало), но за последнее десятилетие развелось столько способов почти автоматически «перепостить» ~~бесплатно online~~ в кучу мест, что сеть прямо заросла копиями. Почти на любой поисковый запрос google/yandex/... предложит нам на выбор одну из нескольких одинаковых страниц. Но мы же хотим выбрать лучшую из нескольких разных! И это происходит не из-за ленивости поисковых машин (они многое делают для борьбы с дублями), а от привычного копирования чужих материалов вместо проставления ссылок на исходники.

Вопрос авторам и администраторам блогов/сайтов: как вы боретесь с тем, что ссылки с ваших ресурсов постепенно теряют актуальность? Я могу написать скрипт, который обнаружит все ссылки, ведущие на несуществующие страницы, но не всегда могу их исправить, так как достаточно трудно вспомнить, что же раньше было по тем адресам...

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

Аукцион «Три двойки»

noreply@blogger.com (Илья Весенний) — Thu, 08 Sep 2011 22:49:35 PDT

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

Например, бывает игра «аукцион скелетик», которая начинается с того, что ведущий называет несколько согласных букв, а игроки называют слова русского языка, состоящие только из этих же согласных (в том же количестве, но любом порядке) и произвольного числа букв, не являющихся согласными. Ведущий может дать тему «ТПР», а игроки будут называть «топор», «ропот», «пират», «партия» и так далее. Если возникает слишком большая пауза (например, более минуты), то игра останавливается, а последний назвавший слово объявляется победителем.

В таких играх можно сразу же называть новый корректный ответ, как только его придумал, а можно «придержать» его (надеясь, что никто другой до него не догадается). Т.е. есть резон называть свои варианты как можно позже, но при этом появляется риск, что кто-то другой их придумает и назовёт. Кстати, мы несколько лет назад рассматривали и другие игры со словами.

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

Сделать ход в комментариях к этой заметке очень просто — надо написать слово «Ход», после него получаемое натуральное число, знак равенства, а потом саму формулу.

Примеры корректных ходов:

Ход 0 = (2-2)*2
Ход 1 = 2 - cos(2-2).
Ход 2 = 2 + 2 - 2.
Ход 222 = 222.
Ход 16 = 2^(2+2).
Ход 26 = (2+2)!+2
Ход 20 = 22-2 (как видите, справа от знака равенства всегда появляются ровно три двойки)

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

Игра началась! Пусть победит сильнейший :)

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

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

Это невозможно и бессмысленно!

noreply@blogger.com (Илья Весенний) — Tue, 13 Dec 2011 00:39:48 PST

Бывает, что формулировка вопроса кажется такой странной, что даже думать о решении не хочется. Но ведь именно в таких граничных проявлениях может вылезти что-то интересное. Грубо говоря, нет никакого интереса в решении тысяч, например, квадратных уравнений. Они все почти одинаковые, с этой работой и компьютер справится. А вот если будет хоть какое-то разнообразие, хоть минимальные ловушечки, то и у человека уже будет возможность развернуться (конечно, с примером по ссылке у компьютера не будет никаких проблем, но и не для него подобные задачки сочиняют).

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

Давайте рассмотрим, например, такую задачку: Задержанный признался, что у него три сына, произведение их возрастов равно 36, а сумма равна числу окон дома, около которого произошло задержание. Милиционер сказал, что для определения возраста детей этого недостаточно. Когда задержанный добавил, что его старший сын рыжий, милиционер определил возрасты детей. Сколько им было лет?

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

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

Итак, диалог:
- Привет!
- Привет!
- Как дела?
- Хорошо. Растут два сына, но пока ещё в школу не ходят.
- А сколько им лет?
- Произведение их возрастов равно числу голубей около этой скамейки.
- Этой информации мне недостаточно…
- Старший похож на мать.
- Вот теперь я знаю ответ на свой вопрос.

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

Кстати, математика здесь, конечно, не очень сложная. Эта задачка была на олимпиаде для пятиклассников в середине прошлого десятилетия. А первая задачка о трёх детях взята из раздела «Задачи для семиклассников» из приложения к журналу «Квант» №4/2000 (А.В.Спивак, «Математический праздник», часть 2). Другими словами, сама математика очень простая, но важно правильно перевести на математический язык эти текстовые задачки.

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

А какие странно звучащие, но при этом очень осмысленные задачки знаете вы?

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

Осмысленная ерунда

noreply@blogger.com (Илья Весенний) — Fri, 02 Sep 2011 07:11:12 PDT

А кто-то может справедливо возразить: нельзя же всё время быть правильными, выверяя с линейкой и транспортиром каждое слово и дело! Да, я тоже думаю, что не получится, даже если очень хочется. Мы все иногда ошибаемся. Просто иногда глупости бывают осмысленными, а иногда совершенно бесполезными.

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

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

Ладно, давайте я воздержусь от возобновления разговоров о том, что хотя бы крупные телеканалы должны распространять грамотную речь, а лучше поздравлю всех причастных с 1 сентября. Хорошего вам года! А родителям напоминаю о том, на что обращать внимание (речь не только об осанке, а о проблеме игнорирования тех вопросов, с которыми у самих родителей не было проблем).

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

А как вы отвечаете на этот вопрос?

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

noreply@blogger.com (Илья Весенний) — Wed, 31 Aug 2011 07:58:28 PDT

Добрый день.

Полтора года назад мы много говорили о математике:

- Рассмотрели парадокс Бертрана, чтобы лишний раз убедиться в большом расстоянии между обыденном представлении о вероятностях и математическими определениями,

- Размышляли о корнях уравнений третьей степени, о полезности этой темы в школе и в жизни, вспоминали, как здорово было в детстве понять что-нибудь красивое,

- А в заметке «Бесконечность — не число» продолжился разговор о бытовом понимании математических терминов. После этого пришлось даже разобраться с тем, сколько будет бесконечность минус бесконечность (точнее, как это можно объяснять школьникам).

Ну а для тех, кто хочет отдохнуть от математики, мы ещё вспоминали три хороших фильма про Алис (а в комментариях ещё больше нашлось).

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

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

Градус бесстыдства

noreply@blogger.com (Илья Весенний) — Tue, 23 Aug 2011 01:37:17 PDT

Люди сразу поверят в истинность утверждения,
если его приписать какому-нибудь известному человеку.
(c) В. И. Ленин

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

Почему по федеральным каналам «человек в костюме преподавателя» позволяет себе говорить, что «каждая точка выпуклой функции может считаться точкой экстремума»? Эта странная фраза была нужна только для того, чтобы попросить ученика её повторить, а он с чистой совестью мог ответить, что никак не может, так как у него память маленькая... Кто целевая аудитория этой рекламы? Люди, которые не могут запомнить фразу из восьми слов? Или люди, которые в университеты ходят, чтобы слушать и повторять бессмысленные наборы терминов? Все гонятся за формой, но не задуряются поиском подходящего содержания (не так давно мы вспоминали американский фильм с похожей ерундой).

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

«27 августа в 00:30, подними глаза и посмотри на ночное небо. В эту ночь планета Марс, пройдет всего лишь в 34,65 тыс. милях от земли. Невооруженным глазом планета будет видна как полная луна. Это будет выглядеть как две луны над землей! Следующий раз когда Марс будет так близко к Земле будет только в 2287 году. Поделись этой новостью со своими друзьями так как никто из живущих на Земле еще такого не видел!»

Безграмотный и в смысле русского языка, и в смысле элементарного здравого смысла (который и жизнь спасти может) текст тиражируется со страшной силой! Ещё бы, следующего такого события ждать более 200 лет!.. Эх, люди умеют создавать сообщения в сети, но не умеют проверять информацию в справочниках (а то бы узнали, что расстояние до Марса занижено на три порядка). А указание расстояния в милях как бы намекает, что этот бред был переведён с языка самых миролюбивых и образованных.

Кстати, о различии нашей и зарубежной культуры, градусе бесстыдства и перспективах: давайте посчитаем, сколько раз слова «sex» и «секс» встречаются на главных страницах английской и русской версий сайта Cosmopolitan. У меня получилось 40 и 10, соответственно. Это значит, нам ещё есть к чему стремиться, так ведь?

У нас повсеместная демократия, верно? А если большинство не просто верит на слово любой ерунде, сказанной правильным голосом и в правильном месте, но и кидается её скорее всем пересказывать, то... разные могут быть варианты.

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

Элементарная задачка

noreply@blogger.com (Илья Весенний) — Fri, 19 Aug 2011 03:30:18 PDT

Добрый день.

В прошлой заметке была сформулирована математическая задача из одного давнего Турнира Городов о выборе таких четырёх карт из пяти, чтобы только их порядком можно было точно указать на пятую (для колод из 52 и 53 карт). А во второй половине этой заметки я объясню, почему расширение этой задачки является элементарным.

Классическим решением задачи с 52 картами, к которому многие приходят сами, является следующее:

0. Можно отсортировать все карты (договориться, что 2 < 3, пики < крести и т.д.). Этот порядок нам пригодится, чтобы уметь отсортировать любой набор карт (и потом строить любые перестановки этого набора).

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

2. Оставшиеся три карты можно расположить 3! = 6 разными способами. И нам этого хватает, чтобы закодировать достоинство пятой карты, поскольку на первом шаге из двух карт одинаковой масти мы выбрали не случайную, а ту, от которой до второй карты будет от 1 до 6 шагов (представьте себе круг из карт 2, 3, 4, 5, 6, 7, 8, 9, 10, В, Д, К, Т).

Соответственно, компьютер, посмотрев на первую карту в переданном ему наборе, выясняет не только масть загаданной карты, но и номер, к которому надо прибавить число от 1 до 6, чтобы узнать достоинство искомой карты. А сам этот номер вычисляется мгновенно, так как совпадает с номером перестановки второй, третьей и четвёртой карты.

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

Итак, у нас есть четыре карты, которые можно переставить 4! = 24 способами. А описать этой перестановкой мы должны одну из 49 карт (53 в колоде минус 4 переданных). Как это сделать? Есть масса способов. Но нам должно быть лениво придумывать новое, если и предыдущее решение сработает (кстати, ниже я покажу, что можно было поступить ещё ленивее):

0. На картах задан порядок, поэтому мы их можем перенумеровать от 1 до 52 (джокера сейчас не считаем),

1. В наборе из четырёх карт с номерами от 1 до 52 всегда найдутся две карты, номера которых имеют одинаковый остаток при делении на 3 (это тот же принцип Дирихле, которым мы пользовались выше для четырёх мастей и пяти карт). Соответственно, давайте одну из этих карт называть картой T (и ставить её первой среди «обычных» карт). Это позволит нам точно указать, какой остаток при делении на 3 даёт номер загаданной карты.

2. Пусть J — джокер, T — карта, указывающая остаток при делении на 3, а A и B — две другие карты. Пересчитаем возможные перестановки:
  1) JTAB,
  2) JTBA,
  3) TJAB,
  4) TJBA,
  5) TAJB,
  6) TBJA,
  7) TABJ,
  8) TBAJ.
Получается, что мы можем передать сдвиг от 1 до 8. Но легко понять, что большего нам и не требуется, так как максимальное расстояние между двумя числами от 1 до 49, имеющих одинаковые остатки при делении на три, не превышает 8 (на множестве этих чисел, конечно).

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

Как надо переформулировать задачу, чтобы её было решать просто и приятно?

Из набора чисел от 1 до N каким-то способом выбирают 5 чисел. Необходимо придумать способ закодировать одно из них порядком оставшихся четырёх чисел. Найти максимальное N, при котором это возможно.

Давайте оценим теоретический предел, выше которого N точно не поднимется. Нам на вход дают множество из пяти карт, а мы в ответ должны вернуть загаданную карту X и ещё четыре карты в определённом порядке. Давайте посчитаем, сколькими способами мы можем это сделать:
- загадать карту можем пятью способами (выбрать одну из пяти возможных),
- оставшиеся четыре переставить можно только 4! = 24 способами.
Итого: 5*24 = 120 — это количество разных состояний, которые мы можем вернуть.

А какую информацию надо сообщить? Требуется указать на одну из оставшихся N-4 карт. Т.е. надо передать одно из N-4 состояний.

Выходит, что если N больше 124, то фокус принципиально невозможно исполнить, потому что закодировать мы можем только одно из 120 состояний, а передать требуется одно из N-4 состояний. Так мы поняли, что N не может быть больше 124.

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

Эту задачу можно было бы смело назвать сложной, если бы не существовало способа кодирования для 124 карт, но был бы какой-нибудь способ для, например, 117 карт (так как тогда стояла бы большая проблема доказать, что для 118 карт никакого способа не существует). Но у нас всё просто — верхняя граница достижима, способ для 124 карт есть, поэтому достаточно всего лишь его предъявить :)
Кстати, в комментариях к прошлой заметке уже была дана ссылка не только на разборы этой задачи при N=124, но и на другие её модификации. Но всё же я предлагаю сначала попробовать найти решение своими руками, а уже потом читать чужой подход.

Хорошей недели!

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

Карты и теория кодирования

noreply@blogger.com (Илья Весенний) — Fri, 12 Aug 2011 07:16:17 PDT

Добрый день.

Можно учить теории кодирования (или любому другому разделу математики) традиционно: читать скучные лекции, формулировать непонятные леммы, доказывать ненужные теоремы... А можно показать всего один карточный фокус, чтобы удивить и заинтересовать, а уже потом читать интересные лекции и доказывать нужные теоремы.

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

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

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

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

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

А что со входными данными? Четыре карты можно сообщить 4! = 24 разными способами (меняя порядок карт). Не так уж и мало, хоть и меньше необходимых 52. Как же двигаться дальше? Надо поискать, где ещё можно спрятать хоть чуть-чуть информации.

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

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

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