Пропонуємо вашій увазі конкурсну задачу з турніру юних математиків.
Завдання
Числовий автомат «ТЮМ-XVI» може виконувати такі операції з натуральними числами:
- відняти від даного числа число 3 (якщо воно більше, ніж 3);
- помножити дане число на 3;
- розділити дане число на 3 (якщо воно ділиться на 3 без залишку).
Дайте відповідь на такі запитання:
- За яку найменшу кількість операцій можна з числа 82 отримати число 81?
- За яку найменшу кількість операцій можна з числа 81 отримати число 82?
- Аналогічне питання щодо отримання числа $$n$$ з числа $$m.$$
Рішення
Перш ніж відповідати на запитання завдання, складемо формули для знаходження попереднього натурального числа з наступного і наступного з попереднього, використовуючи властивості числового автомата «ТЮМ-XVI».
(1) Формула знаходження попереднього натурального числа з наступного
Нехай $$n$$ – натуральне число, $$n+1$$ – наступне за ним натуральне число.
Якщо ми помножимо наступне натуральне число на три, потім з отриманого добутку віднімемо три та результат віднімання розділимо на три, то отримаємо попереднє натуральне число
$$\frac{(n+1) \cdot 3-3}{3}=\frac{3\cdot(n+1-1)}{3}=n$$
Доведемо формулу $$n=\frac{(n+1) \cdot 3-3}{3}$$ методом математичної індукції
Доказ
1) $$n=1, n+1=2$$
$$\frac{2\cdot3-3}{3}=\frac{6-3}{3}=\frac{3}{3}=1$$ – вірно
2) Припустимо, що вірно $$n=\frac{(n+1) \cdot 3-3}{3}$$
$$n+1=\frac{(n+1) \cdot 3-3}{3}+1=\frac{(n+1) \cdot 3-3+3}{3}=\frac{((n+1) +1)\cdot 3-3}{3}$$ – що й треба було довести
(2) Формула знаходження наступного натурального числа з попереднього
Нехай $$n$$ – натуральне число, $$n+1$$ – наступне за ним натуральне число.
Якщо ми двічі помножимо натуральне число на три, з отриманого добутку $$2n-1$$ раз віднімемо трійку і результат віднімання розділимо на три, то отримаємо наступне натуральне число
$$\frac{n\cdot3\cdot3-(2n-1)\cdot3}{3}=\frac{9n-6n+3}{3}=\frac{3n+3}{3}=\frac{3(n+1)}{3}=n+1$$
Доведемо формулу $$n+1=\frac{n\cdot3\cdot3-(2n-1)\cdot3}{3}$$ методом математичної індукції
Доказ
1) $$n=1, n+1=2$$
$$\frac{1\cdot3\cdot3-(2\cdot1-1)\cdot3}{3}=\frac{9-3}{3}=\frac{6}{3}=2$$ – вірно
2) Припустимо, що вірно $$n+1=\frac{n\cdot3\cdot3-(2n-1)\cdot3}{3}$$
$$(n+1)+1=\frac{n\cdot3\cdot3-(2n-1)\cdot3}{3}+1=\frac{n\cdot3\cdot3-(2n-1)\cdot3+3}{3}=$$
$$=\frac{9n-6n+3+3}{3}=\frac{9n-6n+6+9-9}{3}=\frac{(9n+9)-6n-3}{3}=\frac{9(n+1)-3(2n+1)}{3}=$$
$$=\frac{9(n+1)-3(2n+2-1)}{3}=\frac{9(n+1)-3(2(n+1)-1)}{3}=\frac{(n+1)\cdot3\cdot3-(2(n+1)-1)\cdot3}{3}$$ – що й треба було довести
Почнемо відповідати на питання
1. За яку найменшу кількість операцій можна з числа 82 отримати число 81?
Для отримання числа 81 з 82 скористаємося формулою (1) при цьому виконавши три операції числового автомата «ТЮМ-XVI» (одну операцію множення на три, одну операцію віднімання трійки й одну операцію ділення на три).
$$\frac{82\cdot3-3}{3}=81$$
2. За яку найменшу кількість операцій можна з числа 81 отримати число 82?
Для отримання числа 82 з 81 скористаємося формулою (2) при цьому виконавши сто шістдесят чотири операції числового автомата «ТЮМ-XVI» (дві операції множення на три, сто шістдесят одну операцію віднімання трійки й одну операцію ділення на три).
$$\frac{81\cdot3\cdot3-(2\cdot81-1)\cdot3}{3}=\frac{729-483}{3}=\frac{246}{3}=82$$
3. Аналогічне питання щодо отримання числа $$n$$ з числа $$m.$$
На третє запитання пропонуємо відповісти самостійно, застосувавши в загальному вигляді формули (1) або (2), залежно від чисел $$m$$ та $$n.$$
Ми не претендуємо на відповідь останньої інстанції, може бути більш елегантне рішення.