Математические задачи - Алгоритмы
Трём путешественникам нужно пересечь реку. У каждого из них определенное количество золотых монет в рюкзаке. Путешественник А имеет 1000 монет Путешественник B имеет 700 монет Путешественник C имеет 300 монет
Для пересечения реки есть лодка, которая может вместить максимум 2 объекта - двух путешественников или путешественника с рюкзаком. Проблема заключается в том, что если оставить любого путешественника с количеством золота, превышающим его собственное - он сбежит, прихватив все деньги. То же касается и двух путешественников, если они останутся с золотом, превышающим их суммарные запасы - они убегут с золотом. Какая стратегия позволит всем пересечь реку и остаться при деньгах?
"Демократические" выборы
В стране Анчурии, где правит президент Мирафлорес, приблизилось время новых президентских выборов. В стране ровно 20 000 000 избирателей, из которых только один процент (регулярная армия Анчурии) поддерживает Мирафлореса. Он хочет быть демократически избранным.
"Демократическим голосованием" Мирафлорес называет вот что: всех избирателей разбивают на несколько равных групп, затем каждую из этих групп вновь разбивают на некоторое количество равных групп, затем эти последние группы снова разбивают на равные группы и так далее; в самых мелких группах выбирают представителя группы - выборщика, затем выборщики выбирают представителей для голосования в ещё большей группе и так далее; наконец, представители самых больших групп выбирают президента. Мирафлорес сам делит избирателей на группы. Может ли он так организовать выборы, чтобы его избрали президентом? (В каждой группе выборщики выбирают своего представителя простым большинством. При равенстве голосов побеждает оппозиция.)
Найти победителей
У вас имеется 25 скаковых лошадей, среди которых требуется выбрать трех самых быстрых. К сожалению, вам запрещено пользоваться любыми измерениями для определения скорости лошади или времени забега. Какое минимальное количество забегов потребуется провести, если в скачках одновременно могут участвовать только 5 лошадей?
Задача про циклический поезд
Есть поезд, состоящий из некоторого количества вагонов. Вы находитесь в одном из них. Это очень странный поезд, потому что его вагоны сцеплены в кольцо. В каждом вагоне есть лампочка, которую вы можете включать и выключать. Ваша задача заключается в том, чтобы определить количество вагонов в поезде. Опишите алгоритм решения этой задачи.
Других людей и прочих живых или неживых существ в поезде нет. Лампочки нельзя выкручивать, они не перегорают и не нагреваются, рисовать на стенах мелом нельзя, окон у вагонов нет. В общем, состояние поезда — это только лампочки. Кстати, начальное состояние поезда неизвестно, то есть изначально какие-то лампочки могут гореть, а какие-то не гореть. Единственный способ узнать, горит ли лампочка в определенном вагоне — это войти в него и посмотреть.
Конфеты и коробки
2010 конфет лежат в 100 коробках. Девочка и мальчик по очереди берут по одной конфете. Начинает девочка. Выигрывает мальчик, если последние конфеты остались в одной коробке. Иначе выигрывает девочка. Кто выиграет при правильной стратегии?
Спички
В коробке лежат 300 спичек. Двое играющих поочередно имеют право взять из коробки любое количество спичек, но не более половины имеющихся в ней. Проигрывает тот, кто не сможет сделать очередного хода. Кто выиграет и какова выигрышная стратегия?
Натуральные числа
Двое игроков по очереди называют натуральные числа, причем следующее число должно быть строго меньше предыдущего, но не меньше половины предыдущего. Проигрывает тот, кто будет вынужден назвать число 1. Первым ходом первый игрок назвал 2003. Кто выиграет?
Ящик апельсинов
Чебурашка и Шапокляк поедают ящик апельсинов. За один ход Шапокляк может либо съесть один хороший апельсин, либо заменить два хороших апельсина на два гнилых, Чебурашка может либо съесть два хороших апельсина, либо съесть один хороший и выкинуть один гнилой. Первым ходит Чебурашка. Проигрывает тот, кто не сможет сделать ход.
Кто выигрывает при правильной игре, если изначально в ящике было n хороших и ни одного гнилого апельсина?
Пять разбойников делят добычу
Пять разбойников делят добычу в 50 золотых. Делят добычу они следующим образом:
1) Самый старший из них предлагает вариант дележа добычи. 2) Все (включая самого старшего) голосуют. 3) Если за этот вариант дележа проголосует более половины разбойников, то на этом дележ добычи заканчивается. 4) В противном случае все остальные убивают самого старшего разбойника и дележ начинается снова с пункта 1).
Каждый разбойник в первую очередь хочет сохранить себе жизнь, на втором месте в его списке приоритетов стоит получение как можно большей доли. Каков будет результат дележа?
Сосисочная стратегия
Имеется цепочка сосисок длины n. Два кота по очереди перегрызают по одной перемычке между сосисками и съедают образовавшиеся одиночные сосиски. Выигрывает тот, кто съест большее число сосисок. Какой должны быть выигрышная стратегия?
Математическая задача
Петя и Вася (начинает Петя) по очереди стирают буквы из набора "МАТЕМАТИЧЕСКАЯ ЗАДАЧА". За один ход разрешается стереть или ровно одну букву, или все одинаковые буквы. Выигрывает тот, кто сотрет последнюю букву. Кто выиграет в этой игре и какой должна быть выигрышная стратегия?
С вещами на выход
В узком 100-метровом коридоре, шириной в одного человека, стоят 25 узников на некотором расстоянии друг от друга. У всех завязаны глаза. По команде они начинают двигаться. Кто-то налево, кто-то направо. Если они сталкиваются друг с другом, то разворачиваются и идут в другую сторону. Если доходят до конца коридора — выходят на свободу, и их можно больше не учитывать. Скорость каждого — 1 метр в секунду. Время на разворот не считается. Через какое минимальное время все узники гарантированно покинут коридор? (Решение очень простое — не нужно ничего считать.)
Кот Леопольд
Перед котом Леопольдом пять мышиных норок, расположенных в ряд. В одной из этих норок спряталась мышка. Леопольд может засунуть лапу в любую из норок и попробовать поймать мышку. Мышка боится кота, поэтому после каждой его попытки обязательно перебегает в соседнюю норку справа или слева. Может ли кот гарантированно поймать мышку? Если да, то как он должен действовать?
Поменять местами
Поменяйте местами синие и черные фишки. Разрешается двигать фишки только на смежное пустое место:
Обналичивание
На петином счету в банке лежит 500 долларов. Банк разрешает совершать операции только двух видов: снимать 300 долларов или добавлять 198 долларов. Какую максимальную сумму Петя может снять со счета, если других денег у него нет?
Белки и кролики
Перед вами восемь перенумерованных пней. На пнях 1 и 3 сидят кролики, на пнях 6 и 8 - белки. И белки, и кролики почему-то недовольны своими местами и хотят обменяться пнями: белки желают сидеть на местах кроликов, а кролики - на местах белок. Попасть на новое место они могут, прыгая с пня на пень по следующим правилам:
1) прыгать с пня на пень можно только по тем линиям, которые показаны на рисунке; каждый зверек может делать несколько прыжков кряду;
2) два зверька на одном пне поместиться не могут, поэтому прыгать можно только на свободный пень. Имейте также в виду, что зверьки желают обменяться местами за наименьшее число прыжков. Впрочем, меньше чем 16 прыжками им не обойтись.
Как же они это сделают?
P.S. Задачу удобно решать с помощью скрипта, написанного одним из наших посетителей - http://kokoscripts.ucoz.ru/index/belki_i_kroliki/0-14
Чайный сервиз
Мне пришлось как-то целый вечер ждать поезд на маленькой станции. Не было ни книг, ни газет, ни собеседников, и я не знал, чем наполнить часы ожидания. К счастью, я вспомнил об одной занимательной задаче, которая незадолго до того попалась мне в иностранном журнале. Задача состояла в следующем.
Стол разграфлен на 6 квадратов, в каждом из которых, кроме одного, помещается какой-нибудь предмет. Я воспользовался чайной посудой и разместил по квадратам чашки, чайник и молочник, как показано на рисунке:
Суть задачи в том, чтобы поменять местами чайник и молочник, передвигая предметы из одного квадрата в другой по определенным правилам, а именно:
1) предмет перемещать только в тот квадрат, который окажется свободным;
2) нельзя передвигать предметы по диагонали квадрата;
3) нельзя переносить один предмет поверх другого;
4) нельзя также помещать в квадрат более одного предмета, даже временно.
Эта задача имеет много решений, но интересно найти самое короткое, т. е. обменять местами чайник и молочник за наименьшее число ходов.
В поисках решения незаметно прошел вечер; я покидал станцию, так и не найдя кратчайшего решения.
Может быть, читатели найдут его? На всякий случай предупреждаю, что искомое наименьшее число ходов все же больше дюжины, хотя и меньше полутора дюжин.