воскресенье, 9 декабря 2012 г.

Четыре четвёрки

Сегодня у нас загадка из совершенно чумовой книжки "Головоломки профессора Головоломки". Запишите целые числа от 0 до, скажем, 20, используя только четыре четвёрки и математические операции.

Начать можно, например, с такого:
0 = 44 - 44
1 = 4 - 4 + 4/4

понедельник, 3 декабря 2012 г.

Молоко и кофе

Есть два одинаковых стакана: стакан молока и стакан кофе. Изначально объёмы жидкостей в стаканах равны. Некто набрал из стакана чайную ложку молока и перелил в стакан с кофе. Тщательно перемешал, после чего перелил чайную ложку смеси в стакан с молоком. Чего теперь больше: кофе в молоке или молока в кофе?

воскресенье, 25 ноября 2012 г.

Пьяный математик

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

Как, задав единственный вопрос и получив в ответ "Да" или "Нет", математик узнал, из какого племени этот туземец, сколько у него сыновей и сколько дочерей (оказалось 2 и 3), и в какую сторону нужно идти, чтобы попасть в аэропорт?

Считаем, что туземцы знают логику и математику ровно в таком же объёме, что и европейцы.

воскресенье, 18 ноября 2012 г.

Научная гипотеза

Вспомнил на днях интересную задачку из Гарднера. Вопрос: является ли красная корова подтверждением гипотезы, что все вороны - чёрные?

воскресенье, 11 ноября 2012 г.

Две дроби

Есть два рациональных числа: 13/16 и 9/11. Напишите рациональное число, которое находится между ними (больше 13/16 и меньше 9/11) и имеет знаменатель меньше 100.

воскресенье, 4 ноября 2012 г.

Карточный фокус

Фокусник даёт зрителям стандартную колоду из 52 карт: 4 масти от двойки до туза без джокеров. Зрители произвольным образом выбирают из колоды 5 карт и показывают их помощнику фокусника. Помощник смотрит на эти 5 карт и говорит 4 из них фокуснику (какие именно и в каком порядке решает он). После этого фокусник называет пятую карту. Как ему это удаётся?

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

воскресенье, 28 октября 2012 г.

Парадокс фокусника

Сначала фокусник продемонстрировал зрителям пустой цилиндр.
Ровно за минуту до полудня он опустил в цилиндр карточку с числом 1.
За 1/2 минуты до полудня он вытащил из цилиндра и выкинул карточку с числом 1, а вместо неё положил карточки с числами 2 и 3.
За 1/3 минуты до полудня фокусник извлёк из цилиндра карточку с числом 2, положив взамен карточки 4, 5, 6 и 7.
За 1/4 минуты до полудня он удалил из цилиндра число 3, а вместо неё положил в цилиндр числа от 8 до 15.
...

В полдень измученный фокусник вывалил всё содержимое цилиндра на стол. Сколько карточек с числами увидели зрители?

воскресенье, 21 октября 2012 г.

Монеты в тёмной комнате

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

воскресенье, 14 октября 2012 г.

Пожар на острове

Вы оказались на необитаемом острове. Остров очень длинный (скажем, 20 километров), но очень узкий (скажем, 10 метров) и вытянулся с запада на восток. Весь остров порос деревьями.

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

Эту жизненную задачу я давным-давно увидел здесь.

воскресенье, 7 октября 2012 г.

50 красных и 50 синих шаров

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

воскресенье, 30 сентября 2012 г.

Мышиная охота

В стене есть 5 мышиных норок, расположенных в ряд. Мышка сидит в одной из них, причём неизвестно, в какой именно. Кот Леопольд Дорофей хочет поймать эту мышку. За одну попытку он может засунуть лапу в одну из норок. Если он угадал, то мышка становится его добычей. Если нет, то перепуганная мышка обязательно перебегает из той норки, в которой она сидела, в соседнюю справа или слева. Может ли Дорофей гарантированно поймать мышку?

воскресенье, 23 сентября 2012 г.

6 шаров, 2 взвешивания.

Есть 2 красных шара, 2 зелёных шара и 2 синих шара, т.е. всего 6 штук. В каждой паре шаров одинакового цвета один шар легче другого, причём известно, что все лёгкие шары весят 50 грамм, а все тяжёлые - 100 грамм. В вашем распоряжении чашечные весы без гирь. Как определить лёгкие и тяжёлые шары за два взвешивания?

воскресенье, 16 сентября 2012 г.

Цепь резисторов

На рисунке изображена бесконечная цепь, составленная из одинаковых резисторов сопротивлением R. Чему равно общее сопротивление этой цепи, т.е. сопротивление между точками A и B?

воскресенье, 9 сентября 2012 г.

100 ступенек

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

воскресенье, 2 сентября 2012 г.

Задача фон Неймана

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

Между пунктами А и Б проложена одноколейная железная дорога длиной 200 км. Из пункта А в пункт Б вышел поезд со скоростью 50 км/ч. Одновременно навстречу ему из пункта Б в пункт А с той же скоростью вышел другой поезд. В тот же момент муха, сидевшая на ветровом стекле поезда А, отправилась навстречу поезду Б со скоростью 200 км/ч. Долетев до него, она мгновенно развернулась без потери скорости и направилась навстречу поезду А. Так эта муха и летала между поездами, пока они не столкнулись и не раздавили её. Сколько километров успела пролететь муха?

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

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

воскресенье, 26 августа 2012 г.

3 кубика

Я взял 3 одинаковых кубика и на каждую грань каждого кубика нанёс число от 1 до 6, при этом числа на кубике могут повторяться. То есть помимо стандартной раскраски (1, 2, 3, 4, 5, 6) я могу сделать, например, (1, 1, 2, 2, 3, 3) или (5, 5, 5, 5, 5, 5) на своё усмотрение.

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

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

воскресенье, 19 августа 2012 г.

Дмитрий Медведев и 4 таблетки

Однажды Дмитрий Медведев простудился, и к нему прислали доктора, чтобы зачистить все проблемывылечить его. Доктор прописал выпить утром две таблетки, А и Б, а потом повторить приём вечером, то есть всего нужно выпить 4 таблетки. При этом доктор предупредил, что если пропустить приём хотя бы одной таблетки, то можно схлопотать оранжевую чуму в качестве осложнения. Если же выпить за раз две таблетки А или две таблетки Б, то можно и вовсе словить pussy riot головного мозга.

Доктор ушёл, а Дмитрий Медведев случайно высыпал все 4 таблетки на стол и перепутал их. Теперь перед ним 4 совершенно одинаковых сереньких кругляшка, которые надо как-то выпить, чтобы поправиться. Что он должен сделать, чтобы наверняка выпить по таблетке А и Б утром, а потом повторить приём вечером?

воскресенье, 12 августа 2012 г.

Кирпич

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

воскресенье, 5 августа 2012 г.

Пустыня

Перед Вами безводная пустыня длиной 50 км, которую нужно пересечь. На каждый километр пути Вы потребляете 1 литр воды. Вы можете нести на себе запас воды не более чем в 10 литров (больше - слишком тяжело).

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

Какое минимальное количество воды Вам потребуется, чтобы пересечь пустыню?

воскресенье, 29 июля 2012 г.

Бурьян

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

Может ли зарасти всё поле, если изначально бурьян расположен на 9 клетках? Если может, то приведите пример начального расположения этих 9 клеток. Если не может, докажите это.

воскресенье, 22 июля 2012 г.

Выбрать 6 карт из колоды

Есть полная колода из 52-х карт, без джокеров. Сколькими способами можно выбрать из этой колоды 6 карт так, чтобы в этом наборе были представлены все 4 масти?

воскресенье, 15 июля 2012 г.

10 мешков монет, 1 взвешивание

Есть 10 мешков монет, причём в 9 из них все монеты настоящие, а в одном все монеты фальшивые. Известно, что настоящая монета весит 2 грамма, а фальшивая - 1 грамм. Также есть электронные весы, которые показывают вес того, что положили в чашу, в граммах. Как за одно взвешивание вычислить мешок с фальшивыми монетами?

воскресенье, 8 июля 2012 г.

2 мудреца и 2 числа

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

Когда султан сообщил им сумму и произведение, мудрецы задумались.
- Я не знаю этих чисел, - нарушил молчание А.
- Я знал, что ты не знаешь, - ответил Б.
- Тогда я знаю их! - воскликнул А.
- Ну тогда и я знаю, - заключил Б.

Назовите эти числа.

воскресенье, 1 июля 2012 г.

Жизненное

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

Короче говоря, задача такова. Я взял сумму A под r процентов на срок в n периодов. Каким должен быть аннуитетный периодический платёж x, чтобы я полностью рассчитался с банком? Интересует, конечно, как выводится эта формула, а не готовый результат из Википедии.

воскресенье, 24 июня 2012 г.

Русская рулетка

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

воскресенье, 17 июня 2012 г.

Два кубика

Я бросил два одинаковых игральных кубика. На одном из них выпала шестёрка, а другой укатился под стол, и я его не вижу. Какова вероятность того, что на кубике под столом тоже выпала шестёрка? Ответы "1/6" и "1/36" неправильные.

Бонусный вопрос: что нужно изменить в условии задачи, чтобы ответ "1/6" стал правильным?

воскресенье, 10 июня 2012 г.

Игла на плоскости

Бесконечную плоскость расчертили параллельными прямыми, расположенными на расстоянии H друг от друга. На эту плоскость наудачу бросают иголку длины L < H. Какова верятность того, что иголка, упав на плоскость, пересечёт одну из прямых?

воскресенье, 3 июня 2012 г.

Несимметричная монета

Дмитрий Медведев и Владимир Путин должны решить, кому из них ехать в скучную командировку в далёкий Кэмп-Дэвид, пропуская целую неделю тренировок по бадминтону. Обычно они решали это простым броском монетки: едет тот, кому выпадает решка. Однако недавно Дмитрий Медведев прочитал в Твиттере, что в реальном мире все монетки несимметричные: на некоторых чаще выпадает орёл, на некоторых - решка. Поэтому говорить о честном выборе с шансами 50/50 для каждого не приходится.

Как можно модифицировать процесс принятия решения при помощи монетки так, чтобы вероятности исходов были бы равны, даже если монетка несимметричная?

воскресенье, 27 мая 2012 г.

Волейбол

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

воскресенье, 20 мая 2012 г.

4 мухи

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

Могут ли мухи после определённой последовательности ходов расположиться в ряд по диагонали?

воскресенье, 13 мая 2012 г.

Примитивы синхронизации

Представьте, что Вы должны написать многопоточную программу на языке, в котором почти нет примитивов синхронизации. Единственное средство - функция TSL (test, set and lock), которая выглядит следующим образом:
int tsl(int* value) {
   int oldValue = *value;
   *value = 1;
   return oldValue;
}
При этом среда гарантирует, что функция атомарна. Например, что компилятор транслирует её в атомарную машинную инструкцию.

Как реализовать с помощью этого примитива критическую секцию? Оптимально было бы получить реализацию двух функций: lock() и unlock().

воскресенье, 6 мая 2012 г.

Гномы и колпаки

Людоеды поймали 1000 гномов и объявили, что на следующий день им предстоит испытание.

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

У гномов есть возможность посовещаться до начала испытания и договориться о стратегии. Как им нужно поступить, чтобы спаслось как можно больше? Передача информации интонацией запрещена: гном имеет право только сказать "красный" или "синий" максимально нейтральным тоном. Впрочем, он может сказать это достаточно громко, чтобы услышали все стоящие впереди.

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

понедельник, 30 апреля 2012 г.

Презервативы

Два мужчины и две женщины оказались на необитаемом острове. Каждый из них болен каким-то венерическим заболеванием, причём все заболевания разные. Как сделать так, чтобы каждый мужчина смог заняться сексом с каждой женщиной, и никто не подхватил нового заболевания, если у них всего 2 презерватива?

воскресенье, 22 апреля 2012 г.

2 пловца

Два пловца одновременно стартуют по одной дорожке от одного бортика бассейна и плавают туда-сюда с постоянными скоростями. Один проплывает бассейн от одного бортика до противоположного за 11 минут, а второй - за 30 минут. Достигнув бортика, они мгновенно разворачиваются и начинают плыть в обратном направлении с прежней скоростью. Пловцы остановятся, когда оба одновременно окажутся у того бортика, с которого они стартовали. Сколько раз за это время быстрый пловец догонит медленного?

Пользуясь случаем, хочу передать привет Рустему, рассказавшему мне эту задачу два года назад.

воскресенье, 15 апреля 2012 г.

Уснуть и видеть сны

Продолжаем исследовать способы выстрелить себе в ногу на Java. Ещё одна головоломка с уже известного нам сайта.

Иногда бывает такое, что я просыпаюсь только для того, чтобы понять, что на самом-то деле я всё ещё сплю. Каждый раз, когда это случается, я чувствую себя несколько не в своей тарелке. Чтобы этого избежать, я начал считать уровни рекурсии, погружаясь в сон:
public class Sleeper {
    private int level;
    public synchronized int enter(Dream dream) {
        level++;
        try {
            dream.dream(this);
        } finally {
            level--;
        }
        return level;
    }
}
Выглядит надёжно, не так ли? Погружаясь в сон, я увеличиваю счётчик. Выходя из сна, я уменьшаю его. Благодаря блоку finally я уверен, что не забуду уменьшить счётчик, даже если на каком-то уровне рекурсии очередной сон выбросит исключение. Поскольку метод объявлен synchronized, я не боюсь, что в мой сон влезет какой-то другой поток.

Теперь я со спокойной душой ложусь спать следующим образом:
public class Main {
    public static void main(String[] args) {
        if (new Sleeper().enter(new Dream()) != 0) {
            // The goal is to reach this line
            System.out.println("Am I still dreaming?");
        }
    }
}
Есть ли ошибка в моих рассуждениях? Можно ли написать такой класс Dream, что он сломает мою программу, и она напечатать помеченную строку? Изменять классы Sleeper и Main нельзя.
public class Dream {
    public void dream(Sleeper s) {
        // TODO implement me
    }
}
Действуют те же ограничения, что и в задаче про клоунов. Вкратце, нельзя использовать reflection и манипулировать байт-кодом на лету. В остальном можете писать неограниченно грязный код, при условии, конечно, что компилятор его съест.

воскресенье, 8 апреля 2012 г.

Как выбрать президента?

Владимир Путин и Дмитрий Медведев решают, кому из них быть президентом. Путин загадал три натуральных числа X, Y и Z, каждое из которых меньше 1000. Медведев должен назвать три натуральных числа A, B и C (не обязательно меньше 1000), после чего Путин сообщит ему сумму A*X+B*Y+C*Z. Чтобы сохранить за собой президентский пост Медведеву нужно будет угадать задуманные числа. Как он может это сделать?

Эту задачу я нашёл на RSDN'е.

воскресенье, 1 апреля 2012 г.

Сколько клоунов влезет в Фольксваген?

Думаю, многие знают цирковой номер, в котором из крохотного Volkswagen Beetle ("Запорожец" по-немецки) вылезает вереница клоунов, которой, кажется, нет конца. Невольно задумаешься: как же их туда упаковали? Смоделируем эту ситуацию программно.

Даны два класса на Java:
public class Clown {
    // nothing
}
public class Volkswagen {
    private static final int CAPACITY = 5;
    private Set<Clown> clowns = new HashSet<Clown>();

    public synchronized void add(Clown clown) {
        if (clowns.size() >= CAPACITY) {
            throw new IllegalStateException("I'm full");
        } else {
            clowns.add(clown);
        }
    }

    public synchronized void done() {
        if (clowns.size() == 20) {
            // The goal is to reach this line
            System.out.println("I'm a Volkswagen with 20 clowns!");
        }
    }
}
Нужно написать код, который в конце концов вызовет done() и напечатает указанную строку. Начать можно с чего-то такого (работать, конечно, этот пример не будет):
public class Clowns {
    public static void main(String args[]) {
        Volkswagen vw = new Volkswagen();
        for (int i=0; i<20; i++) {
            vw.add(new Clown());
        }
        vw.done();
    }
}
Несколько ограничений:
0. Нельзя изменять данные Вам файлы Clowns.java и Volkswagen.java.
1. Программа должна работать с включенным SecurityManager'ом (т.е. с опцией -Djava.security.manager). Поэтому воспользоваться reflection'ом, чтобы изменить private поле, не получится.
2. Никакие другие опции JVM использовать нельзя. В частности, нельзя подсовывать JVM свой подхаченный ClassLoader, чтобы подменить стандартную реализацию java.util.HashMap
3. Должна выполниться именно указанная строка указанного класса, а не другая строка каким-то хитрым образом скопированного или унаследованного класса.

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

Оригинал задачи на английском я нашёл здесь.

четверг, 29 марта 2012 г.

Наводнение (продолжение)

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

воскресенье, 25 марта 2012 г.

Наводнение

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

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

воскресенье, 18 марта 2012 г.

Старая советская задача

Перед Вами картинка. Глядя на неё, ответьте на 9 вопросов:
1. Сколько туристов живет в этом лагере?
2. Когда они сюда приехали: сегодня или несколько дней назад?
3. На чем они сюда приехали?
4. Далеко ли от лагеря до ближайшего селения?
5. Откуда дует ветер: с севера или юга?
6. Какое сейчас время дня?
7. Куда ушел Шура?
8. Кто был вчера дежурным? (Назовите по имени.)
9. Какое сегодня число какого месяца?

воскресенье, 11 марта 2012 г.

Дмитрий Медведев и 1000 бутылок

Дмитрий Медведев готовится к церемонии вступления в должность одного своего друга, которая состоится через 2 месяца. В качестве подарка он подготовил 1000 бутылок дорогого французского вина.

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

В распоряжении Дмитрия Медведева есть 10 оппозиционеров подопытных кроликов. Он хочет за оставшиеся до церемонии 2 месяца вычислить отравленную бутылку, а остальные 999 подарить. Что он должен для этого сделать?

среда, 7 марта 2012 г.

10 перчаток

В ящике лежит 5 пар печаток: 3 пары синих и 2 пары зелёных, т.е. всего 10 перчаток. Из ящика наугад достали одну за другой 3 перчатки. Какова вероятность того, что среди них найдётся пара (т.е. левая и правая перчатки одного цвета)?

суббота, 3 марта 2012 г.

Эльфийский МММ

Бессмертный эльф Леголас несколько тысяч лет назад вложил 100 золотых монет в инвестиционный фонд "Мордор Может Многое" (МММ) под 5% годовых. Теперь он хочет забрать свои деньги и купить однокомнатное дерево в Лориене.

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

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

Интуитивно, конечно, кажется, что все цифры от 1 до 9 равновероятны, и шансы угадать в любом случае равны 1/9. На самом же деле, Леголас может забрать свой вклад с вероятностью 30%, если назовёт нужную цифру.

воскресенье, 26 февраля 2012 г.

Сумасшедший пассажир

Идёт посадка пассажиров в 100-местный самолёт. У каждого пассажира есть билет, в котором указано его место, и все места проданы (но, конечно, без овербукинга). Однако первый же зашедший в салон пассажир выбрал себе случайным образом одно из 100 мест и разместился на нём.

Следующие 99 пассажиров поступают следующим образом: если место, указанное в билете, свободно, пассажир садится на него. В противном случае (т.е. если назначенное ему место уже занято) пассажир садится на любое из свободных мест случайным образом.

Какова вероятность того, что последний (сотый) пассажир окажется на своём месте?

четверг, 23 февраля 2012 г.

Дмитрий Медведев и метро

Дмитрий Медведев любит немного развеяться после трудного рабочего дня. Для этого он записался в секцию бадминтона (тренер - МСМК В. Путин) и в кружок занимательной арифметики (преподаватель - д.ф.-м.н. В. Чуров).

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

Известно, что поезда в обоих направлениях следуют с одинаковым интервалом в 2 минуты по чёткому расписанию. Дмитрий Медведев спускается в метро между 18:00 и 18:30, и можно считать, что каждый день это время выбирается случайным образом.

Казалось бы, время между кружком и секцией должно было бы распределяться поровну. Однако через год оказалось, что бадминтоном Дмитрий Медведев занимался в среднем в 3 раза чаще, чем арифметикой. Как такое может быть?

воскресенье, 19 февраля 2012 г.

Нормальный алгоритм

Нормальный алгорим Маркова представляет собой упорядоченный набор правил замен подстрок. Например, если у нас есть алгоритм
"Мой" -> "Моя"
"дядя" -> "тётя"
то, применив его к строке "Мой дядя самых честных правил", мы получим строку "Моя тётя самых честных правил".

Другими словами, алгоритм Маркова действует следующим образом:
1. Просматривая список правил сверху вниз, найти первое правило, которое применимо к текущей строке.
2. Если такого правила нет, то закончить алгоритм.
3. Если правило нашлось, то выполнить подстановку и перейти на шаг 1. При этом, если левая часть правила содержится в строке более одного раза, то будет заменено только самое левое вхождение.

Напишите нормальный алгоритм, который будет складывать двоичные числа. То есть, подав ему на вход строку "10+11", мы должны получить на выходе строку "101".

Для проверки решения можно воспользоваться онлайн интерпретатором:

Волшебное число

Назовём волшебным натуральное девятизначное число, которое обладает следующими свойствами:
1. В нём содержатся по одному разу все цифры от 1 до 9 (т.е. все цифры кроме нуля).
2. Само волшебное число делится на 9. Если из него вычеркнуть последнюю цифру, то оставшееся восьмизначное число будет делиться на 8. Если из волшебного числа вычеркнуть последние две цифры, то оставшееся семизначное число будет делиться на 7. И так далее: вычёркивая из волшебного числа n последних цифр, мы будем получать число, которое делится на 9-n.

К примеру, если бы число 123456789 являлось волшебным (оно им не является), то число 12345678 делилось бы на 8, 1234567 делилось бы на 7, 123456 делилось бы на 6 и так далее.

Найдите это волшебное число (оно единственное).

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

5 произведений

Я задумал 4 положительных числа (не обязательно целых): a, b, c и d. Очевидно, что из них можно составить 6 попарных произведений: a*b, a*c, a*d, b*c, b*d и c*d. Я скажу Вам, чему равны 5 из них, но не уточню, каким выражениям они соответствуют. Вот эти произведения: 2, 3, 4, 5, 6.

Чему равно шестое произведение?