В футбольном турнире каждая команда сыграла с каждой по одному разу. Известно, что ровно треть команд хотя бы раз сыграла вничью. Из оставшихся команд ровно 3/4 хотя бы раз проиграли. Сколько матчей этого турнира завершились победой одной из команд?
понедельник, 28 марта 2011 г.
Апельсины и яблоки
Перед Вами три ящика, на которые прилеплены таблички: "Апельсины", "Яблоки" и "Апельсины и яблоки". Известно, что все три таблички перепутаны, и ни одна не висит на своём месте.
Вы должны, не глядя, вытащить из одного ящика ровно один фрукт и после этого перевесить таблички правильно. Как это сделать?
Вы должны, не глядя, вытащить из одного ящика ровно один фрукт и после этого перевесить таблички правильно. Как это сделать?
воскресенье, 27 марта 2011 г.
пятница, 25 марта 2011 г.
Верёвочный мост
Одна из самых известных задач с собеседований в Microsoft.
Четыре путника должны ночью переправиться по шаткому верёвочному мосту на другой берег реки. Мост настолько ненадёжен, что одновременно идти по нему могут только два человека, и только с фонариком. К сожалению, у них всего один фонарик на четверых.
Каждый из путников может пересечь мост со своей скоростью. Первый делает это за 1 минуту, второй за 2 минуты, третий за 5 минут, четвёртый за 10 минут. Если по мосту вместе идут два человека, то они движутся со скоростью самого медленного из них.
За какое минимальное время путники могут переправиться через реку? Ответ "19 минут" неправильный.
Четыре путника должны ночью переправиться по шаткому верёвочному мосту на другой берег реки. Мост настолько ненадёжен, что одновременно идти по нему могут только два человека, и только с фонариком. К сожалению, у них всего один фонарик на четверых.
Каждый из путников может пересечь мост со своей скоростью. Первый делает это за 1 минуту, второй за 2 минуты, третий за 5 минут, четвёртый за 10 минут. Если по мосту вместе идут два человека, то они движутся со скоростью самого медленного из них.
За какое минимальное время путники могут переправиться через реку? Ответ "19 минут" неправильный.
среда, 23 марта 2011 г.
Закольцованный поезд
Несколько вагонов сцеплены кольцом: последний вагон прицеплен к первому. В каких-то вагонах горит свет, в каких-то темно. Вы находитесь в одном из вагонов и можете переходить из вагона в вагон и включать/выключать свет.
Как определить, сколько вагонов в кольце, если все вагоны неотличимы друг от друга, а начальное распределение тёмных и светлых вагонов заранее неизвестно?
Как определить, сколько вагонов в кольце, если все вагоны неотличимы друг от друга, а начальное распределение тёмных и светлых вагонов заранее неизвестно?
вторник, 22 марта 2011 г.
Выбрать все числовые отрезки из таблицы
Для разнообразия, небольшая задачка по SQL.
У Вас есть таблица numbers из одной колонки num. Нужно написать запрос, который выберет все отрезки, на которые числа из таблицы разбивают числовую ось. К примеру, если в таблице есть записи 1, 3, 7 и 10, то в результате выполнения запроса Вы должны получить 3 строки: (1,3), (3,7) и (7,10).
У Вас есть таблица numbers из одной колонки num. Нужно написать запрос, который выберет все отрезки, на которые числа из таблицы разбивают числовую ось. К примеру, если в таблице есть записи 1, 3, 7 и 10, то в результате выполнения запроса Вы должны получить 3 строки: (1,3), (3,7) и (7,10).
Монеты на столе
Двое играют в следующую игру: они по очереди выкладывают на прямоугольный стол одинаковые монеты (в варианте для взрослых - ставят кружки пива). Проигрывает тот, кто не может сделать ход (т.е. тот, кто в свой ход не может найти места для монеты). Есть ли выигрышная стратегия у одного из игроков?
На мой взгляд, задача довольно сложная, но, например, на малом мехмате уверены, что задача по силам пятиклассникам.
На мой взгляд, задача довольно сложная, но, например, на малом мехмате уверены, что задача по силам пятиклассникам.
понедельник, 21 марта 2011 г.
Знаменитость
Знаменитостью (celebrity) на вечеринке называется человек, которого знают все остальные присутствующие, а сам он не знает никого. (Нужно отметить, что если Петя знает Васю, то не факт, что Вася знает Петю).
Вы пришли на вечеринку, на которой присутствуют n человек, чтобы выяснить, есть ли на ней знаменитость. Вы можете подходить к очередному гостю и задавать вопрос вида "Простите, Вы знаете человека X?" и получать ответ да/нет.
Как выяснить, есть ли на вечеринке знаменитость, и если есть, то кто именно, задав минимальное число вопросов?
Есть более формальная версия задачи. Рассмотрим ориентированный граф G(V,E). Вершину v назовём стоком графа, если для любой вершины u отличной от v существует дуга (u, v) и не существует дуги (v, u). Требуется либо найти такую вершину в графе, либо указать, что её нет.
Вы пришли на вечеринку, на которой присутствуют n человек, чтобы выяснить, есть ли на ней знаменитость. Вы можете подходить к очередному гостю и задавать вопрос вида "Простите, Вы знаете человека X?" и получать ответ да/нет.
Как выяснить, есть ли на вечеринке знаменитость, и если есть, то кто именно, задав минимальное число вопросов?
Есть более формальная версия задачи. Рассмотрим ориентированный граф G(V,E). Вершину v назовём стоком графа, если для любой вершины u отличной от v существует дуга (u, v) и не существует дуги (v, u). Требуется либо найти такую вершину в графе, либо указать, что её нет.
Домино
Кость домино представляет собой прямоугольник размером 2x1. На костях нет никаких обозначений, все они неотличимы друг от друга.
У Вас есть коробка размера 2xn, в которую помещаются n костей. Вы можете упаковывать кости плашмя, не помещая одну на другую. К примеру, если у Вас коробка 2x3 и 3 кости, то Вы можете упаковать их тремя различными способами:
Сколькими способами можно упаковать n костей в коробку 2xn?
По данным разведки, такую задачу дают на собеседовании в московском офисе Гугла.
У Вас есть коробка размера 2xn, в которую помещаются n костей. Вы можете упаковывать кости плашмя, не помещая одну на другую. К примеру, если у Вас коробка 2x3 и 3 кости, то Вы можете упаковать их тремя различными способами:
По данным разведки, такую задачу дают на собеседовании в московском офисе Гугла.
Деление отрезка пополам
Вот и первая задача в этом блоге.
Все мы с детского садика знаем, как разделить отрезок на две равные части с помощью циркуля и линейки. А вот как разделить отрезок пополам, пользуясь ТОЛЬКО циркулем (без линейки)?
Все мы с детского садика знаем, как разделить отрезок на две равные части с помощью циркуля и линейки. А вот как разделить отрезок пополам, пользуясь ТОЛЬКО циркулем (без линейки)?
Hello World
Лишь отметив 25-й день рождения, я созрел для того, чтобы завести себе уютненький бложик.
Так сложилось, что в моей голове скопилась масса интересных задачек на сообразительность. Поскольку с годами память лучше не становится, я решил записывать их в блог. С одной стороны, это позволит делиться понравившимися головоломками с друзьями. С другой - я смогу не беспокоиться о том, что забуду красивую задачку, которую мне дали 10 лет назад.
Сразу скажу, что совершенно не претендую на оригинальность. Наверняка каждый найдёт здесь "жуткий боян", который он слышал, читал или придумал сто лет назад. Тем не менее, я надеюсь, что среди известных вам головоломок вы всегда найдёте здесь что-то новое.
Так сложилось, что в моей голове скопилась масса интересных задачек на сообразительность. Поскольку с годами память лучше не становится, я решил записывать их в блог. С одной стороны, это позволит делиться понравившимися головоломками с друзьями. С другой - я смогу не беспокоиться о том, что забуду красивую задачку, которую мне дали 10 лет назад.
Сразу скажу, что совершенно не претендую на оригинальность. Наверняка каждый найдёт здесь "жуткий боян", который он слышал, читал или придумал сто лет назад. Тем не менее, я надеюсь, что среди известных вам головоломок вы всегда найдёте здесь что-то новое.
Подписаться на:
Сообщения (Atom)