MathDB

2

Part of 2011 China Team Selection Test

Problems(6)

Inequality with the mulitplicities of distances in a plane

Source: China TST 2011 - Quiz 1 - D1 - P2

5/19/2011
Let SS be a set of nn points in the plane such that no four points are collinear. Let {d1,d2,⋯ ,dk}\{d_1,d_2,\cdots ,d_k\} be the set of distances between pairs of distinct points in SS, and let mim_i be the multiplicity of did_i, i.e. the number of unordered pairs {P,Q}⊆S\{P,Q\}\subseteq S with ∣PQ∣=di|PQ|=d_i. Prove that ∑i=1kmi2≤n3−n2\sum_{i=1}^k m_i^2\leq n^3-n^2.
inequalitiesgeometryperpendicular bisectorcombinatorics proposedcombinatorics
Number of 1's in binary representation of n

Source:

11/14/2011
Let nn be a positive integer and let αn\alpha_n be the number of 11's within binary representation of nn.
Show that for all positive integers rr, 22n−αn−1∣−10∑k=−nn(2nn+k)k2r.2^{2n-\alpha_n}\phantom{-1} \bigg|^{\phantom{0}}_{\phantom{-1}} \sum_{k=-n}^{n} \binom{2n}{n+k} k^{2r}.
calculusfunctionnumber theorycombinatorics
Find all possible values of m, n

Source: China TST 2011 - Quiz 2 - D1 - P2

5/20/2011
Let ℓ\ell be a positive integer, and let m,nm,n be positive integers with m≥nm\geq n, such that A1,A2,⋯ ,Am,B1,⋯ ,BmA_1,A_2,\cdots,A_m,B_1,\cdots,B_m are m+nm+n pairwise distinct subsets of the set {1,2,⋯ ,ℓ}\{1,2,\cdots,\ell\}. It is known that AiΔBjA_i\Delta B_j are pairwise distinct, 1≤i≤m,1≤j≤n1\leq i\leq m, 1\leq j\leq n, and runs over all nonempty subsets of {1,2,⋯ ,ℓ}\{1,2,\cdots,\ell\}. Find all possible values of m,nm,n.
calculusderivativefunctionalgebrapolynomialmodular arithmeticcombinatorics unsolved
Periodic Sequences - Find all values of m

Source: China TST 2011 - Quiz 2 - D2 - P2

5/20/2011
Let {bn}n≥1∞\{b_n\}_{n\geq 1}^{\infty} be a sequence of positive integers. The sequence {an}n≥1∞\{a_n\}_{n\geq 1}^{\infty} is defined as follows: a1a_1 is a fixed positive integer and an+1=anbn+1,∀n≥1.a_{n+1}=a_n^{b_n}+1 ,\qquad \forall n\geq 1. Find all positive integers m≥3m\geq 3 with the following property: If the sequence {anmod  m}n≥1∞\{a_n\mod m\}_{n\geq 1 }^{\infty} is eventually periodic, then there exist positive integers q,u,vq,u,v with 2≤q≤m−12\leq q\leq m-1, such that the sequence {bv+utmod  q}t≥1∞\{b_{v+ut}\mod q\}_{t\geq 1}^{\infty} is purely periodic.
inductionnumber theory unsolvednumber theory
Prove that there exists a such that n | a^2 - a

Source: China TST 2011 - Quiz 3 - D1 - P2

5/20/2011
Let n>1n>1 be an integer, and let kk be the number of distinct prime divisors of nn. Prove that there exists an integer aa, 1<a<nk+11<a<\frac{n}{k}+1, such that n∣a2−an \mid a^2-a.
modular arithmeticnumber theory proposednumber theory
There exist infinitely many i with gcd(a_i, a_i+1) ≤ 3i/4

Source: China TST 2011 - Quiz 3 - D2 - P2

5/20/2011
Let a1,a2,…,an,…a_1,a_2,\ldots,a_n,\ldots be any permutation of all positive integers. Prove that there exist infinitely many positive integers ii such that gcd⁡(ai,ai+1)≤34i\gcd(a_i,a_{i+1})\leq \frac{3}{4} i.
ceiling functionfloor functionnumber theory unsolvednumber theory