Заключённые и телефоны-2

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

Задача. 50 заключённых будут рассажены по звуконепроницаемым одиночным камерам, из которых нельзя выходить. В каждой камере установлено два телефона: чёрный и белый. Как только заключённых рассадят по камерам, начальник тюрьмы позвонит в случайную камеру на чёрный телефон и спросит согласно своей инструкции: «Тюремный звонок номер один. На телефон какого цвета я должен позвонить следующему заключённому?» Получив ответ, тюремщик снова выбирает случайным образом камеру (равновероятно, то есть в одну камеру могут позвонить несколько раз подряд) и звонит в неё на телефон того цвета, который указал предыдущий заключённый: «Тюремный звонок номер два. На телефон какого цвета я должен позвонить следующему заключённому?» — и т. д. Номер звонка, сообщаемый заключённому, каждый раз возрастает на единицу.

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

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

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

Заключённые и телефоны-1

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

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

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

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

R-squared и эволюция форм господства

Regression line with outlier

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

 

 

 

consumer

Поначалу им сверху приказывали говорить: «Боже, царя храни!» — и они верили. Затем... Сейчас Греция охвачена нестабильностью — греки не хотят подчиняться, работать больше и платить больше налогов. Революция! А затем, ослеплённые собственной жадностью, они попадают под контроль, основанный на алчности, ещё более сильный, чем религиозный, основанный на страхе. Я уже купил в супермаркете всё по списку и так горжусь тем, что у меня всё уже есть, что с упаковкой и доставкой это обошлось всего лишь в 4 000 без малого рублей. Внимание, скоро новогодние праздники — ПОКУПАЕМ, ПОКУПАЕМ, ПОКУПАЕМ!

Хорошие веб-комиксы

Товарищ Velica с DeviantArt, занятый в области биотехнологии, стал известным благодаря своему рисунку «Ретровирус». Ниже предлагаются его комиксы, адаптированные для русскоговорящих читателей.

r-squared

Мне так часто приходится наблюдать подобные случаи...

 

 

 

histogram

Человеку свойственно ошибаться.

 

 

 

virus and retrovirus

 

 

 

retrovirus-1

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

 

 

 

tissue culture

Должен же был кто-нибудь обыграть эту многозначность.

 

 

 

drama

 

 

 

amoeba

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

 

 

 

argument

Свобода индивида против свободы рынка.

 

 

 

Papa

Если пригвоздить социалиста к кресту, то через две тысячи лет получите вот это.

Дональд Эрвин Кнут

Сегодня ночью, помимо беготни по обстреливаемым улицам Таиланда в поисках магнитика для фокуса Копперфильда и написания на ЕГЭ изложения по американским мультяшным комиксам, я видел Дональда Кнута. Он был молод, сорокалетен, очень был похож на Марка-Андре Амлена. Он жил на одном этаже со мной, а дверь в его квартиру находилась в лифте. Я беседовал с Кнутом и чувствовал, как в процессе разговора становлюсь умнее, постигаю комбинаторику, дискретную математику, алгоритмы... Его речь текла, как будто мёд. Однако в действительности ему публичные выступления даются не так свободно, поэтому я возьму на себя труд по донесению идей Кнута до молодого поколения.

donald erwin knuth

Очень часто мне задают такой забавный вопрос: «Какой совет вы бы дали молодому поколению?»

Первое, что мне приходит на ум, — это мысль: «Не верьте чему-либо только потому, что это модно; это не обязательно хорошо». Я, скорее, нахожусь в другой крайности, которая состоит в том, что если слишком много людей принимает какую-либо идею, то она, вероятно, ошибочна. Если какие-то мои работы становились слишком популярными, то я считал, что мне надо меняться. Это, по всей видимости, нелепо, но слишком часто это подтверждается тем, что люди делают что-то против своих внутренних чувств, поскольку они считают, что общество хочет этого способа работы от них, и поэтому люди будут работать в какой-то области, даже зная, что их это не увлекает, но уверясь в том, что их репутация от этого возрастёт. Я считаю, что репутация повышается благодаря хорошим научным исследованиям, а не популярным научным исследованиям, поскольку если вы занимаетесь какой-то работой, которую сами считаете важной, то тогда более высока вероятность того, что это действительно окажется важным в долгосрочной перспективе, а ведь именно ориентация на последнюю оказывает самое благотворное влияние на мир. Поэтому когда я пишу или издаю книгу, то она отличается от книг, выпущенных ранее, поскольку я чувствую, что такая книга будет востребована, и востребована не потому, что кто-то просит: «Пожалуйста, напиши такую книгу», — и не потому, что другие тоже занимаются выпуском таких книг. Мне кажется, следовать своим инстинктам и чувствам — это лучше, чем следовать за стадом. Мой друг Питер Вегнер (Peter Wegner) сказал мне в 1960-х касательно «Искусства программирования», что не нужно сразу всю серию книг писать целиком, что следует сначала написать краткое изложение структуры для читателя, а затем уже расширять разделы этой структуры. Возможно, этот совет пригодился бы ему, но я работаю совсем по-другому: я должен следовать за материалом до тех пор, пока я полностью его не охвачу и не пойму его, и только после этого я смогу писать об этом уверенно — вот как я работаю. Я не хочу писать о чём-то высокоуровневом, пока я не усвоил всех тонкостей на более низком уровне.

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

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

Donald Erwin Knuth, из интервью сайту Webstories: http://www.webofstories.com/play/17060

Как вычислить самую правую цифру числа-2

Предлагается самый простой алгоритм вычисления \(k\)-й слева цифры любого числа (придуманный уже не мной, а коллективным разумом программистов на C).

Если поделить число \(n\) на 10, то тогда остаток от деления \(n\) на 10 (обозначим его \(n \bmod 10\)) будет равен самой правой цифре. Сколько цифр в числе \(n\)? Правильно, \(\lceil \log_{10} n \rceil\). Далее, если поделить число \(n\) на 100, то остаток, разделённый на 10 и округлённый вниз до целого, будет равен второй цифре. Чувствуете закономерность?

\[n_{i_k} = \left\lfloor \frac{n}{10^{\lceil \log_{10} n - k \rceil}}\right\rfloor \bmod 10\]

Для самой правой цифры числа формула примет вид

\[n_{i_K} = n \bmod 10.\]

Как вычислить самую правую цифру числа-1

Пусть у нас есть число \(n\) в десятичной записи: \(n_{i_1}n_{i_2}n_{i_3}\ldots n_{i_k}\ldots n_{i_K}\). Требуется определить его последний знак (\(n_{i_K}\)). Как это сделать?

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

(1) Сколько разрядов в числе \(n\)? Очевидно, их \(K\): \(K=\lceil \log_{10} n\rceil\).
(2) Как вычислить самую левую цифру числа \(n\) (обозначим её за \(n_{i_1}\))? Очевидно, надо поделить это число на десять в степени, на единицу меньшей числа разрядов, и откинуть хвост (то есть округлить вниз до целого).
(3) Как вычислить вторую справа цифру числа \(n\)? Провести ту же самую вычислительную операцию с числом \(n\) без левой цифры.
(4) Как откинуть левую цифру числа \(n\) (то есть \(n_{i_1}\))? От числа \(n\) отнять произведение левой цифры и 10 в степени \(K-1\).
(5) Сколько раз надо провести процедуру вычисления \(k\)-й по счёту слева цифры числа \(n\)? Очевидно, \(k\) раз.

Итак, у нас уже есть рекурсивный алгоритм. Теперь запишем всё это дело по пунктам на языке математики.

(1)
\[K=\lceil \log_{10} n\rceil.\]

(2)
\[n_{i_1} = \left\lfloor \frac{n}{10^{\lfloor \log_{10}n \rfloor}} \right\rfloor = f(n).\]

(3, 4) Для \(\mathbb{N} \ni p>1\)
\[n_{i_k} = f\left( n - \sum\limits_{m=1}^{k-1} \bigl( n_{i_m} \cdot 10^{\lfloor\log_{10} n \rfloor} \bigr) \right) = g(n,k).\]

(5)
\[\mathrm{Rightmost\ digit} = n_{i_K} = n_{i_{\lceil \log_{10} n\rceil}} = g(n,K).\]

При этом понятно и ежу, что функция \(g(n,k)\) рекуррентна по \(k\) (требует вычисленных \(g(n,1),\ldots,g(n,K-1)\)), поэтому придётся вычислять все цифры, пока не придём к последней.

В данном алгоритме кроется страшнейшая ошибка. Если \(n_{i_k}=0\), тогда будет вычисляться следующая ненулевая цифра, поэтому число шагов будет не \(K\), а \(K-\zeta(n)\), где \(\zeta(n)\) — число нулей в числе \(n\).

И вот я думаю: неужели нет более простого и очевидного математического алгоритма вычисления правой цифры числа? Наверняка есть. Наверняка надо проверить остаток от деления на чи́сла из определённого набора.

Задание 1. Придумать подобный алгоритм на основе вычисления остатка от деления \(n\) на числа из определённого набора.

Задание 2. Придумать на основе вышеприведённого алгоритма новый метод вычисления \(n_{i_k}\), который бы выдавал 0 для \(n_{i_k}=0\) (пока что он будет выдавать следующее ненулевое \(n_{i_{k+q}}\)).

Задание 3. Придумать \(\zeta (n)\). Пока что \(\zeta(n) = K - s\), где \(s = \max \{k \leqslant K\}\), то есть количество цифр, которые мы вообще вычислили. Иными словами, \(s\) — номер шага, который выдал нам корректную последнюю цифру. Но зачем же так сложно?

Русский и украинский язык

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

Но как было бы здорово, если бы исчез этот придурочный придуманный водораздел между русским и украинским! Якби лінгвісти попалили к бісу ці дурні карти! Я искренне полагаю, что малороссийские говоры обогатили бы художественную русскую речь, привнесли бы в неё ещё больше нюансов, усложнили бы организацию языка. Подумать только: сколько рифм бы пришло вместо избитых и раздражающих «тайно — случайно» и «любовь — кровь — вновь». Появилось бы просторечное «негайно». Начали бы «когда любов, разрушил бы тысячи будо́в». Естественно, истинные поэты отыскали бы куда более изящные совпадения, которые бы меньше пахли салом сельской местностью. «Вдохну я в грудь аэрозолю \\ И моментально сбожеволю». Некоторые грамматические формы, безусловно, должны оставаться «приписанными» к своим областям. Однако некоторые тонкости, наоборот, приукрасят речь. Так, даже галлицизм «я поправил свой бель крават» станет понятным говорящему на обогащённом языке, так как «кроватка» в украинском — это галстук. «Меня пленил вершковый кофий» — насколько это возвышеннее, чем какой-то «кофий со сливками»! Сливки — это как будто кто-то что слил; опивки, не иначе! Господарь (в значении «хозяин») суворо (строго) окинул меня взглядом, и мне сразу стало жутко, будто бы в меня без шубы на улице вцепился лютый (февраль). И уж как прозрачна бы стала шутка «Гений без буквы „е“»! Посыпались бы лозунги против пиянства, содержащие рифму «зелёный змий — гний» (последнее слово — в значении «навоз», а не повелительное наклонение от «гнить»).

Подсолнухи

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

Модель падающего тела при измерении расстояния, часть 1

В школе часто задают задачку: рассчитать глубину колодца, если в наличии есть только камень и секундомер. При этом предлагается воспользоваться простейшей формулой для измерения координаты тела, падающего равноускоренно без нулевой скорости:
\[ h = \frac{gt^2}{2}, \]

где \(h\) — путь (глубина колодца), \(g\) — ускорение свободного падения, \(t\) — время на секундомере.

При этом упускается важнейшая деталь. Скорость звука на этой планете очень невысока. Естественно, как только камень по параболе упадёт на дно, звук со дна начнёт лететь равномерно и прямолинейно, безо всякого замедления. Ушей слушателя он достигнет через время, равно отношению глубины ущелья к скорости звука. Если глубина невелика, то тогда всё нормально. Однако при глубине в 123 метра (или высоте, что то же самое; 123 метра — это высота 33-этажного MCI Centre в Лос-Анджелесе... или любого другого здания подобной этажности) звуку потребуется более трети секунды, чтобы достичь ушей слушателя. Как видно из иллюстраций, дальше — больше. Расстояние квадратично зависит от времени, поэтому доля возврата звука обратно в общем измеренном времени неуклонно растёт.

1s

5s

15s

42s

Если бы мы в модели с конечной скоростью звука просверлили в центре Эвереста отверстие-тоннель до земли и бросили туда камень, то он бы падал примерно 42 секунды, а обратно звук бы дошёл за половину этого времени (!). Радостные, мы бы стояли с секундомером, получили бы примерно минуту, подставили бы её в формулу \(h = \frac{gt^2}{2}\) и вычислили бы высоту Эвереста, которая бы отличалась от истинной в бо́льшую сторону... всего в несколько раз (иными словами, мы бы определили высоту горы с точностью до константы).

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

Звук летит равномерно прямолинейно без ускорения. Человек с секундомером измеряет сумму двух временных промежутков: время полёта камня (\(t_1\)) и время возврата звука (\(t_2\)). То есть мы знаем \(t = t_1+t_2\), а в формулу высоты, с которой падает тело, надо подставлять \(t=t_1\): \(h = \frac{gt_1^2}{2}\). Более того, \(h = \frac{gt_1^2}{2} = ct_2\), \(t=t_1+t_2\). Выразим \(t_1\) через \(t\):
\[ h = \frac{gt^2_1}{2} = ct_2 \quad \leadsto \quad t_2 = \frac{gt_1^2}{2c} \]
\[t = t_1 + \frac{gt_1^2}{2c} \quad \leadsto \quad \frac{g}{2c}t_1^2 + t_1 - t = 0\]
\[D = b^2-4ac = 1 + \frac{2gt}{c} \quad \leadsto \quad t_1 = \frac{c}{g}\left( \sqrt{1 + \frac{2gt}{c}} -1 \right)\]

Скорость звука (о ней будет сказано ниже) нам известна (≈340 м/с), ускорение свободного падения тоже известно (9,80665 м/с²). Поэтому итоговая формула, позволяющая определить высоту объекта по времени падения камня, который стучит о дно, будет иметь вид:
\[ h = \frac{gt_1^2}{2} = \frac{c^2}{2g}\left( \sqrt{1 + \frac{2gt}{c}} -1 \right)^2 = c\left( t - \frac{c}{g} \left( \sqrt{1 + \frac{2gt}{c}} +1 \right) \right).\]

Легко убедиться в том, что при очень большой скорости звука время \(t_1\) будет стремиться ко времени \(t\):
\[ \lim\limits_{c\rightarrow\infty} \frac{c}{g}\left( \sqrt{1 + \frac{2gt}{c}} -1 \right) = \lim\limits_{c\rightarrow\infty} \frac{c}{g}\frac{\left( \sqrt{1 + \frac{2gt}{c}} -1 \right)\left( \sqrt{1 + \frac{2gt}{c}} +1 \right)}{\left( \sqrt{1 + \frac{2gt}{c}} +1 \right)} = \]
\[= \lim\limits_{c\rightarrow\infty} \frac{c}{g}\frac{2gt}{c\left( \sqrt{1 + \frac{2gt}{c}} +1 \right)} = \lim\limits_{c\rightarrow\infty} \frac{2t}{ \sqrt{1 + \left\{\frac{2gt}{c_{\rightarrow\infty}} \right\}}_{\rightarrow0} +1 } = \lim\limits_{c\rightarrow\infty} \frac{2t}{\sqrt1 + 1} = t.\]

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

diff1

diff2

diff3

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