MathDB

2

Part of 1988 Polish MO Finals

Problems(2)

permutation and expected value

Source: Problem 2, Polish NO 1988

10/16/2005
For a permutation P=(p1,p2,...,pn)P = (p_1, p_2, ... , p_n) of (1,2,...,n)(1, 2, ... , n) define X(P)X(P) as the number of jj such that pi<pjp_i < p_j for every i<ji < j. What is the expected value of X(P)X(P) if each permutation is equally likely?
symmetryprobabilityexpected valuecombinatorics unsolvedcombinatorics
sequence a_{n+3} = a_{n+2}a_{n+1} + a_n

Source: Problem 5, Polish NO 1988

10/16/2005
The sequence a1,a2,a3,...a_1, a_2, a_3, ... is defined by a1=a2=a3=1a_1 = a_2 = a_3 = 1, an+3=an+2an+1+ana_{n+3} = a_{n+2}a_{n+1} + a_n. Show that for any positive integer rr we can find ss such that asa_s is a multiple of rr.
inductionpigeonhole principlemodular arithmeticnumber theory unsolvednumber theory