Combinatorics I - 23 Feb 2010
Sergey Sobolev
Номера с возрастающим порядком цифр
На сайте кружка
http://mathcircle.csmath.org
на странице задания есть pdf-файл для печати. Кроме этого, в
Google Docs задание разложено в папки учеников (папка доступна,
если зайти в своём аккаунте). Пишите там решение после условия
задачи (рекомендуем тёмно-синий цвет) и вставляйте, где нужно,
рисунки. Пожалуйста, отмечайте неточности, опечатки и т.п.
Источник задания -- задание ВЗМШ, написанное Н.Б.Васильевым и
В.Л.Гутенмахером по материалам бесед И.М.Гельфанда со
школьниками (1971-72 г.). В своём изложении я сделал акцент на
номера, а не на числа, и дописал "про системы счисления".
Решения принимаются до 23 февраля. Некоторые из задач 1-14
решены, в таких случаях требуется разобрать решение, переписать
непонятные места так, чтобы всё стало понятно, сделать
недостающие рисунки. Поэкспериментируйте с более наглядными
случаями, например, когда номера делаются в системе счисления с
основанием 5 (цифры 0, 1, 2, 3, 4). Если сделать рисунок с
компьютером трудно или нет времени, можно сделать его от руки,
отсканировать или сфотографировать и вставить в текст. Задачи
15-21 "с буквой n" требуют усилий другого характера, и старшим
участникам кружка (13-14 лет) нужно оставить на эти задачи
больше половины всего времени. Ну а тем, кто помладше,
достаточно решить 2-3 из этих задач.
Если какие-то задачи были решены раньше, нужно отметить
зачтённые задачи и решать оставшиеся.
Далее приложен извлечённый из задания список задач (без
обсуждения, подсказок, рисунков).
Задачи
1. Сколько двузначных номеров с различными цифрами?
2. Сколько двузначных номеров с возрастающим порядком цифр
(первая цифра меньше второй)?
3. На окружности 10 точек. Сколько отрезков с концами в этих
точках?
4. Сколько трехзначных номеров с различными цифрами?
5. Пусть a, b и c -- три различные цифры. Сколько различных
трехзначных номеров можно составить из них?
6. Сколько трехзначных номеров с возрастающим порядком цифр
(первая цифра меньше второй, вторая меньше третьей)?
7. На окружности отмечено 10 точек. Сколько имеется
треугольников с вершинами в этих точках?
8. Докажите, что семизначных номеров с возрастающим порядком
цифр столько же, сколько и трехзначных номеров с возрастающим
порядком цифр.
9. Сколько существует четырехзначных номеров, все цифры которых
различны?
10. Пусть a, b, c, d -- четыре различные цифры. Сколько можно
составить из них различных четырехзначных номеров?
11. Сколько четырехзначных номеров с возрастающим порядком
цифр?
12. На окружности выбрано 10 точек. Сколько существует выпуклых
четырехугольников с вершинами в этих точках?
13. Докажите, что шестизначных номеров с возрастающим порядком
цифр столько же, сколько и четырёхзначных номеров с
возрастающим порядком цифр.
14. Сколько существует k-значных номеров с возрастающим
порядком цифр? Здесь k = 0, 1, 2, ..., 10. Ответ представьте
таблицей.
Номера в системе счисления с основанием n
Мы не будем вычислять в системе счисления с основанием n,
номера в ней для нас будут просто слова, которые можно
упорядочивать так же, как фамилии по алфавиту.
В этой системе счисления имеется n цифр, мы занумеруем их по
порядку (однозначными) номерами 0, 1, ..., n-1 и будем работать
с ними вместо цифр. Из них мы будем делать двузначные,
трёхзначные и т.д. номера.
15. Сформулируйте обобщения задач про двузначные номера и дайте
краткие решения и ответы.
16. Посчитав двумя способами количество двузначных номеров с
возрастающим порядком цифр, получите тождество
1 + 2 + 3 + ... + (n-1) = n(n-1)/2
Заменив здесь n на n+1, получаем формулу для n-го треугольного
числа:
T_n = 1 + 2 + 3 + ... + n = n(n+1)/2
17. Сформулируйте обобщения задач про трёхзначные номера и
дайте краткие решения и ответы.
18. Посчитав двумя способами количество трёхзначных номеров с
возрастающим порядком цифр, получите тождество
T_1 + T_2 + ... + T_{n-2} = n(n-1)(n-2)/6
Заменив здесь n на n+2, получаем формулу для n-го
пирамидального числа:
P_n = T_1 + T_2 + ... + T_n = n(n+1)(n+2)/6
19. Докажите формулу для суммы квадратов первых n натуральных
чисел:
1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6
20. Сколько имеется трёхзначных номеров, в которых третья цифра
больше первых двух? А в которых третья цифра наибольшая (т.е.
не меньше первых двух)?
21. Докажите, что количество k-значных номеров с возрастающим
порядком цифр в системе счисления с основанием n равно
n(n-1)...(n-k+1)/k!,
где k! = 1*2*...*k (факториал числа k). Это число называется
числом сочетаний из n по k.