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 therebdo not exist three elements a, b, c ∈ S such that a = c and such that there do not exist three elementsba, b, c ∈ T such that a = c ( a and b need not be distinct). Find the smallest positive integer n suchthat 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 therebdo not exist three elements a, b, c ∈ S such that a = c and such that there do not exist three elementsba, b, c ∈ T such that a = c ( a and b need not be distinct). Find the smallest positive integer n suchthat 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 } showsthat n ≥ 65536. Therefore n = 65536 .