Факториал в егэ по математике

29 декабря 2011

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

где k — число благоприятных исходов, n — общее число исходов (см. «Тест по теории вероятностей»).

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

Однако последние пробные экзамены показали, что в настоящем ЕГЭ по математике могут встречаться значительно более сложные конструкции. Отыскание значений n и k становится проблематичным. В таком случае на помощь приходит комбинаторика. Ее законы работают там, где искомые значения не выводятся непосредственно из текста задачи.

В сегодняшнем уроке не будет строгих формулировок и длинных теорем — они слишком сложны и, к тому же, совершенно бесполезны для решения настоящих задач B6. Вместо этого мы рассмотрим простые правила и разберем конкретные задачи, которые действительно встречаются на ЕГЭ. Итак, поехали!

Число сочетаний и факториалы

Пусть имеется n объектов (карандашей, конфет, бутылок водки — чего угодно), из которых требуется выбрать ровно k различных объектов. Тогда количество вариантов такого выбора называется числом сочетаний из n элементов по k. Это число обозначается C_n^k и считается по специальной формуле.

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

Выражение n! читается как «эн-факториал» и обозначает произведение всех натуральных чисел от 1 до n включительно: n! = 1 · 2 · 3 · … · n.

Кроме того, в математике по определению считают, что 0! = 1 — подобный бред редко, но все же встречается в задачах по теории вероятностей.

Что дает нам эта формула? На самом деле, без нее не решается практически ни одна серьезная задача.

К сожалению, в школе совершенно не умеют работать с факториалами. Кроме того, в формуле числа сочетаний очень легко запутаться: где стоит и что обозначает число n, а где — k. Поэтому для начала просто запомните: меньшее число всегда стоит сверху — точно так же, как и в формуле определения вероятности (вероятность никогда не бывает больше единицы).

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

Задача. У бармена есть 6 сортов зеленого чая. Для проведения чайной церемонии требуется подать зеленый чай ровно 3 различных сортов. Сколькими способами бармен может выполнить заказ?

Тут все просто: есть n = 6 сортов, из которых надо выбрать k = 3 сорта. Число сочетаний можно найти по формуле:

Задача. В группе из 20 студентов надо выбрать 2 представителей для выступления на конференции. Сколькими способами можно это сделать?

Опять же, всего у нас есть n = 20 студентов, а выбрать надо k = 2 студента. Находим число сочетаний:

Обратите внимание: красным цветом отмечены множители, входящие в разные факториалы. Эти множители можно безболезненно сократить и тем самым значительно уменьшить общий объем вычислений.

Задача. На склад завезли 17 серверов с различными дефектами, которые стоят в 2 раза дешевле нормальных серверов. Директор купил в школу 14 таких серверов, а сэкономленные деньги своровал и купил дочке шубу из меха соболя за 200 000 рублей. Сколькими способами директор может выбрать бракованные серверы?

В задаче довольно много лишних данных, которые могут сбить с толку. Наиболее важные факты: всего есть n = 17 серверов, а директору надо k = 14 серверов. Считаем число сочетаний:

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

Как видите, число сочетаний из n по k считается достаточно просто. Проблема в том, что многие школьники никогда не работали с факториалами. Для них это новый и незнакомый математический объект, и для его освоения требуется некоторая тренировка.

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

Закон умножения

Закон умножения в комбинаторике: число сочетаний (способов, комбинаций) в независимых наборах умножается.

Другими словами, пусть имеется A способов выполнить одно действие и B способов выполнить другое действие. Путь также эти действия независимы, т.е. никак не связаны между собой. Тогда можно найти число способов выполнить первое и второе действие по формуле: C = A · B.

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

Итак, сначала Петя достает k = 1 монету из n = 4 имеющихся монет номиналом 1 рубль. Число способов сделать это равно C₄¹ = … = 4.

Затем Петя снова лезет в карман и достает k = 1 монету из n = 2 имеющихся монет номиналом 10 рублей. Здесь число сочетаний равно C₂¹ = … = 2.

Поскольку эти действия независимы, общее число вариантов равно C = 4 · 2 = 8.

Задача. В корзине лежат 8 белых шаров и 12 черных. Сколькими способами можно достать из этой корзины 2 белых шара и 2 черных?

Всего в корзине n = 8 белых шаров, из которых надо выбрать k = 2 шара. Это можно сделать C₈² = … = 28 различными способами.

Кроме того, в корзине имеется n = 12 черных шаров, из которых надо выбрать опять же k = 2 шара. Число способов сделать это равно C₁₂² = … = 66.

Поскольку выбор белого шара и выбор черного — события независимые, общее число комбинаций считается по закону умножения: C = 28 · 66 = 1848. Как видим, вариантов может быть довольно много.

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

Именно этой формулы многим не хватило для решения задачи B6 на пробном ЕГЭ по математике. Разумеется, существуют и другие методы решения, в которых комбинаторика не используется — и мы обязательно рассмотрим их ближе к настоящему экзамену. Однако ни один из них не сравнится по надежности и лаконичности с теми приемами, которые мы сейчас изучаем.

Закон сложения

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

Например, «Петя вынул из кармана 1 монету» и «Петя не вынул из кармана ни одной монеты» — это взаимоисключающие события, поскольку вынуть одну монету и при этом не вынуть ни одной невозможно.

Аналогично, события «Выбранный наугад шар — белый» и «Выбранный наугад шар — черный» также являются взаимоисключающими.

Закон сложения в комбинаторике: если два взаимоисключающих действия можно выполнить A и B способами соответственно, то эти события можно объединить. При этом возникнет новое событие, которое можно выполнить X = A + B способами.

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

Можно сказать, что закон сложения — это логическое «ИЛИ» в комбинаторике, когда нас устраивает любой из взаимоисключающих вариантов. И наоборот, закон умножения — это логическое «И», при котором нас интересует одновременное выполнение и первого, и второго действия.

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

Если шары одинакового цвета, то вариантов немного: оба они либо черные, либо красные. Очевидно, что эти варианты — взаимоисключающие.

В первом случае мальчику предстоит выбирать k = 2 черных шара из n = 9 имеющихся. Число способов сделать это равно C₉² = … = 36.

Аналогично, во втором случае выбираем k = 2 красных шара из n = 7 возможных. Число способов равно C₇² = … = 21.

Осталось найти общее количество способов. Поскольку варианты с черными и красными шарами — взаимоисключающие, по закону сложения имеем: X = 36 + 21 = 57.

Задача. В ларьке продаются 15 роз и 18 тюльпанов. Ученик 9-го класса хочет купить 3 цветка для своей одноклассницы, причем все цветы должны быть одинаковыми. Сколькими способами он может составить такой букет?

По условию, все цветы должны быть одинаковыми. Значит, будем покупать либо 3 розы, либо 3 тюльпана. В любом случае, k = 3.

В случае с розами придется выбирать из n = 15 вариантов, поэтому число сочетаний равно C₁₅³ = … = 455. Для тюльпанов же n = 18, а число сочетаний — C₁₈³ = … = 816.

Поскольку розы и тюльпаны — это взаимоисключающие варианты, работаем по закону сложения. Получаем общее число вариантов X = 455 + 816 = 1271. Это и есть ответ.

Дополнительные условия и ограничения

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

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

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

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

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

Другими словами, если из 5 ручек надо выбрать 3, при этом одна из них должна быть красной, то выбирать придется из n = 5 − 1 = 4 элементов по k = 3 − 1 = 2 элемента. Таким образом, вместо C₅³ надо считать C₄².

Теперь посмотрим, как это правило работает на конкретных примерах:

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

Итак, есть группа из n = 20 студентов. Но выбрать надо лишь k = 4 из них. Если бы не было дополнительных ограничений, то количество вариантов равнялось числу сочетаний C₂₀⁴.

Однако нам поставили дополнительное условие: 2 отличника должны быть среди этих четырех. Таким образом, согласно приведенному выше правилу, мы уменьшаем числа n и k на 2. Имеем:

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

Итак, есть n = 8 монет. Петя перекладывает k = 3 монеты, из которых 2 — десятирублевые. Получается, что из 3 монет, которые будут переложены, 2 уже зафиксированы, поэтому числа n и k надо уменьшить на 2. Имеем:

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

В заключение отмечу, что в первой задаче мы получили 153 варианта — это намного меньше, чем исходные C₂₀⁴ = … = 4845 вариантов. Аналогично, 3 монеты из 8 можно переложить C₈³ = … = 56 способами, что значительно больше 6 способов, которые мы получили в последней задаче.

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

Смотрите также:

1. Комбинаторика в задаче B6: легкий тест
2. Задачи B6 с монетами
3. Что такое логарифм
4. Четырехугольная пирамида: как найти координаты вершин
5. Задача B15: работаем с показательной функцией без производной
6. Сложные задачи B15: комбинация тригонометрии и многочленов

Задачи повышенной сложности

Числовые множества

1. Натуральные числа – числа, которые мы используем для счета предметов, счёт начинается с единицы, поэтому ноль не является натуральным числом. Множество натуральных чисел обозначается $N$.

2. Целые числа – это ноль и «плюс – минус натуральные числа». Множество целых чисел обозначается $Z$.

3. Рациональные числа – это всевозможные дроби ${m}/{n}$, где $m$ — целое число, а $n$ – натуральное число, т.е. $n≠0$. Множество рациональных чисел обозначается $Q$.

Делимость

Число $а$ делится на число $с≠0$, если найдется такое число $b$, что $a=c·b$.

Если число $а$ делится на $с$, то число с называется делителем числа $а$.

Если числа $а$ и $b$ делятся на $с$, то их сумма $а + b$ тоже делится на $с$.

Признаки делимости:

Признак делимости на $2$

Число делится на $2$ тогда и только тогда, когда его последняя цифра ноль или делится на $2$, то есть является чётной.

Признак делимости на $3$

Число делится на $3$ тогда и только тогда, когда сумма его цифр делится на 3.

Признак делимости на $4$

Число делится на $4$ тогда и только тогда, когда число из двух последних его цифр нули или делится на $4$.

Признак делимости на $5$

Число делится на $5$ тогда и только тогда, когда последняя цифра делится на $5$ (то есть равна $0$ или $5$).

Признак делимости на $6$

Число делится на $6$ тогда и только тогда, когда оно делится на $2$ и на $3$.

Признак делимости на $7$

Число делится на $7$ тогда и только тогда, когда результат вычитания удвоенной последней цифры из этого числа без последней цифры делится на $7$ (например, $217$ делится на $7$, так как $21 — (2 · 7) = 7$ делится на $7$).

Признак делимости на $8$

Число делится на $8$ тогда и только тогда, когда три его последние цифры — нули или образуют число, которое делится на $8$.

Признак делимости на $9$

Число делится на $9$ тогда и только тогда, когда сумма его цифр делится на $9$.

Признак делимости на $10$

Число делится на $10$ тогда и только тогда, когда оно оканчивается на ноль.

Признак делимости на $11$

Число делится на $11$ тогда и только тогда, когда сумма цифр с чередующимися знаками делится на $11$ (то есть $182919$ делится на $11$, так как $1 — 8 + 2 — 9 + 1 — 9 = -22$ делится на $11$). Следствие факта, что все числа вида $10^n$ при делении на $11$ дают в остатке $(-1)^n$.

Признак делимости на $12$

Число делится на $12$ тогда и только тогда, когда оно делится на $3$ и на $4$.

Признак делимости на $13$

Число делится на $13$ тогда и только тогда, когда число его десятков, сложенное с учетверённым числом единиц, кратно $13$ (например, $949$ делится на $13$, так как $94 + (4 · 9) = 130$ делится на $13$).

Признак делимости на $14$

Число делится на $14$ тогда и только тогда, когда оно делится на $2$ и на $7$.

Признак делимости на $15$

Число делится на $15$ тогда и только тогда, когда оно делится на $3$ и на $5.$

Признак делимости на $17$

Число делится на $17$ тогда и только тогда, когда разность между числом его десятков и упятеренным числом единиц, кратно $17.$

Признак делимости на $19$

Число делится на $19$ тогда и только тогда, когда число его десятков, сложенное с удвоенным числом единиц, кратно $19$ (например, $646$ делится на $19$, так как $64 + (6 · 2) = 76$ делится на $19$).

Четность и нечетность чисел

1. Число называется четным, если оно делится нацело на $2$. Если $а$ четное число, то его вид можно записать $a=2n$.
2. Число называется нечетным, если оно не делится нацело на $2$. Если $а$ нечетное число, то его вид можно записать $a=2n+1$.
3. Сумма любого количества четных слагаемых четна.
4. Сумма четного количества нечетных слагаемых – четное число.
5. Сумма нечетного количества нечетных слагаемых – нечетное число.
6. Если в произведении все множители нечетные числа, то произведение – нечетное число.
7. Если в произведении попадется хотя бы одно четное число, то в результате умножения получится четное число.

Простые и взаимно простые числа

Простые числа – это целые числа, большие единицы, которые имеют только два положительных делителя, а именно самих себя и $1$.

Взаимно простые числа – это числа, которые не имеют общих делителей, кроме единицы. Например, числа $15$ и $4$ взаимно просты, так как их общий делитель равен $1$.

Свойства взаимно простых чисел.

Пусть $а$ и $b$ – взаимно простые числа, тогда для них справедливы следующие высказывания.

1. Если некоторое число делится на $а$ и $b$, то оно делится и на их произведение $аb$.
2. Если произведение $ас$ делится на $b$, то с делится на $b$.
3. Если целые числа $а$ и $b$ взаимно просты, то их сумма $(а + b)$ и произведение $(а·b)$ так же являются взаимно простыми числами.
4. Если целые числа $а$ и $b$ взаимно просты, то НОД (наименьший общий делитель) из суммы $(а + b)$ или разности ($а — b$) равен $1$ или $2$.
5. Любые два последовательных натуральных числа взаимно просты.
6. Если целые числа $а$ и $b$ взаимно просты, то НОД $(а + b$ или $a^2-ab+b^2)$ равен $1$ или $3$.

Числовые свойства степеней

1. Точный квадрат целого числа не может оканчиваться цифрами $2, 3, 7, 8,$ а также нечётным количеством нулей.
2. Квадрат натурального числа либо делится на $4$, либо при делении на $8$ даёт остаток $1$.
3. Квадрат натурального числа либо делится на $9$, либо при делении на $3$ даёт остаток $1$.
4. Разность квадратов двух целых чисел одинаковой четности делится на $4$.
5. При делении на $3$ куб целого числа и само число дают одинаковые остатки $(0,1,2)$.
6. При делении на $9$ куб целого числа дает в остатке $0,1$ или $8$.
7. При делении на $4$ куб целого числа дает в остатке $0,1$ или $3$.
8. Число $m^5$ оканчивается на ту же цифру, что и число $m$.

Среднее арифметическое чисел

Среднее арифметическое нескольких величин — это отношение суммы величин к их количеству.

Чтобы вычислить среднее арифметическое нескольких чисел, нужно взять сумму этих чисел и разделить все на количество слагаемых. Частное и будет средним арифметическим этих чисел.

Среднее геометрическое чисел

Чтобы найти среднее геометрическое чисел надо:

1. Перемножить все числа
2. Из полученного выражения в п.1 надо извлечь корень, степени, равной количеству элементов ряда.

Факториал

Факториал числа — это произведение натуральных чисел от $1$ до самого числа (включая данное число). Обозначается знаком (!).

$n!=1·2·3·….·n$

Факториал нуля равен единице $0!=1$

Последовательности

Последовательность чисел – это набор чисел, в котором каждому числу можно присвоить некоторый номер, причем каждому номеру соответствует единственное число данного набора. Номер числа – это всегда натуральное число, нумерация номеров начинается с единицы. Число с номером $n$ (то есть $n$ — ый член последовательности) обычно обозначается $a_n$.

Большинство последовательностей можно задать аналитическим способом.

Последовательность задана аналитически, если указана формула ее $n$ – го члена. Например, $a_n=4n+3$. В данной формуле указав конкретное число $n$, нетрудно найти член последовательности с соответствующим номером. Если номер $n=5$, то подставим $5$ в формулу последовательности, получим числовое выражение, вычислив которое получим член последовательности с соответствующим номером. $a_5=4·5+3=23$

Прогрессии

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

$а_1$ — первый член арифметической прогрессии

$d$ — разность между последующим и предыдущим членом прогрессии

$d=a_(n+1)-a_n$

$a_n$ — член арифметической прогрессии, стоящий на $n$-ом месте

$n$ — номер места для членов арифметической прогрессии

$S_n$ — сумма первых n членов арифметической прогрессии

Формула, для нахождения n-ого члена прогрессии:

$a_n=a_1+d(n-1)$

Формула суммы первых n членов арифметической прогрессии:

$S_n={(a_1+a_n)·n}/{2}$

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

$b_1$ — первый член геометрической прогрессии

$q$ — знаменатель геометрической прогрессии, показывает во сколько раз последующее число больше предыдущего.

$q={b_{n+1}}/{b_n}$

$b_n$ — $n$-ый член геометрической прогрессии

$S_n$ — сумма первых $n$ членов геометрической прогрессии

Формула, для нахождения $n$-ого члена прогрессии:

$b_n=b_1·q^{n-1}$

Формула суммы первых n членов арифметической прогрессии:

$S_n={b_1·(q^n-1)}/{q-1},q≠1$

Факториалом натурального числа n (обозначается n!) называется произведение всех натуральных чисел от 1 до n. Например, 4! = 1 · 2 · 3 · 4 = 24.

Дано целое положительное число A. Необходимо найти минимальное натуральное K, для которого K! ≥ A.

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

Ниже эта программа для Вашего удобства приведена на пяти языках программирования.

Бейсик	Python
DIM A, K, F AS INTEGER INPUT A K = 0 F = 1 WHILE F <= A     K = K + 1     F = F * K WEND PRINT K END	a = int(input()) k = 0 f = 1 while f <= a:     k += 1     f *= k print(k)
Паскаль	Алгоритмический язык
var a, k, f: integer; begin     read(a);     k := 0;     f := 1;     while f <= a do begin         k := k + 1;         f := f * k     end;     writeln(k) end.	алг нач     цел a, k, f     ввод a     k := 0     f := 1     нц пока f <= a         k := k + 1         f := f * k     кц     вывод k кон
Си++
#include using namespace std; int main(){     int a, k, f;     cin >> a;     k = 0;     f = 1;     while (f <= a) {         ++k;         f *= k;     }     cout << k;     return 0; }

Последовательно выполните следующее.

1.  Напишите, что выведет эта программа при вводе A = 6.

2.  Назовите минимальное A, большее 10, при котором программа выведет неверный ответ.

3.  Найдите в программе все ошибки (их может быть одна или несколько).

Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде.

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

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

ЕГЭ №18 (19). Теория чисел. Рекуррентная задача – самая сложная задача мартовского статграда 2021

ЕГЭ 18 (19) – это задачи на теорию чисел, на свойства чисел, на последовательности. Что такое рекуррентная последовательность?

Сейчас узнаете…

Последовательности чисел нам хорошо известны ещё с 8 – 9 класса. Например, прогрессии – арифметическая и геометрическая.

На ЕГЭ довольно часто попадаются задачи на последовательности – как на стандартные прогрессии, так и на необычные – у каждой из которых какая-то своя формула. И формулы у таких последовательностей обычно рекуррентные – то есть такие, когда каждое следующее число вычисляется через значения каких-то предыдущих.

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

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

Например, говорят, что Фибоначчи свою последовательность придумал, наблюдая за размножением кроликов: первые 2 месяца жизни кролик просто растёт, а потом начинает каждый месяц рожать нового кролика (в среднем).

Сколько будет кроликов через полгода? Через год? В задаче 18 (19 из последнего статграда нам попалась как раз такая последовательность.

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