Шарики

[wpoms.]

В одной сумке лежит `m` шариков, в другой их `n` (`m, n > 0`). Можно выполнять две разные операции: a) Удалить равное количество шариков из обеих сумок; b) Удвоить количество шариков в одной из сумок. Всегда ли возможно опустошить обе сумки с помощью конечной последовательности операций a) и b)? Операцию b) заменяют на b') Утроить количество шаров в одной из сумок. Всегда ли возможно опустошить обе сумки с помощью конечной последовательности операций a) и b')?

@темы: Дискретная математика

Comments

[MestnyBomzh]

Для первого пункта так решил:
Не теряя общности: m > n. Далее удаляем из обеих сумок n-1 шаров. Получаем: m-n+1 и 1. Далее удваиваем единицу и вынимаем по одному шару из каждой сумки, получаем: m-n и 1. И так пока m-n не станет степенью двойки. Далее очевидно