10.27 Задачи
1. A и B и еще 8 человек стоят в очереди. Сколькими способами можно расположить людей в очереди, чтобы A и B были отделены друг от друга тремя лицами?
2. Сколько четырехзначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5 , если:
а) цифры не повторяются;
б) цифры могут повторяться;
в) используются только нечетные цифры и могут повторяться;
г) должны получиться только нечетные числа и цифры могут повторяться.
Ответ: а) 5 5 4 3=300; б) 5 6 3 = 1080; в) 3 4 ; г) 5 6 6 3 = 540.
3. В классе изучается 10 предметов. Сколькими способами можно составить расписание на понедельник, если в понедельник должно быть 6 уроков и все разные?
Ответ: 
4. На одной прямой взято m точек, на параллельной ей прямой n точек. Сколько треугольников с вершинами в этих точках можно получить?
Ответ: 
5. Сколько есть пятизначных чисел, которые читаются одинаково справа налево и слева направо, например, 67876.
Ответ: 9 10 10 = 900.
6. Сколько разных делителей (включая 1 и само число) имеет число 3 5 5 4 ?
7. В прямоугольной матрице A =
8. В комнате n лампочек. Сколько разных способов освещения комнаты, при которых горит:
а) ровно k лампочек (k n);
б) хотя бы одна лампочка.
Ответ: а) Cn k ; б) Cn 1 + Cn 2 + . + Cn n = 2 n — 1
9. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра больше предыдущей?
10. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра меньше предыдущей?
11. Имеются p белых и q черных шаров. Сколькими способами их можно выложить в ряд, чтобы никакие 2 черных шара не лежали рядом (q p + 1)?
Ответ: 
.
12. Имеется p разных книг в красных переплетах и q разных книг в синих переплетах (q p + 1). Сколькими способами их можно расставить в ряд, чтобы никакие две книги в синих переплетах не стояли рядом?
Ответ: 
p!q!.
13. Сколькими способами можно упорядочить <1, 2, . n>чисел так, чтобы числа 1, 2, 3 стояли рядом в порядке возрастания ?
14. На собрании должны выступить 4 докладчика: A, B, C и D, причем B не может выступить раньше A. Сколькими способами можно установить их очередность.
Ответ: 12 = 3! + 2 2 +2.
15.Сколькими способами m + n + s предметов можно распределить на 3 группы, чтобы в одной группе было m предметов, в другой — n, в третьей — s предметов.
Ответ: 
16. Сколько целых неотрицательных решений имеет уравнение
Ответ: 
.
17. Найти число векторов = (1 2 . n), координаты которых удовлетворяют условиям:
Ответ: 1) 2 n ; 2) k n ; 3) k1 k2 . kn ; 4) 
.
18. Каково число матриц
1) строки могут повторяться;
2) строки попарно различны.
Ответ: 1) 2 m n ; 2) 
.
19. Дано m предметов одного сорта и n другого. Найти число выборок, составленных из r элементов одного сорта и s другого.
Ответ: 
.
20. Сколькими способами число n можно представить в виде суммы k натуральных слагаемых (представления, различающиеся лишь порядком слагаемых считаются разными).
Ответ: 
.
Сколько имеется четырехзначных чисел у которых каждая следующая цифра больше предыдущей
Загрузка. Пожалуйста,
подождите.
Профиль
Группа: Участник
Сообщений: 80
Регистрация: 5.12.2006
Где: Беларусь, Минск
Репутация: 1
Всего: 2
Профиль
Группа: Участник
Сообщений: 126
Регистрация: 22.5.2006
Репутация: 1
Всего: 3
| Код |
| Dim mas(8999) As Integer For i = 0 To 8999 mas(i) = 1000 + i Next i For i = 0 To 8999 st = mas(i) odin = Mid(st, 1, 1) dva = Mid(st, 2, 1) tri = Mid(st, 3, 1) chetire = Mid(st, 4, 1) If chetire < tri And tri < dva And dva < odin Then chisel = chisel + 1 End If Next i Label1.Caption = chisel |
А вот объяснение с другого форума
| Цитата |
| [b]Интересно всё таки в какой школе задают такие задания? И какие мутанты способны решить его без компутера. |
Это сообщение отредактировал(а) DimkraS — 6.5.2007, 12:36
Профиль
Группа: Участник
Сообщений: 55
Регистрация: 2.2.2007
Репутация: 2
Всего: 2
| Цитата |
| А решается задачка, как оказалось, очень просто: Поскольку оговаривается, что каждая следующая цифра строго больше (или меньше) предыдущей, то все цифры в числе различны. Не так ли? Т.е. нас интересуют наборы из четырёх различных цифр. Идём дальше. Какой попало порядок выбранных цифр нас не устроит, но, главное выбрать, а уж расставить мы их сами сможем по возрастанию или убыванию, это ведь можно сделать только одним способом. Короче, нас интересует, сколькими способами можно выбрать четыре циферки, из которых мы будем составлять число. Но в первом случае мы будем выбирать из 9 цифр, т.к. число с нуля не начинается, а дальше цифры только возрастают. А во-втором случае будем выбирать из 10 цифр, т.к. уже может участвовать и ноль. Таким образом, в первом случае нас интересуют неупорядоченные наборы по 4 цифры из 9, а во втором случае неупорядоченные наборы по 4 цифры из 10. Имеем дело с сочетаниями, вот и все. Т.е. для случая а: C<subscript>9</subscript><superscript>4</superscript>. У меня получилось 126. Во втором случае C<subscript>10</subscript><superscript>4</superscript>. Вроде 210. |
Фу, зачем так много болтовни? Все гораздо проще. Цифр 10, а мест под них 4. Стало быть 10С4=210. Вот и ответ. Одно действие. Почти устная задача.
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!
- Название темы должно отражать её суть! (Не следует добавлять туда слова «помогите», «срочно» и т.п.)
- При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
- В названии темы не нужно указывать происхождение задачи (например «школьная задача», «задача из учебника» и т.п.), не нужно указывать ее сложность («простая задача», «легкий вопрос» и т.п.). Все это можно писать в тексте самой задачи.
- Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
- Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку «Код»). Не забывайте выбирать при этом соответствующий язык.
- Помните: один топик — один вопрос!
- В данном разделе запрещено поднимать темы , т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
- Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
- Если вопрос решён, то воспользуйтесь ссылкой «Пометить как решённый», которая находится под кнопками создания темы или специальным флажком при ответе.
Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
[ Время генерации скрипта: 0.1135 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Сколько имеется четырехзначных чисел, у которых каждая следующая цифра меньше предыдущей? Больше предыдущей?
1. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра меньше предыдущей? Больше предыдущей?
если можно то с объяснением) а то препод — зверюга, ничего не объясняет толком, только ждет когда мы сами решим.
Проверить, что каждая следующая цифра трехзначного числа на единицу больше предыдущей
верно ли, что каждая следующая цифра натурального трехзначного числа на единицу больше предыдущей?
Сколько существует комбинаций чисел, таких, что каждая его цифра меньше, либо равна предыдущей
Сколько существует комбинаций чисел, таких, что каждая его цифра меньше, либо равна предыдущей? При.
Перестановки: каждая следующая получается из предыдущей перестановкой двух соседних чисел
Расскажите пожалуйста как это сделать в СИ#: Напечатать все перестановки чисел 1. n, чтобы.
Сообщение от Doomsday
Сообщение от Doomsday
Сколько четырехзначных чисел можно составить из цифр от 0 до 5, если каждая цифра может повторяться?
Сколько четырехзначных чисел можно составить из цифр от 0 до 5, если каждая цифра может.
Создать массив из 7 кнопок, каждая новая кнопка должна быть больше предыдущей
Создать массив из 7 кнопок, каждая новая кнапка должна быть больше предыдущей на 10 по ширине и на.
Сколько существует двузначных чисел, у которых первая цифра меньше второй?
1) Сколько существует двузначных чисел, у которых первая цифра меньше второй? решил, но не.
Сколько существует пятизначных десятичных чисел, в каждом из которых первая цифра меньше последней
4) Сколько существует пятизначных десятичных чисел, в каждом из которых первая цифра меньше.
10. Элементы комбинаторики
10.1 Пусть есть некоторое конечное множество элементов U =
Комбинаторные задачи связаны с подсчетом числа выборок объема r из n элементов, где выборки подчиняются определенным условиям, т. е. выбор производится по какому-нибудь принципу. Подсчет числа выборок основывается на двух правилах теории множеств.
10.2 Принцип суммы: если card A = m, card B = n и AÇB = Æ , то card A È B = m+n. На комбинаторном языке это означает: если объект A можно выбрать m способами, объект B другими n способами и их одновременный выбор невозможен, то выбор “A или B” может быть осуществлен m+n способами.
10.3 Принцип произведения: если card A = m, card B = n, то card (A´B) = m´n. На комбинаторном языке это означает: если объект A может быть выбран m способами, при любом выборе A объект B может быть выбран n способами, то выбор “A и B” может быть осуществлен m×n способами.
10.4 Пример. A = <10 различных шоколадок>, B = <5 различных пачек печенья>. Выбор “A или B” означает, что выбирается что-то одно и способов выбора в это случае будет 15. Выбор “A и B” означает, что выбирается 1 шоколадка и 1 пачка печенья и различных вариантов для такого выбора будет 50.
10.5 Пример. Бросают 2 игральные кости. Сколькими способами они могут выпасть так, что на каждой кости выпадет четное число очков либо на каждой кости выпадет нечетное число очков?
Пусть m — число возможностей для выпадения четного числа на одной кости, n — число возможностей для выпадения нечетного числа. Здесь m = n = 3. По правилу произведения количество выпадения четных чисел, равно как и нечетных, равно 9. По правилу суммы количество возможностей для выпадения двух четных или двух нечетных чисел будет 18.
Рассмотрим основные способы формирования выборок.
10.6 Определение. Выборка называется Упорядоченной, если в ней задан порядок следования элементов. Если порядок следования элементов несущественен, то выборка называется неупорядоченной.
Из определения следует, две упорядоченные выборки, состоящие из одних и тех же элементов, но расположенных в разном порядке, являются различными.
10.7 Перестановки. Упорядоченные выборки объемом n из n элементов, где все элементы различны, называются Перестановками из n элементов. Число перестановок из n элементов обозначается Pn.
10.8 Теорема. P = n!
Доказательство проводится по индукции. Очевидно, если n = 1, то перестановка только одна и P1 = 1!. Пусть для n = k теорема верна и Pk = k!, покажем, что она тогда верна и для n = k + 1. Рассмотрим (k+1)-ый элемент, будем считать его объектом A, который можно выбрать k+1 способами. Тогда объект B — упорядоченная выборка из оставшихся k элементов по k. B соответствии с индуктивным предположением объект B можно выбрать k! способами. По принципу произведения выбор “A и B” можно осуществить k!´(k + 1) = (k + 1)! способами. А совместный выбор “A и B” есть упорядоченная выборка из k + 1 элементов по k + 1.
10.9 Пример. Сколько существует способов, чтобы расположить на полке 10 различных книг? Ответ: 10 !
Можно рассуждать иначе. Выбираем первый элемент, это можно сделать n способами. Затем выбираем второй элемент, это можно сделать (n — 1) способами. По правилу произведения упорядоченный выбор двух элементов можно осуществить n´(n — 1) способами. Затем выбираем третий элемент, для его выбора останется n — 2 возможности, последний элемент можно выбрать единственным способом. Мы вновь приходим к формуле: n(n — 1)( n — r) . 1.
10.10 Размещения. Упорядоченные выборки объемом m из n элементов (m < n), где все элементы различны, называются Размещениями. Число размещений из n элементов по m обозначается .
10.11 Теорема. =
Доказательство. Обозначим x = . Тогда оставшиеся (n — m) элементов можно упорядочить (n — m) ! способами. По принципу произведения, если объект A можно выбрать x способами, объект B (n — m)! способами, то совместный выбор “A и B” можно осуществить x ×(n — m)! способами, но выбор “A и B” есть перестановка и Pn = n! Отсюда x = =
Рассуждая иначе: первый элемент выбираем n способами, второй — (n — 1) способами и т. д. , m — ый элемент выбираем (n — m + 1) способом. По принципу произведения вновь имеем: n(n — 1). (n — m +1), что совпадает с .
10.12 Пример. Группа из 15 человек выиграла 3 различные книги. Сколькими способами можно распределить эти книги среди группы?
Имеем = 15 ×14 ×13 = 2730.
10.13 Сочетания. Неупорядоченные выборки объемом m из n элементов (m < n) называются Сочетаниями. Их число обозначается .
10.14 Теорема.
Доказательство. Очевидно, Действительно, объект A — неупорядоченная выборка из n элементов по m, их число . После того, как эти m элементов отобраны, их можно упорядочить m! способами (в роли объекта B выступает “ порядок “ в выборке). Совместный выбор “A и B“ — упорядоченная выборка.
10.15 Пример. Группа из 15 человек выиграла 3 одинаковые книги. Сколькими способами можно распределить эти книги?
Сочетания, размещения и перестановки являлись подмножествами исходного множества. Рассмотрим выборки, которые не являются подмножествами.
10.16 Размещения с повторениями. Упорядоченные выборки объемом m из n элементов, где элементы могут повторяться, называются размещениями с повторениями. Их число обозначается (n).
10.17 Теорема. (n) = nm.
Доказательство. Первый элемент может быть выбран n способами, второй элемент также может быть выбран n способами и так далее, m — тый элемент также может быть выбран n способами. По принципу произведения получаем nm.
10.18 Пример. Кодовый замок состоит из четырех разрядов, в каждом разряде независимо от других могут быть выбраны цифры от 0 до 9. Сколько возможных комбинаций?
Здесь n = 10, m = 4 и ответом будет 104.
10.19 Пример. Рассмотрим вектор длины m, каждая координата которого может принимать всего 2 значения: 0 или 1. Сколько будет таких векторов?
Это есть выборка объемом m из двух элементов. Ответ : 2m
10.20 Перестановки с повторениями. Пусть имеется n элементов, среди которых k1 элементов первого типа, k2 элементов второго типа и т. д., ks элементов s-того типа, причем k1 + k2 + . + ks = n. Упорядоченные выборки из таких n элементов по n называются Перестановками с повторениями, их число обозначается Сn(k1, k2, . ks). Числа Сn(k1, k2, . ks) называются полиномиальными коэффициентами.
10.21 Теорема. Сn(k1, . ks) =
Доказательство проведем по индукции по s, то есть по числу типов элементов. При s = 1 утверждение становится тривиальным: k1 = n, все элементы одного типа и Сn(n) = 1. В качестве базы индукции возьмем s = 2, n = k1 + k2. В этом случаем перестановки с повторениями превращаются в сочетания из n элементов по k1 (или k 2): выбираем k1 место, куда помещаем элементы первого типа.
Пусть формула верна для s = m, т. е. n = k1 + . + km и
Докажем, что она верна для s = m + 1 (n = k1 +. + km + km+1). В этом случае перестановку с повторениями можно рассматривать как совместный выбор двух объектов: объект A — выбор k m + 1 места для элементов (m + 1)-го типа; объект B — перестановка с повторениями из (n — km+1) элементов. Объект A можно выбрать способом, B — (k1, . km) способами. По принципу произведения
И мы получили требуемую формулу.
Замечание. Числа называются биноминальными коэффициентами. Из этой формулы следует, что
10.22 Пример. Сколько различных слов можно получить, переставляя буквы в слове “математика”?
Решение. Буква “а” входит 3 раза (k 1= 3), буква “м” — 2 раза (k2 = 2), “т”-2 раза ( k3 = 2), буквы “е”,”к”,”и” входят по одному разу, отсюда k3 = k4 = k5 = 1.
С10 (3, 2, 2, 1, 1, 1) = =151200.
10.23 Сочетания с повторениями. Пусть имеется n типов элементов, каждый тип содержит не менее m одинаковых элементов. Неупорядоченная выборка объемом m из имеющихся элементов (их число ³ m´n ) называется Сочетанием с повторениями. Число сочетаний с повторениями обозначается (n).
10.24 Теорема. (n) = .
Доказательство. Пусть в выборку вошло m1 элементов первого типа, m2 элементов вторго типа, . mn — n — ного типа. Причем каждое 0 £ mi £ m и m1 + m2 + . + mn = m. Сопоставим этой выборке вектор следующего вида:
Очевидно, между множеством неупорядоченных выборок с повторениями и множеством векторов
Число векторов равно числу способов, которыми m единиц можно поставить на m + n — 1мест, а это будет .
10.25 Пример. В кондитерской имеется 7 видов пирожных. Покупатель берет 4 пирожных. Сколькими способами он может это сделать? (Предполагается, что пирожных каждого вида ³ 4).
Число способов будет
10.26 Пример. Пусть V =
10.27 Задачи
1. A и B и еще 8 человек стоят в очереди. Сколькими способами можно расположить людей в очереди, чтобы A и B были отделены друг от друга тремя лицами?
2. Сколько четырехзначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5 , если:
А) цифры не повторяются;
Б) цифры могут повторяться;
В) используются только нечетные цифры и могут повторяться;
Г) должны получиться только нечетные числа и цифры могут повторяться.
Ответ: а) 5 × 5 × 4 × 3=300; б) 5 × 63 = 1080; в) 34; г) 5 × 6 × 6 × 3 = 540.
3. В классе изучается 10 предметов. Сколькими способами можно составить расписание на понедельник, если в понедельник должно быть 6 уроков и все разные?
4. На одной прямой взято m точек, на параллельной ей прямой n точек. Сколько треугольников с вершинами в этих точках можно получить?
5. Сколько есть пятизначных чисел, которые читаются одинаково справа налево и слева направо, например, 67876.
Ответ: 9 × 10 × 10 = 900.
6. Сколько разных делителей (включая 1 и само число) имеет число 35 × 54?
7. В прямоугольной матрице A =
8. В комнате n лампочек. Сколько разных способов освещения комнаты, при которых горит:
А) ровно k лампочек (k < n);
Б) хотя бы одна лампочка.
Ответ: а) Cnk ; б) Cn1 + Cn2 + . + Cnn = 2n — 1
9. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра больше предыдущей?
10. Сколько имеется четырехзначных чисел, у которых каждая следующая цифра меньше предыдущей?
Ответ: С104 = 210.
11. Имеются p белых и q черных шаров. Сколькими способами их можно выложить в ряд, чтобы никакие 2 черных шара не лежали рядом (q £ p + 1)?
12. Имеется p разных книг в красных переплетах и q разных книг в синих переплетах (q £ p + 1). Сколькими способами их можно расставить в ряд, чтобы никакие две книги в синих переплетах не стояли рядом?
13. Сколькими способами можно упорядочить <1, 2, . n>чисел так, чтобы числа 1, 2, 3 стояли рядом в порядке возрастания?
14. На собрании должны выступить 4 докладчика: A, B, C и D, причем B не может выступить раньше A. Сколькими способами можно установить их очередность.
Ответ: 12 = 3! + 2× 2 +2.
15.Сколькими способами m + n + s предметов можно распределить на 3 группы, чтобы в одной группе было m предметов, в другой — n, в третьей — s предметов.
16. Сколько целых неотрицательных решений имеет уравнение
x1 + x2 + . + xm = n
17. Найти число векторов a = (a1 a2 . an), координаты которых удовлетворяют условиям:
4) ai Î <0, 1>и a1 + a2 + . + an = r.
Ответ: 1) 2n ; 2) kn ; 3) k1 k2 . kn ; 4) .
18. Каково число матриц
1) строки могут повторяться;
2) строки попарно различны.
19. Дано m предметов одного сорта и n другого. Найти число выборок, составленных из r элементов одного сорта и s другого.
20. Сколькими способами число n можно представить в виде суммы k натуральных слагаемых (представления, различающиеся лишь порядком слагаемых считаются разными).