Subcontests
(6)Guess the Median
Positive integers n and k satisfying n≥2k+1 are known to Alice. There are n cards with numbers from 1 to n, randomly shuffled as a deck, face down. On her turn, she does the following in order:(i) She first flips over the top card of the deck, and puts it face up on the table.
(ii) Then, if Alice has not signed any card, she can sign the newest card now.The game ends after 2k+1 turns, and Alice must have signed on some card. Let A be the number on the signed cards, and M be the (k+1)st largest number among all 2k+1 face-up cards. Alice's score is ∣M−A∣, and she wants the score to be as close to zero as possible.For each (n,k), find the smallest integer d=d(n,k) such that Alice has a strategy to guarantee her score no greater than d.Proposed by usjl SNOW in Taiwan
Let ABC be an acute triangle with circumcenter O and circumcircle Ω. Choose points D,E from sides AB,AC, respectively, and let ℓ be the line passing through A and perpendicular to DE. Let ℓ intersect the circumcircle of triangle ADE and Ω again at points P,Q, respectively. Let N be the intersection of OQ and BC, S be the intersection of OP and DE, and W be the orthocenter of triangle SAO.Prove that the points S, N, O, W are concyclic.Proposed by Li4 and me. A functional equation with strange domain
Let X be the collection of all non-empty subsets (not necessarily finite) of the positive integer set N. Determine all functions f:X→R+ satisfying the following properties: (i) For all S, T∈X with S⊆T, there holds f(T)≤f(S).
(ii) For all S, T∈X, there hold
f(S) + f(T) \le f(S + T), f(S)f(T) = f(S\cdot T),
where S+T={s+t∣s∈S,t∈T} and S⋅T={s⋅t∣s∈S,t∈T}. Proposed by Li4, Untro368, and Ming Hsiao. Generalized Sylvester-Galai
Let n,s,t be three positive integers, and let A1,…,As,B1,…,Bt be non-necessarily distinct subsets of {1,2,…,n}. For any subset S of {1,…,n}, define f(S) to be the number of i∈{1,…,s} with S⊆Ai and g(S) to be the number of j∈{1,…,t} with S⊆Bj. Assume that for any 1≤x<y≤n, we have f({x,y})=g({x,y}). Show that if t<n, then there exists some 1≤x≤n so that f({x})≥g({x}).Proposed by usjl Extremely weird gcd problem
Denote the set of all positive integers by N, and the set of all ordered positive integers by N2. For all non-negative integers k, define good functions of order k recursively for all non-negative integers k, among all functions from N2 to N as follows:(i) The functions f(a,b)=a and f(a,b)=b are both good functions of order 0.(ii) If f(a,b) and g(a,b) are good functions of orders p and q, respectively, then gcd(f(a,b),g(a,b)) is a good function of order p+q, while f(a,b)g(a,b) is a good function of order p+q+1.Prove that, if f(a,b) is a good function of order k≤(3n) for some positive integer n≥3, then there exist a positive integer t≤(2n) and t pairs of non-negative integers (x1,y1),…,(xn,yn) such that
f(a,b)=gcd(ax1by1,…,axtbyt)
holds for all positive integers a and b.Proposed by usjl