РЕШУ ОЛИМП, математика: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 0 № 6712 Добавить в вариант

Найдите и докажите явное выражение (в терминах известных операций на целых числах) для функции g(m, n), определенной для целых неотрицательных аргументов следующим образом: g(m, n)  =   если m  =  0 то n иначе g(m − 1, m × n).

Спрятать решение

Решение.

Сначала давайте «поэкспериментируем» и вычислим «символически» значение функции g для какого-либо небольшого значения m, например, вычислим $g левая круглая скобка 3, n правая круглая скобка :$

$g левая круглая скобка 3, n правая круглая скобка =g левая круглая скобка левая круглая скобка 3 минус 1 правая круглая скобка , левая круглая скобка 3 \times n правая круглая скобка правая круглая скобка =g левая круглая скобка 2, левая круглая скобка 3 \times n правая круглая скобка правая круглая скобка =g левая круглая скобка левая круглая скобка 2 минус 1 правая круглая скобка , левая круглая скобка 2 \times левая круглая скобка 3 \times n правая круглая скобка правая круглая скобка правая круглая скобка =$
$=g левая круглая скобка 1, , левая круглая скобка 2 \times 3 \times n правая круглая скобка правая круглая скобка =g левая круглая скобка левая круглая скобка 1 минус 1 правая круглая скобка , левая круглая скобка 1 \times левая круглая скобка 2 \times 3 \times n правая круглая скобка правая круглая скобка правая круглая скобка =$
$=g левая круглая скобка 0, левая круглая скобка 1 \times 2 \times 3 \times n правая круглая скобка правая круглая скобка = левая круглая скобка 1 \times 2 \times 3 \times n правая круглая скобка = левая круглая скобка 1 \times 2 \times 3 правая круглая скобка \times n= левая круглая скобка 3 ! правая круглая скобка \times n.$

Поэтому, естественно, возникает гипотеза, что $g левая круглая скобка m, n правая круглая скобка = левая круглая скобка m ! правая круглая скобка \times n$ для всех целых неотрицательных m и n. Докажем индукцией по $m больше или равно 0,$ что $g левая круглая скобка m, n правая круглая скобка = левая круглая скобка m ! правая круглая скобка \times n$ для любого целого $n больше или равно 0.$

База индукции $m=0:$ $g левая круглая скобка 0, n правая круглая скобка =n= левая круглая скобка 0! правая круглая скобка \times n$ для любого $n больше или равно 0.$

Индукционная гипотеза: пусть для всех $k принадлежит левая квадратная скобка 0 . . m правая квадратная скобка$ верно, что $g левая круглая скобка k, n правая круглая скобка = левая круглая скобка k! правая круглая скобка \times n$ для любого целого $n больше или равно 0.$

Шаг индукции:

$g левая круглая скобка левая круглая скобка m плюс 1 правая круглая скобка , n правая круглая скобка =g левая круглая скобка m, левая круглая скобка левая круглая скобка m плюс 1 правая круглая скобка \times n правая круглая скобка правая круглая скобка = левая круглая скобка m ! правая круглая скобка \times левая круглая скобка левая круглая скобка m плюс 1 правая круглая скобка \times n правая круглая скобка = левая круглая скобка левая круглая скобка m плюс 1 правая круглая скобка ! правая круглая скобка \times n.$

Ответ: в соответствии с принципом математической индукции $g левая круглая скобка m, n правая круглая скобка = левая круглая скобка m ! правая круглая скобка \times n$ для всех целых неотрицательных m и n.

Олимпиада Университета Иннополис Innopolis Open, 10 класс, 2 тур (заключительный), 2020 год

Классификатор: Методы алгебры. Метод математической индукции

Спрятать решение · Помощь