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

Научный форум dxdy

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

Как я считал: $A_5^3 -5 -16$ , где $5$ — числа вида <img decoding= x$» />, $16$ — числа вида хх$

Где ошибка? Помогите пожалуйста.

Если формулировка «все цифры различны» выливается в результат $A_5^3$ , то зачем из него потом вычитать числа вида <img decoding= x$» />? Их там и быть-то не может.

Последний раз редактировалось Quadrelle 06.04.2015, 14:17, всего редактировалось 1 раз.

Хорошо, тогда получаем так: $A_5^3 -16$ , где $16$ — числа вида $хх

Последний раз редактировалось nnosipov 06.04.2015, 14:19, всего редактировалось 1 раз.

Опять неверно, причём по той же причине.

— Пн апр 06, 2015 18:19:37 —

числа вида хх

Руководство по решению дискретки

в) остался один случай, когда цифры, кратные двум, занимают три первых места, а последнее место занимает цифра, кратная трём: 3·4 2 ·3 = 144.

Сложим полученные частные результаты: 81 + 108 + 144 = 333.

Пример 2. Десятизначное двоичное число b (условимся называть его b -числом) разделили на две части: число b 1 шестизначное ( b 1 -число) b 2 – четырёхзначное ( b 2 -число). Сколько существует двоичных b -чисел, для каждого из которых выполняется условие: в числе b 1 столько же единиц, сколько и в числе b 2 ?

Решение. Всего необходимо рассмотреть пять частных случаев:

а) в обоих числах нет единиц. Такое десятизначное b -число существует только одно. Оно состоит из последовательности десяти нулей;

б) в обоих числах b 1 и b 2 содержится по одной единице. Существует 6 b 1 -чисел, каждое из которых представляет собой шестизначное двоичное число, содержащее одну единицу и пять ну-

лей: 000001, 000010, 000100, 001000, 010000, 100000. Для b 2 существует четыре числа: 0001, 0010, 0100, 1000. По правилу произведения: количество искомых b -чисел равно 6·4 = 24;

в) в числах b 1 и b 2 содержится точно по две единицы. Существует C 62 15 b 1 -чисел, где каждое из них представляет собой двоичное шестизначное число, содержащее две единицы и че-

тыре нуля. Существует C 42 6 b 2 -чисел, т.е. четырёхзначных чисел, содержащих две единицы и два нуля каждое. По правилу произведения искомое количество b -чисел равно 15·6 = 90;

г) в числах b 1 и b 2 содержится точно по три единицы. Рассуждая, как и в предыдущих случаях, находим, что искомое количество b -чисел равно

C 6 3 C 4 3 20 4 80;

д) в числах b 1 и b 2 содержится точно по четыре единицы. Тогда C 64 C 44 15 1 15. Просуммируем все эти частные результаты: 1 + 24 + 90 + 80 + 15 = 210.

Пример 3. Сколько существует чётных трёхзначных чисел пятеричной системы счисления, если числа могут начинаться с нуля, и в каждом числе возможны повторы цифр? Например: 012, 224, 110 и др.

Решение. В последовательности натуральных чисел, представленных в пятеричной системе, чётные и нечётные числа чередуются, начиная с числа 000, которое является чётным, и кончая числом 444, которое также является чётным. Следовательно, чётных пятеричных чисел на единицу больше, чем нечётных. По формуле числа размещений с повторениями находим, что всего существует 5 3 = 125 трёхзначных пятеричных чисел. Отсюда вывод: существует 62 нечётных трёхзначных пятеричных числа и 63 – чётных.

Пример 4. Из цифр множества <1, 2, 3, 4, 5, 6, 7>выбирают четыре цифры и записывают ими семизначное число. Сколько возможно таких чисел, если одна из выбранных четырёх цифр входит в семизначное число точно четыре раза, а все остальные – по одному разу? Например, если выбрали цифры 2, 3, 6, 7 то искомыми являются числа 2222376, 7727637, 6663267 и т.д.

Решение. Пусть выбранными являются цифры 1, 2, 3, 4. Рассмотрим частные случаи.

Сначала предположим, что повторяется цифра 1. Одно из чисел имеет вид 1111234. Все остальные числа с повтором цифры 1 могут быть получены перестановкой цифр этого числа. Количество таких чисел находим по формуле числа перестановок с повторениями

Очевидно, что столько же существует чисел, если повторяется цифра 2, а также 3 и 4. Следовательно, из цифр 1, 2, 3, 4 можно образовать 840 семизначных чисел, в записи которых одна из цифр повторяется точно 4 раза.

Если выберем другие четыре цифры, то получим ещё 840 чисел. Из семи цифр четыре можно выбрать

способами. Таким образом, всего искомых чисел существует 840·35 = 29400.

Пример 5. Сколько существует 15-значных двоичных чисел, в каждом из которых содержится точно четыре единицы, причём эти единицы нигде рядом не стоят? Числа могут начинаться с нуля.

Решение. В 15-значном двоичном числе, содержащем четыре единицы, имеется 11 нулей. Запишем эти нули в ряд, поставив между нулями, а также слева и справа от них по одной точке:

Если выберем какие-либо четыре точки и заменим их единицами, то получим 15-значное число, в котором не будет рядом стоящих единиц. Всего точек 12. Следовательно, выбрать четыре из них можно

способами. Столько же существует искомых чисел.

Известно, что существует 2925 n -значных двоичных чисел, в каждом из которых содержится точно три единицы (и соответственно n – 3 нулей). Числа могут начинаться с нуля. Требуется найти n . Решение. Запишем условие с применением формулы числа сочетаний (без повторений) из n элементов по 3:

Сократим дробь на ( n – 3)!:

Умножив левую и правую части на 6, получаем уравнение:

Это уравнение третьей степени. Его можно решить с применением формул Кардано. Однако в данном случае решение можно найти другим, более простым путём. Левая часть полученного уравнения – это произведение трёх натуральных чисел, из которых большее число отличается от среднего на единицу и среднее отличается от меньшего также на единицу, т.е. они идут непосредственно один за другим в последовательности натурального ряда. Следовательно, задача сводится к тому, чтобы правую часть представить в виде произведения трёх таких чисел.

Разложим число 2925 на простые множители: 2925 = 3 3 5 5 13.

Тогда уравнение примет вид

n ( n 1)( n 2) 2 3 3 3 5 5 13.

Сгруппируем простые множители так, чтобы получились три числа с вышеприведенными свой-

2 3 3 3 5 513 (3 3 3) (2 13) (5 5) 27 26 25.

Подставим этот результат в уравнение: n ( n 1)( n 2) 27 26 25. Отсюда непосредственно следует, что n = 27.

Пример 7. Из алфавита выбрали семь различных букв и каждую из них записали на отдельной карточке. Из карточек составляют 4-буквенные слова. Сколько существует таких слов, буквы в которых идут в алфавитном порядке?

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

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

Р 1 Р 2 = , то | Р 1 Р 2 | = | Р 1 | + | Р 2 |,

т.е. если элемент первого множества может быть выбран | Р 1 | способами, а элемент второго множества – | Р 2 | способами, то выбор «либо элемент множества Р 1 , либо элемент множества Р 2 » может быть осуществлен | Р 1 | + | Р 2 | способами.

Пример 8. В тарелке 7 яблок и 5 груш. Сколькими способами можно выбрать один плод? Решение. Если Р 1 – множество яблок, Р 2 – множество груш, то:

| Р 1 | + | Р 2 | = 7 + 5 = 12.

Если же Р 1 Р 2 Ø (т.е. множества Р 1 и Р 2 имеют общие элементы) то правило суммы записывается в виде более сложной формулы:

| Р 1 Р 2 | = | Р 1 | + | Р 2 | – | Р 1 Р 2 |.

Пример 9 . Даны множества: Р 1 = <1, 2, 4, 7, 9>; Р 2 = < 1, 4, 5, 6, 8>.

Сколько элементов во множестве Р 1 Р 2 ?

Решение. По правилу суммы | Р 1 Р 2 | = 5 + 5 – 2 = 8.

В случае трех множеств правило суммы записывается в виде

| Р 1 Р 2 Р 3 | = | Р 1 Р 2 | + | Р 3 | – |( Р 1 Р 2 ) Р 3 | = = | Р 1 | + | Р 2 | – | Р 1 Р 2 | + | Р 3 | – | Р 1 Р 3 Р 2 Р 3 | =

= | Р 1 | + | Р 2 | – | Р 1 Р 2 | + | Р 3 | – (| Р 1 Р 3 | + | Р 2 Р 3 | – | Р 1 Р 2 Р 3 |)=

= | Р 1 | + | Р 2 | + | Р 3 | – | Р 1 Р 2 | – | Р 1 Р 3 | – | Р 2 Р 3 | + | Р 1 Р 2 Р 3 |.

Для четырех множеств получаем аналогично:

| Р 1 Р 2 Р 3 Р 4 | = | Р 1 | + | Р 2 | + | Р 3 | + | Р 4 | –

– | Р 1 Р 2 | – | Р 1 Р 3 | – | Р 1 Р 4 | – | Р 2 Р 3 | – | Р 2 Р 4 | – | Р 3 Р 4 | +

+ | Р 1 Р 2 Р 3 | + | Р 1 Р 2 Р 4 | + | Р 1 Р 3 Р 4 | + | Р 2 Р 3 Р 4 | –

– | Р 1 Р 2 Р 3 Р 4 |.

Пример 10. Из 100 студентов английский язык знают 28 человек, немецкий – 30, французский – 42, английский и немецкий – 8, английский и французский – 10, немецкий и французский – 5, все три языка знают 3 человека. Сколько студентов не знают ни одного из этих трех иностран-

ных языков [21, с. 15]?

| Р 1 | – число студентов, знающих английский язык;

| Р 2 | – число студентов, знающих немецкий язык;

| Р 3 | – число студентов, знающих французский язык.

| Р 1 Р 2 | = 8 – число студентов, знающих два языка – английский и немецкий; | Р 1 Р 3 | = 10 – число студентов, знающих два языка – английский и французский; | Р 2 Р 3 | = 5 – число студентов, знающих два языка – немецкий и французский;

| Р 1 Р 2 Р 3 | = 3 – число студентов, знающих три языка. По правилу суммы:

| Р 1 Р 2 Р 3 | = 28 + 30 + 42 – 8 – 10 – 5 + 3 = 80.

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

13.2. Комбинаторика в теории вероятностей

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

Например, пусть монету подбрасывают два раза. Вероятность того, что оба раза выпадет герб, равна 1/4. Здесь знаменатель равен 4. Столько всего существует исходов эксперимента, когда монету подбрасывают два раза: ГГ, ГЦ, ЦГ, ЦЦ, где буквой Г обозначено падение монеты гербом вверх, а Ц – падение монеты цифрой вверх. Числитель равен 1, так как существует только один исход эксперимента, когда оба раза монета упадёт гербом вверх.

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

Если события независимы, то вероятность их произведения определяется по формуле

P ( A 1 · A 2 ) = P ( A 1 )· P ( A 2 ),

а в случае n случайных событий A 1 , A 2 , A 3 ,…, A n :

P ( A 1 · A 2 · A 3 ·,…, · A n ) = P ( A 1 )· P ( A 2 )· P ( A 3 ) ·…· P ( A n ).

Если же события A 1 и A 2 являются зависимыми, то говорят об условной вероятности:

P ( A 1 · A 2 ) = P ( A 1 )· P ( A 2 / A 1 ),

где P ( A 2 / A 1 ) – условная вероятность, т.е. вероятность события A 2 при условии, что событие A 1 состоялось.

Например, пусть в урне находятся 4 белых шара и 3 чёрных. Наугад вынимают один шар (событие A 1 ), записывают его цвет, шар возвращают в урну и снова наугад вынимают один шар (событие A 2 ). Какова вероятность того, что в обоих случаях будут вынуты только чёрные шары?

Эти события независимы. Вероятность того, что первый шар будет чёрным, равна: P ( A 1 ) = 3/7. Вероятность того, что и второй шар будет чёрным, также равна P ( A 2 ) = 3/7. Следовательно, искомая вероятность равна P ( A 1 A 2 ) = 9/49.

Изменим условие эксперимента: из урны вынимают один шар (событие A 1 ), после чего не возвращая его в урну, наугад вынимают второй шар (событие A 2 ). Какова вероятность того, что оба вынутых шара будут чёрными? Очевидно, что при первом извлечении вероятность вынуть чёрный шар равна P ( A 1 ) =3/7. Так как шар не возвращается в урну, то теперь в ней не 7 шаров, а только 6. Кроме того, состоялось событие: вынут чёрный шар. Следовательно, в урне осталось два чёрных шара и условная вероятность вынуть чёрный шар равна: P ( A 2 / A 1 ),) = 2/6. После сокращения P ( A 2 / A 1 ),) = 1/3. Искомая вероятность равна:

P ( A 1 )· P ( A 2 / A 1 ) = 7 3 7

Рассмотрим ещё ряд примеров.

Пример 1. Игральную кость подбрасывают 2 раза. Найти вероятность того, что второе выпавшее число будет в 2 раза больше первого (грани пронумерованы: 1, 2, 3, 4, 5, 6).

Решение. Первый бросок может закончиться шестью исходами, и второй шестью. Следовательно, число всех исходов равно 36. Это знаменатель искомой вероятности. Числитель равен 3. Это исходы 1 и 2, 2 и 4, 3 и 6. Искомая вероятность равна 1/12.

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

Решение. Знаменатель искомой вероятности равен 90 – столько существует двузначных десятичных чисел, не начинающихся с нуля. Это числа 10, 11, 12, . 99.

Определим числитель. В двоично-десятичном коде каждая десятичная цифра заменяется тетрадой – четырехзначным двоичным кодом. Например: 35| 10 = 00110101| 2-10 , где 35| 10 – десятичная запись числа 35, а 00110101| 2-10 – двоично-десятичное изображение того же числа. Здесь десятичная цифра 3 заменена тетрадой 0011, а цифра 5 – тетрадой 0101.

Если две единицы находятся в первой тетраде, то во второй их нет (так как во всём коде должно быть 2 единицы). Всего существует шесть тетрад с двумя единицами. Четырьмя из них кодируются цифры 3, 5, 6 и 9, следовательно, существует четыре двоично-десятичных кода, окан-

чивающихся четырьмя нулями: 00110000, 01010000, 01100000, 10010000.

Если в первой тетраде одна единица, то и во второй одна. Это тетрады вида: 0001, 0010, 0100, 1000. Из них можно составить 16 двоично-десятичных кодов:

00010001, 00100001, 01000001, 10000001, 00010010, 00100010, 01000010, 10000010, 00010100, 00100100, 01000100, 10000100, 00011000, 00101000, 01001000, 10001000.

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

Таким образом, всего существует 20 двоично-десятичных кодов, в каждом из которых точно две единицы. Искомая вероятность равна 20/90. После сокращения: 2/9.

Пример 3. Некто задумал двузначное десятичное число N (с нуля двузначные числа не начинается). Найти вероятность того, что в задуманном числе нет ни одной цифры 5. Повторы цифр возможны.

Решение. Существует 90 двузначных десятичных чисел, не начинающихся с нуля. Среди них 18 чисел содержат хотя бы одну цифру 5. Это числа:

15, 25, 35, 45, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 65, 75, 85, 95.

Следовательно, всего существует 90 – 18 = 72 числа, в каждом из которых нет ни одной цифры 5. Таким образом, искомая вероятность равна: 72/90. После сокращения: 4/5.

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

Решение. Пронумеруем мишени цифрами троичной системы 0, 1, 2, и закодируем исходы выбора мишеней пятизначными троичными числами, где каждому троичному разряду соответствует один из стрелков. Например, код 10021 обозначает: первый стрелок выбрал первую мишень, второй и третий – нулевую, четвертый – вторую, пятый – первую. Всего существует 3 5 = 243 пятизначных троичных кодов, которые могут начинаться с нуля. Столько же существует и вариантов выбора мишеней. Это знаменатель искомой вероятности.

Определим числитель. Существует только три варианта выбора мишеней, когда поражена одна мишень из трех. Это коды: 00000 – все пули попали в нулевую мишень, 11111 – все пули попали в первую мишень, 22222 – все пули попали во вторую мишень. Искомая вероятность равна 3/243. После сокращения на 3 получаем 1/81.

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

Как и в предыдущем примере пронумеруем мишени: 0, 1, 2, 3, и закодируем все варианты выбора мишеней 5-значными числами четверичной системы счисления. Всего существует 4 5 = 1024 пятизначных четверичных кодов, которые могут начинаться с нуля. Столько же существует и вариантов выбора мишеней. Это знаменатель искомой вероятности.

Определим числитель. Сначала предположим, что будут поражены мишени с номерами 0 и 1. Этому соответствуют пятизначные двоичные коды, в каждом из которых содержится хотя бы один нуль и хотя бы одна единица. Число таких кодов равно 30, так как всего существует 32 пятизначных двоичных числа, среди которых код 00000 не содержит единиц, а код 11111 не содержит нулей, а все остальные коды содержат и нули и единицы. Если предположить, что поражёнными будут другие две мишени, то и в этом случае возможно 30 вариантов выбора мишеней. Все-