Размещения. Если в алфавите N букв, то количество слов (осмысленных или бессмысленных) из k различных букв равно N^k = N(N-1)(N-2)...(N-k+1) – всего k сомножителей. Например, в алфавите A,B,C есть 3·2 двухбуквенных слова: AB, AC, BA, BC, CA, CB.

1. a) Сколько есть трехзначных чисел без 0 в записи, где все цифры различны?
b) Сколько есть трехзначных чисел без 0 в записи, где не более двух различны цифр?

2. a) В заезде участвуют 8 лошадей. Зритель может за заполнить карточку с предсказанием, кто какое место займет. Кто угадает первые 4 места, выиграет миллион. Сколько карточек должен заполнить Петр, чтобы точно получить выиграть миллион?
b) Конюх – друг Петра – точно знает, какие 4 лошади придут первыми, и в каком порядке, но говорить об этом ему запрещено. Петр, однако, может вслух высказывать предположения, а эксперт подмигиванием подтверждает или опровергает его. Предположения могут быть сложными, например «Лошадь A обгонит ровно одну из лошадей B,C,D» За какое минимальное число предположений Петр сможет узнать, как ему правильно заполнить карточку. 

3. а) Среди 6 монет две фальшивых – одна тяжелее, другая легче настоящих. Можно ли наверняка найти обе фальшивые монеты и выяснить, которая из них легче за 3 взвешивания на чашечных весах без гирь?
b) Среди 4 монет две фальшивых – одна тяжелее, другая легче настоящих. За какое наименьшее число взвешиваний на чашечных весах без гирь можно наверняка найти обе фальшивые монеты и выяснить, которая из них легче?

Перестановки. N предметов можно разложить в ряд N(N-1)…2·1 способами. Сокращенно это произведение чисел от N до 1 обозначается N! и называется N-факториал. Например, 4!=4·3·2·1=24.

4. Вычислите 1!, 2!, 3!, 5!, 6! и 7!.

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

6. Найдите две последние цифры числа 11!, не находя самого числа.

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

8. Вычислите a) 2004!/2003! b) 100!/98!

9. Есть 4 камня разного веса и чашечные весы без гирь. За какое наименьшее число взвешиваний их можно разложить в порядке возрастания весов?

10. Что больше: 100! или 2100? Почему?

11. В забеге участвуют 7 тараканов. Зритель может за 200 крон заполнить карточку с предсказанием, кто какое место займет. Если он угадает, то получит приз миллион крон. Выгодна ли эта игра зрителю, если он про этих тараканов ничего не знает?

12* а) В стране 4 города, каждая пара соединена отдельной дорогой. Злой колдун хочет сделать все дороги с односторонним движением так, что если можно добраться из города A в город B, то обратно из B в A нельзя будет добраться даже через другие города. Сколькими способами колдун может так заколдовать дороги?
b) Тот же вопрос – про 10 городов.

13* Есть 4 гири. Известно, что их веса 101, 102, 103 и 104 г, но какая сколько весит - неизвестно. За какое наименьшее число взвешиваний на чашечных весах без гирь можно выяснить веса всех гирь?

14* Среди 5 монет – две фальшивых. Настоящие весят 10 г каждая, фальшивые – 9 г и 11 г. За какое наименьшее число взвешиваний на чашечных весах без гирь можно наверняка найти обе фальшивые монеты и выяснить их вес?