Рыцари и лжецы
Условие
Путешественник приехал на остров, каждый из 100 жителей которого или лжец, который всегда обманывает, или рыцарь, который всегда говорит правду. При этом среди жителей острова есть хотя бы один лжец.
Лжецы решили лгать таким образом, чтобы каких бы 50 жителей путешественник не собирал вместе, присутствующие среди них лжецы всегда отвечали на вопрос о числе рыцарей среди собранных туземцев так, чтобы путешественник получал один и тот же набор из 50 ответов. Какое наибольшее число рыцарей могло быть на острове?
Ответ
Решая эту головоломку, нужно рассуждать следующим образом: рыцарей на острове менее 50, иначе путешественник, выбрав всех рыцарей, получил бы 50 ответов "пятьдесят", а, выбрав одного лжеца и 49 рыцарей, услышал бы иной набор ответов. Получается, что лжецов на острове не менее 50 человек.
Поскольку набор ответов должен выглядеть правдоподобно, в наборе ответов должен быть 1 ответ "один", 2 ответа "два", 3 ответа "три", 9 ответов "девять" и еще 5 неправдоподобных ответов. Из этого можно сделать вывод, что на острове может быть не больше 9 рыцарей.
Десант
Условие
В игре "Десант" две армии захватывают страну. Игроки ходят по очереди, каждым ходом занимая один из свободных городов. Первый город захватывается с воздуха, а каждым следующим ходом можно захватить любой населенный пункт, соединенный дорогой с каким-либо городом, уже занятым этой армией. Если таких городов нет, армия прекращает боевые действия, и игрок считается проигравшим.
Постройте такую схему городов и дорог, чтобы игрок, который ходит вторым, смог захватить более половины всех городов, независимо от того, как будет действовать армия его соперника.
Ответ
Пусть на кольце последовательно расположены точки А1, В2, А3, В1, А2, В3, причем от точек А1, А3, А2 отходят "ветки" с N городами в каждой.
Если первый игрок первым ходом занимает точку на ветке, армия второго игрока должна занять соответствующую точку Аi.
Если первая армия первым ходом занимает точку Ai, то вторая – Bi.
Если первый игрок первым ходом занимает точку Bi, то второй – любую из точек Aj (j не равно i). Дальнейшие действия очевидны. Поскольку в конце игры вторая армия занимает хотя бы две точки Ai, первый игрок захватывает не более, чем n + 3 точек. Поэтому доля городов, захваченных армией второго игрока, не менее (2n + 3)/(3n + 6) > 1/2.
В условии задачи вместо 1/2 можно взять любое число, меньшее 2/3 (в этом случае N надо выбирать достаточно большим).
Фокусники
Условие
Два фокусника показывают зрителям интересный фокус. Одному из присутствующих они дают колоду карточек с числами от 1 до 78, чтобы он перемешал ее, отобрал любые 40 карточек и отдал их первому фокуснику.
Тот выбирает из полученных карточек две и возвращает их зрителю. Последний добавляет к ним одну карточку из своих 38 и, перемешав, отдает эти карточки второму фокуснику, который сразу же показывает, какая из карточек была добавлена в стопку зрителем. Попробуйте разоблачить фокус.
Ответ
Фокусники любым образом разбивают 78 карточек на 39 групп по две карты и запоминают эту комбинацию. Какие бы 40 карточек зритель не отдал первому фокуснику, среди них обязательно окажутся две карточки из одной пары (поскольку пар всего 39).
Первый фокусник должен дать зрителю две карточки из одной пары. Тогда карта, добавленная зрителем, будет из другой пары, ее сможет определить второй фокусник.
Кладоискатели
Условие
Три кладосикателя – Илья, Дмитрий и Алексей – нашли шкатулку, в которой было 6 монет: 3 золотых и 3 серебряных. Кладоискатели перемешали все монеты и по очереди с завязанными глазами вытащили по 2 монеты, не сказав друг другу, кому какие монеты достались.
Илья не знает, какие монеты досрались Дмитрию, а какие Алексею, но знает, какие монеты достались ему самому.
Придумайте вопрос, на который Илья ответит "да", "нет" или "не знаю", и по ответу на который вы сможете догадаться, какие монеты ему достались.
Ответ
Вопрос: "Правда ли, что у тебя золотых монет больше, чем у Алексея?".
Если у Ильи 2 золотые монеты, он скажет "да", поскольку у Алексея не может быть больше одной золотой монеты.
Если обе монеты у Ильи серебряные, а у Алексея хотя бы одна золотая, он ответит "нет".
Если же ему достались разные монеты, он ответит "не знаю", так как у Алексея может оказаться как 2 золотые, так и 2 серебряные монеты.
Пятидесятикопеечные монеты
Условие
В ряд выложили 2001 монету достоинством 5, 10 и 50 копеек. Оказалось, что между любыми двумя пятикопеечными монетами лежит хотя бы одна монета, между двумя десятикопеечными монетами лежат хотя бы две монеты, а между любыми двумя пятидесятикопеечными монетами лежат хотя бы три монеты. Определите, сколько в ряду пятидесятикопеечных монет.
Ответ
Рассмотрим любые четыре идущие подряд монеты и попробуем доказать, что среди них есть одна пятидесятикопеечная. Если среди них нет пятидесятикопеечной, то пятикопеечные и десятикопеечные монеты чередуются, что невозможно.
Двух пятидесятикопеечных монет тоже быть не может, поскольку между ними должно быть хотя бы три монеты. Из этого можно сделать вывод, что среди первых 2000 монет ровно 500 пятидесятикопеечных. Следовательно, всего пятидесятикопеечных монет может быть 500 или 501.
Неверные мужья
Условие
В некотором королевстве правил король. Все мужчины этого королевства хорошо разбирались в математике, все они почитали своего короля и выполняли все, что он им прикажет.
Король всегда говорил только правду. Все выстрелы в королевстве слышны в каждом доме, а все перечисленные факты известны каждому жителю королевства.
Король был озабочен неверностью некоторых жен в королевстве и решил покончить с их изменами раз и навседа. Поэтому он собрал всех женатых мужчин на городской площади и сделал следующее заявление: "Существует по крайней мере одна неверная жена в королевстве. Все женатые мужчины знают о верности или неверности всех чужих жен, но о своей супруге не имеют никакой информации. Я запрещаю вам обсуждать верность своей жены с другими мужчинами. Как только муж узнает, что его жена изменяет ему, он должен застрелить ее в тот же день в полночь".
Тридцать девять тихих ночей минуло после речи короля. В сороковую ночь прозвучали выстрелы. Сколько жен было убито?
Ответ
Обозначим n – число неверных жен. Тогда муж каждой неверной жены знает о существовании (n – 1) неверной жены. Пусть n = 1. Тогда муж этой жены полагает, что все жены верны.
Услышав от корял, что существует по крайней мере одна неверная жена – он понимает, что это его супруга, которую он обязан застрелить.
Далее пусть n = 2. Мужья этих женщин полагают, что в королевстве есть лишь одна неверная жена и ждут, что ее супруг застрелит ее в первую же ночь. Поскольку убийства не произошло, это значит, что их собственная жена неверна и ее следует застрелить. Действуя далее по индукции, получаем, что n неверных жен будет застрелено в n-ю ночь, то есть в сороковую ночь было убито 40 неверных жен.
Адрес Саши
Условие
Даша и Наташа хотят отправиться в гости к Саше. Все они живут на одной и той же улице (в разных домах), но Даша и Наташа не знают, где живет Саша. Дома на улице имеют номера от 1 до 99.
Даша спросила Сашу: "Верно ли, что номер твоего дома – полный квадрат?". Саша ответил. Затем Даша спросила: "Верно ли, что номер твоего дома больше 50?". Саша ответил.
Затем Даша подумала, что она знает адрес Саши и пошла к нему в гости. Оказалось, что она ошиблась, что неудивительно, поскольку Саша ответил правдиво только на второй вопрос.
После этого Наташа спросила Сашу: "Верно ли, что номер твоего дома – полный куб?". Саша ответил. Затем Наташа спросила: "Верно ли, что номер твоего дома больше 25?". Саша ответил.
Наташа решила, что она знает номер дома Саши и отправилась к нему в гости. Оказалось, что и она ошиблась, поскольку Саша ответил правдиво только на второй вопрос.
Определите адрес всех троих друзей, если известно, что номер дома Саши меньше, чем номера домов девушек и что сумма всех трех номеров – удвоенный полный квадрат.
Ответ
Обозначим Nd, Nn, Ns – номера домов Даши, Наташи и Саши. Очевидно, что Саша ответил Даше оба раза утвердительно. Существует только два квадрата больше 50: 64 и 81 – значит в одном из этих домов живет Даша. Поэтому она и подумала, что Саша живет в другом. Значит, на самом деле, Ns > 50 и Ns не равно 64 и не равно 81; Nd = 64 или Nd = 81.
Аналогично Саша ответил Наташе оба раза "да". Существует только два куба больше 25: 27 и 64 – значит в одном из этих домов живет Наташа. Именно поэтому она и подумала, что Саша живет по другому адресу. Учитывая, что Ns > 50 и Ns не равно 64 и не равно 81, получаем Nd = 81, Nn = 64, Ns > 50, Ns < 64. Перебором находим, что Ns = 55 (81 + 64 + 55 = 2 х 102).
Получается, что номер дома Даши 81, Наташи – 64, а Саши – 55.
Опечатка
Условие
В одном из учебников по математике написано, что наибольшее известное простое число – это разность 23021377-1. Не опечатка ли это?
Ответ
Это опечатка. Любая степень числа, оканчивающегося на 1, тоже оканчивается на 1. Поэтому, разность 23021377 – 1 оканчивается на 0 и, следовательно, не является простым числом.
Торт
Условие
Хозяйка купила торт. К ней может прийти или 10, или 11 гостей.
На какое наименьшее число кусков ей необходимо заранее разрезать торт так, чтобы его можно было поделить поровну как между 10, так и между 11 гостями?
Ответ
Хозяйке следует разрезать торт на 20 кусков. Докажем сначала, что разрезать торт меньше, чем на 20 кусков, не удастся. Если придут
10 человек, то каждый из них должен получить не меньше двух кусков. В самом деле, в противном случае один из 10 гостей получил бы один кусок в 1/10 часть торта, а если бы пришло
11 гостей, то этот кусок нужно было бы дополнительно разрезать. Таким образом, количество кусков не меньше, чем 2 х 10 = 20.
Покажем, что 20 кусков торта хватит всем гостям. Разрежем торт на 10 кусков по части и на 10 кусков по 1/110. Если придут 10 гостей, то каждый получит один большой кусок и один маленький – всего + 1/110 = 1/10. Если же придут 11 человек, то 10 из них получат по одному большому куску, а один человек – 10 маленьких кусков.
Рулетка
Условие
Пьер никогда не проигрывает в рулетку больше четырех раз подряд и никогда не ставит на кон больше 20 долларов.
Каким образом он может выиграть 1000 долларов, если в случае выигрыша в рулетку возвращается удвоенная ставка и в самом начале игры у Пьера есть 100 долларов?
Ответ
Пусть Пьер поставит сначала 1 доллар и, если выиграет, скажет: "Ок'ей" и снова поставит 1 доллар. Если проиграет, то в следующей ставке он ставит 2 доллара. Если выиграет, то его выигрыш покроет предыдущий проигрыш, и по сумме двух ставок он выиграет 1 доллар.
После этого пусть Пьер снова скажет: "Ок'ей" и в новой ставке ставит 1 доллар. Если он проиграет и во второй раз, в третий раз он поставит 4 доллара, чтобы в случае выигрыша покрыть предыдущие проигрыши. Если проигрывает в третий раз, то в четвертый раз ставит 8 долларов, если проигрывает и в четвертый, то в пятый раз ставит 16 долларов.
По условию он не проигрывает пять раз подряд, значит играя таким образом до первого выигрыша, он заработает 1 доллар не более, чем за 5 ставок. После этого он скажет: "Ок'ей" и будет делать ставки также, как вначале.
Получается, что после 1000 "Ок'ей" Пьер выиграет 1000 долларов. Для этого ему потребуется сделать не более 5000 ставок.
Альпинист
Условие
Альпинисты стоят на горе высотой 100 м. На вершине горы – дерево, на высоте 50 м (посередине горы) – еще одно дерево.
У альпиниста есть только 75 м веревки и нож. Может ли он спуститься с горы?
Подсказка: альпинисту следует разрезать веревку на два куска по 50 и 25 м.
Ответ
Альпинисту нужно отрезать 25 м веревки, один конец привязать к дереву на вершине горы, а на другом сделать петлю, через которую следует пропустить оставшиеся 50 м веревки, сложенные вдвое: 25 + 50 х 1/2 = 50, то есть ему как раз хватит веревки, чтобы добраться до дерева, расположенного на высоте 50 м.
Далее альпинисту необходимо вытянуть веревку из петли, привязать дереву и спуститься вниз.
Можно ли "сотку" разделить на 9?
Условие
В следующих многозначных числах цифры заменены буквами (одинаковые цифры – одинаковыми буквами, а разные – разными). Оказалось, что слово "девяносто" делится на 90, а "девятка" – на 9.
Можно ли "сотку" разделить на 9?
Ответ
Буква "о" равна нулю. Сумма восьми различных цифр д + е + в + я + н + о + с + т делится на 9. Поскольку сумма всех цифр 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45 делится на 9, то сумма двух оставшихся цифр а + к делится на 9. В этом случае слово "сотка" делится на 9 тогда, когда с + т делится на 9 (так как о = 0, а + к делится на 9).
С другой стороны, д + е + в + я + т + к + а делится на 9 (д + е + в + я + т делится на 9, н + с делится на 9, так как д + е + в + я + н + о + с + т делится на 9 и о = 0).
Из этого можно сделать вывод, что с + т не может делиться на 9, следовательно слово "сотка" тоже на 9 не делится.
Клоуны
Условие
В шеренгу выстроено n клоунов. На голову каждому надевают колпак одного из цветов: красного, желтого или зеленого. Клоун, стоящий в шеренге n-м видит всех остальных клоунов, n-1-й клоун видит n-2 клоунов, стоящих впереди, ... 2-й клоун видит только первого, первый клоун не видит никого.
Цвет своего колпака клоун определить не может. Каждого клоуна по порядку, начиная с n-го, просят ответить, какого цвета у него колпак. Клоун обязан назвать один из трех цветов.
Какое максимальное число клонов могут гарантированно угадать цвет своего колпака? При этом клоуны перед опоросом могут договориться, но не могут заранее знать, какие колпаки на них наденут.
Ответ
Пронумеруем цвета числами от 0 до 2. n-й клоун, видя всех, кроме себя, складывает числа, соответствующие цветам видимых им колпаков, и называет цвет, соответствующий остатку от деления полученной им суммы на 3.
n-1-й клоун слышит ответ n-го и видит всех остальных клоунов, кроме себя и n-го. Он также может сложить числа, соответствующие видимым им колпакам и взять остаток от деления на 3.
Разность между ответом n-го клоуна и этим числом будет соответствовать цвету колпака на п-1-м клоуне, что даст ему возможность правильно назвать цвет своего колпака.
Таким же образом действует и n-2-й клоун, учитывая два предыдущих ответа. Получается, что все клоуны, кроме n-го, гарантированно узнают цвет своего колпака (n-й клоун не может узнать цвет своего колпака, так как его колпак никто не видит).
Бесконечные крестики-нолики
Условие
На бесконечной клетчатой бумаге двое играют в крестики-нолики. Один игрок ставит своим ходом два крестика (не обязательно рядом), а другой – один нолик.
Сможет ли играющий крестиками поставить 10 крестиков в ряд?
Ответ
Первые 29 = 512 крестика (за 256 ходов) следует ставить далеко друг от друга (например, на расстоянии 30 клеток друг от друга по горизонтальной прямой). Ответными ходами второй игрок может "испортить" только 256 крестиков, поставив рядом нолик, а 28 = 256 останутся "неиспорченными". Поставив 256 крестиков (за 128 ходов) рядом с каждым "неиспорченным", получим не менее 27 = 128 "неиспорченных" пар.
Далее аналогично получаем 26 = 64 "неиспорченных" тройки крестиков, 25 = 32 "неиспорченных" четверки крестиков, 2 "неиспорченных" восьмерки и 1 "неиспорченную" девятку. За один ход второй игрок не сможет закрыть ряд из девяти крестиков с двух сторон. И следующим ходом первый игрок поставит еще один крестик, то есть получит ряд из 10 крестиков.
Коммунальная квартира
Условие
В коммунальной квартире 10 комнат. Жители этих комнат просыпаются по очереди. Если дверь их комнаты на месте, они снимают дверь какой-либо другой комнаты и относят ее в подвал. Если же дверь их комнаты отсутствует, они забирают из подвала любую дверь и ставят ее на место своей (если ни одно из этих действий невозможно, они не делают ничего).
Какое наибольшее количество дверей может оказаться в подвале после того, как все жители комнат проснутся?
Ответ
Представим, что жильцы коммунальной квартиры просыпаются в порядке нумерации их комнат: сначала – первой, потом – второй и т. д.
Рассмотрим комнату, с которой сняли дверь жители первой комнаты. Когда жильцы комнаты со снятой дверью проснутся, они повесят свою дверь на место. В результате этих двух операций ни одной двери в подвале не прибавится и, если даже жильцы остальных восьми комнат снимут по двери, в подвале окажется не более 8 дверей.
Например: жители первой комнаты снимают дверь с десятой комнаты, жители второй комнаты снимают дверь с первой, жители n-й комнаты снимают дверь с n – 1 (1 < n < 10) комнаты.
Проснувшиеся последними жители десятой комнаты вешают свою дверь на место, после чего в подвале окажется 8 дверей от первой, второй, третьей, четвертой, пятой, шестой, седьмой и восьмой комнат.
Конструктор
Условие
Никите подарили игру "Конструктор", в которой было 100 деталей разной длины. В инструкции к игре написано, что из любых трех деталей можно составить треугольник. Никита решил проверить это утверждение и стал составлять из деталей треугольники.
Детали лежат в наборе по возрастанию длин.
Какое наименьшее число проверок необходимо сделать Никите, чтобы доказать или опровергнуть то, что написано в инструкции?
Ответ
Никите нужна только одна проверка. Ему достаточно проверить, можно ли составить треугольник из двух самых коротких деталей и одной самой длинной.
Если треугольник не составляется, то утверждение инструкции опровергнуто. Если же его можно составить, то сумма длин двух самых коротких деталей больше длины самой длинной, а это означает, что из любых деталей можно составить треугольник.