Math    schooL

 

 

Логические задачи

 

Логические задачи

 

Немного теории

Часто знакомство с олимпиадной математикой начинается с логических задач. Сюда относятся, прежде всего, текстовые задачи, в которых требуется распознать объекты или расположить их в определенном порядке по имеющимся свойствам. При этом часть утверждений условия задачи может выступать с различной истинностной оценкой (быть истинной или ложной). К классу логических задач относятся также задачи на переливания и взвешивания.

В логических задачах нет «серьёзной» математики – нет ни сложных числовых выражений, ни функций, ни соотношений в треугольнике, ни векторов, но есть лжецы и мудрецы, фальшивые монеты и необычные шахматные фигуры, разноцветные фишки и сказочные герои. В то же время дух математики в таких задачах чувствуется весьма ярко. Половина решения логической задачи (а иногда и гораздо больше половины) состоит в том, чтобы как следует разобраться в условии, распутать все связи между участвующими объектами.

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

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

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

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

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

 

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

 

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

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

Узники выбирают одного определённого человека (будем называть его "счётчиком"), который будет считать узников по такой системе: если, приходя в комнату, он обнаруживает, что свет включён, то он прибавляет к уже посчитанному числу узников единицу и выключает свет, если же свет не горит, то он, ничего не меняя, возвращается обратно в свою камеру. Каждый из оставшихся узников действует по такому правилу: если, приходя в комнату, он обнаруживает, что свет не горит, и он до этого ни разу не включал свет, то он его включает. В остальных случаях он ничего не меняет. Когда число посчитанных узников становится равным 99, "счётчик" говорит, что все узники уже побывали в комнате.

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

Остаётся доказать, что каждый из 99 узников включит свет. Предположим, что это не так – свет будет включён менее 99 раз. Тогда, начиная с некоторого дня n, свет включаться не будет. Так как никакой заход в комнату не будет для счётчика последним, он побывает в комнате после этого дня (например, на m-й день, m > n). Если свет при этом горел, он его выключит. Значит, начиная с (m+1)-го дня свет будет всё время выключен. Рассмотрим узника, который свет ещё ни разу не зажигал. Так как и для него никакой заход в комнату не последний, он побывает в комнате после m-го дня. Но тогда он должен включить свет – противоречие.

 

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

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

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

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

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

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

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

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

 

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

 

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

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

 

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

 

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

 

Нам 4 года!

14 марта 2016 года сайту Математика для школы|math4school.ru исполнилось 4 года. Поскольку число 4 для нашего сайта не чужое, мы решили подвести некоторые итоги.

Новый формат главного меню

Расширены функциональные возможности главного меню.

Галерея на сайте math4school.ru
Приглашаю посетить Галерею, – новый раздел на сайте.

444 года со дня рождения Иоганна Кеплера

27 декабря 2015 года исполнилось 444 года со дня рождения Иоганна Кеплера.

Новый раздел на сайте math4school.ru

Закончена работа над новым разделом сайта Работа над ошибками.

Союз образовательных сайтов