Задание 1 "Номера"

1.1. Сколько  двузначных  номеров  с  различными цифрами? Какую
часть их составляют номера с возрастающим порядком цифр (первая
цифра меньше второй)? Попробуйте найти различные  подходы к от-
ветам на эти вопросы.

1.2. Сколько имеется трехзначных номеров с различными цифрами?

1.3. Сколько трехзначных номеров с различными  цифрами, в кото-
рых наибольшая цифра стоит в конце номера?

1.4. Сколько  трехзначных  номеров с возрастающим порядком цифр
(первая цифра меньше второй, вторая меньше третьей)?

1.5. На окружности отмечено 10 точек. Сколько имеется треуголь-
ников с вершинами в этих точках?

1.6. Сформулируйте и решите обобщения этих задач: например, но-
мера могут  быть k-значными, может использоваться система счис-
ления с основанием n и т.д.

1.7. Напишите  программу на том языке программирования, который
Вы учите, генерирующую  все k-значные номера   а) с  различными
цифрами,  б) с  возрастающим  порядком цифр. Можно использовать
систему счисления с  основанием n  и проверять работу программы
при небольших n, от 3 до 10.

   Не обязательно отвечать на все вопросы. Например, шестиклас-
снику достаточно  разобраться  с пунктом 1.1. Сначала приведите
ответ, потом решение. Программу для  пункта  1.7  приводить  не
нужно, если Вы справились с  этим  пунктом  (он больше подходит
студентам 1-2 курсов), то напишите, чем пользовались, какую ис-
пользовали идею.

                           О задачах

   Задачи  1.1,  1.2,  1.4  и 1.5 впервые были  использованы  в
1971-72 учебном году на только что организованном тогда трехго-
дичном потоке Заочной Математической Школы при МГУ. Они вошли в
задание, подготовленное  В.Л.Гутенмахером по материалам  лекций
И.М.Гельфанда. Задание несколько раз совершенствовалось, задача
1.3 вошла в него позднее, возможно,  при участии Н.Б.Васильева.
В этом задании не было слов "размещение" или  "сочетание", но в
нем учили 8-классников принципам подсчета, разбиению  множества
на классы. k-значные номера (1.6) тоже там были.

   Пункт 1.7 рассчитан на старшеклассников, уже изучающих прог-
раммирование, или на студентов 1-2 курсов.  Полезным может быть
учебник  А.Шеня  "Программирование: теоремы  и  задачи",  издан
МЦНМО (Московским Центром  непрерывного математического образо-
вания) в 1995 г., рекомендован тогда как учебное пособие Минис-
терством образования  Российской  Федерации. Может быть взят по
ftp:
            ftp://mccme.ru/users/shen/progbook/

(С) С.И.Соболев, 1999-2002