MathDB

1.3

Part of MathLinks Contest 7th

Problems(1)

0713

Source:

4/14/2008
We are given the finite sets X X, A1 A_1, A2 A_2, … \dots, A_{n \minus{} 1} and the functions fi: X→Ai f_i: \ X\rightarrow A_i. A vector (x1,x2,…,xn)∈Xn (x_1,x_2,\dots,x_n)\in X^n is called nice, if f_i(x_i) \equal{} f_i(x_{i \plus{} 1}), for each i \equal{} 1,2,\dots,n \minus{} 1. Prove that the number of nice vectors is at least \frac {|X|^n}{\prod\limits_{i \equal{} 1}^{n \minus{} 1} |A_i|}.
functionvectorprobabilityinequalitieslinear algebramatrixinduction