31 авг. 2011 г.

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

Добрый день.

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

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

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

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

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

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

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

23 авг. 2011 г.

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

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

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

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

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

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

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

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

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

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

16 авг. 2011 г.

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

Добрый день.

В прошлой заметке была сформулирована математическая задача из одного давнего Турнира Городов о выборе таких четырёх карт из пяти, чтобы только их порядком можно было точно указать на пятую (для колод из 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, но и на другие её модификации. Но всё же я предлагаю сначала попробовать найти решение своими руками, а уже потом читать чужой подход.

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

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

12 авг. 2011 г.

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

Добрый день.

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

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

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

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

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

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

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

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

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

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

11 авг. 2011 г.

Мясные суши (роллы)

Добрый день.

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

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

На фотографии справа представлена разделочная досочка, на которой есть всё необходимое.

Из чего сделать мясные роллыИтак, нам понадобится:
1. Тонкий лаваш,
2. Мясо (можно два вида, чтобы было интереснее),
3. Сыр (тоже рекомендую заготовить разные, чтобы роллы получались с разными вкусами),
4. Огурцы,
5. Помидоры,
6. Базилик (или что любите)
7. Майонез (чтобы было не слишком сухо и диетично).

Всё (кроме лаваша и майонеза) надо порезать «столбиками» высотой около 7 сантиметров, а лаваш нарежьте ножницами на полоски шириной 7-10, а длиной 17-25 сантиметров (только без линейки, а «на глаз» :). Как говорят программисты, эта деятельность «хорошо параллелится», поэтому веселее всего все приготовления делать хорошей компанией (лишь бы досок и ножей хватило).

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

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

Если сложить роллы в пластиковый контейнер, то они прекрасно сохранятся в холодильнике, а если оставить снаружи, то они очень быстро пропадут (будут съедены :). Знаете, очень здорово бывает навернуть супчика, используя вместо хлеба такие роллы!..

Ну а если вы не любите мясо и сыр, а хотите чего-то к чаю, то напоминаю старинный рецепт торта из мясорубки.

Хорошего завершения недели!