Subcontests
(6)Exponential Growth
A finite set K consists of at least 3 distinct positive integers. Suppose that K can be partitioned into two nonempty subsets A,B∈K such that ab+1 is always a perfect square whenever a∈A and b∈B. Prove that
k∈Kmaxk≥⌊(2+3)min{∣A∣,∣B∣}−1⌋+1,where ∣X∣ stands for the cartinality of the set X, and for x∈R, ⌊x⌋ is the greatest integer that does not exceed x. Cool Optimization Problem on Trees.
There are n cities in a country, where n>1. There are railroads connecting some of the cities so that you can travel between any two cities through a series of railroads (railroads run in both direction.) In addition, in this country, it is impossible to travel from a city, through a series of distinct cities, and return back to the original city. We define the degree of a city as the number of cities directly connected to it by a single segment of railroad. For a city A that is directly connected to x cities, with y of those cities having a smaller degree than city A, the significance of city A is defined as xy.Find the smallest positive real number t so that, for any n>1, the sum of the significance of all cities is less than tn, no matter how the railroads are paved.Proposed by houkai Games in Quarantine
Alice and Bob are stuck in quarantine, so they decide to play a game. Bob will write down a polynomial f(x) with the following properties:(a) for any integer n, f(n) is an integer;
(b) the degree of f(x) is less than 187.Alice knows that f(x) satisfies (a) and (b), but she does not know f(x). In every turn, Alice picks a number k from the set {1,2,…,187}, and Bob will tell Alice the value of f(k). Find the smallest positive integer N so that Alice always knows for sure the parity of f(0) within N turns.Proposed by YaWNeeT Easy Geometry with Simple Property about OI Line
Let I,O,ω,Ω be the incenter, circumcenter, the incircle, and the circumcircle, respectively, of a scalene triangle ABC. The incircle ω is tangent to side BC at point D. Let S be the point on the circumcircle Ω such that AS,OI,BC are concurrent. Let H be the orthocenter of triangle BIC. Point T lies on Ω such that ∠ATI is a right angle. Prove that the points D,T,H,S are concyclic.Proposed by ltf0501