Завдання. Розв’язати конкурсну задачу на числовий автомат з турніру юних математиків “ТЮМ–XVI”

Пропонуємо вашій увазі конкурсну задачу з турніру юних математиків.

Завдання

Числовий автомат «ТЮМ-XVI» може виконувати такі операції з натуральними числами:

  • відняти від даного числа число 3 (якщо воно більше, ніж 3);
  • помножити дане число на 3;
  • розділити дане число на 3 (якщо воно ділиться на 3 без залишку).

Дайте відповідь на такі запитання:

  1. За яку найменшу кількість операцій можна з числа 82 отримати число 81?
  2. За яку найменшу кількість операцій можна з числа 81 отримати число 82?
  3. Аналогічне питання щодо отримання числа $$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.$$

Ми не претендуємо на відповідь останньої інстанції, може бути більш елегантне рішення.