MathDB

6

Part of 2022 China Team Selection Test

Problems(4)

Colorful subsets

Source: 2022 China TST, Test 1, P6

3/24/2022
Let mm be a positive integer, and A1,A2,…,AmA_1, A_2, \ldots, A_m (not necessarily different) be mm subsets of a finite set AA. It is known that for any nonempty subset II of {1,2…,m}\{1, 2 \ldots, m \}, ∣⋃i∈IAi∣≥∣I∣+1. \Big| \bigcup_{i \in I} A_i \Big| \ge |I|+1. Show that the elements of AA can be colored black and white, so that each of A1,A2,…,AmA_1,A_2,\ldots,A_m contains both black and white elements.
combinatoricscoloringsgraph theoryHall s marriage theoremTSTChina TST
Distance between products with sums

Source: 2022 China TST, Test 2, P6

3/29/2022
Let m,nm,n be two positive integers with m≥n≥2022m \ge n \ge 2022. Let a1,a2,…,an,b1,b2,…,bna_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n be 2n2n real numbers. Prove that the numbers of ordered pairs (i,j) (1≤i,j≤n)(i,j) ~(1 \le i,j \le n) such that ∣ai+bj−ij∣≤m |a_i+b_j-ij| \le m does not exceed 3nmlog⁡n3n\sqrt{m \log n}.
algebracombinatorics
Bounding the norm of complex roots

Source: 2022 China TST, Test 3 P6

4/30/2022
(1) Prove that, on the complex plane, the area of the convex hull of all complex roots of z20+63z+22=0z^{20}+63z+22=0 is greater than π\pi. (2) Let a1,a2,…,ana_1,a_2,\ldots,a_n be complex numbers with sum 11, and k1<k2<⋯<knk_1<k_2<\cdots<k_n be odd positive integers. Let ω\omega be a complex number with norm at least 11. Prove that the equation a1zk1+a2zk2+⋯+anzkn=w a_1 z^{k_1}+a_2 z^{k_2}+\cdots+a_n z^{k_n}=w has at least one complex root with norm at most 3n∣ω∣3n|\omega|.
combinatorial geometrygeometrycomplex numbers
Two mutually non-divisible subsets

Source: 2022 China TST, Test 4 P6

4/30/2022
Given a positive integer nn, let DD be the set of all positive divisors of nn. The subsets A,BA,B of DD satisfies that for any a∈Aa \in A and b∈Bb \in B, it holds that a∤ba \nmid b and b∤ab \nmid a. Show that ∣A∣+∣B∣≤∣D∣. \sqrt{|A|}+\sqrt{|B|} \le \sqrt{|D|}.
number theoryDivisibilityDivisors