Олимпиадная задача о Сизифе: максимальный заработок с камнями, алгебра и инварианты
Задача
Имеется три кучи камней. Сизиф таскает по одному камню из кучи в кучу. За каждое перетаскивание он получает от Зевса количество монет, равное разности числа камней в куче, в которую он кладёт камень, и числа камней в куче, из которой он берёт камень (сам перетаскиваемый камень при этом не учитывается). Если указанная разность отрицательна, то Сизиф возвращает Зевсу соответствующую сумму. (Если Сизиф не может расплатиться, то великодушный Зевс позволяет ему совершать перетаскивание в долг.) В некоторый момент оказалось, что все камни лежат в тех же кучах, в которых лежали первоначально. Каков наибольший суммарный заработок Сизифа на этот момент?
Решение
Решение 1:Будем называть камни из одной кучи знакомыми, из разных – незнакомыми. Тогда доход Сизифа за одно перетаскивание равен изменению количества пар знакомых камней. Так как в конечный момент все камни оказались в исходных кучах, то общее изменение количества знакомств равно нулю, а, значит, и доход Сизифа равен нулю.
Решение 2:Покажем, что величина A = ab + bc + ca + S, где a, b и c – количества камней в кучах, S – доход Сизифа, не изменяется при перетаскивании камней. Действительно, пусть Сизиф перетащил камень из первой кучи во вторую. Тогда A' = (a – 1)(b + 1) + (b + 1)c + c(a – 1) + S' = A, так как
S' = S + (b – (a – 1)). Но величина ab + bc + ca в начальный и конечный момент одна и та же, а, следовательно, и конечный доход Сизифа равен начальному, то есть нулю.
Ответ
Чтобы оставлять комментарии, войдите или зарегистрируйтесь