Задачка на инвариант Петя написал на первой доске число 5, а на второй число 8. За один ход оба написанных числа разрешается либо увеличить на 1, либо умножить на какое-нибудь натуральное число, либо разделить на какой-нибудь их натуральный общий делитель. Можно ли несколькими такими операциями добиться, чтобы на первой доске было написано число 3, а на второй – число 5?
Понятно, что ответ на вопрос: "нет". Но как его объяснить не понятно.
Тут вроде должен использоваться инвариант. В принципе, Вы можете всё решение не расписывать, а просто сказать, какой тут инвариант или полуинвариант.

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно использовать инвариант, связанный с делением чисел. Мы можем обратить внимание на сначала написанные числа: 5 и 8.

Одним из возможных инвариантов является некое свойство пар чисел, которое не будет изменяться в процессе выполнения операций. В данном случае мы можем рассмотреть разность их значений по модулю:

Обозначим ( a ) — первое число, ( b ) — второе (т.е. ( a = 5 ), ( b = 8 )).Разность по модулю 3: ( a \mod 3 ) и ( b \mod 3 ).

Теперь найдем значения:

( 5 \mod 3 = 2 )( 8 \mod 3 = 2 )

Таким образом, начальная пара чисел ( (5, 8) ) дает инвариант ( (2, 2) ).

Теперь посмотрим, какое значение будет у конечной пары ( (3, 5) ):

( 3 \mod 3 = 0 )( 5 \mod 3 = 2 )

Таким образом, конечная пара дает инвариант ( (0, 2) ).

Сравнивая эти инварианты, мы видим, что они не совпадают. Начальная пара имеет один инвариант, а конечная пара — другой. То есть, перейти от ( (5, 8) ) к ( (3, 5) ) невозможно, потому что инварианты не совпадают.

Следовательно, ответ на вопрос: нельзя добиться, чтобы на первой доске было написано число 3, а на второй – число 5.