Делать или думать?

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

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

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

Изложу оба подхода:

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

Как мы уже поняли, фигуру эту можно разрезать на четыре г-образные фигуры в два раза меньше (у них максимальная ширина будет 64). Но и эти фигурки можно разрезать на 4 фигурки в два раза меньше (со шириной 32). Далее аналогично - режем на 4 меньших фигурки с шириной 16, потом - 8, потом - 4, потом - 2, пока не доходим до исходной триминошки.

Всё это можно было сформулировать в терминах математической индукции:
Теорема 1. Г-образную фигуру (квадрат со стороной 2^k, из которого вырезали одну четверть - угловой квадрат со стороной 2^k-1), можно покрыть триминошками.
Доказательство: Применим метод математической индукции.
База индукции - при k=1 утверждение верно, так как исходная г-образная фигура совпадает с триминошкой.
Шаг индукции - Предположим, что утверждение верно при k=n-1. Тогда при k=n нам достаточно просто разрезать фигуру на 4 вдвое меньших - а их мы уже разрезать умеем (согласно предположению). Что и требовалось доказать.

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

Решение получилось длинное и занудное, потому что мы бросились излагать его, чуть-чуть не додумав.

Пришло время для изящного решения:

Теорема 2. Для квадрата со стороной 2^k, из которого вырезали одну клетку в произвольном месте, существует покрытие г-образными триминошками.
Доказательство: Опять применяем метод математической индукции:
1) База такая же, как и в предыдущей теореме: квадрат со стороной 2, из которого вырезали одну клетку, можно покрыть одной триминошкой, потому что они совпадают по форме.
2) Шаг индукции: Пусть нам известен способ покрыть любой квадрат без одной клетки, у которого сторона 2^k-1. Тогда квадрат со стороной 2^k без одной клетки можно разрезать на 4 квадрата со стороной 2^k-1, каждый из которых тоже будет без одной клетки (с ними мы умеем справляться по предположению). Причём мы сгруппируем три новых дырки так, чтобы в них можно было вставить одну триминошку (как на рисунке).
Что и требовалось доказать.

Ну а раз мы имеем утверждение для любого квадрата со стороной 2^k, то и для квадрата со стороной 128 оно тоже верно. Кстати, это нам показывает, что иногда существовании чего-то частного проще обосновать, доказав существование чего-то общего.

Закончим сегодня ещё одной задачкой на метод математической индукции.

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

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

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

Математическая индукция

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

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

Пусть наш подопытный человек спустится в метро, выйдет на платформу и сядет в первый подъехавший поезд. Известно, что поезда на обоих платформах ходят через равные промежутки времени. Верно ли, что пассажир уедет с правой или с левой платформы с одинаковыми вероятностями?

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

Идея проста как лестница:
1) если мы уже стоим на первой ступеньке лестницы,
2) если мы умеем с любой ступеньки подняться на следующую,
то мы теоретически можем достичь любой ступени.

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

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

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

Первая естественная мысль: раз фигурки состоят из трёх клеток, то и количество клеток доски должно делиться на 3, чтобы такое покрытие было возможно. Проверяем: 128²-1=(128-1)(128+1). Второй множитель очевидно делится на три. Другими словами, малой кровью ответить «нет» на вопрос задачки мы уже не можем.

А что можем? Можем взять листок бумаги 128 на 128 клеток, вырезать из него одну произвольную клеточку, подготовить множество триминошек... И методично пытаться уложить фишки на поле так, чтобы выполнить условие задачи. Если удастся, то надо будет попробовать вырезать из поля другую клеточку, так как требуется проверить все случаи... Представляете масштаб работы?

Что можем ещё? Можем вспомнить тему этой заметки - метод математической индукции. Если заранее не знать, то трудно придумать его применение для такой формулировки. В данном случае мы всё вспомнили, поэтому триминошки должны легко сдаться. Удачи!

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

Хорошего дня! И поделитесь своими соображениями по поводу пассажира метро :)

Инфляция печатного слова

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

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

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

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

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

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

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

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

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

Успехов вам!

Три ссылки

Вот и подоспело продолжение рубрики три чего-нибудь. Сегодня это ссылки на три темы:

1. Экономика. Алексей Глазков опубликовал содержательную подборку статей. Интересно.

2. Страхование. Макс Крайнов сформулировал 4 правила, а Сергей Макаров дополнил их своими соображениями. Некоторые мысли естественны, а до некоторых можно дойти только негативным опытом - лучше чужим, чем своим.

3. Хорошее настроение. Боб Макферрин шикарно продемонстрировал сходство людей различых культур и продолжил тему звуковых иллюзий. Неважно, какое образование получили зрители, где родились, как воспитывались. Важно, что они одинаково чувствуют красоту звучания.

(ссылка)

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

А кому тогда верить?

Добрый день.

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

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

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

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

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

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

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

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

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

Оставайтесь сложными! Это трудно, но интересно.

Живи настоящим!

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

Но есть и изменения смыслов в массовом сознании при сохранении звучания. Одно из самых известных - название романа «Война и мир». Есть следующая легенда, которую многократно воспроизводили СМИ: якобы Толстой использовал в названии романа слово «міръ» (что означало не противоположность войне, а место обитания, планету), а не «миръ» (антоним слову «война»). Эта красивая легенда так удачно «добавляет глубину» роману, что в неё многие поверили, стали многократно повторять. Например, вопрос об этом дважды задавался в «Что? Где? Когда?» - знатоки оба раза отвечали неправильно (с точки зрения специалистов), но верно (с точки зрения организаторов), что ещё сильнее укрепило веру в эту легенду.

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

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

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

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

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

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

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

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