MathDB

6

Part of 2019 China Team Selection Test

Problems(4)

Cinderella and the Wicked Stepmother

Source: China TST Test 1 Day 2 Q6

3/11/2019
Let kk be a positive real. AA and BB play the following game: at the start, there are 8080 zeroes arrange around a circle. Each turn, AA increases some of these 8080 numbers, such that the total sum added is 11. Next, BB selects ten consecutive numbers with the largest sum, and reduces them all to 00. AA then wins the game if he/she can ensure that at least one of the number is ≥k\geq k at some finite point of time.
Determine all kk such that AA can always win the game.
combinatoricsgameChina TST
Sum of bad integers to the power of 2019

Source: China TST 2019 Test 2 Day 2 Q6

3/11/2019
Given coprime positive integers p,q>1p,q>1, call all positive integers that cannot be written as px+qypx+qy(where x,yx,y are non-negative integers) bad, and define S(p,q)S(p,q) to be the sum of all bad numbers raised to the power of 20192019. Prove that there exists a positive integer nn, such that for any p,qp,q as described, (p−1)(q−1)(p-1)(q-1) divides nS(p,q)nS(p,q).
number theoryChina TST
Coloring is hard

Source: 2019 China TST Test 3 P6

3/29/2019
Given positive integers d≥3d \ge 3, r>2r>2 and ll, with 2d≤l<rd2d \le l <rd. Every vertice of the graph G(V,E)G(V,E) is assigned to a positive integer in {1,2,⋯ ,l}\{1,2,\cdots,l\}, such that for any two consecutive vertices in the graph, the integers they are assigned to, respectively, have difference no less than dd, and no more than l−dl-d. A proper coloring of the graph is a coloring of the vertices, such that any two consecutive vertices are not the same color. It's given that there exist a proper subset AA of VV, such that for GG's any proper coloring with r−1r-1 colors, and for an arbitrary color CC, either all numbers in color CC appear in AA, or none of the numbers in color CC appear in AA. Show that GG has a proper coloring within r−1r-1 colors.
combinatoricsgraph theory
Combinatorial numbers are all even

Source: 2019 China TST Test 4 P6

3/29/2019
Given positive integer n,kn,k such that 2≤n<2k2 \le n <2^k. Prove that there exist a subset AA of {0,1,⋯ ,n}\{0,1,\cdots,n\} such that for any x≠y∈Ax \neq y \in A, (yx){y\choose x} is even, and ∣A∣≥(k⌊k2⌋)2k⋅(n+1)|A| \ge \frac{{k\choose \lfloor \frac{k}{2} \rfloor}}{2^k} \cdot (n+1)
number theorycombinatorics