Home

Комбинаторика

  • Основы комбинаторики

    Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиально возможное количество различных вариантов развития событий.

    Основная формула комбинаторики

    Пусть имеется $k$ групп элементов, причем $i$-я группа состоит из $n_i$ элементов. Выберем по одному элементу из каждой группы. Тогда общее число $N$ способов, которыми можно произвести такой выбор, определяется соотношением $N=n_1*n_2*n_3*...*n_k.$

    1. Пример 1. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из $n_1$ элементов, а вторая - из $n_2$ элементов. Сколько различных пар элементов можно составить из этих двух групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить $n_2$. Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет $n_2$. Так как в первой группе всего n1 элемент, всего возможных вариантов будет $n_1*n_2$.
    2. Пример 2. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?

    Решение: $n_1=6$ (т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), $n_2=7$ (т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5, 6), $n_3=4$ (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4, 6).

    Итак, $N=n_1*n_2*n_3=6*7*4=168$.

    В том случае, когда все группы состоят из одинакового числа элементов, т.е. $n_1=n_2=...n_k=n$ можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно $n*k$.Такой способ выбора носит название выборки с возвращением.

    Пример 3. Сколько всех четырехзначных чисел можно составить из цифр 1, 5, 6, 7, 8?

    Решение. Для каждого разряда четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=54=625.

    Рассмотрим множество, состоящие из n элементов. Это множество будем называть генеральной совокупностью. 

     

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

     

    Пример 4. Различными размещениями из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.

    Число размещений обозначается Anm и вычисляется по формуле:

     

    Замечание: n!=1*2*3*...*n (читается: "эн факториал"), кроме того полагают, что 0!=1.

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

    Решение: т.к. нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:

     

    Определение 2. Сочетанием из n элементов по m называется любой неупорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.

    Пример 6. Для множества {1, 2, 3}сочетаниями являются {1, 2}, {1, 3}, {2, 3}.

    Число сочетаний обозначается $C_n^m$

    и вычисляется по формуле: $C_n^m = \frac{n!}{m!(n-m)!}$

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

    Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:

     

    Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.

    Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).

    Число различных перестановок из n элементов обозначается Pn и вычисляется по формуле Pn=n!.

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

    Решение: эта задача о числе перестановок семи разных книг. Имеется P7=7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.

    Обсуждение. Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно.

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

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

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

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

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

    Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок, которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.

     

     

    Задачи для самопроверки

    1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?

    2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

    3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день?

    4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек?

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

    6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?

     

     

    и еще задачки:

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

    2. Некое современное здание имеет форму куба, стоящего на четырёх колоннах. Имеется 6 красок. Сколькими способами можно покрасить грани здания этими красками в 6 цветов? (Каждая грань красится целиком в один цвет, разные грани красятся в разные цвета.) 

    3. а) В заборе 20 досок, каждую надо покрасить в синий, зелёный или жёлтый цвет, причём соседние доски красятся в разные цвета. Сколькими способами это можно сделать? 

      б) А если требуется ещё, чтобы хоть одна из досок обязательно была синей? 

        

    4. а) Сколько можно составить различных (не обязательно осмысленных) слов из k букв, используя русский алфавит? 

      б) А если потребовать, чтобы буквы в словах не повторялись? 

      в) Сколькими способами можно переставить буквы в слове из k различных букв?  

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

      б) Сколько из них содержит цифру 9 (хотя бы одну)?  

    6. а) Десять девушек водят хоровод. Сколькими способами они могут встать в круг? б) Сколько ожерелий можно составить из 10 различных бусин? в)* А если в ожерелье всего 3 белых и 7 синих бусин? 

    7. а) Сколько строк можно составить из 0 и 1, чтобы в каждой строке было 10 цифр? 

      б) На дереве растут 10 яблок. Сколькими способами можно сорвать несколько из них? 

    8. Меню в школьном буфете постоянно и состоит из n разных блюд. Петя хочет каждый день выбирать себе завтрак по-новому (за раз он может съесть от 0 до n разных блюд). 

      а) Сколько дней ему удастся это делать?  

      б) Сколько блюд он съест за это время? 

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

      г) Сколько блюд он съест за это время? 

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

      б) Ответом в предыдущем пункте является квадрат некоторого числа. Объясните это явление. 

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

    11. Фабрика игрушек выпускает разноцветные кубики. У всякого кубика каждая грань окрашена целиком одной из шести красок, имеющихся на фабрике, причём разные грани одного кубика окрашены разными красками. Сколько видов кубиков выпускает фабрика? 

    12. Фабрика из предыдущей задачи начала выпуск параллелепипедов 1×1×2, склеивая по два из выпускаемых ею кубиков. Сколько получится различных видов новой игрушки? 

    13. Решите две предыдущие задачи, заменив куб на тетраэдр (и 6 цветов на 4). 

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

      б) Докажите, что число способов такой расстановки — квадрат некоторого числа. 

      в)* Найдите это число. (Сначала решите такую же задачу для досок 2×2, 3×3, 4×4, ...)  

    15. Сколько существует строк из 20 цифр, в которых встречаются только нули и единицы, причём никакие два нуля не стоят рядом? 

    16. В таблицу размера k×l записывают числа +1 и -1 так, чтобы произведение чисел в каждой строке и в каждом столбце равнялось 1. Сколькими способами это можно сделать?


          Решений: 17

  • Перестановки

    Задачи для младшей лиги

    Каждая задача по 5 баллов!

    Задача 1

    В пассажирском поезде 17 вагонов. Сколькими способами можно распределить по вагонам 17 проводников, если за каждым вагоном закрепляется один проводник? 

    Задача 2

    На танцплощадке собрались N юношей и N девушек. Сколькими способами они могут разбиться на пары для участия в очередном танце?

    Задача 3

    Сколько существует различных возможностей рассадить 5 юношей и 5 девушек за круглый стол с 10 креслами так, чтобы они чередовались?

    Задача 4

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

    Задача 5

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

    Задача 6

    а) Сколькими способами 28 учеников могут выстроиться в очередь в столовую? 
    б) Как изменится это число, если Петю Иванова и Колю Васина нельзя ставить друг за другом?  

    Задача 7

    Анаграммой называется произвольное слово, полученное из данного слова перестановкой букв. Сколько анаграмм можно составить из слов:
    а) "точка";   б) "прямая";   в)  "перешеек";   г)  "биссектриса";   д)  "абракадабра";   е)  "комбинаторика"?

    Задача 8 

    Даны шесть слов:

    ЗАНОЗА
ЗИПУНЫ
КАЗИНО
КЕФАЛЬ
ОТМЕЛЬ
ШЕЛЕСТ

    За один шаг можно заменить любую букву в любом из этих слов на любую другую (например, за один шаг можно получить из слова ЗАНОЗА слово ЗКНОЗА. Сколько шагов нужно, чтобы сделать все слова одинаковыми (допускаются бессмысленные)? Приведите пример и докажите, что меньшим числом шагов обойтись нельзя. 

    Задача 9

    a1, a2, ..., a101 — такая перестановка чисел 2, 3, ..., 102 , что ak делится на k при каждом k. Найти все такие перестановки.

    Задача 10

    В алфавите племени Бум-Бум шесть букв. Словом является любая последовательность из шести букв, в которой есть хотя бы две одинаковые буквы. Сколько слов в языке племени Бум-Бум? 

    Задача 11

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

    б) Найдите сумму всех семизначных чисел, которые можно получить всевозможными перестановками цифр 1, ..., 7.

  • Подсчет в комбинаторных задачах

    Доброе время суток!

    Решил также начать свой блог, спасибо Асану за это в первую очередь :)

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

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

    Итак, как говорил Ю. А. Гагарин, "Поехали!"

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

    Рассмотрим, к примеру следующую задачу: Назовем билет с номером от 000000 до 999999 отличным, если разность некоторых двух соседних цифр его номера равна 5. Найдите число отличных билетов.

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

    Прежде всего дадим слово кэпу отметим, что цифры, разность между которыми равна 5, разбиваются на пары: 0-5, 1-6, 2-7, 3-8, 4-9, 5-0. Приступим теперь непосредственно к решению.

    Интуиция подсказывает, что в данном случае проще найти число неотличных билетов. Пусть $a_1$$a_2$$a_3$$a_4$$a_5$$a_6$ - номер какого-либо неотличного билета. В качестве $a_1$ можно выбрать любую из 10 цифр. В качестве же цифры $a_2$ в неотличном билете можно взять любую из 9 цифр (исключается, разумеется, цифра, входящая в пару с $a_1$). Аналогично, после выбора $a_2$ в качестве $a_3$ можно выбрать любую из 9 цифр и т. д. Таким образом, число неотличных билетов равно $10$∙$9$∙$9$∙$9$∙$9$∙$9=10$∙$9^5$. Число же отличных билетов тогда составляет $10^6$$-10$∙$9^5$.

    Далее я бы хотел привести ряд задач для самостоятельного решения:

    №1. В Мехико для ограничения транспортного потока для каждой частной автомашины устанавливаются двя дня недели, в которые она не может выезжать на улицы города. Семье требуется каждый день иметь в распоряжении на менее 10 машин. Какое наименьшее количество машин нужно купить семье, если ее члены сами могут выбирать запрещенные дни для своих автомобилей?

    №2. Назовем раскраску доски 8 на 8 в три цвета хорошей, если в любом уголке из пяти клеток присуствуют клетки всех трех цветов (уголок из пяти клеток - это фигура, получающаяся из квадрата 3 на 3 вырезанием квадрата 2 на 2). Докажите, что количество хороших раскрасок не меньше, чем $6^8$.

    №3. В Думе 1600 депутатов, которые образовали 16000 комитетов по 80 человек в каждом. Докажите, что найдутся два комитета, имеющие не менее четырех общих членов.

    Желаю удачи! Разбор данных задач будет осуществлен в следующей записи.

          Решений: 5

  • Множества чисел в комбинаторике. Упорядочивание.

    В этой статье мы рассмотрим подходы к решению олимпиадных задач, связанные с множествами чисел.
    Пример. Даны 7 различных натуральных чисел, сумма которых равна 100. Докажите, что сумма каких-то трех из них не меньше 50.
    Решение: Зачастую такие задачи требуют к упорядочивания чисел - в таком случае вести с ними операции становится возможным. Пусть $a_1 \leq a_2 \leq ... \leq a_7$ и $\sum\limits_{i=1}^7 a_i=100$. Тогда достаточно доказать, что сумма трех наибольших из них не меньше 50. Иными словами необходимо доказать, что $a_5+a_6+a_7 \geq 50$.

    Теперь если $a_5 \geq 16$, то $a_5+a_6+a_7 \geq 16+17+18=51$ (так как они различные). Поэтому достаточно рассмотреть случай, когда $a_5 \leq 15$. Но тогда это накладывает ограничения не на $a_6$ и $a_7$, а на $a_1, a_2, a_3, a_4$.

    Поэтому $a_1+a_2+a_3+a_4 \leq 14+13+12+11=50$. Отсюда сумма оставшихся трех чисел $a_5, a_6, a_7$ не меньше 50.
    Задачи для самостоятельного решения:
    1)        Доказать, что цифры любого шестизначного числа можно переставить таким образом, что сумма первых трех цифр нового номера отличается не более чем на 9 от сумма оставшихся цифр.
    2)        Докажите, что если 2n +1 действительных чисел обладают тем свойством, что сумма любых n меньше чем сумма оставшихся n+1, то все эти числа являются положительными.
    3)      Рассмотрим семь различных натуральных чисел, не превышающих 1706. Докажите, что среди них есть три числа А, B, C, такие, что А<B + C <4А.
    4)      Рассмотрим 2n различных натуральных чисел $a_1, a_2, ... a_{2n} $ не превышающих $n^2$ (n>2). Докажите, что некоторые три разности $a_i-a_j$ равны.
    Литература: Изменено с Titu Andreescu, Razvan Gelca. 2006. Mathematical Olympiad Challenges. Second edition.

          Решений: 9

  • Задачи олимпиады по комбнаторике, участвовать могут все.

      Привет дорогие друзья, задачи к олимпиаде:


      1)(7 баллов) Дан квадрат 10х10. В самой нижней левой клетке с координатами (1;1) сидит кузнечик, который собирается попасть в клетку с координатами (10;10). Он может прыгать на одну клетку вверх, или на одну клетку вправо, причем вероятность того, что он прыгнет так, как и в предыдущий раз равна 60%, (например, если первым ходом он прыгнет вправо, то вероятность того что и вторым ходом он прыгнет вправо равна 60%, а того, что он вторым ходом прыгнет вверх - 40%).За предделы доски кузнечик выпрыгнуть не может и вероятность того, что первым ходом он прыгнет вправо равна 50%, тогда:


     а) Какова вероятность того, что кузнечик выберет следующий путь: (1;1)-(1;2)-(1;3)-(2;3)-(2;4)-(2;5)-(3;5)-(3;6)-(4;6)-(5;6)-(5;7)-(6;7)-(7;7)-(7;8)-(7;9)-(8;9)-(8;10)-(9;10)-(10;10)?


     б) Какой путь от клетки (1;1) до (10;10) наиболее вероятный?


     в) Какой путь от клетки (1;1) до (10;10) наименее вероятный?


     2)(6 баллов) Три снайпера стреляют по мишени, их имена А, В и С. Если будет дождь, то вероятность того что А попадет по мишени равна 70%, того, что В попадет по мишени равна 90%, а вероятность промашки С составляет 45%. Если будет солнечная погода, то А и В стреляют с вероятностью попадания равной 80%, а С с вероятностью попадания 85%. Если же будет сильный ветер, то А и В стреляют с вероятностью попадания 90%, а С стрелять не будет. При каких погодных условиях вероятность того, что хотя бы один из снайперов попадет по мишени наибольшая? Выстрелы снайперами производятся независимо друг от друга.(Считается, что погодные условия комбинироваться не могут, и будет либо дождь, либо солнце, либо ветер.)


      3)(6 баллов) Назовем четырехзначное число "клевым", если произведение первых двух его цифр равно произведению последних двух его цифр. Сколько существует клевых четырехзначных чисел, последняя цифра которых равна 7?


      4)(8 баллов) Дана квадратная доска nxn, некоторые клетки которой черные, а остальные - белые. Каждую минуту каждая белая клетка становится черной, если хотя бы две ее соседние по стороне клетки черного цвета. При каком наименьшем первоначальном количестве черных клеток все клетки доски станут черными, после нескольких таких изменений?


      5)(10 баллов) На бесконечном поле пасутся 100 овец, где то на том же поле стоят два волка. Максимальные скорости овец и волков равны 1метр/мин. Считается, что волк поймал овцу, если они стоят в одной и той же точке поля. При любом ли начальном расположении овец и волков хотя бы один волк поймает хотя бы одну овцу?


      6)(10 баллов) Дан куб 5х5х5 состоящий из 125 маленьких кубиков 1х1х1. Мальчик Петя хочет разобрать большой куб. Куб  считатся разобраным, если в нем не осталось ни одного кубика. Он убирает из конструкции по одному кубику каждую минуту, Петя может убрать любой кубик из конструкции. Считается, что конструкция "ломается", если в какой то  момент есть хотя бы один кубик, который не имеет ни одного другого кубика, соседнего с ним по грани (исключение: когда в конструкции остается только один кубик, она не считается сломаной). Когда Петя убирает какой то кубик, другие он не затрагивает. Сколькими способами Петя может разобрать куб, что бы во время его разборки куб ни разу не "ломался"?


      Вот и все задачи. Прием задач оканчивается в воскресенье вечером, примерно до 12. Совет младшим: пишите все ваши идеи и мысли, при решении задач на комбинаторику они хорошо вознаграждаются. Просьба к старшим: объясняйте все подробно, даже если некоторые вещи для вас очевидны, т.к. это олимпиада. Решения присылать по адресу atriy79@rambler.ru, а некоторые другие правила проведения данной олимпиады вам следует прочитать в статье "Читать всем! Пифагоровская олимпиада по комбинаторике". Спасибо Almas за правку задач.


      Всем удачи! 

          Решений: 16

  • Читать всем! Пифагоровская олимпиада по комбинаторике

      Привет дорогие друзья!


      На следующей неделе (12-14 августа) состоится олимпиада по комбинаторике! Эту олимпаду организую я при поддержке ЦДО Пифагор, а конкретнее Жолдасова Асана. Участниками могут быть все желающие, и те кто учатся в школе, и те кто ее закончил. Все задачи на этой олимпиаде будут либо придуманы мной, либо мной усовершенствованы. На счет сроков проведения олимпиады еще точно не известно, задачи будут вывешаны на сайте на следующей неделе либо в пятницу, либо в субботу вечером в разделе блоги, а решения приниматься до вечера воскресенья той же недели. Решения отправлять по электронной почте по адресу: atriy79@rambler.ru - это моя почта, в формате Microsoft Word, блокнот, и как фотографии формата .jpg (вроде все, что ниже Vista читает), после проверки решений я вывешу рейтинг учасников, и разумеется несколько человек получивших места получат подарки: что то от Асана, и сникерс от меня! Система оценки будет не семибальная, у каждой задачи будет своя стоимость, в зависимости от ее сложности. Пока предполагается, что задачи будут на следующие темы: Комбинаторика, Теория вероятности, Графы, Игры. Аппиляции скорее всего не будет, я постараюсь оценивать как можно правильнее, честность проведения олимпиады я вам обещаю. Есть несколько организационных вопросов, которые желательно обсудить в комментариях к этой статье: Если вы желаете принять участие, то желательно, что бы вы написали об этом в комментариях. Если у вас есть какие то предложения - можете написать их в комментариях. Разделения на младших и старших скорее всего не будет, но это так же еще не решенный вопрос.


      Ну что ж вот и вся информация, удачи всем, участвуйте, побеждайте. Да здравствует комбинаторика!   

          Решений: 9

  • Математика и шахматы.

    Привет всем!

            Многие математики любят играть в шахматы, а шахматисты как правило не плохо понимают математику, разумеется это не означает, что всякий математик - шахматист, и каждый шахматист - математик, но лично я очень люблю шахматы, и поэтому эту статью решил посвятить именно им ... Шахматная доска, с ее обитателями и правилами довольно часто встречается в математических задачах, чаще всего, это задачи на комбинаторику, инвариант и теорию игр. И если вы еще не перешли в 10, 11 ккласс, то скорее всего вам придет хоть одна такая задача. Ну что ж начнем:                               

    1)Комбинаторика. На шахматной доске есть где разгулятся комбинатору, ведь вариантов лишь первого хода - 400, второго больше чем 160000, да уж, это достаточно много. Развивались шахматы, чуть дальше продвигалась комбинаторика, придумывались новые комбинации и задачи, вот например одна из них: Сколькими способами можно поставить на шахматную доску:а) белую и черную ладью, так что бы они не били друг друга? б) двух черных ладей?

       Решение: сначала решим пункт а): Белую ладью можно поставить на любую из 64 клеток, и она побьет 15 клеток: 7 по вертикали, 7 по горизонтали и плюс еще та клетка, на которой она стоит. И так будет всегда, независимо от того, где она будет стоять. Тогда остается 64-15=49 клеток, для того, что бы поставить черную ладью, следовательно ответом задачи является число 64*49. Теперь пункт б) Все то же самое, что и в пункте а), но еще разделить на 2, т.к. там ладьи были различны, а теперь одинаковые. Вот пример белая ладья стоит на поле а1, а черная на в1 и наоборот - это два различных случая, и черные ладьи стоят на полях а1 и в1 и наоборот - это два одинаковых случая. Поэтому в пункте б) случаев в 2 раза меньше.   И так чему мы научились из этой задачи: во первых, полезно делать действия последовательно например расставлять сначала белые, потом черные. Во вторых, не забывать о цвете фигур, в третьих, есть вещи которые остаются неизменными при любом расположении фигуры (и их на самом деле очень много, поисследуйте это очень интересно!).

    2)Теория игр. В теории игр в задачах про шахматы как правило используется симметрия и поиск выигрышных полей. Вот задачи, что бы объяснить и показать это наглядней: 1. Двое играют в игру, ставят слонов на клетки шахматной доски, так что бы слоны не били дуг друга, проигрывает тот кто не может сделать ход. Кто выиграет при правильной игре? Ответ: выирает второй. Его стратегия: он будет ставить своих слонов симметрично, относительно линии между 4 и 5 горизонталями.(осевая симметрия), очевидно что пока есть ход у первого есть ход и у второго, симметричный ходу первого. И когда ходы кончаться (а кончаться т.к. шахматная доска не бесконечна), то будет очередь ходить первому, и он проиграет. А вот еще одна задача: ладья стоит на поле а1, двое по очереди делают им ходы вверх, или вправо, победившим считается тот, кто поставит ладью на поле h8, кто выиграет при правильной игре? Ответ: второй. Стратегия: он каждым своим ходом возвращает ладью на главную диагональ. И т.к. клетка на которую нужно попасть, находится на главной диагонали, значит именно второй поставит туда ладью, как я догадался, составил схему выигрышных полей, идя с конца, (жаль если вы его не знаете, не смогу объяснить коротко, так что если вы его не знаете, то не читайте Виленкина, не читайте Виноградова, а идите заниматься в ЦДО Пифагор, вас там ему научат=), и еще я кажется в Горбачеве видел несколько задач на эту тему с подробным решением. Так что и в теории игр шахматы встречаются довольно часто.

    3) Инвариант и раскраски.  В задачах на раскраску советую начинать с шахматной - это классика. Вот классическая задача на эту тему, наверняка многие из вас ее знают: дана доска 8х8, у которой вырезали две угловые клетки с координатами (1;1) и (8;8). Можно ли теперь доску полностью покрыть костяшками домино, без наложений? Ответ: нет. Почему? А вы покрасте доску как шахматную, теперь заметим, что всякая доминошка, как бы она не стояла покрывает ровно одну белую и одну черную клетку доски, и тогда если бы покрыть было можно, то количесвто белых и черных клеток было бы равно, но у нас на доске белых клеток на 2 больше, поэтому покрыть нельзя. Теперь немного об инварианте: Инвариант - это то, что не меняется при любых опирациях, допустимых в задаче, так вот иногда бывают задачи на инвариант с шахматами, к сожалению, задачу на который можно было бы наглядно объяснить инвариант в задачах про шахматы я недавно уже вывесил на сайте в "задачи", у нее номер 719 кажется, так что я лишь дам несколько полезных советов: Инвариант как правило связан с чередованием черных и белых полей при ходах фигуры, а что бы найти его надо поиследовать задачу, попробовать походить и найти неизменное, если у вас рука набита, то просто щелкнет в мозгах, и инвариант найден.

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

       До свидания, до новых встреч, играйте в шахматы!

          Решений: 3

  • Шары и перегородки

       Привет всем!

      Один из базовых методов решения задач по комбинаторике - это метод "ШАРЫ и ПЕРЕГОРОДКИ".

      Однако для полного понимания этого метода на мой взгляд необходимо разбираться в перестановках! Поэтому я начну статью именно с них:

    1) $P_n$=$n!$ - что означает, перестановка $n$ различных элементов равняется $n!$, доказательство: первым элементом в данном ряду может быть любой из $n$ элементов, вторым $n-1$ и.т.д. Всего получим $n!$, это кстати равно выборке из $n$ элементов по $n$ с учетом порядка выбора.

    2)А если среди них есть повторяющиеся? Например: сколько различных слов можно составить из букв слова МАТЕМАТИКА, если каждую букву можно использовать ровно один раз?(словом считается любая последовательность букв) Решение: всего в данном слове 10  букв, и их перестановка равна10!, но были повторы, к примеру назовем буквы М - (М1) и (М2) тогда есть перестановки (М1)АТЕ(М2)АТИКА и (М2)АТЕ(М1)АТИКА, но оба полученные слова - одинаковы. Поэтому необходимо поделить изначальные 10! на число перестановок всех повторяющихся букв:2! - буква М, 2! - буква Т, 3! - буква А, 1! - буква Е, 1! - буква И, 1! - буква К. Получим $\frac{10!}{2!*2!*3!}$ - ответ задачи.

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

    Когда я только начинал заниматься математикой, а конкретнее комбинаторикой, мне пришла такая задача: Имеется 25 яблок, которые нужно разложить по пяти корзинам, сколькими способами можно это сделать? Честно говоря задача поставила меня в ступор! Я не знал что делать, начал считать варианты: если в первой корзине лежит 25 яблок, а что если 24, а что если 14, здесь же до фига перебора!!!  Задачу я сам решить так и не смог, и мне рассказали об этом методе, и задча стала очевидной, решение: пусть яблоки будут шарами, а корзины - промежутками между перегородками, ПЕРЕГОРОДКАМИ? да именно, а вот наглядное объяснение: 0000000000000000000000000|||| где нули - это яблоки, а палочки - перегородки. В данном примере в первой корзине лежат все 25 яблок, а в остальных ни одного, т.к. те шары которые лежат перед первой перегородкой - считаются лежащими в первой корзине (считаем с лево на право), те шары, которые располагаются между первой и второй перегородками - лежат во второй корзине, шары, лежащие между второй и третьей - в третьей корзине, те, что между третьей и четвертой - в четвертой, а те что после четвертой перегородки - в пятой. Тогда ответом задачи является число перестановок 29 элментов, 25 из которых одинаковы и оставшиеся 4 тоже одинаковы, а это по ранее доказаному равно $\frac{29!}{25!*4!}$. очевидно что при различных перестановках не получиться двух одинаковых разложений по корзинам. Вот это и есть метод шары и перегородки.

    ТЕПЕРЬ ЗАДАЧИ:

    1) Сколько различных слов можно составить из букв слова КРОКОДИЛ, БЕГЕМОТ?

    2) А что если яблок $n$, а корзин $k$?

    3) Сколькими способами можно рзложить 25 яблок по 5 корзинам, так что бы ни одна из корзин не была пуста?

    Ну вот и все до новых встреч!

     

     

          Решений: 4

  • Виленкин Н.А., “Комбинаторика’’

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

     

     

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

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

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

    Никаких первоначальных знаний не требуется, изучать комбинаторику можно “с нуля’’. Начиная с самых простых вещей и решая задачи, постепенно ученик приходит к довольно серьезным и сложным понятиям. Да, книжка особенно понравится тем, кто любит учиться на задачах. Особой теории здесь нет, но есть очень много различных задач: как разобранных примеров, так и задач для самостоятельного решения. И вся теория постигается в процессе решения. Знания усваиваются накрепко.

    Ну вот, кажется все. Теперь о том, где можно купить книгу. Кстати сказать, в электронном виде я ее не встречал. А так, кажется, продается она много где. Наверное, есть в любом достаточно большом приличном книжном магазине. Или ее можно приобрести y нас в наших кружках Пифагор

     

    Источник статий: http://hijos.ru/

          Решений: 2

Архив данных

New forum topics

more

Who's new

Кім онлайн?

There are currently 3 users and 3 guests online.

Сайтағы оқущылар

Syndicate

Syndicate content

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer