Математический кружок

при школе Сони Ковалевской

(руководитель Александр Шаповалов)

Занятие 3. Размещения, факториалы, перестановки

 Обсуждение

Размещения. Если в алфавите 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(N-1)…2·1 способами (читается 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! или 2¹⁰⁰? Почему?    Ответ

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

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

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

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