MathDB
China TST 2010, Problem 4

Source:

August 28, 2010
inequalitiesinductionfunctioncombinatorics unsolvedcombinatorics

Problem Statement

Let G=G(V,E)G=G(V,E) be a simple graph with vertex set VV and edge set EE. Suppose ∣V∣=n|V|=n. A map f: V→Zf:\,V\rightarrow\mathbb{Z} is called good, if ff satisfies the followings: (1) ∑v∈Vf(v)=∣E∣\sum_{v\in V} f(v)=|E|; (2) color arbitarily some vertices into red, one can always find a red vertex vv such that f(v)f(v) is no more than the number of uncolored vertices adjacent to vv. Let m(G)m(G) be the number of good maps. Prove that if every vertex in GG is adjacent to at least one another vertex, then n≤m(G)≤n!n\leq m(G)\leq n!.
Back to ProblemsView on AoPS