MathDB

5

Part of 2014 China Team Selection Test

Problems(3)

Arithmetic progressions

Source: 2014 China TST 1 Day 2 Q5

3/18/2014
Let a1<a2<...<ata_1<a_2<...<a_t be tt given positive integers where no three form an arithmetic progression. For k=t,t+1,...k=t,t+1,... define ak+1a_{k+1} to be the smallest positive integer larger than aka_k satisfying the condition that no three of a1,a2,...,ak+1a_1,a_2,...,a_{k+1} form an arithmetic progression. For any x∈R+x\in\mathbb{R}^+ define A(x)A(x) to be the number of terms in {ai}i≥1\{a_i\}_{i\ge 1} that are at most xx. Show that there exist c>1c>1 and K>0K>0 such that A(x)≥cxA(x)\ge c\sqrt{x} for any x>Kx>K.
limitcombinatorics proposedcombinatorics
Simple graph with 2 disjoint cycles, cycle contain chord

Source: 2014 China TST 2 Day 2 Q5

3/20/2014
Find the smallest positive constant cc satisfying: For any simple graph G=G(V,E)G=G(V,E), if ∣E∣≥c∣V∣|E|\geq c|V|, then GG contains 22 cycles with no common vertex, and one of them contains a chord.
Note: The cycle of graph G(V,E)G(V,E) is a set of distinct vertices v1,v2...,vn⊆V{v_1,v_2...,v_n}\subseteq V, vivi+1∈Ev_iv_{i+1}\in E for all 1≤i≤n1\leq i\leq n (n≥3,vn+1=v1)(n\geq 3, v_{n+1}=v_1); a cycle containing a chord is the cycle v1,v2...,vn{v_1,v_2...,v_n}, such that there exist i,j,1<i−j<n−1i,j, 1< i-j< n-1, satisfying vivj∈Ev_iv_j\in E.
combinatorics proposedcombinatoricsgraph theory
China Team Selection Test 2014 TST 3 Day 2 Q5

Source: China Nanjing , 24 Mar 2014

3/24/2014
Let nn be a given integer which is greater than 11 . Find the greatest constant λ(n)\lambda(n) such that for any non-zero complex z1,z2,⋯ ,znz_1,z_2,\cdots,z_n ,have that \sum_{k\equal{}1}^n |z_k|^2\geq \lambda(n)\min\limits_{1\le k\le n}\{|z_{k+1}-z_k|^2\}, where zn+1=z1z_{n+1}=z_1.
complex numbersinequalities proposedinequalitiesChina TST