ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2003. Simple Magic

Proof
Posted by andreyDagger 22 Jan 2022 15:48
This is proof of why answer < 3.

Suppose, we have 3 elements x, y, z, with gcd(x, y, z) != 1. Then, after first transformation array will contain elements: gcd(x, y), gcd(x, z), gcd(y, z), Let's call them a = gcd(x, y), b = gcd(x, z), c = gcd(y, z). After second tranformation array will contain elements: gcd(a, b), gcd(a, c), gcd(b, c), we can notice, that:
gcd(a, b) = gcd(gcd(x, y), gcd(x, z)) = gcd(x, y, x, z) = gcd(x, y, z). Doing similar things with gcd(a, c) and gcd(b, c), it turns out, that gcd(a, b) = gcd(a, c) = gcd(b, c) = gcd(x, y, z). That means, that after 2nd transformation array will contain 3 equal numbers greater than 1. I think it's obvious, that answer will be infinity, if array contains 3 equal numbers greater than 1.


Now, if gcd of any tripple of numbers equals one, that means, that we will end in less than 2 transformations (Proof this by yourself)

Edited by author 22.01.2022 15:49