MathDB

6

Part of 2021 China Team Selection Test

Problems(4)

Game on GCD and LCM

Source: 2021 China TST, Test 1, Day 2 P6

3/17/2021
Given positive integer nn and rr pairwise distinct primes p1,p2,⋯ ,pr.p_1,p_2,\cdots,p_r. Initially, there are (n+1)r(n+1)^r numbers written on the blackboard: p1i1p2i2⋯prir(0≤i1,i2,⋯ ,ir≤n).p_1^{i_1}p_2^{i_2}\cdots p_r^{i_r} (0 \le i_1,i_2,\cdots,i_r \le n).
Alice and Bob play a game by making a move by turns, with Alice going first. In Alice's round, she erases two numbers a,ba,b (not necessarily different) and write gcd⁡(a,b)\gcd(a,b). In Bob's round, he erases two numbers a,ba,b (not necessarily different) and write lcm(a,b)\mathrm{lcm} (a,b). The game ends when only one number remains on the blackboard.
Determine the minimal possible MM such that Alice could guarantee the remaining number no greater than MM, regardless of Bob's move.
number theorygreatest common divisorleast common multiple
Any three points contained in equilateral triangle

Source: China TST 2021, Test 2, Day 2 P6

3/22/2021
Find the smallest positive real constant aa, such that for any three points A,B,CA,B,C on the unit circle, there exists an equilateral triangle PQRPQR with side length aa such that all of A,B,CA,B,C lie on the interior or boundary of △PQR\triangle PQR.
geometry
maximum area of lattice triangle containing exactly one m-lattice

Source: 2021ChinaTST test3 day2 P3

4/13/2021
Proof that there exist constant λ\lambda, so that for any positive integer m(≥2)m(\ge 2), and any lattice triangle TT in the Cartesian coordinate plane, if TT contains exactly one mm-lattice point in its interior(not containing boundary), then TT has area ≤λm3\le \lambda m^3. PS. lattice triangles are triangles whose vertex are lattice points; mm-lattice points are lattice points whose both coordinates are divisible by mm.
geometrycombinatoricscombinatorial geometry
chain with "big vertex" exists in partial order set

Source: 2020ChinaTST test4 day2 P3

4/14/2021
Let n(≥2)n(\ge 2) be an integer. 2n22n^2 contestants participate in a Chinese chess competition, where any two contestant play exactly once. There may be draws. It is known that (1)If A wins B and B wins C, then A wins C. (2)there are at most n316\frac{n^3}{16} draws. Proof that it is possible to choose n2n^2 contestants and label them Pij(1≤i,j≤n)P_{ij}(1\le i,j\le n), so that for any i,j,i′,j′∈{1,2,...,n}i,j,i',j'\in \{1,2,...,n\}, if i<i′i<i', then PijP_{ij} wins Pi′j′P_{i'j'}.
graph theoryPartial Orderscombinatorics