Олимпиадные задания (логические задачи)

Существуют несколько различных способов решения логических задач. Вот некоторые из них:

• Способ рассуждений – самый простой способ. Этим способом решаются самые простые логические задачи. Его идея состоит в том, что мы проводим рассуждения, используя последовательно все условия задачи, и приходим к выводу, который и будет являться ответом задачи.

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

• Способ «с конца» – довольно часто применим в задачах с предугадываемым ответом, и состоит в анализе ответа или конечной стадии некоторого процесса, описанного в задаче.

• Способ блок-схем – подходит, например, к решению задач "на переливание". Суть этого метода состоит в следующем. Сначала выделяются операции, которые позволяют нам точно отмерять жидкость. Эти операции называются командами. Затем устанавливается последовательность выполнения выделенных команд. Эта последовательность оформляется в виде схемы. Подобные схемы называются блок-схемами. Составленная блок-схема является программой, выполнение которой может привести нас к решению поставленной задачи. Для этого достаточно отмечать, какие количества жидкости удается получить при работе составленной программы. При этом обычно заполняют отдельную таблицу, в которую заносят количество жидкости в каждом из имеющихся сосудов.

Задачи с решениями

1. На ступеньках дома сидят рядышком мальчик и девочка.

– Я мальчик, – говорит ребёнок с чёрными волосами.

– А я девочка, – говорит ребёнок с рыжими волосами.

Если по крайней мере один из детей говорит неправду, то кто из них мальчик, а кто девочка?

Решение

Для двух произвольных высказываний существуют четыре возможные комбинации типа «истина – ложь», а именно:

И – И,   И – Л,   Л – И,   Л – Л.

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

Итак, у мальчика рыжие волосы, а у девочки чёрные.

2. В одной урне лежат два белых шара, в другой – два чёрных, в третьей – один белый шар и один чёрный. На каждой урне висела табличка, указывающая её состав: ББ, ЧЧ, БЧ. Но какой-то шутник перевесил все таблички так, что теперь каждая из них указывает состав урны неправильно. Разрешается вынуть шар из любой урны, не заглядывая в неё. Какое наименьшее число извлечений потребуется, чтобы определить состав всех урн? (Вы осведомлены о проделке шутника. После каждого извлечения шар опускается обратно.)

Решение

3. Абрахам, хилый старик, подрядился выкопать канаву за 2 доллара. Он нанял Бенджамина, здоровенного парня, чтобы тот ему помог. Деньги они должны были поделить в соответствии с «копательными» способностями каждого. Абрахам копает так же быстро, как Бенджамин выбрасывает грунт, а Бенджамин копает в четыре раза быстрее, чем Абрахам выбрасывает грунт.

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

Решение

Пусть, например, Бенджамин (Б) может выкопать канаву за время t, и выбросить грунт за время 2t. Тогда Абрахам (А) выкапывает канаву за время 2t часа и выбрасывает весь грунт за 4t. Следовательно, при рытье канавы их силы относятся как t к 2t, а при выбрасывании грунта – как 2t к 4t (отношение сил остаётся неизменным). При этом А может выкопать канаву за то же время, за которое Б может выбросить весь грунт (время 2t), а Б может выкопать канаву за четвёртую часть того времени, которое А тратит на выбрасывание грунта.

Следовательно, Абрахаму причитается треть всей суммы, а Бенджамину – две трети.

4. Андерсон покинул отель в Сан-Ремо в 9 часов и находился в пути целый час, когда Бакстер вышел вслед за ним по тому же пути. Собака Бакстера выскочила одновременно со своим хозяином и бегала всё время между ним и Андерсоном до тех пор, пока Бакстер не догнал Андерсона. Скорость Андерсона составляет 2 км/ч, Бакстера – 4км/ч и собаки – 10 км/ч. Сколько километров пробежала собака к моменту, когда Бакстер догнал Андерсона?

Решение

Вполне очевидно, что Бакстер догонит Андерсона через один час, поскольку к этому времени они пройдут по 4 километра в одном направлении. Так как скорость собаки составляет 10 км/ч, то за этот час она пробежит 10 километров.

Ответ: 10 км.

5. Можно ли расставить по окружности 20 красных и несколько синих фишек так, чтобы в каждой точке, диаметрально противоположной красной фишке, стояла синяя и никакие две синие фишки не стояли рядом?

Решение

Из условия следует, что красные и синие фишки должны чередоваться (на окружности), значит, всего их 40. Фишки по окружности размещаются равномерно в том смысле, что две диаметрально противоположные фишки делят множество оставшихся 38 фишек на две части по 19 фишек, расположенные в одной и другой полуокружностях относительно двух данных фишек. Это так, потому что согласно условию, каждая фишка имеет диаметрально противоположную. Диаметрально противоположные фишки имеют разный цвет, поэтому 19 фишек, расположенные в одной из полуокружностей должны чередоваться по цвету и начинаться и заканчиваться фишками разного цвета, что невозможно при нечётном 19. Следовательно, указанная в задаче расстановка фишек не возможна.

Ответ: нельзя.

6. Разбирается дело Брауна, Джонса и Смита. Один из них совершил преступление. В процессе расследования каждый из них сделал по два заявления.

Браун: «Я не делал этого. Джонс не делал этого.»

Джонс: «Браун не делал этого. Смит сделал это.»

Смит: «Я не делал этого. Браун сделал это.»

Было установлено далее, что один из них дважды солгал, другой дважды сказал правду, третий – раз солгал, раз сказал правду. Кто совершил преступление?

Решение

Если вор – Смит, то и Браун, и Джонс оба сказали правду. Если вор – Джонс, то и Браун, и Смит одновременно сказали и правду, и ложь. Итак, Браун – преступник. Джонс оба раза солгал, Смит оба раза сказал правду, Браун один раз солгал, второй раз сказал правду.

7. «Суперкоролева» – это шахматный ферзь, который может ходить еще и как конь. Надо разместить четырех суперкоролев на доске 5 на 5 таким образом, чтобы ни одна из них не могла атаковать другую. Если вам это удастся, то попробуйте 10 суперкоролев разместить на доске 10 на 10 так, чтобы ни одна не имела возможности напасть на другую. Обе задачи имеют единственное решение, если не учитывать повороты доски и ее зеркальные отражения.

Решение

Оба решения показаны на следующем рисунке.

8. У автомобиля новые шины. Шина на заднем колесе выдерживает пробег 16000 км, а на переднем – 24000 км. Какой максимальный пробег можно осуществить на этих калёсах?

Решение

Будем считать, что скорость роста износа колеса является постоянной и не зависит от того насколько оно давно служит.

Очевидно, что задние колёса изнашиваются в 1,5 раза быстрее передних. Значит, когда задние колёса износятся на 60%, то передние – только на 40%. Это произойдёт после пробега

0,6 · 16000 = 0,4 · 24000 = 9600 (км).

В этот момент и следует сменить колёса. Оставшийся 40%-й ресурс задних колёс, поставленных спереди, и 60%-й ресурс передних колёс, поставленных сзади, очевидно, исчерпается одновременно, и произойдёт это ещё через 9600 км. Таким образом максимальный пробег составляет 2·9600 = 19200 км.

Замечание. Это лишь одно из множества возможных решений этой задачи. Попробуйте найти своё.

Ответ: 19200 км.

9. Переаттестация Совета Мудрецов происходит так: король выстраивает их в колонну по одному и надевает каждому колпак белого или чёрного цвета. Все мудрецы видят, какого цвета колпак каждого впереди стоящего мудреца, а цвет своего и всех стоящих сзади не видят. Раз в минуту один из мудрецов должен выкрикнуть один из двух цветов (каждый мудрец выкрикивает цвет один раз). После окончания этого процесса король казнит каждого мудреца, выкрикнувшего цвет, отличный от цвета его колпака. Накануне переаттестации все сто членов Совета Мудрецов договорились и придумали, как минимизировать число казнённых. Скольким из них гарантированно удастся избежать казни?

Решение

10. В тюрьму поместили 100 узников. Надзиратель сказал им: "Я дам вам вечер поговорить друг с другом, а потом рассажу по отдельным камерам, и общаться вы больше не сможете. Иногда я буду одного из вас отводить в комнату, в которой есть лампа (вначале она выключена). Уходя из комнаты, вы можете оставить лампу как включенной, так и выключенной. Если в какой-то момент кто-то из вас скажет мне, что вы все уже побывали в комнате, и будет прав, то я всех вас выпущу на свободу. А если неправ - скормлю всех крокодилам. И не волнуйтесь, что кого-нибудь забудут - если будете молчать, то все побываете в комнате, и ни для кого никакое посещение комнаты не станет последним."

Придумайте стратегию, гарантирующую узникам освобождение.

Решение

Задачи без решений

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

а) Джо ловкач,

б) Джо не везет,

в) Джо везет, но он не ловкач,

г) если Джо ловкач, то ему не везет,

д) Джо является ловкачом тогда и только тогда, если ему везет,

е) либо Джо ловкач, либо ему везет, но не то и другое одновременно.

2. Мать разделила между своими сыновьями груши. Первому она дала половину всех груш и ещё половину груши, второму – половину остатка и ещё половину груши и, наконец, третьему – половину нового остатка и ещё половину груши. Ни одной груши при этом не нужно было разрезать. Сколько груш получил каждый сын, если мать раздала все груши?

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

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

4. Имеется 10 мешков монет. В девяти мешках монеты настоящие, весят по 10 г, а в одном мешке все монеты фальшивые, весят по 11 г. Одним взвешиванием определить, в каком мешке фальшивые монеты. (Взвешивание осуществляется на весах способных показать точный вес.)

5. Переаттестация Совета Мудрецов происходит так: король выстраивает их в колонну по одному и надевает каждому колпак белого, синего или красного цветов. Все мудрецы видят цвета всех колпаков впереди стоящих мудрецов, а цвет своего и всех стоящих сзади не видят. Раз в минуту один из мудрецов должен выкрикнуть один из трех цветов (каждый мудрец выкрикивает цвет один раз). После окончания этого процесса король казнит каждого мудреца, выкрикнувшего цвет, отличный от цвета его колпака. Накануне переаттестации все сто членов Совета Мудрецов договорились и придумали, как минимизировать число казненных. Скольким из них гарантированно удастся избежать казни?