MathDB

4

Part of 2001 Romania Team Selection Test

Problems(2)

Finding pairwise friends from each of the 3 schools

Source: Romanian TST 2001

1/16/2011
Three schools have 200200 students each. Every student has at least one friend in each school (if the student aa is a friend of the student bb then bb is a friend of aa). It is known that there exists a set EE of 300300 students (among the 600600) such that for any school SS and any two students x,y∈Ex,y\in E but not in SS, the number of friends in SS of xx and yy are different. Show that one can find a student in each school such that they are friends with each other.
combinatorics proposedcombinatoricsHi
Defining the sequence from neighbours of P

Source: Romanian TST 2001

1/16/2011
Consider a convex polyhedron PP with vertices V1,…,VpV_1,\ldots ,V_p. The distinct vertices ViV_i and VjV_j are called neighbours if they belong to the same face of the polyhedron. To each vertex VkV_k we assign a number vk(0)v_k(0), and construct inductively the sequence vk(n) (n≥0)v_k(n)\ (n\ge 0) as follows: vk(n+1)v_k(n+1) is the average of the vj(n)v_j(n) for all neighbours VjV_j of VkV_k . If all numbers vk(n)v_k(n) are integers, prove that there exists the positive integer NN such that all vk(n)v_k(n) are equal for n≥Nn\ge N .
functioncombinatorics unsolvedcombinatorics