MathDB

4

Part of 2008 Romania Team Selection Test

Problems(3)

Polygon and set of points inside, triangulation

Source: Romanian TST 1 2008, Problem 4

5/1/2008
Prove that there exists a set S S of n \minus{} 2 points inside a convex polygon P P with n n sides, such that any triangle determined by 33 vertices of P P contains exactly one point from S S inside or on the boundaries.
analytic geometryinductioncombinatorics proposedcombinatorics
Minimum number of edges of complete triangular graphs

Source: Romanian TST 2 2008, Problem 4

6/7/2008
Let G G be a connected graph with n n vertices and m m edges such that each edge is contained in at least one triangle. Find the minimum value of m m.
inductioncombinatorics proposedcombinatorics
Another Turan-type problem

Source: Romanian TST 3 2008, Problem 4

6/7/2008
Let n n be a nonzero positive integer. A set of persons is called a n n-balanced set if in any subset of 3 3 persons there exists at least two which know each other and in each subset of n n persons there are two which don't know each other. Prove that a n n-balanced set has at most (n \minus{} 1)(n \plus{} 2)/2 persons.
inequalitiesinductiongraph theorycombinatorics proposedcombinatorics