14.4.Еще пример задания

Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика:

Вперед 4 – Кузнечик прыгает вперед на 4 единицы,

Назад 3 – Кузнечик прыгает назад на 3 единицы.

Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 27?

Решение (составление уравнения, подбор решения):

1. обозначим через количество команд «Вперед 4» в программе, а через – количество команд «Назад 3»

2. для того, чтобы КУЗНЕЧИК попал в точку 27 из точки 0, должно выполняться условие

1. это уравнение называется диофантовым; поскольку числа 4 и 3 – взамнопростые (их наибольший общий делитель равен 1), оно имеет бесконечно много решений

2. из всех решений нас интересует такое, при котором – наименьшее возможное неотрицательное (!) число

3. представим уравнение в виде

нужно подобрать минимальное неотрицательное , при котором правая часть делится на 4

1. дальше используем метод подбора (или перебора), начиная от 1; получаем

1. видим, что первое , при котором делится на 4, это (при этом ).

2. таким образом, ответ – 3.