Тема : расчет количества возможных вариантов (комбинаторика) icon

Тема : расчет количества возможных вариантов (комбинаторика)



НазваниеТема : расчет количества возможных вариантов (комбинаторика)
Дата конвертации06.10.2012
Размер127.72 Kb.
ТипДокументы
источник

© К. Поляков, 2009-2010

A7к (базовый уровень, время – 2 мин)


Тема: расчет количества возможных вариантов (комбинаторика)1

Что нужно знать:

  • если на каждом шаге известно количество возможных вариантов выбора, то для вычисления общего количества вариантов нужно все эти числа перемножить;
    например, в двузначном числе мы можем выбрать первую цифру 9 способами (она не может быть нулем), а вторую – 10 способами, поэтому всего есть 9·10=90 двузначных чисел

  • если мы разбили все нужные нам комбинации на несколько групп (не имеющих общих элементов!) и подсчитали количество вариантов в каждой группе, то для вычисления общего количества вариантов нужно все эти числа сложить;
    например, есть 9·10=90 трехзначных чисел, оканчивающихся на 5, и 9·10=90 трехзначных чисел, оканчивающихся на 2, поэтому 90+90=180 трехзначных чисел оканчиваются на 2 или на 5

  • если в предыдущем случае группы имеют общие элементы, их количество нужно вычесть из полученной суммы;
    например, есть 9·10=90 трехзначных чисел, оканчивающихся на 5, и 10·10=100 трехзначных чисел, начинающихся на 5; в обе группы входят числа, которые начинаются и заканчиваются на 5, их всего 10 штук, поэтому количество чисел, которые начинаются или заканчиваются на 5, равно 90+100-10=180.

^ Что не мешает знать:

  • если есть n различных элементов, число их различных перестановок равно факториалу числа n, то есть произведению всех натуральных чисел от 1 до n:

n! = 1·2·3·…·(n-1)·n

например, три объекта (А, Б и В) можно переставить 6 способами (3!=1·2·3=6):

(А, Б, В), (А, В, Б), (Б, А, В), (Б, В, А), (В, А, Б) и (В, Б, А)

  • если нужно выбрать m элементов из n (где nm) и две комбинации, состоящие из одних и тех же элементов, расположенных в разном порядке, считаются различными, число таких комбинаций (они называются размещениями) равно



например, в соревновании пяти спортсменов призовые места (первые три) могут распределиться 60 способами, поскольку



  • если нужно выбрать m элементов из n (где nm) и порядок их расположения не играет роли, число таких комбинаций (они называются сочетаниями) равно



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

.
^

Пример задания:


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

1) 125 2) 250 3) 500 4) 625

Решение:

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




    x

    ?

    ?

    ?

    Вариантов

    4










  2. предположим, что первая цифра выбрана; независимо от нее на втором месте может стоять любая из четных цифр – 0, 2, 4, 6 или 8, всего 5 вариантов:




    x

    y

    ?

    ?

    Вариантов

    4

    5







  3. аналогично находим, что последние две цифры также могут быть выбраны 5-ю способами каждая, независимо друг от друга и от других цифр (первой и второй):




    x

    y

    z

    w

    Вариантов

    4

    5

    5

    5

  4. общее количество комбинаций равно произведению

4·5·5·5 = 500

  1. таким образом, правильный ответ – 3.

Возможные ловушки и проблемы:

    • легко забыть, что первая цифра не может быть нулем, при этом мы получим неверный ответ 625 (ответ 4)
^

Еще пример задания:


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

1) 3528 2) 4536 3) 5040 4) 9000

Решение:

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




    x

    ?

    ?

    ?

    Вариантов

    9










  2. предположим, что первая цифра x выбрана; на втором месте может стоять любая цифра y, кроме x, всего 9 вариантов (ноль тоже может быть!):




    x

    y

    ?

    ?

    Вариантов

    9

    9







  3. третья цифра z может быть любой, кроме тех двух, которые уже стоят на первых двух местах, всего 8 вариантов:




    x

    y

    z

    ?

    Вариантов

    9

    9

    8




  4. наконец, четвертая цифра может быть любой из 7 оставшихся (не равных x, y и z)




    x

    y

    z

    w

    Вариантов

    9

    9

    8

    7

  5. общее количество комбинаций равно произведению

9·9·8·7 = 4536

  1. таким образом, правильный ответ – 2.

Возможные ловушки и проблемы:

    • легко забыть, что первая цифра не может быть нулем, при этом мы получим неверный ответ 10·9·8·7=5040 (ответ 3)

    • нужно учитывать, что выбор каждой следующей цифры зависит от предыдущих, иначе мы получим неверный ответ 9·10·10·10=9000 (ответ 4)
^

Еще пример задания:


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

1) 212 2) 225 3) 243 4) 280

Решение:

  1. возможны три случая: 99, 99 и 99, где жирная точка обозначает некоторую цифру, не равную 9

  2. для каждого из этих случаев нужно подсчитать количество вариантов и эти числа сложить

  3. в варианте 99 две последних цифры могут быть любыми, кроме девятки (по 9 вариантов выбора):






9

9

x

y

Вариантов

1

1

9

9

поэтому всего получаем 1·1·9·9 = 81 вариант

  1. в варианте 99 первая цифра не может быть нулем и девяткой (остается 8 вариантов), а последняя может быть любой, кроме девятки (9 вариантов):




x

9

9

y

Вариантов

8

1

1

9

поэтому всего получаем 8·1·1·9 = 72 варианта

  1. в варианте 99 первая цифра не может быть нулем и девяткой (остается 8 вариантов), а последняя может быть любой, кроме девятки (9 вариантов):




x

x

9

9

Вариантов

8

9

1

1

поэтому всего получаем 8·9·1·1 = 72 варианта

  1. общее количество вариантов равно сумме

81 + 72 + 72 = 225

  1. таким образом, правильный ответ – 2.

Возможные ловушки и проблемы:

    • можно забыть, что первая цифра не может быть нулем, при этом мы получим неверный ответ 81+81+81=243 (ответ 3)

    • можно забыть, что числа x и y не могут быть равны 9, при этом мы получим неверный ответ 100+90+90=280 (ответ 4)
^

Еще пример задания:


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

1) 446 2) 516 3) 576 4) 640

Решение:

  1. обозначим первую цифру через x, она не может быть нулем, поэтому возможно 9 вариантов выбора




    x

    ?

    ?

    ?

    Вариантов

    9










  2. другую цифру обозначим через y, ее тоже можно выбирать 9 способами (она может быть нулем, но не может быть равна x)

  3. нужно отдельно рассмотреть три случая: xy, xxy и xxx; для каждого из этих случаев нужно подсчитать количество вариантов и эти числа сложить

  4. в варианте xy две последних цифры могут быть (независимо друг от друга) выбраны равными x или y (по 2 варианта выбора):




x

y

x или y

x или y

Вариантов

9

9

2

2

поэтому всего получаем 9·9·2·2 = 324 варианта

  1. в варианте xxy последняя цифра может быть равна только x или y (2 варианта):




x

x

y

x или y

Вариантов

9

1

9

2

поэтому всего получаем 9·1·9·2 = 162 варианта

  1. в варианте xxx последняя цифра может быть любой (10 вариантов):




x

x

x

x или y

Вариантов

9

1

1

10

поэтому всего получаем 9·1·1·10 = 90 вариантов

  1. общее количество вариантов равно сумме

324 + 162 + 90 = 576

  1. таким образом, правильный ответ – 3.

Возможные ловушки и проблемы:

    • можно забыть, что первая цифра не может быть нулем, при этом мы получим неверный ответ 360+180+100=640 (ответ 4)
^

Еще пример задания:


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

1) 226 2) 369 3) 500 4) 625

Решение (вариант 1):

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

  2. в случае 5 три последних цифры могут быть любыми нечетными (по 5 независимых вариантов выбора):






5

x

y

z

Вариантов

1

5

5

5

поэтому всего получаем 1·5·5·5 = 125 вариантов

  1. с первого взгляда для случая 5 ситуация та же самая, но это не так; дело в том, что часть этих вариантов (с пятеркой на первом месте) уже вошла в первую группу 5, поэтому второй раз их учитывать не нужно; это значит, что на первом месте может быть одна из 4-х цифр – 1, 3, 7 или 9:




x

5

y

z

Вариантов

4

1

5

5

всего получаем 4·1·5·5 = 100 вариантов

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




x

y

5

z

Вариантов

4

4

1

5

всего получаем 4·4·1·5 = 80 вариантов

  1. для 5 аналогично получаем




x

y

z

5

Вариантов

4

4

4

1

всего получаем 4·4·4·1 = 64 варианта

  1. общее количество вариантов

125 + 100 + 80 + 64 = 369 вариантов

  1. таким образом, правильный ответ – 2.

Возможные ловушки и проблемы:

    • можно забыть отбросить повторяющиеся варианты при рассмотрении групп 5, 5 и 5; при этом мы получим неверный ответ 125+125+125+125=500 (ответ 3)

Решение (вариант 2):

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

  2. общее число чисел, состоящих только из нечетных цифр, находим аналогично первой рассмотренной задаче; учитывая, что среди них нет нуля, получаем

5·5·5·5 = 625 вариантов

  1. теперь аналогично найдем количество чисел, состоящих только из цифр 1, 3, 7 и 9 (без пятерки); поскольку на каждом из 4-х мест может стоять одна из 4-х цифр, получаем

4·4·4·4 = 256 вариантов

  1. нужный нам результат – это разница

625 – 256 = 369 вариантов

  1. таким образом, правильный ответ – 2.
^

Еще пример задания:


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

1) 10 2) 20 3) 30 4) 60

Решение (вариант 1):

  1. будем рассуждать так: сначала Виктор выбирает одну (любую) книгу, затем – вторую (из оставшихся), затем – третью

  2. у него есть 5 разных способов выбрать первую книгу, затем – 4 разных способа выбрать вторую книгу (поскольку ту, что он выбрал сначала, уже нет смысла брать снова), и 3 способа выбрать третью книгу:




книга 1

книга 2

книга 3

Вариантов

5

4

3

всего получаем 5·4·3 = 60 вариантов

  1. проблема состоит в том, что среди этих 60 вариантов есть повторяющиеся: предположим, что книги имеют номера от 1 до 5, тогда наборы книг (1, 2, 3) и (3, 2, 1) – одинаковые (это разные перестановки чисел 1, 2 и 3)

  2. подсчитаем число перестановок трех чисел; на первом месте может стоять любое из 3-х чисел (3 варианта), на втором месте – любое из двух оставшихся (2 варианта), на третьем месте – только одно оставшееся число:




книга 1

книга 2

книга 3

Вариантов

3

2

1

всего получаем 3·2·1 = 6 вариантов

  1. это означает, что каждое сочетание было подсчитано 6 раз в п. 2, поэтому различных сочетаний книг – в 6 раз меньше, то есть 60 / 6 = 10

  2. таким образом, правильный ответ – 1.

Возможные ловушки и проблемы:

    • можно забыть, что среди сочетаний, подсчитанных в п. 2, есть одинаковые (неверный ответ 60)

    • можно неверно подсчитать количество повторяющихся комбинаций, разделив 60 на количество выбранных книг (неверный ответ 20)

Решение (вариант 2, формулы комбинаторики):

  1. нам нужно выбрать 3 объекта из 5, причем порядок выбора здесь не важен – нам нужны разные сочетания

  2. зная формулу для вычисления количества сочетаний, сразу находим (при m = 3 и n = 5)

.

  1. таким образом, правильный ответ – 1.

Возможные проблемы:

    • нужно помнить формулы комбинаторики



^

Задачи для тренировки:


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

1) 216 2) 224 3) 234 4) 243

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

1) 96 2) 120 3) 500 4) 625

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

1) 3289 2) 4536 3) 8375 4) 9000

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

1) 900 2) 1000 3) 1800 4) 2000

  1. Сколько существует четырехзначных чисел, не превышающих 3000, в которых ровно две цифры «3»?

1) 36 2) 54 3) 81 4) 162

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

1) 780 2) 800 3) 1560 4) 1600

  1. В вазе лежат яблоко, груша, персик и абрикос. Кате разрешили выбрать два каких-то фрукта. Сколько у Кати вариантов выбора?

1) 6 2) 12 3) 16 4) 24

  1. У Паши есть 6 воздушных шариков разного цвета. Три из них он хочет подарить Маше. Сколькими способами он может это сделать?

1) 6 2) 12 3) 20 4) 60

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

1) 50 2) 90 3) 100 4) 120

  1. Цепочка из трех бусин формируется по следующему правилу: На первом месте в цепочке стоит одна из бусин А, Б, В. На втором – одна из бусин Б, В, Г. На третьем месте – одна из бусин А, В, Г, не стоящая в цепочке на первом или втором месте. Сколько всего есть таких цепочек?

1) 9 2) 16 3) 21 4) 27



1 В демонстрационных вариантах заданий такого типа нет. Однако репетиционные экзамены в различных центрах тестирования (в том числе при ВУЗах) говорят о том, что они могут быть.




Похожие:

Тема : расчет количества возможных вариантов (комбинаторика) iconЗадача на расчет количества теплоты, которое потребуется для нагревания тела. Билет №2
Измерение силы тока, проходящего через резистор, и напряжения на нем, расчет сопротивления проволочного резистора
Тема : расчет количества возможных вариантов (комбинаторика) iconЗадача на расчёт количества теплоты, которое потребуется для нагревания тела. Билет 2
Измерение силы тока, проходящего через резистор, и напряжения на нём, расчёт сопротивления проволочного резистора
Тема : расчет количества возможных вариантов (комбинаторика) iconЗачет по теме "Антропогенез"
Чтобы получить одну оценку, вам нужно ответить на все десять вопросов из трех возможных вариантов (1-10; 11-20; 21-30)
Тема : расчет количества возможных вариантов (комбинаторика) iconКомбинаторика. Перестановки. Размещения. Сочетания
Решать такие задачи помогает комбинаторика раздел математики, в котором исследуются и решаются задачи выбора элементов из исходного...
Тема : расчет количества возможных вариантов (комбинаторика) iconРекомендации по разработке образовательной программы школы ■ М. Пильдес, А. Бакурадзе
Существуют различные подходы к назначению, струк­туре и технологиям разработки программы. Один из возможных вариантов вы найдете...
Тема : расчет количества возможных вариантов (комбинаторика) iconЗадачи для школьной олимпиады по физике 2009/2010 учебный год
Один из возможных вариантов решения. Для определения d используем метод рядов. Приборы: линейка, иголка, мензурка
Тема : расчет количества возможных вариантов (комбинаторика) iconТема: Алфавитный подход к определению количества информации
Цель: рассмотреть способ определения количества информации с помощью алфавитного подхода
Тема : расчет количества возможных вариантов (комбинаторика) iconУрок. Программная обработка данных на компьютере Ход урока Организационный момент. Устная работа. Ответить на вопросы
Как определяется количество информации в зависимости от количества возможных событий?
Тема : расчет количества возможных вариантов (комбинаторика) iconТема: Определение количества информации с использованием вероятностного подхода
Цель: познакомить учащихся с формулой Шеннона и вероятностным подходом к определению количества информации
Тема : расчет количества возможных вариантов (комбинаторика) iconТема: Кодирование и обработка графической информации
Запишите формулу связи количества цветов в палитре и количества информации, необходимое для кодирования точки
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©lib2.podelise.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы