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

Размещено на http://www.allbest.ru/

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

Бывает так, что дети интуитивно находят правильное решение, тогда следует разобрать с ребенком логическое построение его решение, объяснить, что интуитивное понимание задачи это хорошо, но нужно обосновывать свою догадку четкими рассуждениями.

Важно чтобы дети поняли, что недостаточно просто подобрать ответ и проверить, что он подходит. Нужно так же объяснить, почему все остальные варианты не проходят, а для этого необходимо осознавать по какому признаку эти варианты перебираются. Кроме полного перебора бывает также перебор по какому-либо признаку. Какой-то факт выясняется перебором: во всех вариантах, кроме одного получают противоречие, а потом оставшиеся факты выводятся прямо. Противоречие в каком-то варианте перебора может получиться не быстро. Бывает, что для каждого из вариантов перебора приводятся длинные логические цепочки, ведущие к противоречию. Конечно, решение может быть и целиком «дедуктивным».

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

Задача 1.1. В День рождения дяди Федора почтальон Печкин хочет выяснить, сколько тому лет. Шарик говорит, что дяде Федору больше 11 лет, а кот Матроскин утверждает, что больше 10 лет. Сколько лет дяде Федору, если известно, что ровно один из них ошибся? Ответ обоснуйте.

Решение. Заметим, что если не ошибся Шарик, то не ошибся и Матроскин, что противоречит условию. Значит, Шарик сказал неправду, в отличие от кота Матроскина. Таким образом, дяде Федору больше 10 лет, но не меньше 11. Следовательно, дяде Федору исполнилось 11 лет.

Задача 1.2. На острове живут рыцари, лжецы и хитрецы. Рыцари всегда говорят правду, лжецы всегда лгут, а хитрецы могут соврать или не соврать, как им захочется. Одного жителя спросили: «Вы кто?». И он ответил: «Я лжец». Кто этот житель на самом деле?

Решение. На поставленный вопрос рыцарь ответит «я рыцарь», лжец ответит… как угодно, но только не «лжец», хитрец ответит вообще что угодно.

Ответ: это был хитрец.

Задача 1.3. В Стране Чудес проводилось следствие по делу об украденном бульоне. На суде Мартовский Заяц заявил, что бульон украл Болванщик. Соня и Болванщик тоже дали показания, но что они сказали, никто не запомнил, а запись смыло алисиными слезами. В ходе судебного заседания выяснилось, что бульон украл лишь один из подсудимых и что только он дал правдивые показания. Так кто украл бульон?

Решение. Вором не может быть Мартовский Заяц, потому что вор сказал правду, а Заяц, в этом случае, соврал. Вором не может быть Болванщик, потому что, в этом случае, Заяц сказал правду, а правду сказал только вор. Значит, бульон украла -- Соня.

Задача 1.4. Когда идет дождь, кошка сидит в комнате или в подвале. Когда кошка в комнате, мышка сидит в норке, а сыр лежит в холодильнике. Если сыр на столе, а кошка - в подвале, то мышка в комнате. Сейчас идет дождь, а сыр лежит на столе. Где сейчас мышка?

Решение. Раз идет дождь, значит кошка сидит в комнате или подвале. Но в комнате она сидеть не может, т.к. в этом случае сыр лежал бы в холодильнике. Значит, кошка в подвале и сыр на столе => мышка в комнате.

Задача 1.5. Один из попугаев всегда говорит правду, другой всегда врет, а третий - хитрец - может сказать что ему вздумается - и правду, и ложь. На вопрос: «Кто Кеша?» - они ответили:

Гоша: «Кеша лжец».

Кеша: «Я хитрец!»

Рома: «Кеша абсолютно честный попугай».

Кто из попугаев лжец, а кто - хитрец?

Решение 1. Будем перебирать варианты «кто Кеша?»

Кеша не может быть правдивым, т.к. он говорит «я хитрец»

Если Кеша хитрец, то Гоша и Рома оба сказали неправду, а один из них правдивый. Получили противоречие.

Раз оба предыдущих варианта не подходят, то заключаем, что Кеша лжец. Рома сказал неправду, значит он хитрец. Гоша правдивый.

Решение 2. Будем искать, кто из попугаев может быть «правдецом». Рома не может говорить правду, т.к. честный попугай всего один и если Рома сам честный, то, как он говорит, Кеша честным уже быть не может.

Кеша тоже честным быть не может, т.к. он сказал, что он хитрец.

Остался один вариант - что чесный попугай - это Гоша. Если Гоша говорит правду, то Кеша лжец (и он солгал, что хитрец), ну а хитрец тогда - это Рома (и он схитрил, что Кеша честный). Все сошлось.

Решение 3. Выпишем все варианты правдивости попугаев

Гоша	Кеша	Рома	сходится?
лжец	хитрец	правдивый	нет
…	…	…	…
…	…	…	…

(всего шесть вариантов)

И в каждом варианте проверим, соответствуют ли высказывания попугаев их ролям.

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

Задача 1.6. В стране три города: А, Б и В. Жители города А всегда говорят правду, города Б - лгут, а города В - строго попеременно лгут и говорят правду. В одном из городов случился пожар. Дежурному на каланче позвонили. Состоялся такой диалог:

- У нас пожар!

- Где горит?

- В городе В.

Куда ехать пожарным?

Решение. Если звонили из города А, то оба утверждения должны быть верными, но это невозможно (из первого следует, что пожар в городе А, а . из второго - в городе В). Значит, звонили не из А.

Если звонили из города Б, то оба утверждения должны быть ложные, значит, пожар не в Б и не в В, то есть в городе А. Вроде решение задачи закончено, но вдруг звонили из В - в этом случае результат может оказаться другой (и, например, задача некорректной), поэтому и третий случай надо обязательно разобрать.

Если звонили и В, то оба утверждения оказываются либо истинными (если пожар в В), либо оба ложными, но жители города В строго попеременно лгут и говорят правду, значит, звонили не из В.

Задача 1.7*. Однажды Алиса повстречала Льва и Единорога, отдыхавших под деревом. Странные это были существа. Лев лгал по понедельникам, вторникам и средам и говорил правду во все остальные дни недели. Единорог же вел себя иначе: он лгал по четвергам, пятницам и субботам и говорил правду во все остальные дни недели. Они высказали следующие утверждения:

Лев: Вчера был один из дней, когда я лгу.

Единорог: Вчера был один из дней, когда я тоже лгу.

Из этих двух высказываний Алиса сумела вывести, какой день недели был вчера.

Что это был за день?

Решение. Если некто говорит «Вчера был один из дней, когда я лгу» _ это означает, что у него со вчерашнего дня сменилась роль (вчера лгал, и сегодня в этом честно признается, либо вчера говорил правду, но сегодня отрицает это).

В какой день недели меняется роль и у Льва, и у Единорога? В ночь со среды на четверг.

Ответ: среда.

Задача 1.8*. В дурдоме 2014 пациентов, часть из них Рыцари, часть - Лжецы. Переписчику необходимо узнать сколько там Рыцарей и сколько Лжецов. Какое наименьшее количество вопросов ему необходимо задать, чтобы выяснить это, учитывая то, что каждый из них при ответе на вопрос «Да», меняется Рыцарь на Лжеца, а Лжец на Рыцаря?

Решение. Необходимо разделить пациентов на пары и спросить каждого про своего соседа: «Он рыцарь?». Лжец (Л), Рыцарь (Р)

Варианты пар до ответа Ответ Варианты пар после ответа

ЛЛ Да РЛ

ЛР Нет ЛР

РЛ Нет РЛ

РР Да ЛР

Таким образом сколько бы не было Лжецов и Рыцарей до опроса, после опроса их будет поровну, т.е. по 1007. Вопросов соответственно, тоже 1007.

Ответ. 1007.

Складывание и разрезание.

Задачи на складывание и разрезание развивают пространственное мышление и очень полезны для учащихся.

Задача 4. а) Разрежьте фигуру на рисунке по сторонам клеточек на четыре равные (по площади и по форме) части.

б) Попробуйте разрезать ее другим способом.

Решение. Возможно три варианта разрезаний:

1. а) Сложите из пяти каких-нибудь треугольников а) четырехугольник; б) 10-угольник; в) 15-угольник.

Ответ. Возможные примеры показаны на рисунках.

2. Задача 1. У Иры и Серёжи было два квадратных торта. Каждый сделал на своем торте по 2 прямолинейных разреза от края до края. При этом у Иры получилось четыре треугольных куска, а у Серёжи -- три треугольных куска. Как это могло быть?

Решение. Например, так



Задача 7*. В стране Полосатии произошёл переворот и новый лидер приказал перекроить старый флаг на новый (см. рисунки). Как выполнить такой приказ, если разрешается разрезать старый флаг ровно на четыре части?

Решение

3. Задача 8*. Разрежьте каждую из фигур на рисунке по сторонам клеточек на три равные части

Решение.

4. а) В конструкции на рисунке переложите две спички так, чтобы получилось пять равных квадратов.

б) Из новой фигуры уберите 3 спички так, чтобы осталось только 3 квадрата.

Ответ

а)

5. Петя выкладывал примеры из спичек. Цифры он «записывал» следующим образом:

Когда Петя отвлёкся, Вася в записанном им верном примере на сложение внутри каждой цифры переложил ровно одну спичку и получил:

Восстановите исходное равенство.

Ответ. 29+36=65.

Решение. Заметим, что количество спичек в каждой цифре не менялось. Посчитаем из скольки спичек какие цифры состоят.

2 спички: 1

3 спички: 7

4 спички: 4

5 спичек: 2, 3, 5,

6 спичек: 6, 9, 0

7 спичек: 8

Теперь посмотрим на наше равенство. Минимально значение каждого слагаемого левой части (если все цифры заменять на наименьшие возможные) - это 20. Поэтому правая часть - двузначное число. Т.е. 9 (в правой части) можно заменить только на 6. Посмотрим на левую часть, если тройку заменить на 5, то результат сложения будет >=70 (50+20=70) - значит 3 можно заменить только на 2. Но тогда (чтобы в результате получилось >=60) 5 надо заменять на 3. Далее смотрим на вторые цифры слагаемых. Надо, чтобы в результате получилось число заканчивающееся на 2 или на 5 (т.к. 3 справа можно заменить только на 2 или на 5), но (9 или 0)+(6 или 0)=…(2 или 5) подходит только 9+6=15. Т.о. исходное равенство восстановлено: 29+36=65.

Ребусы.

Обычно дети любят разгадывать ребусы. При решении ребуса комбинируются две вещи - ребята учатся конструированию и перебору. При этом обычно перебор происходит на подсознательном уровне - при поиске решения им приходится что-то предположить, перебрать и отмести лишние варианты. Важно научить ребят (помочь им) делать этот подсознательный перебор явным, четко сформулированным. Объяснить, что если требовалось решить ребус (а не найти хотя бы одно решение - а так тоже бывает, например в задаче 5 про Незнайку), то необходимо его действительно решить - значит найти все решения, и объяснить, почему других решений нет (почему другие случаи не подходят).

Решения задач.

1. Аня выложила из карточек с цифрами пример на сложение:

314159

+ 2918 28

5857 87

а затем Елисей поменял местами две карточки. Как видите, равенство нарушилось. Какие карточки переставил Елисей?

Ответ. Он поменял карточки 9 и 7

314159

+ 2918 28

5857 87

Решение. Заметим, что сумма не сходится в выделенных желтым разрядах. Значит в них обоих хотя бы одна карточка должна быть заменена. А значит в других разрядах все карточки останутся на месте. Итак, одну карточку надо взять из первого желтого столбика и поменять ее с какой-то карточкой из второго желтого столбика. В первом желтом столбике у нас есть карточки 1, 9, 8. Пробуем и видим, что ни 1, ни 8 ни с какой карточкой из второго столбика поменять нельзя. Остается 9 - ее можно поменять только с 7.

314159

+ 2918 28

5857 87

2. Может ли быть верным равенство КЧОЧТ = УЧЧЧЁЧНЧЫЧЙ если в него вместо букв подставить цифры от 1 до 9? Разным буквам соответствуют разные цифры.

Решение: Равенство не может быть верным, потому что одной из букв обязательно должна соответствовать цифра 7; тогда та часть равенства, в которую входит эта буква, будет делиться на 7, а вторая часть равенства -- не будет. Значит, они не могут быть равны. Это рассуждение справедливо и для цифры 5.

3. Расшифруйте ребус, изображённый на рисунке. Одинаковым буквам соответствуют одинаковые цифры, разным -- разные.



Решение:

Для решения этого ребуса можно составить систему уравнений:

Решив эту систему, получим: A = 6, B = 7, C = 4. Ребус можно записать в виде 6 + 67 + 674 = 747.

4. В ряд записаны шестнадцать пятерок и одна четверка: 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 4. Поставьте между каждыми двумя соседними числами знак + или * так, чтобы результат стал равен 2009 (Скобки ставить нельзя).

Ответ. 5*5*5*5+5*5*5*5+5*5*5*5+5*5*5+5+4

Дополнительные задачи.

5. Семь девяток выписали подряд: 9 9 9 9 9 9 9. Поставьте между некоторыми из них знаки «+» или «?», чтобы получившееся выражение равнялось 1989.

Ответ: 999 + 999 ? 9 =1989.

6. Шифр кодового замка является двузначным числом. Буратино забыл код, но помнит, что сумма цифр этого числа, сложенная с их произведением, равна самому числу. Напишите все возможные варианты кода, чтобы Буратино смог быстрее открыть замок.

Решение:

Пусть первая цифра кода x, а вторая y. Тогда само число записывается как 10x + y, а условие задачи можно записать уравнением

(x + y) + x ^. y = 10x + y



Следовательно, x ^. y = 9x.

Так как код -- двузначное число, то x не равно 0, а значит, y = 9. При этом x можно взять любым, кроме 0.

7. Напишите в строку пять чисел, чтобы сумма любых двух соседних чисел была отрицательна, а сумма всех чисел -- положительна.

Решение: Числа могут быть, например, такими: +3 ?4, +3 ?4, +3. Хитрость в том, что сумма «немного отрицательна», а крайние числа «сильно положительны».

Соответствия и графы

Методические рекомендации

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

В начале занятия можно вспомнить, что такое граф, ребро, степень вершины.

В целом занятие посвящено усвоение двух основных фактов:

1) сумма степеней вершин равна удвоенному количеству ребер.

2) не существует графа, сумма степеней вершин которого нечетна

Решение задач.

1. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля - Меркурий, Плутон - Венера, Земля - Плутон, Плутон - Меркурий, Меркурий - Венера, Уран - Нептун, Нептун - Сатурн, Сатурн - Юпитер, Юпитер - Марс и Марс - Уран. Можно ли добраться с Земли до Марса?

Решение. Нарисуем схему (построим граф): планетам будут соответствовать точки, а соединяющим их маршрутам - пересекающиеся между собой линии. Что же получили в итоге? По нарисованной схеме понятно, что долететь от Земли до Марса нельзя.

2. В фирме 50 компьютеров, некоторые пары компьютеров должны быть соединены кабелями. От каждого компьютера должно отходить по 8 кабелей. Сколько всего понадобится кабелей?

Решение. Рассмотрим граф, вершинами которого являются компьютеры, а ребрами - кабели. Степень каждой вершины по условию равна 8. Подсчитаем число ребер в графе: =200. Следовательно, понадобится 200 кабелей.

3. В стране 15 городов, каждый из которых соединен дорогами не менее чем с семью другими. Докажите, что из любого города можно добраться в любой другой (возможно, проезжая через другие города).

Решение. Рассмотрим любую пару городов A и B. Если между ними есть дорога, все хорошо. Если нет, то рассмотрим 7 городов, в которые можно добраться из A и 7 городов, в которые можно добраться из B. Эти 14 городов не могут быть все различны, так как тогда вместе с A и B получилось бы 16 городов. Значит, есть город C, в который можно добраться как из A, так и из B. Значит, из A в B можно добраться через C.

4. На дискотеке каждый мальчик танцевал ровно с десятью девочками, а каждая девочка -- ровно с девятью мальчиками. Кого было больше: мальчиков или девочек?

Решение. Пусть мальчиков было m, а девочек d. Построим граф, в котором вершины будут двух цветов: синие будут обозначать мальчиков, а красные -- девочек. Рёбра будут соединять только вершины разных цветов, причём в том и только в том случае, если соответствующие мальчик и девочка танцевали на дискотеке. Так как из каждой синей вершины выходит ровно 10 рёбер, а у каждого ребра есть ровно один синий конец, то отсюда следует, что количество рёбер в нашем графе равно 10m. Из аналогичных соображений можно получить, что оно также равно 9d. Значит, 10m = 9d или m = 0,9d. Следовательно, девочек было больше.

Впрочем, если задачу переформулировать в равносильную, но с другим сюжетом, то решение становится очевидным:

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

5. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 - по 4 друга, а 10 - по 5 друзей?

Решение. Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 - степень 4, 10 - степень 5. Однако у такого графа 19 нечетных вершин, чего не может быть (вспомним лемму о рукопожатиях).

6. На некотором острове расположено 15 государств. Для каждого из них хотя бы одно соседнее государство - дружественное. Докажите, что найдется государство, у которого четное количество дружественных соседей. (Два государства называются соседними, если у них имеется целый кусок общей границы).

Решение. Предположим, что у каждого государства нечетное количество дружественных соседей, тогда, сложив 15 нечетных чисел, получим нечетное число. С другой стороны, если государство А дружественно государству В, то и В дружественно А (отношение «дружбы» между государствами обладает свойством симметричности). Следовательно, найденная нами сумма должна быть четной. Из полученного противоречия следует, что наше предположение не верно и хотя бы у одного государства - четное количество дружественных соседей, ч. т. д.

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

Решение. Пусть количество площадей (вершин графа) - n, а количество улиц (ребер графа) - m, тогда, количество улиц, соединяющих все площади должно быть равно . Получим уравнение в натуральных числах: 5n = 2m. Так как НОД (2; 5) = 1, то n кратно двум, а m кратно пяти, ч. т. д.

8. Требуется подключить к сети люстру с 15 лампочками так, чтобы можно было зажигать любое количество лампочек (в том числе, и ни одной). Можно ли это сделать, если разрешить использовать только четыре выключателя?

Решение. Да, можно. Для доказательства достаточно подсчитать сколько различных состояний можно обеспечить четырьмя выключателями. Каждый из них имеет два состояния: включен или выключен (0 или 1). Значит, занумеровав выключатели, мы имеем 16 = 2⁴ всевозможных комбинаций их состояний (количество различных четырехзначных чисел в двоичной системе счисления). Количество состояний люстры также равно 16, то есть, мы сможем установить взаимно - однозначное соответствие между множеством состояний выключателей и множеством состояний люстры.

Задачу легко обобщить: N выключателей смогут «обслужить» люстру, в которой не более, чем 2^{N - 1} лампочек.

9. Можно ли «занумеровать» все ребра куба целыми числами так, чтобы суммы «номеров» ребер, сходящихся в каждой вершине, были одинаковыми, если это числа: а) 1; 2; ...; 12; б) - 6; - 5; ...; - 1; 1; 2; ...; 6?



Ответ: а) нет; б) да.

Решение. а) Предположим, что это возможно и сумма «номеров» ребер, сходящихся в каждой вершине, равна x. Тогда, сумма чисел на всех восьми ребрах куба равна 8x. С другой стороны, так как каждый «номер» вошел в эту сумму дважды, то эта же сумма равна: (1 + 2 + ... + 11 + 12)2 = (1 + 12)12 = 156. Уравнение 8x = 156 в целых числах решения не имеет, поэтому наше предположение не верно.

б) Например, см. рис. Сумма «номеров» ребер, сходящихся в каждой вершине, равна 0.

Методические комментарии.

Знание комбинаторики очень полезно, т.к. она являются частью многих задач на разные темы, в первую очередь на принцип Дирихле. В таких задачах нужно подсчитать количество чего-то или число способов сделать что-то, а потом сравнить с каким-то числом, например, см. задачи 2, 7.

В этом смысле комбинаторика сравнима с арифметикой. Посчитать «сколько существует пятизначных чисел, все цифры которых различны» должно быть так же естественно, как посчитать 77*88. Простые («прямые») задачи по комбинаторике похожи по формулировкам: «сколько бывает...» или «каким числом способов можно сделать...» с небольшими вариациями. Конечно, бывают сложные интересные задачи по комбинаторике, но основная цель изучения темы -- чтобы простые задачи решались быстро и правильно, как арифметические примеры.

По поводу записи ответа, приведения выражений. Не обязательно вычислять число, достаточно записать ответ в виде 5⁴*3 или, например, 10!/(6!4!). Ответы в виде степеней и факториалов лучше запоминаются, а запоминать их стоит, потому что задачи однотипные. Если ребенок запомнит, что выбрать 6 носков из 10 можно 10!/6!4! способами, то ему будет легче обобщить это на другие числа, чем если ответ отложился бы в памяти как 210.

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

Вначале с ребятами можно решить какие-то задачи, чтобы вспомнить и «включиться» в тему

l Сколько существует четырехзначных чисел, в записи которых нет нулей?

Ответ: 9⁴ = 6561

Решение. На каждое место можно поставить любую из 9 цифр. Для каждого из 9 способов выбрать первую цифру перед нами еще 9 способов выбрать вторую цифру, две цифры можно выбрать 9*9 = 81 способами. Три цифры можно выбрать уже 81*9 = 729 способами, т.к. от каждого способа выбрать две цифры отходит еще 9 вариантов. Все 4 цмфры можно выбрать 729*9 = 6561 способами.

Процесс выбора удобно изобразить в ввиде дерева. Вверху одна вершина (****), из нее выходит вниз 9 ребер к вершинам вида (1***), (2***), ..., (9***), от них от каждой выходит еще по 9 ребер к вершинам, где выбрано по 2 цифры: (11**), (12**), ..., (99**), таких вершин уже 9*9, каждая вершина соответствует двухзначному числу, в записи которого нет нулей. На третьем уровне этого дерева будут вершины, соответствующие числам, где первые 3 цифры уже выбраны. Таких вершин будет 729. На четвертом уровне будут завершенные 4-значные числа, 6561 вершина.

l Каким числом способов можно расставить на доске 4x4 четыре ладьи так, чтобы они не били друг друга?

Ответ: 4! = 24 способа.

Решение. Заметим, что больше 4 ладей так, чтобы они не били друг друга поставить не удастся -- в самом деле, если есть хотя бы 5 ладей, то какие-то две ладьи стоят в одной строке, а значит бьют друг друга. Ну а если расставили 4, то мы поставили по ладье в каждой из 4 строк. В первой строке ладью можно поставить на любую из 4 клеток. Для каждого из этих четырех способов существует три способа поставить ладью во второй строке (вторую ладью можно поставить в любую из клеток, кроме того столбца, в котором уже стоит первая ладья, т.е. ставить можно в любую из 3 клеток). Таким образом, в первые две строки поставить ладей можно 4*3=12 способами. Аналогично далее: для каждого из этих 12 способов есть два способа поставить ладью в третью строку (в любую из клеток, кроме двух уже занятых столбцов). В последней оставшейся строке у нас уже нет выбора. Итого, 4! способов расставить все 4 ладьи.

l В зоопарке 7 слонов. Сторож решил отпустить 2 из них на прогулку в город. Сколькими способами он может выбрать 2 счастливцев?

Ответ: 7*6/2 = 21

Решение. Первого слона 7-ью способами, потом второго 6-ью способами, всего 42 способа. Но каждая пара слонов посчитана два раза (Вася-Петя, Петя-Вася), поэтому надо разделить число способов на 2.

l В зоопарке 7 слонов и 4 бегемота. Сколькими способами можно отпустить 3 животных так, чтобы среди них был и слон, и бегемот?

Ответ: 126.

Решение 1. Способы разбиваются на 2 категории: 2 слона + 1 бегемот и 1 слон + 2 бегемота. Посчитаем число способов из первой категории. 2 слона можно выбрать 21 способами (см. решение задачи 18), бегемота 4 способами. Всего 84 способа. Во второй категории двух бегемотов можно выбрать 6 способами и слона 7 способами, всего 42 способа. В сумме 126 способов.

Решение 2. Сначала посчитаем число способов отпустить 3 любых животных. Выбрать 3 животных из 11 можно 11*10*9 способами с учетом порядка и 11*10*9 / (3*2*1) = 165 способами без учета порядка (см. решение задачи 8б или 9а). Среди посчитанных способов есть такие, где отпустили гулять 3 слонов или 3 бегемотов. Посчитаем количество таких неподходящих способов и вычтем их из 165. 3 слонов можно отпустить 7*6*5 / (3*2*1) = 35 способами, а выбрать 3 бегемотов можно 4*3*2 / (3*2*1) = 4 способами (или просто выбрать бегемота-неудачника, который останется в зоопарке можно 4-мя способами). 165 - 35 - 4 = 126.

Решения задач.

1. Сколько существует двузначных чисел, у которых все цифры четные?

Ответ: 20

Решение. Первая цифра может быть 2, 4, 6 или 8, всего 4 варианта. Вторая цифра может быть равна кроме уже перечисленных цифр еще и 0, т.е. 5 вариантов. Первую и фторую цифру можно выбрать независимо друг от друга, поэтому количества вариантов перемножаются.

2. У Вани есть 10 шорт и 10 футболок. Сможет ли мальчик все лето каждый день ходить гулять так, чтобы его наряд не повторился?

Ответ: да.

Решение. Каждый день он может выбрать шорты 10 способами и футболку 10 способами. Всего 100 комбинаций. 100 дней это даже больше, чем «все лето».

а) Сколько существует трехзначных чисел, состоящих из различных цифр?

б) Каким числом способов можно поставить 5 человек в колонну?

Ответ: а) 9*9*8 = 648; б) 5*4*3*2*1 = 5! =120

Решение. а) первую цифру можно выбрать любую от 1 до 9 (9 вариантов). После выбора первой цифры выберем вторую. Это можно сделать 9 способами, т.к. одну из цифр использовать нельзя -- ту, которую мы уже выбрали на первое место. Не важно, какая выбрана цифра на первое место, для выбора второй все равно остается 9 вариантов. Третью цифру можно выбрать 8 способами, т.к. она должна быть не равна первой и второй (и эти две недоступные цифры различны между собой). Все три цифры можно выбрать 9*9*8 способами.

б) Сначала выберем, кого поставим во главе колонны (первым). Любого из 5 человек. Потом выберем, кто будет стоять вторым. У нас будет 4 человека на выбор, не важно кого мы назначили первым. На третье место будет выбор из 3 человек, на четвертое место из 2 человек, последнее место без выбора. Всего 5*4*3*2 вариантов.

3. Сколько диагоналей в 20-угольнике?

Ответ: 20*17/2 = 170

Решение. Из каждой вершины выходят диагонали во все остальные вершины, кроме дух соседних. Это 17 вершин (20 всего, 1 вершина сама и 2 соседние). Из всех 20 вершин выходит в сумме 20*17=340 диагоналей. Однако каждую диагональ мы посчитали 2 раза, как выходящую из одного ее конца и из другого конца. Поэтому нжно полученное число разделить пополам.

4. Гриша спешил на свидание. В тумбочке он нашел 15 разных носков. Из них 7 синих, 5 красных и 3 зеленых носка.

а) Каким числом способов он может взять себе два носка разных цветов?

б) Каким числом способов он может взять себе два носка одного цвета?

Комментарий. Имеется в виду, что носки все разные между собой, т.е. можно составить пару синих носков из разных носков, и это считается уже другим способом.

Ответ: а) 7*5 + 7*3 + 5*3 = 71; б) 7*6/2 + 5*4/2 + 3*2/2 = 34

Решение. а) Посчитаем, скольким способами можно выбрать сине-красную пару. Синий носок берем любой из 7, а красный любой из 5. Это независимый выбор, всего вариантов 7*5 = 35. Аналогично посчитаем количество способов выбрать сине-зеленую пару и красно-зеленую пару и сложим.

б) Посчитаем количество способов выбрать синюю пару. Первый носок берем любой из 7, второй любой из 6 оставшихся. Всего способов 7*6 = 42. Однако надо учесть, что нам не важен порядок носков, а при нашем способе подсчета мы считали способы с учетом порядка. Например, один способ, когда сначала выбрали синий носок №5, потом синий носок №3, а второй способ, когда сперва мы выбрали синий носок №3, а потом синий носок №5. Нам нужно эти два способа считать за один, т.к. пара носков одна и та же. Для этого разделим количество способов пополам (каждую пару мы посчитали 2 раза, как в примере 5-3 и 3-5), получится 42/2 = 21. Аналогично посчитаем количество способов выбрать зеленую пару и красную пару и сложим.

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

Ответ: 9*8/2 = 36

Решение. Первого преподавателя выбираем 9 способами, второго любого из оставшихся, т.е. 8 способами. Т.к. порядок не важен, то разделим общее количество вариантов пополам (каждую пару преподавателей мы учитывали по два раза). Получается 9*8/2 способов.

6. Туземцы захватили в плен Паганеля и заставили его быть поваром. Он умеет готовить 10 видов мяса и 5 видов гарнира. Каждый день на обед надо приготовить один гарнир и два вида мяса. Если он повторит меню - его съедят за ужином. Через полгода придет спасительный корабль. Сможет ли Паганель продержаться?

Ответ: да.

Решение. 2 вида мяса из 10 можно выбрать 10*9/2 = 45 способами (см. решение задачи 6), независимо от этого можно выбрать гарнир 5 способами. Итого, обед можно приготовить 45*5 = 225 способами. Этого должно хватить на полгода.

7. а) Каким числом способов из 10 различных горшков можно выбрать один для фикуса, один для крокуса, и один для кактуса? б) А каким числом способов из 10 горшков можно выбрать три, чтобы посадить в них лук?

Ответ: а) 10*9*8 = 720; б) 10*9*8 / (3*2*1) = 120

Решение. а) Горшок для фикуса можно взять любой из 10, потом горшок для крокуса возьмем любой из 9 оставшихся (не важно, в какой именно горшок посадили фикус, все равно останется 9 на выбор), и, наконец, кактус посадим в любой из оставшихся 8 горшков. Всего 10*9*8 вариантов.

б) Итак, в пункте «а» мы нашли 720 способов посадить фикус, крокус и кактус. Пусть теперь и фикус, и крокус, и кактус превратились в лук. Вопрос: сколько способов из тех 720 превратятся при этом в один способ (раньше эти способы были различные потому, что в одном горшке рос фикус, а в другом кактус, а теперь и там и там стал лук, способы стали одинаковыми)?

Вот мы наблюдаем 3 луковицы в каких-то трех горшках. Первая луковица могла быть раньше фикусом, кактусом или крокусом. Вторая -- любым из двух оставшихся растений. Т.е. у любого варианта рассадки трех луковиц есть 3*2 = 6 вариантов «прошлого»; ему соответствуют 6 вариантов рассадить фикус, крокус и кактус; все эти 6 вариантов после превращения станут искомым вариантом рассадки лука.

Значит, чтобы найти количество вариантов рассадки лука, нужно количество вариантов рассадки фикуса-крокуса-кактуса разделить на 6.

8. Забор состоит из 11 досок. Требуется покрасить три доски в синий цвет. Сколькими способами это можно сделать? А если нужно покрасить 4 доски?

Ответ: а) 11*10*9 / (3*2*1) = 165; б) 11*10*9*8 / (4*3*2*1) = 330

Решение. а) Аналогично задаче 8б. Сначала покрасим первую доску, ее можно выбрать 11 способами, потом вторую 10 способами, потом третью 9 способами, итого 11*10*9 = 990 способов. Каждый способ покрасить 3 доски мы посчитали 3*2 = 6 раз, т.к. мы различали способы, когда определенная доска крашена в первую или во вторую или в третью очередь. Нам же не важен порядок покраски досок, поэтому нужно разделить 990 на количество способов расставить по порядку 3 доски, т.е. на 6.

б) Способов раскрасить доски по порядку 11*10*9*8 = 7920, способов расставить 4 доски по порядку (определить порядок покраски) 4*3*2 = 24. Способов покрасить доски без учета порядка 7920 / 24 = 330

9. На шахматной доске стоит ладья. Сколькими способами можно поставить на доску вторую ладью так, чтобы она не оказалась под боем первой?

Ответ: 49.

Решение. Под боем находится одна горизонталь и одна вертикаль. Соответственно 7 горизонталей и 7 вертикалей свободны. Ладью можно поставить на любую горизонталь и любую вертикаль из свободных, т.е. 7*7 = 49 способами

10. Сколькими способами можно расставить три ладьи на доске 8Ч8 так, чтобы они не били друг друга?

Ответ: (8*8)*(7*7)*(6*6)/(3*2*1) = 18816

Решение. Первую ладью ставим в любое место 8*8 = 64 способами, вторую на любую из 7 незанятых горизонталей и 7 незанятых вертикалей, 7*7 = 49 способами (см. решение задачи 10). Третью ладью ставим на любую из 6 незанятых горизонталей и 6 незанятых вертикалей, это можно сделать 6*6 = 36 способами. Теперь нам нужно сократить варианты, где одна и та же расстановка тройки ладей получена выставлением ладей в разном порядке. Для этого надо разделить 64*49*36 на число способов расставить по порядку три ладьи, это число 6 (см. решения задач 8б, 9а).

Дополнительные задачи.

11. Сколько существует семизначных чисел, в записи которых не встречается нулей и которые делятся а) на 4? б) на 9?

Ответ: а) 18*9⁵ = 1062882; б) 9⁶ = 531441

Решение.

а) Число делится на 4, если его 2 последние цифры делятся на 4. В норме эти 2 последние цифры можно взять 25 способами (всего 100 способов, каждый четвертый делятся на 4). Но у нас нет нулей. Из-за отсутствия нулей выпадают способы 00, 04, 08, 20, 40, 60, 80, всего 7 способов. Итак, последние 2 цифры можно выбрать 25-7 = 18 способами. Предыдущие 5 цифр можно выбирать произвольно, каждую 9 способами. Это 9*9*9*9*9 = 9⁵ вариантов. Для каждого из этих 9⁵ вариантов выбора первых пяти цифр последние две мы можем выбрать 18 способами, т.е. всего вариантов выбрать все семь цифр будет 9⁵*18.

Вариант решения. Первые 6 цифр выберем произвольно, это можно сделать 9⁶ способами. Последняя цифра должна быть четной. Если мы взяли предпоследнюю цифру нечетную, то последняя может быть только 2 и 4. Если же шестая цифра была четной, то последняя, седьмая, может быть только 4 или 8.

б) Первые 6 цифр выберем произвольно, это можно сделать 9⁶ способами, а последнюю цифру выбирать не придется: она находится однозначно из условия делимости на 9

12. Сколькими способами из коробки, содержащей 12 различных цветных карандашей, можно выбрать 3 карандаша так, чтобы один из них был черным?

Ответ: 11*10/2 = 55

Решение. Возьмем черный карандаш. Нам осталось выбрать 2 любых. Первый 11 способами, второй 10. И еще число способов надо разделить пополам, т.к. порядок выбора тех двух карандашей не важен.

13. Сколькими способами из коробки, содержащей 12 различных цветных карандашей, можно выбрать 3 карандаша?

Ответ: 12*11*10 / (3*2*1) = 220

Решение. См. решение задачи 8б или 9а.

14. Под кроватью у Полины стоят 5 разноцветных левых и 13 разноцветных правых босоножек. Сколькими способами она может обуться, надев одну левую и одну правую босоножку?

б) Тот же вопрос, если требуется обуть сороконожку, а под кроватью стоят 30 левых и 130 правых босоножек.

Комментарий. Для внешнего вида сороконожки важно, наденет она данную босоножку на первую левую ногу, или же на последнюю левую ногу. Способы, получающиеся переодеванием босоножек между разными левыми ногами считать различными.

Ответ: а) 5*13 = 65; б) (30!/10!) * (130!/110!)

Решение. а) босоножку для левой ноги можно выбрать 5-ью способами, для правой 13-ью. Всего способов 5*13

б) На первую левую ногу можно надеть любую из 30 босоножек, на вторую любую из 29 оставшихся, и т.д. Всего количество способов обуть все 20 левых ног равно произведению чисел от 30 до 11. Это можно записать как 30!/10!. Число способов обуть правые ноги считается аналогично и равно 130!/110! (произведение всех чисел от 130 до 111)

15. Сколькими способами можно расставить 5 ладей на доске 13Ч13 так, чтобы они не били друг друга?

Ответ: 13²*12²*11²*10²*9² / (5*4*3*2*1) = (13!/8!)²/5!

Решение. См. решение задачи 11.

Размещено на Allbest.ru