28 мар. 2012 г.

А пусть не пищит!

Добрый день!

Если вам тоже не нравятся посторонние звуки (как кваканье машин), то, возможно, коротенькая заметка на Хабре о том, как своими руками избавиться от лишних писков, будет кстати.

Я её опубликовал только там, так как правила Хабрахабра не одобряют публикацию одного и того же текста у них и где-то ещё. Поэтому, если вы желаете избавиться от писков микроволновки или кофеварки, то добро пожаловать в статью «А пусть не пищит» на Хабре.

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

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

23 мар. 2012 г.

Ленивее лентяя

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

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

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


Пояснение: в этих задачах, как и во всех нормальных автобусных билетиках, мы не можем «склеивать» цифры (например, из двух единиц мы можем получить 1+1 и 1*1, но никак не можем сделать 11).

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

Главное искусство здесь — придумать правильную гипотезу. Например, решать задачу про поле 128 на 128 клеток достаточно тяжело, но если сообразить, что это поле 2^n на 2^n клеток, то сразу станет обозримее и проще.

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

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

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

21 мар. 2012 г.

Не надо "ква-ква"

— Сколь же можно про математику?! В каждой заметке только она!
— Хорошо, давайте поговорим о расширении зоны комфорта.

Когда автовладелец закрывает или открывает дверь своей машины с пульта сигнализации, она обычно «радует» весь двор задорным кваканьем. Давайте подумаем, какая от этого может быть польза:

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

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

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

Стоп... А почему я это всё назвал пользой? Действительно, пользы хозяину машины от этого никакой. Давайте тогда сформулируем настоящие причины «кваканья» сигнализаций:

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

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

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

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

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

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

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

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

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

19 мар. 2012 г.

От Колмогорова к Максвеллу, Лапласу, Байесу

Добрый день.

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

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

А теперь я передаю слово Артуру.

Адекватное раскрытие темы, подразумеваемой таким провокационным названием, потребовало бы целого трактата. Но наши цели здесь гораздо скромнее:

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

Одна теория, которая ассоциируется с именем Колмогорова, основана на достаточно узком и ограниченном понимании вероятности, как частоты повторяющихся событий; она является замкнутой и чисто математической теорией. Другая теория, которая ассоциируется с такими именами как Байес, Лаплас и Максвелл, основана на очень широком понимании вероятности, как степени достоверности умозаключений любого характера; она является открытой логической теорией познания.

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

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

Мысль, которую мы пытаемся здесь передать, наиболее выпукло была выражена в 1850 году основателем классической электродинамики Максвеллом в его письме к Льюису Кэмпбеллу:

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

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

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

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

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

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

6 мар. 2012 г.

Теорема Пифагора

Добрый день.

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

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

Ещё эта задачка бывает хороша на собеседованиях (естественно, многое зависит от специфики отбора), так как позволяет за короткое время услышать много разных идей... Но об этом позже. А сначала давайте вспомним теорему Пифагора. Она нам позволяет вычислить гипотенузу прямоугольного треугольника, зная его катеты, что можно использовать, например, для вычисления длины диагонали прямоугольника. А как теперь вычислить длину диагонали прямоугольного параллелепипеда (со сторонами a, b и c)? Правильно, сначала применить теорему пифагора для одной из граней — так мы найдём длину её диагонали d = sqrt(a^2 + b^2). А уже потом вычислить длину искомой большой диагонали sqrt(d^2 + c^2) = sqrt(sqrt(a^2 + b^2)^2 + c^2) = sqrt(a^2 + b^2 + c^2).

Сейчас мы не будем говорить о том, что таким элементарным путём мы пришли к определению евклидового расстояния, а лишь заметим неограниченность этого подхода. В n-мерном пространстве мы можем найти расстояние между двумя точками, n-1 раз воспользовавшись теоремой Пифагора. Естественно, обычно так никто не делает , потому что глупо считать квадратный корень, а потом сразу же возводить результат в квадрат. Но важно понимать, откуда возникла странная формула расстояния между точками d(A, B) = sqrt((A1-B1)^2 + (A2-B2)^2 + ... + (An-Bn)^2). Сейчас, скорее всего, мы это неплохо понимаем.

Теперь переходим к задаче, а заодно пользуемся возможностью поучаствовать в создании этой заметки (подробности будут в квадратных скобках ниже). Начать этот разговор проще всего с двумерного пространства. Представьте себе квадрат со стороной 2. Его можно разбить на четыре квадрата 1x1, в каждый из которых легко вписать окружность диаметра 1. Давайте найдём величину D2 (диаметр окружности, вписанной между этими четырьмя окружностями).

Если в большом квадрате, разделенном на маленькие, провести диагональ, то увидим, что искомый диаметр D2 состоит из двух равных половинок. Каждая половинка — это расстояние от угла маленького квадрата до окружности, которая в этот квадрат вписана. И такая же половинка находится с другой стороны окружности в этом же квадрате. Получается, что искомый диаметр равен диагонали маленького квадрата минус диаметр окружности. Т.е. D2 = sqrt(2) - 1. [Спасибо KYegres за это объяснение (в комментариях есть ещё несколько решений этой задачи)]

Отлично, так мы нашли D2. Теперь давайте рассмотрим трёхмерный случай. Представьте себе куб со стороной 2. Его можно разбить на восемь кубов 1x1x1, в каждый из которых легко вписать сферу диаметра 1. Давайте найдём величину D3 (диаметр сферы, вписанной между этими восемью сферами).

Расстояние между центрами сфер, лежащих на большой диагонали куба, равно sqrt(3), а радиус каждой из этих сфер равен 1/2. Получается, между центрами этих сфер есть только они сами и вписанная сфера => D3 = sqrt(3)-1/2-1/2 = sqrt(3)-1. [спасибо анонимному комментатору за это решение]

Прекрасно, теперь мы нашли D3. А теперь давайте зададимся вопросом: к какой величине будет стремиться значение Dn при росте n? Или по-русски: к чему приближается диаметр сферы, вписанной между единичных сфер, прижатых к углам n-мерного куба со стороной 2?

Что такое сфера в n-мерном пространстве? Это множество n-мерных точек, удалённых от центра сферы на одинаковое расстояние. Так как расстояние мы считать умеем, то и с множеством таких точек работать можем. С n-мерными кубами ещё проще, так как там даже корни с квадратами считать не надо, а всё прямо задаётся неравенствами.

Давайте попробуем найти D9 и D16 (диаметры вписанной окружности для случаев девятимерного и шестнадцатимерного пространств). Достаточно посмотреть на одну из главных диагоналей n-мерного куба. Ее длина 2*sqrt(n), центр искомой сферы лежит прямо посередине неё, центры двух вписанных в куб сфер лежат на ней, точки касания искомой сферы и сфер, вписанных в куб лежат тоже на ней (строго не готов доказать, но визуально достаточно очевидно и из всяческой симметрии вроде бы должно получиться). Теперь смотрим на половинку этой диагонали. Расстояние от ее конца, являющегося углом куба, до центра вписанной в куб сферы — sqrt(n)/2 (ровно четверть всей диагонали), радиус вписанной в куб сферы 1/2, в итоге радиус искомой сферы (sqrt(n)-1)/2, а диаметр — sqrt(n)-1 [Спасибо Eyeless за это описание].

Подставим 9 и 16 в найденную формулу:
- D9 = sqrt(9) - 1 = 3 - 1 = 2,
- D16 = sqrt(16) - 1 = 4 - 1 = 3.
Получается, что диаметр сферы, зажатой между сфер, вписанных в углы куба, совпадает со стороной этого куба (или даже выходит за его пределы). «Немного» странно, верно?

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

[Благодарю Arthur Baraov за очень подробные рассуждения по поводу этой задачи]

Хорошего вечера!

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

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



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

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