HMMT 二月 2021 · 团队赛 · 第 8 题

HMMT February 2021 — Team Round — Problem 8

[80] For each positive real number α , define b α N c := {b αm c | m ∈ N } . Let n be a positive integer. A set S ⊆ { 1 , 2 , . . . , n } has the property that: for each real β > 0 , if S ⊆ b β N c , then { 1 , 2 , . . . , n } ⊆ b β N c . Determine, with proof, the smallest possible size of S .

解析

[80] For each positive real number α , define b α N c := {b αm c | m ∈ N } . Let n be a positive integer. A set S ⊆ { 1 , 2 , . . . , n } has the property that: for each real β > 0 , if S ⊆ b β N c , then { 1 , 2 , . . . , n } ⊆ b β N c . Determine, with proof, the smallest possible size of S . Proposed by: Krit Boonsiriseth Answer: b n/ 2 c + 1 Solution: For each k ∈ {d n/ 2 e , . . . , n } , picking β = 1 + 1 /k gives b β N c ∩ [ n ] = [ n ] \ { k } so S must contain k . Now we show that S = {d n/ 2 e , . . . , n } works; this set S has b n/ 2 c + 1 elements. Suppose β satisfy S ⊆ b β N c , and suppose for the sake of contradiction that [ n ] 6 ⊂ b β N c . Since we may increase β by a small amount ε without affecting b β N c ∩ [ n ], we may assume β is irrational. Let α satisfy 1 /α + 1 /β = 1. By Beatty’s Theorem, b α N c and b β N c are complement sets in N . Let m be the maximal element of [ n ] that is not in b β N c . Then m = b kα c for some integer k . Consider ′ ′ m = b 2 kα c ∈ { 2 m, 2 m + 1 } , which must be an element of b α N c . Clearly, m > m , and since m < n/ 2, ′ ′ m 6 n , so m is also an element of [ n ] that is not in b β N c . This contradicts the maximality of m , and we are done.