HMMT 十一月 2015 · 团队赛 · 第 4 题

HMMT November 2015 — Team Round — Problem 4

[ 5 ] Call a set of positive integers good if there is a partition of it into two sets S and T , such that there b do not exist three elements a, b, c ∈ S such that a = c and such that there do not exist three elements b a, b, c ∈ T such that a = c ( a and b need not be distinct). Find the smallest positive integer n such that the set { 2 , 3 , 4 , . . . , n } is not good.

解析

[ 5 ] Call a set of positive integers good if there is a partition of it into two sets S and T , such that there b do not exist three elements a, b, c ∈ S such that a = c and such that there do not exist three elements b a, b, c ∈ T such that a = c ( a and b need not be distinct). Find the smallest positive integer n such that the set { 2 , 3 , 4 , . . . , n } is not good. Proposed by: Sam Korsky Answer: 65536 First, we claim that the set { 2 , 4 , 8 , 256 , 65536 } is not good. Assume the contrary and say 2 ∈ S . Then 2 4 2 since 2 = 4, we have 4 ∈ T . And since 4 = 256, we have 256 ∈ S . Then since 256 = 65536, we have 65536 ∈ T . Now, note that we cannot place 8 in either S or T , contradiction. Hence n ≤ 65536. And the partition S = { 2 , 3 } ∪ { 256 , 257 , . . . , 65535 } and T = { 4 , 5 , . . . , 255 } shows that n ≥ 65536. Therefore n = 65536 .