31 янв. 2011 г.

Оптимальные построения

Сегодня у нас будут две забавные задачки на построение, но сначала немного теории.

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

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

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

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

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

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

Что такое вспомогательные линии? Это все линии, которые вам придётся провести циркулем и линейкой, чтобы найти точки, через которые будете проводить искомую прямую. Например, классическое школьное решение задачи (а) требует три линии:
1) построим окружность с центром в точке A и большим радиусом (чтобы заведомо пересекла прямую l), так мы получим точки пересечения B и C, потратив одну линию.
2) с центрами в точках B и C построим две окружности одинакового радиуса (чтобы они пересеклись друг с другом), так мы получим точки D и E, потратив ещё две линии.
3) ну а теперь через точки D и E проводим искомую прямую.

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

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

P.S.
Да, я знаю, что в школьном решении выше предложены неаккуратные формулировки. Но если писать «академичнее», то текст станет в полтора раза длиннее, а понятность его снизится. Поэтому я считаю, что при решении простых задач вполне допустимы подобные огрубления. Это облегчает понимание и уменьшает пустую трату времени.

Одновременно с этим я пропустил важный этап доказательства того факта, что построенная прямая является перпендикуляром к l, проходящим через точку А. Это очень простое упражнение, поэтому оставляю его для желающих.

23 янв. 2011 г.

Всё для людей!

Добрый день!

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

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

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

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

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

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

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

Итак, ситуация:
1) есть 240 ёмкостей с квасом, но ровно одна из них отравлена очень сильным ядом (все цистерны одинаково выглядят, поэтому отравители не могут вспомнить, в какой из них яд),
2) впрочем, враги сознались, что яд этот убивает не сразу после употребления, а в течение суток (может через 10 минут, а может и через 24 часа),
3) за попытку отравить жителей города пятёрку злодеев уже приговорили к смертной казни, но приговор ещё не исполнили,
4) осталось всего двое суток до начала жары, поэтому надо как можно большее количество прицепов с квасом проверить на отсутствие яда, чтобы вывести их на улицы города.

Вопрос: какое максимальное количество прицепов-цистерн кваса (но только заведомо без яда) можно выпустить на улицы через двое суток?


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

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

Хорошего вам завершения выходных!

13 янв. 2011 г.

Три вкусных задачки

Добрый день!

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

1) Итак, первую задачку недавно напомнил Макс Крайнов в заметке о вопросах из интервью крупных компаний. У нас есть цилиндрический торт «Картошка» и плоский нож. Как тремя разрезами поделить торт на 8 одинаковых частей?

В условии следующих задачек будут подсказки к первой, поэтому рекомендую читать их только после её решения :)

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

3) В третьей же задаче мы объединим условия первой и второй: торт опять слоёный (поэтому резать его можно только перпендикулярно поверхности), но имеет форму прямоугольного параллелепипеда. Как сделать три разреза прямым ножом, чтобы получилось 8 одинаковых по форме кусочков?

Разыгрался аппетит, пока решали задачки? Не проблема! Мы же уже умеем делать вкусный торт :)

Вкусного вам вечера и хорошей недели!

12 янв. 2011 г.

Сопоставление размеров

Добрый день!

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

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

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

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

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

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

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

А теперь обещанная (классическая) задачка о сопоставлении размеров:
Представьте себе треугольник, все высоты которого меньше единицы. Может ли у такого треугольника площадь быть больше 100? А больше 1000000?

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

6 янв. 2011 г.

Только у нас!

Всяк кулик своё болото хвалит.
Народная мудрость

Иногда мне вспоминаются следующие дворовые сцены из детства:

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

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

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

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

Давайте коротко пройдёмся по популярным темам последнего года:

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

2. С этого года в России начинают собирать налог со всех носителей данных (жёстких дисков, компакт-дисков, флешек...) и с оборудования для записи. Забавно, что эта инициатива позиционируется как исключительно поддержка авторов, хотя из собранной суммы им запланировано передавать всего 15%. Яркое несоответствие дела и слова? Да. Только у нас? Нет. Франция придумала похожий налог - с мобильных устройств не под управлением Windows. Интересно, что ранее во Франции уже был налог с MP3-плееров в пользу правообладателей. Но потом законодатели поняли, что планшеты тоже могут быть MP3-плеерами. И ещё они поняли, что только пользователи Microsoft Windows не станут пиратствовать, а вот пользователей всяких Android, Linux или MacOS надо обложить дополнительным налогом.

3. Ну а сколько разговоров о недоверии правоохранительным органам? Мол, «только у нас население не верит решению суда и действиям людей в форме». Встречаются и обратные утверждения: «Только у нас власть не может навести порядок, если народ разбушевался». Хотя буквально в 1992 году в США с 29 апреля по 4 мая беспорядки в Лос-Анджелесе, начавшиеся после оглашения решения суда, привели к гибели 53-х человек и убытком на миллиард долларов.

4. Можно долго и подробно говорить, почему у нас не биржа, а игра инсайдеров, почему у нас некоторые компании имеют такие привилегии, что им даже стараться не надо, чтобы иметь огромные прибыли. Но правда ли, что такое бывает только у нас? Буквально летом прошлого года структуру Goldman Sachs поймали за интересным мошенничеством бизнесом.

5. Или та же свобода слова: сейчас уже все потихоньку признали, что в 2008-ом году не Россия начала конфликт в Грузии, но во время боевых действий западные СМИ бодро показывали кадры 1994-го года с подписью «Русские танки в Тбилиси». Или то же оперативное фабрикование расследование дел против основателя WikiLeaks?

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

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

Хорошего вам 2011-го года!
Пусть у близких вам людей всё будет хорошо!
И пусть окружающий мир нравится вам всё больше и больше!

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

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



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

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