Докажите, что если  (m, 10) = 1,  то существует репьюнит E_n, делящийся на m. Будет ли их бесконечно много?

   Решение

Петя приобрёл в магазине вычислительный автомат, который за 5 к. умножает любое введённое в него число на 3, а за 2 к. прибавляет к любому числу 4. Петя хочет, начиная с единицы, которую можно ввести бесплатно, набрать на автомате число 1981 и затратить наименьшую сумму денег. Во сколько обойдутся ему вычисления? А что будет, если он захочет набрать число 1982?

   Решение

Темы:    [ Классическая комбинаторика (прочее) ] [ Сочетания и размещения ] [ Мощность множества. Взаимно-однозначные отображения ]

Сложность: 4 Классы: 10,11

Прислать комментарий

Условие

Улитка должна проползти вдоль линий клетчатой бумаги путь длины 2n, начав и кончив свой путь в данном узле.
Доказать, что число различных её маршрутов равно  

Решение

При любом таком маршруте число ходов вверх равно числу ходов вниз, а число ходов вправо равно числу ходов влево. Выпишем на один лист бумаги номера ходов, ведущих вправо или вверх, а на другой — номера ходов, ведущих влево или вверх. На каждом листе будет выписано ровно n номеров. По каждой паре таких наборов маршрут однозначно восстанавливается (например, если номер входит в оба набора, то ему соответствует ход вверх). Этот маршрут замкнутый, поскольку число ходов вправо равно числу ходов влево (оба они дополняют число ходов вверх до n), а число ходов вверх равно числу ходов вниз (вычитая из общего числа 2n ходов число ходов вправо, влево и вверх, мы, с одной стороны, получим число ходов вниз, а с другой стороны, – число ходов вверх). Итак, число маршрутов равно числу пар наборов из n номеров, то есть  

Источники и прецеденты использования