MathDB
turkey 1993 q3

Source:

October 27, 2006
functionprobabilityexpected valuecombinatorics unsolvedcombinatorics

Problem Statement

n∈Z+n\in{Z^{+}} and A=1,…,nA={1,\ldots ,n}. f:N→Nf: N\rightarrow N and σ:N→N\sigma: N\rightarrow N are two permutations, if there is one k∈Ak\in A such that (f∘σ)(1),…,(f∘σ)(k)(f\circ\sigma)(1),\ldots ,(f\circ\sigma)(k) is increasing and (f∘σ)(k),…,(f∘σ)(n)(f\circ\sigma)(k),\ldots ,(f\circ\sigma)(n) is decreasing sequences we say that ff is good for σ\sigma. SσS_\sigma shows the set of good functions for σ\sigma. a) Prove that, SσS_\sigma has got 2n−12^{n-1} elements for every σ\sigma permutation. b)n≥4n\geq 4, prove that there are permutations σ\sigma and τ\tau such that, Sσ∩Sτ=ϕS_{\sigma}\cap S_{\tau}=\phi .
Back to ProblemsView on AoPS