MathDB

5

Part of 2015 Iran Team Selection Test

Problems(3)

Edges in a Table

Source: Iran TST 2015, exam 1, day 2 problem 2

5/11/2015
Let AA be a subset of the edges of an n×nn\times n table. Let V(A)V(A) be the set of vertices from the table which are connected to at least on edge from AA and j(A)j(A) be the number of the connected components of graph GG which it's vertices are the set V(A)V(A) and it's edges are the set AA. Prove that for every natural number ll: l2≤min∣A∣≥l(∣V(A)∣−j(A))≤l2+l2+1\frac{l}{2}\leq min_{|A|\geq l}(|V(A)|-j(A)) \leq \frac{l}{2}+\sqrt{\frac{l}{2}}+1
combinatoricsgraph theory
Good permutations

Source: Iranian TST 2015 second exam p5

6/5/2015
We call a permutation (a1,a2,⋯ ,an)(a_1, a_2,\cdots , a_n) of the set {1,2,⋯ ,n}\{ 1,2,\cdots, n\} "good" if for any three natural numbers i<j<ki <j <k, n∤ai+ak−2ajn\nmid a_i+a_k-2a_j find all natural numbers n≥3n\ge 3 such that there exist a "good" permutation of a set {1,2,⋯ ,n}\{1,2,\cdots, n\}.
number theorycombinatorics
Iran TST 2015 Polynomial

Source: Iran TST 2015,third exam,second day,problem 5

6/1/2015
Prove that for each natural number dd, There is a monic and unique polynomial of degree dd like PP such that P(1)P(1)≠00 and for each sequence like a1a_{1},a2a_{2}, ...... of real numbers that the recurrence relation below is true for them, there is a natural number kk such that 0=ak=ak+1=...0=a_{k}=a_{k+1}= ... : P(n)a1+P(n−1)a2+...+P(1)an=0P(n)a_{1} + P(n-1)a_{2} + ... + P(1)a_{n}=0 n>1n>1
polynomialalgebra