HMMT 二月 2022 · 团队赛 · 第 1 题

HMMT February 2022 — Team Round — Problem 1

[20] Let ( a , a , . . . , a ) be a permutation of (1 , 2 , . . . , 8). Find, with proof, the maximum possible 1 2 8 number of elements of the set { a , a + a , . . . , a + a + · · · + a } 1 1 2 1 2 8 that can be perfect squares.

解析

[20] Let ( a , a , . . . , a ) be a permutation of (1 , 2 , . . . , 8). Find, with proof, the maximum possible 1 2 8 number of elements of the set { a , a + a , . . . , a + a + · · · + a } 1 1 2 1 2 8 that can be perfect squares. Proposed by: Akash Das Answer: 5 Solution: We claim the maximum is 5, achieved by the sequence (1 , 3 , 5 , 7 , 2 , 4 , 6 , 8). Now we prove that we cannot do better. Since a + a + . . . + a = 1 + 2 + . . . + 8 = 36, then there are at most 6 squares in 1 2 8 { a , a + a , . . . , a + a + · · · + a } . 1 1 2 1 2 8 2 2 Note that if a + · · · + a = n and a + · · · + a = ( n + 1) , then a + . . . + a = 2 n + 1. Since 2 n + 1 1 k 1 j k +1 j is odd, a must be odd for some m ∈ [ k + 1 , j ]. m Thus, if all of 1 , 4 , 9 , 16 , 25 , and 36 are in { a , a + a , . . . , a + a + · · · + a } , 1 1 2 1 2 8 then a = 1, and there are five more odd values in { a , a , . . . , a } , which is a contradiction because 1 1 2 8 there are only four odd numbers in { 1 , 2 , . . . , 8 } .