Averaging Principle Average height of the students in class is l. →There is a student of height≥l(sl) max avg min For a random variable X, ·3x≤EX☑，such that X=is possible; ●3x≥ElX☑，such that X=x is possible
• Average height of the students in class is l. ⇒ There is a student of height ≥ l ( ≤ l ) Averaging Principle min max avg • For a random variable X, • ∃ x ≤ E[X], such that X = x is possible; • ∃ x ≥ E[X], such that X = x is possible
Hamiltonian paths in tournament Hamiltonian path: a path visiting every vertex exactly once. Theorem (Szele 1943) There is a tournament on n players with at least n!2-(n-1)Hamiltonian paths
Hamiltonian paths in tournament There is a tournament on n players with at least n!2(n1) Hamiltonian paths. Theorem (Szele 1943) Hamiltonian path: a path visiting every vertex exactly once