MathDB

4

Part of 2015 Moldova Team Selection Test

Problems(3)

Coloring the vertices of a n-gon

Source: Moldova TST Problem 4

3/31/2015
In how many ways can we color exactly kk vertices of an nn-gon in red such that any 22 consecutive vertices are not both red. (Vertices are considered to be labeled)
combinatoricsElementary counting
Counting sets that contain their cardinality

Source: Moldova TST Problem 8

4/1/2015
Consider a positive integer nn and A={1,2,...,n}A = \{ 1,2,...,n \}. Call a subset X⊆AX \subseteq A perfect if ∣X∣∈X|X| \in X. Call a perfect subset XX minimal if it doesn't contain another perfect subset. Find the number of minimal subsets of AA.
combinatoricscountingSubsets
find number of functions...

Source: Moldova TST Problem 4, day 3

3/31/2015
Let nn and kk be positive integers, and let be the sets X={1,2,3,...,n}X=\{1,2,3,...,n\} and Y={1,2,3,...,k}Y=\{1,2,3,...,k\}. Let PP be the set of all the subsets of the set XX. Find the number of functions f:P→Y f: P \to Y that satisfy f(A∩B)=min⁡(f(A),f(B))f(A \cap B)=\min(f(A),f(B)) for all A,B∈PA,B \in P.
functioncombinatorics