Разработка пропедевтического курса "Комбинаторика"

Решение. Кузнечик должен совершить всего 27 прыжков - по 9 в каждом направлении. Обозначим направления буквами A, B и C. Каждый путь однозначно определяется последовательностью длины 27, в которой буквы A, B и C встречаются по 9 раз.

Ответ. способами.

Занятие 2

Задача 6. Нарисуйте на плоскости 6 точек так, чтобы они служили вершинами ровно для 17 треугольников.

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

Ответ. Например, можно взять вершины и середины сторон произвольного треугольника.

Задача 7. Сколько существует натуральных чисел, меньших тысячи, которые не делятся ни на 5, ни на 7?

Решение. Сначала вычеркнем из набора чисел 1, 2, ..., 999 числа, кратные 5; их количество равно . Затем из того же набора чисел 1, 2, ..., 999 вычеркнем числа, кратные 7; их количество равно = 142. При этом числа, кратные 35, будут вычеркнуты дважды. Их количество равно = 28. Значит, всего мы вычеркнули 199 + 142 - 28 = 313 чисел, а осталось 999 - 313 = 686 чисел.

Ответ. 686 чисел.

Решение данной задачи связано со следующими темами: «Теория делимости», «Круги Эйлера», «Формула включений - исключений», «Комбинаторная формула сложения для пересекающихся множеств.

Задача 8. Международная комиссия состоит из 9 человек. Материалы комиссии хранятся в сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно изготовить и как их разделить между членами комиссии, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся не менее 6 членов комиссии?

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

Ответ. 126 замков, по 4 ключа к каждому замку.

Задача 9. Может ли произведение двух последовательных натуральных чисел равняться произведению двух последовательных чётных чисел?

Решение 1. Пусть последовательные числа - это n и n + 1, а соседние чётные числа - это m и m + 2 (m > 0). Если m ? n, то m(m + 2) > n(n +1). Если же m < n, то

m + 2 ? n + 1 и m(m + 2) < n(n + 1).

Решение 2. Пусть m(m + 2) = n(n + 1). Тогда (m + 1)² = m(m + 2) + 1 = n(n + 1)+ 1 = n² + n + 1. Но n² < n² + n + 1 < (n + 1)², то есть

n² < (m +1)² < (n +1)²,

откуда n < m + 1 < n + 1, что невозможно.

Ответ. Не может.

Задача 10. В тёмной комнате на полке в беспорядке лежат 4 пары носков двух разных размеров и двух разных цветов. Какое наименьшее число носков необходимо, не выходя из комнаты, переложить с полки в чемодан, чтобы в нем оказались две пары различного размера и цвета?

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

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

Ответ. 7 носков.

9 класс

Урок 1

Тема урока: «Размещения с повторениями»

Задачи на повторение

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

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

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

Ответ. 120 способами.

Задача 2. Рота состоит из трех офицеров, шести сержантов и 60 рядовых. Сколькими способами можно выделить из них отряд, состоящий из офицера, двух сержантов и 20 рядовых?

Решение. Одного офицера из трех можно выбрать способами. Двух сержантов из шести можно выбрать способами, а 20 рядовых из 60 - способами. Итого, по правилу умножения, получили:

?

Ответ. способами.

Задача 3. На плоскости дано n точек. Сколько имеется отрезков с концами в этих точках?

Ответ. отрезков.

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

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

Ответ. 32 способами.

Задача 5. Ладья стоит на левом поле клетчатой полоски 1Ч30 и за ход может сдвинуться на любое количество клеток вправо.

а) Сколькими способами она может добраться до крайнего правого поля?

б) Сколькими способами она может добраться до крайнего правого поля ровно за 7 ходов?

Решение. а) Здесь мы не берем в учет два крайних поля. Остается 28 полей. На каждом из них ладья может побывать, либо не побывать. Получаем, способов.

б) Если ладья доберется до поля за 7 ходов, то она остановится на шести полях, последний ход - это шаг на крайнее поле. Т. е нам нужно выбрать 6 полей из 28, как и в первом случае 2 крайних поля выпадают, на которых ладья сделает остановки. Получаем: .

Ответ. а); б) способами.

Новая тема

Рассмотрим такую задачу.

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

Решение: В данной задаче речь идет о размещении без повторений. Воспользовавшись формулой числа размещений, получаем:

?

Ответ. 6 способов.

Задача 7. А сколько станет способов, если в предыдущей задаче убрать условие про единственный шарик в лунке?

Решение. тогда к шести способам из предыдущей задачи добавится еще 3: оба шарика либо в первой лунке, либо во второй, либо в третьей. Т.е. способов решения данной задачи 6+3=9.

Ответ. 9 способов.

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

Размещение с повторениями из типов элементов по элементов (допускается ), может содержать любой элемент сколько угодно раз, от 1 до включительно, или не содержать его совсем; т. е. каждое размещение с повторениями из типов элементов по элементов может состоять не только из различных элементов, но и каких угодно и как угодно повторяющихся элементов.

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

Обозначение: .

Давайте попробуем вывести формулу для подсчета числа размещений с повторениями в общем виде. Для этого решим следующую задачу.

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

Решение. В первую лунку мы можем поместить шарик n способами, во вторую так же n способами, и т.д. И так будем продолжать столько раз, сколько у нас имеется лунок, т.е. m раз. По правилу умножения, получили:

?

Итак, число всех различных размещений с повторениями из типов элементов по элементов вычисляется по формуле:

?

Задача 9. В лифт восьмиэтажного дома вошли 5 пассажиров. Сколькими способами могут выйти пассажиры на каждом этаже, начиная со второго?

Решение. Задача сводится к распределению 5 пассажиров по 7 этажам (т. е. набор упорядоченный), причем возможны повторения (т. е. несколько пассажиров могут выйти на одном этаже). Таким образом, задача сводится к нахождению числа размещений с повторениями:

?

Ответ. 16807 способов.

Домашнее задание

Задача 10. Буквы азбуки Морзе состоят из символов - точка и тире. Сколько букв получим, если потребуем, чтобы каждая буква состояла не более чем из пяти указанных символов?

Ответ. 62 буквы.

Задача 11. Сколькими способами девочка Яна может разложить 12 кукол по трём ящикам, если каждый ящик может вместить все куклы?

Ответ. способов.

Задача 12. Сколькими различных восьмизначных чисел можно написать, пользуясь только тремя цифрами 3, 5, 7 при условии, что цифра 5 в каждом числе встречается ровно два раза?

Решение. Сначала рассмотрим сколькими способами может занять места «5»: из 8 мест она должна занять 2, так как порядок не важен, то воспользуемся формулой числа сочетаний Так как в числе два места уже заняты «5», то оставшиеся две цифры 3 и 7 нужно разместить на шести местах. Так как никаких ограничений на количество цифр в числе нет, то воспользуемся формулой для подсчета числа размещений с повторениями:

?

Итого, по правилу умножения, получили: 28

Ответ. 1792 числа.

Урок 2

Тема урока: «Перестановки с повторениями»

Новая тема

Рассмотрим такие задачи.

Задача 1. За слово будем считать любое сочетание букв алфавита. Сколько получится слов, при перестановке букв в слове «толпа»?

Решение. В данной задаче речь идет о перестановках без повторений, т.к. все буквы в слове различны. Поэтому воспользуемся формулой для подсчета числа перестановок и получим = 5! = 120 слов.

Ответ. 120 слов.

Задача 2. А сколько слов получится, если же переставлять буквы в слове «топот»?

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

Ответ. 30 слов.

Таким образом, мы столкнулись с понятием «перестановки с повторением».

Общую задачу сформулируем следующим образом. Имеется элементов различных типов: элементов первого типа, элементов второго типа, …, элементов k-го типа, .

Перестановки с повторениями - это количество различных перестановок, которые можно составить из этих элементов.

Число перестановок c повторениями обозначают

Для того чтобы вывести формулу числа перестановок с повторениями, решим следующую задачу:

Задача 3. У Ани было конфет «Мишка косолапый», конфет «Метелица» и конфет «Красная шапочка». Каждый день она съедала по одной конфете. Сколькими способами она могла это сделать?

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

Поэтому число способов, которыми Аня может съесть конфеты равно:

?

Ответ. способов.

Нетрудно догадаться, что для каких - либо k типов элементов, формула будет выглядеть так:

?

Задача 4. Сколькими способами можно нанизать на нить 4 зеленых, 5 синих и 6 красных бус?

Решение. Речь идет об отыскании числа перестановок с повторениями, которые можно сделать из =4 элементов первого типа (зеленых бус), =5 элементов второго типа (синих бус) и =6 элементов третьего типа (красных бус). Применив формулу, получаем:

?

Ответ. 630630 способов.

Задачи на закрепление

Задача 5. Сколько различных «слов» можно образовать, переставляя буквы в словах: а) мама; б) барабан?

Ответ. а) 6 слов; б) 420слов.

Задача 6. Сколько сигналов можно составить, меняя порядок семи флагов: один красный, два синих, три зеленых и один белый?

Ответ. 420 сигналов.

Задача 7. Сколько слов можно составить из пяти букв а и не более, чем трех букв b?

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

1) Если в слове 5 букв, то все слово состоит из букв a. Т.е. существует всего одно такое слово.

2) Если слово состоит из шести букв - 5 a и 1 b. То количество таких слов мы будем вычислять по формуле:

слов.

3) Аналогично рассуждаем для слов из семи букв:

слов.

4) Слова из восьми букв:

слов.

Итого, получили, что всего слов, удовлетворяющих данным условиям:

1+6+21+56=84 слова.

Ответ. 84 слова.

Домашнее задание

Задача 8. Сколькими способами можно расположить в ряд пять книг: два одинаковых романа и три одинаковых томика стихов?

Ответ. 10 способов.

Задача 9. Сколькими способами можно переставлять буквы в слове «огород», если: нельзя, чтобы три буквы «о» не стояли рядом?

Решение. Если пока откинуть условие про букву «о», то буквы данного слова можно переставлять P(3,1,1,1) = 120 способами. Теперь нам нужно исключить случаи, когда три буквы «о» стоят рядом, для этого рассмотрим эти три буквы как одну, тогда получится перестановка четырех различных чисел. Тогда буквы можно переставлять 4! = 24 способами. Теперь из общего случая нужно вычесть те перестановки, которые нам не подходят по условию. Получаем 120 - 24 = 96 способов.

Ответ. 96 способов.

Урок 3

Тема урока: «Сочетания с повторениями»

Новая тема

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

Поясним это на следующем примере. Пусть имеется три элемента: Тогда из этих трёх элементов можно составить три сочетания без повторений по два элемента: А что изменится, если допустить, что элементы могут повторяться? Добавится еще три сочетания Итого, получили, что число сочетаний с повторениями из трех элементов по 2 равно 6.

Различные комбинации должны отличаться количеством предметов хотя бы одного типа. Такие комбинации называются «сочетаниями с повторениями», а их общее число принято обозначать .

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

Теперь нужно вывести формулу для подсчета числа различных сочетаний с повторениями. Для этого рассмотрим следующую задачу:

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

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

Например, в кондитерском магазине продаются пирожные 4 видов: корзиночки, наполеоны, песочные и эклеры. Если куплено 3 корзиночки (к), 1 наполеон (н), 2 песочных (п) и 1 эклер (э), то получим такую запись:

?

В этой записи единицы отделяют одну группу пирожных от другой. Если же куплено 2 корзиночки и 5 песочных, то получим запись 001100000. Ясно, что разным покупкам соответствуют при этом разные комбинации из 7 нулей и 3 единиц. Обратно, каждой комбинации нулей и единиц соответствует какая-то покупка. Например, комбинации 1000100001 соответствует покупка 3 «наполеона» и 4 песочных (крайние группы отсутствуют).

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

Итак, число сочетаний с повторениями из элементов типов по равно числу перестановок с повторениями из единиц и нулей.

?

Таким образом получили, что число сочетаний с повторениями вычисляется по формуле:

?

Задача 2. В кондитерской имеется 3 вида пирожных. Сколькими способами можно купить 9 пирожных?

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

способов.

Ответ. 55 способов.

Задачи на закрепление

Задача 3. Сколькими способами можно выбрать три книги из трех одинаковых романов и трех одинаковых томиков стихов?

Ответ. 56 способов.

Задача 4. В почтовом отделении продаются открытки 10 видов. Сколькими способами можно купить 12 открыток для поздравлений?

Ответ. 293930 способов.

Задача 5. Сколькими способами Буратино, кот Базилио и лиса Алиса могут поделить между собой 5 одинаковых золотых монет?

Ответ. 21 способ.

Задача 6. Сколько всего чисел (не больше 100000) можно составить из цифр 1, 2, 3, 4 и 5 в каждом из которых цифры расположены в неубывающем порядке?

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

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

5 + 15+ 35 + 70 + 126 = 251 чисел.

Ответ. 251 чисел.

Домашнее задание.

Задача 7. В кондитерской имеется пять разных сортов пирожных. Сколькими способами можно выбрать набор из четырёх пирожных?

Ответ. 70 способов.

Задача 8. Сколько существует треугольников, длины сторон которых принимают одно из значений 4, 5, 6, 7?

Ответ. 20 треугольников.

Задача 9. Сколько можно построить различных прямоугольных параллелепипедов, длина каждого ребра которых является целым числом от 1 до 10?

Ответ. 220 прямоугольных параллелепипедов.

Урок 4

Тема урока: «Комбинации с повторениями. Обобщение»

На обобщающем уроке нужно повторить все изученные формулы и каким-нибудь образом систематизировать информацию. Мы предлагаем дополнить нашу таблицу - алгоритм, приведенную в разработке уроков за 8 класс, новой информацией.

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

Задача 1. Группу из 20 студентов нужно разделить на 3 бригады, причем в первую бригаду должны входить 3 человека, во вторую -- 5 и в третью -- 12. Сколькими способами это можно сделать?

Решение. В первую группу мы выбираем из 20 студентов 3 - это способов, так как порядок нам не важен; во вторую группу из 17 оставшихся студентов выбираем 5 - это способов; в третью, аналогично - способов.

По правилу произведения, получаем

Ответ. 7054320 способов.

Задача 2. Сколько слов можно получить, переставляя буквы в слове «гора» и «институт»?

Ответ. 24 слова; 3360 слов.

Задача 3. Сколько различных дробей можно составить из чисел 3, 5, 7, 11, 13, 17 так, чтобы в каждую дробь входили 2 различных числа? Сколько среди них будет правильных дробей?

Ответ. 30 дробей, из них 15 правильных.

Задача 4. У Васи дома живут 4 кота:

а) сколькими способами можно рассадить котов по углам комнаты?

б) сколькими способами можно отпустить гулять котов?

в) сколькими способами Вася может взять на руки 2-х котов (одного на левую, другого - на правую)?

Ответ. а) 24; б) 15; в) 12 способов.

Задача 5. В студенческой столовой продают сосиски в тесте, ватрушки и пончики. Сколькими способами можно приобрести пять пирожков?

Ответ. 21 способ.

Задача 6. Сколько существует четырёхзначных пин-кодов?

Ответ. 1000 вариантов.

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

Ответ. 5040 способов.

Задача 8. Сколькими способами можно переставить буквы слова «опоссум» так, чтобы буква «п» шла непосредственно после буквы «о»?

Ответ. 360 способов.

Самостоятельная работа на 10 - 15 минут

1. Алексей занимается спортом, причём 4 дня в неделю - лёгкой атлетикой, 2 дня - силовыми упражнениями и 1 день отдыхает. Сколькими способами он может составить себе расписание занятий на неделю? (105).

2. В кошельке находится достаточно большое количество рублей, 2-, 5- и 10-рублёвых монет. Сколькими способами можно извлечь три монеты из кошелька? (20).

3. Согласно государственному стандарту, автомобильный номерной знак состоит из 3 цифр и 3 букв. При этом недопустим номер с тремя нулями, а буквы выбираются из набора А, В, Е, К, М, Н, О, Р, С, Т, У, Х (используются только те буквы кириллицы, написание которых совпадает с латинскими буквами). (1726272).

Спецкурс

Занятие 1

Задача 1. В шахматном кружке занимаются 2 девочки и 7 мальчиков. Для участия в соревновании необходимо составить команду из четырех человек, в которую обязательно должна входить хотя бы одна девочка. Сколькими способами это можно сделать?

Решение. В команду входит либо одна девочка, либо две. Разберем оба случая. Если в команде две девочки, то двух мальчиков к ним можно добавить способами. Если же в команду входит только одна девочка (ее можно выбрать двумя способами), то команду можно дополнить тремя мальчиками различными способами. Таким образом, общее число возможных команд равно .

Ответ. 91 способом.

Задача 2. Было 7 ящиков. В некоторые из них положили еще по 7 ящиков (не вложенных друг в друга) и т. д. В итоге стало 10 непустых ящиков. Сколько всего стало ящиков?

Решение. При каждой операции заполняется один пустой ящик. Поскольку стало 10 непустых ящиков, то было проведено 10 операций. При каждой операции добавлялось по 7 ящиков.

Поэтому в результате стало 7 + 10·7 = 77 ящиков.

Ответ. 77 ящиков.

Задача 3. Какое наименьшее число карточек спортлото (6 из 49) надо купить, чтобы наверняка хоть в одной из них был угадан хоть один номер?

Решение. Заполним 8 карточек следующим образом: в первой зачеркнем числа от 1 до 6, во второй - от 7 до 12 и т. д., в последней - от 43 до 48. Не зачеркнутым ни в одной карточке останется только число 49. Поэтому среди выигрышных номеров, по крайней мере, пять окажутся зачеркнутыми.

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

Ответ. 8 карточек.

Задача 4. Найти такое трёхзначное число, удвоив которое, мы получим число, выражающее количество цифр, необходимое для написания всех последовательных целых чисел от единицы до этого искомого трёхзначного числа (включительно).

Решение. Пусть x - искомое число. Однозначных чисел всего 9, двузначных - 90, трёхзначных чисел до x включительно - (). Количество цифр, необходимое для написания всех последовательных чисел от 1 до x, равно 9 + 2·90 + 3·(x - 99) = 3x - 108.

Получим уравнение 2x = 3x - 108, откуда x = 108.

Ответ. 108.

Задача 5. Сколько существует разных способов разбить число 2004 на натуральные слагаемые, которые приблизительно равны?

Слагаемых может быть одно или несколько.

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

Решение. Каждый способ однозначно определяется числом слагаемых. Действительно, пусть 2004 разбито на n слагаемых, r из которых равны q + 1, а остальные равны q (0 ? r < n). Тогда 2004 = qn + r. Таким образом, числа q и r суть частное и остаток от деления 2004 на n, они однозначно определены выбором n. Итак, выбирая любое n от 1 до 2004, получаем единственное разбиение 2004 на n приблизительно равных слагаемых.

Ответ. 2004 способа.

Занятие 2

Задача 1. Автобусная сеть города устроена следующим образом:

1) с каждой остановки на любую другую остановку можно попасть без пересадки;

2) для каждой пары маршрутов найдется, и притом единственная, остановка, на которой можно пересесть с одного из этих маршрутов на другой;

3) на каждом маршруте ровно три остановки.

Сколько автобусных маршрутов в городе? (Известно, что их больше одного.)

Решение. Пусть a - один из маршрутов, B - остановка, через которую маршрут a не проходит. Каждый маршрут, проходящий через B, пересекает маршрут a. При этом два разных маршрута, проходящих через B, пересекают a по разным остановкам (иначе они имели бы две общие остановки, что противоречит условию 2). Поэтому через B проходит ровно три маршрута.

На каждом из них есть по две остановки, отличных от B. Значит, всего в городе 7 остановок. Через каждую пару остановок (а их 21) проходит единственный маршрут, при этом на каждом маршруте - три пары остановок. Следовательно, всего маршрутов 21: 3 = 7.

Ответ. 7 маршрутов.

Задача 2. У Пети есть 12 одинаковых разноцветных вагончиков (некоторые, возможно, одного цвета, но неизвестно, сколько вагончиков какого цвета). Петя считает, что различных 12-вагонных поездов он сможет составить больше, чем 11-вагонных. Не ошибается ли Петя? (Поезда считаются одинаковыми, если в них на одних и тех же местах находятся вагончики одного и того же цвета.)

Решение. Для краткости будем называть поезд из 11 вагончиков - "поезд-11", а поезд из двенадцати вагончиков - "поезд-12".

Рассмотрим два различных "поезда-12" и отцепим от них последние вагончики. Если эти вагончики у них одинаковые, то, отцепив их, мы получим различные "поезда-11" (так как "поезда-12" были различными, а отцеплены одинаковые вагончики). Если же последние вагончики были различными, то на каком-то месте в этих поездах также должны находиться различные вагончики, так как все поезда составлены из одного и того же набора вагончиков (из всех вагончиков, которые есть у Пети).

Таким образом, все получившиеся "поезда-11" будут состоять из различных наборов вагончиков, то есть также будут различными. Следовательно, из различных "поездов-12" получаются различные "поезда-11", то есть "поездов-11" не меньше, чем "поездов-12".

Ответ. Ошибается.

Замечание. На самом деле, "поездов-11" ровно столько же, сколько и "поездов-12". Действительно, если рассмотреть два различных "поезда-11", то после добавления к ним последнего вагончика не могут получиться одинаковые "поезда-12", так как среди первых 11 вагончиков есть отличия. Поэтому из различных "поездов-11" получаются различные "поезда-12", то есть "поездов-12" не меньше чем "поездов-11". В итоге мы установили взаимно однозначное соответствие между двумя множествами: различных "поездов-12" и различных "поездов-11".

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

Задача 3. Квадрат разбит прямыми на 25 квадратиков-клеток. В некоторых клетках нарисована одна из диагоналей так, что никакие две диагонали не имеют общей точки (даже общего конца). Каково наибольшее возможное число нарисованных диагоналей?

Решение. Пример с 16 диагоналями см. на рисунке.

Оценка. Предположим, что удалось провести 17 диагоналей. Приведём два способа прийти к противоречию.

Решение 1. Каждая диагональ имеет два конца, расположенных в узлах квадратной сетки. Всего таких узлов в квадрате 36. 12 из них расположены на границе внутреннего квадрата 3Ч3 (рис. слева), поэтому диагоналей с концами в этих узлах проведено не больше 12. Оставшиеся пять диагоналей могут располагаться только в центральной и четырёх угловых клетках. Значит, четыре узла, расположенные в вершинах квадрата, не являются концами проведённых диагоналей, то есть 17 диагоналей имеют не более 36 - 4 = 32 концов. Противоречие.

Решение 2. В каждом прямоугольнике 5Ч2 проведено не больше 6 диагоналей: на его средней линии всего шесть узлов, а каждая диагональ имеет один из них своим концом. Значит, во всех горизонталях квадрата, кроме средней, проведено в сумме не более 12 диагоналей. Поэтому в средней горизонтали их не меньше, чем 17 - 12 = 5, то есть в каждой ее клетке проведена диагональ.

Аналогично доказывается, что диагонали проведены во всех клетках средней вертикали. Но диагонали, проведённые в соседних (имеющих общую сторону) клетках, параллельны. Значит, весь "центральный крест" заполнен параллельными диагоналями. Но тогда диагонали в двух соседних с центром клетках имеют общую точку (см. рис. справа). Противоречие.

Ответ: 16 диагоналей.

Задача 4. Пусть 6 ящиков занумерованы числами от 1 до 6. Сколькими способами можно разложить по этим ящикам 20 одинаковых шаров

а) так, чтобы ни один ящик не оказался пустым?

б) если некоторые ящики могут оказаться пустыми?

Решение. а) Выложим шары в ряд. Для определения расклада наших шаров по шести ящикам разделим ряд 5 перегородками на 6 групп: первая группа для первого ящика, вторая - для второго и так далее. Таким образом, число вариантов раскладки шаров по ящикам равно числу способов расположения пяти перегородок. Перегородки могут стоять на любом из 19 мест (между 20 шарами - 19 промежутков). Поэтому число их возможных расположений равно .

б) Рассмотрим ряд из 25 предметов: 20 шаров и 5 перегородок, расположенных в произвольном порядке. Каждый такой ряд однозначно соответствует некоторому способу раскладки шаров по ящикам: в первый ящик попадают шары, расположенные левее первой перегородки, во второй - расположенные между первой и второй перегородками и т. д. (между какими-то перегородками шаров может и не быть). Поэтому число способов раскладки шаров по ящикам равно числу различных рядов из 20 шаров и 5 перегородок, т.е. равно .

Ответ. а) ; б) способами.

Задача 5. Сколькими способами натуральное число n можно представить в виде суммы

а) k натуральных слагаемых?

б) k неотрицательных целых слагаемых?

(Представления, отличающиеся порядком слагаемых, считаются различными.)?

Решение. Представим n в виде суммы n единиц: n = 1 + 1 + ... + 1. Теперь, по аналогии с предыдущей задачей, назовем теперь эти n единиц "шарами", а k слагаемых из условия задачи - "ящиками".

Ответ. а) ; б) способами.

3.2 Апробация пропедевтического курса

Основная задача апробации - повышение уровня мыслительной деятельности учащихся с помощью курса «Комбинаторика».

В апробации пропедевтического курса «Комбинаторика» принимали участие учащиеся 5 и 6 классов.

Общее количество учащихся - 60 человек, возраст детей - 10-12 лет.

Уровень подготовки ребят приблизительно одинаков.

В соответствии с учебно-тематическим планом было проведено 12 учебных занятий в 5 и 6 классах. Занятия проводились один раз в неделю по два часа.

Был составлен список вопросов для проверки входных знаний для учащихся 5 и 6 классов, который представлен в УМК по курсу

Для проверки знаний и оценки результатов апробации курса был проведен итоговый тест, в двух вариантах, для учащихся 5 и 6 классов. Тест состоял из 30 вопросов, темы которых соответствовали темам разделов курса

Апробация дала положительные результаты, учащиеся выполнили все предложенные им практические работы, тесты, задания, овладели требуемыми знаниями и умениями.



Заключение

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

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

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

3. Применение в реальной жизни: Множество задач комбинаторики происходят из повседневной жизни, поэтому ученики могут научиться применять эти знания в реальной жизни.

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

Целью данной выпускной квалификационной работы является разработка пропедевтического курса «Комбинаторика» для учащихся 5 - 9 классов.

Для достижения заданной цели мы решили следующие задачи:

1. Описать теоретические основы развития математического мышления школьников посредством решения комбинаторных задач;

2. Изучить методику решения задач по курсу «Комбнаторика»;

3. Разработать пропедевтический курс «Комбинаторика» для учащихся 5 - 9 классов;

4. Провести апробацию разработанного курса.



Список использованных источников

1. Дворяткина С. Н., Щербатых С. В. Роль системы дополнительного профессионального образования в развитии нового стиля мышления современного специалиста (на примере переподготовки учителя математики) //Психология образования в поликультурном пространстве. - 2019. - №. 3. - С. 76-88.

2. Яковлева Н. С. КОМБИНАТОРИКА В ЗАДАЧАХ И В ОБЫДЕННОЙ ЖИЗНИ //Редакционная коллегия. - 2019. - С. 311.

3. Тестов В. А. РЕШЕНИЕ ЗАДАЧ КАК ОСНОВА РАЗВИТИЯ МАТЕМАТИЧЕСКОГО МЫШЛЕНИЯ //Математика и проблемы образования. - 2022. - С. 158-160.

4. Половникова Г. В. «Математика для всех» возраст обучающихся-15-16 лет.

5. Рыбдылова Д. Д., Бадеев А. В., Булатова В. Б. Формирование у студентов содержательного обобщения в процессе решения комбинаторных задач //Современное педагогическое образование. - 2021. - №. 2. - С. 221-226.

6. Бочкова В. П. МАТЕМАТИКА В ДЕЙСТВИИ.

7. Шикер К. В. Занимательная математика.

8. Прахт Н. Ю. Нестандартные задачи как средство формирования познавательных универсальных учебных действий на уроках математики в начальных классах: дис. - Сибирский федеральный университет; Лесосибирский педагогический институт--филиал СФУ, 2020.

9. Яковлева Н. С. ВНЕУРОЧНЫЕ ЗАНЯТИЯ ПО МАТЕМАТИКЕ В 3 КЛАССЕ КАК СРЕДСТВО ФОРМИРОВАНИЯ КОМБИНАТОРНЫХ УМЕНИЙ //ПЕДАГОГ-ИССЛЕДОВАТЕЛЬ: ВЗГЛЯД В БУДУЩЕЕ. - 2020. - С. 24.

10. Базарова Е. Г., БРИОП К. Диагностика математических способностей учащихся в средней общеобразовательной школе.

11. Маньшина Т. В. РАЗРАБОТКА РАБОЧЕЙ ПРОГРАММЫ ЭЛЕКТИВНОГО КУРСА ПО ТЕМЕ «ОСНОВЫ ТЕОРИИ ВЕРОЯТНОСТЕЙ И МАТЕМАТИЧЕСКОЙ СТАТИСТИКИ. РЕШЕНИЕ ЗАДАЧ ПО ТЕОРИИ ВЕРОЯТНОСТЕЙ» //РОЛЬ И МЕСТО ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ В СОВРЕМЕННОЙ НАУКЕ. - 2019. - С. 5.

12. Тютина О. Д., Орлова Л. Н., Минаева Т. А. Рабочая программа по учебному предмету «Алгебра» 7 класс уровень профильный один год обучения.

13. Шадрина И. Теория и методика математического развития. Учебник и практикум для СПО. - Litres, 2022.

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