HMMT 二月 2020 · 团队赛 · 第 5 题
HMMT February 2020 — Team Round — Problem 5
题目详情
- [40] Let a , b , c , a, b, c be integers such that gcd( a , b , c ) = gcd( a, b, c ) = 1. Prove that there exists 0 0 0 0 0 0 a positive integer n and integers a , a , . . . , a = a, b , b , . . . , b = b, c , c , . . . , c = c such that for all 1 2 n 1 2 n 1 2 n 1 ≤ i ≤ n , a a + b b + c c = 1. i − 1 i i − 1 i i − 1 i ( ) 2 n 1
解析
- [40] Let a , b , c , a, b, c be integers such that gcd( a , b , c ) = gcd( a, b, c ) = 1. Prove that there exists 0 0 0 0 0 0 a positive integer n and integers a , a , . . . , a = a, b , b , . . . , b = b, c , c , . . . , c = c such that for all 1 2 n 1 2 n 1 2 n 1 ≤ i ≤ n , a a + b b + c c = 1. i − 1 i i − 1 i i − 1 i Proposed by: Michael Ren Solution: The problem statement is equivalent to showing that we can find a sequence of vectors, each with 3 integer components, such that the first vector is ( a , b , c ), the last vector is ( a, b, c ), and 0 0 0 every pair of adjacent vectors has dot product equal to 1. We will show that any vector ( a, b, c ) can be sent to (1 , 0 , 0). This is sufficient, because given vectors ( a , b , c ) and ( a, b, c ), we take the sequence from ( a , b , c ) to (1 , 0 , 0) and then add the reverse of 0 0 0 0 0 0 the sequence from ( a, b, c ) to (1 , 0 , 0). First, suppose that some two of a , b , c are relatively prime. Here we will suppose that a and b are relatively prime; the other cases are similar. If neither of a or b is 0, then by Bezout’s identity, there exist p , q such that | p | + | q | < | a | + | b | and ap + bq = 1, so we can send ( a, b, c ) to ( p, q, 0). (Finding such numbers can be done using the extended Euclidean algorithm.) Clearly p and q must also be relatively prime, so we can apply Bezout’s identity repeatedly until we eventually have (1 , 0 , 0) , ( − 1 , 0 , 0) , (0 , 1 , 0) , or (0 , − 1 , 0). Now, starting from (0 , − 1 , 0), we can do (0 , − 1 , 0) → (1 , − 1 , 0) → (1 , 0 , 0) , and we can do something similar to convert ( − 1 , 0 , 0) to (0 , 1 , 0). Now suppose that no two of a , b , c are relatively prime. Let f = gcd( a, b ) . We claim that we can find x , y , z such that axy + bx + cz = 1 . Notice that this is the same as ( ay + b ) x + cz = 1 . Since gcd( a, b, c ) = 1, there exists y such that gcd( ay + b, c ) = 1 . Then by Bezout’s identity, there exist x, z such that ( ay + b ) x + cz = 1 . Therefore, we can send ( a, b, c ) to ( xy, x, z ) . Clearly x and z must be relatively prime, so we have reduced to the case above, and we can apply the process described above for that case. At the end of this process, we will have (1 , 0 , 0), (0 , 1 , 0), or (0 , 0 , 1). The second of these can be converted into (1 , 0 , 0) by doing (0 , 1 , 0) → (1 , 1 , 0) → (1 , 0 , 0) , and a similar sequence shows the same for the third. Therefore, ( a, b, c ) can be sent to (1 , 0 , 0). ( ) 2 n 1