MathDB

1

Part of 2012 France Team Selection Test

Problems(2)

A group of k people where some (n+1)-th knows all n

Source: French TST 2012

8/2/2012
Let nn and kk be two positive integers. Consider a group of kk people such that, for each group of nn people, there is a (n+1)(n+1)-th person that knows them all (if AA knows BB then BB knows AA). 1) If k=2n+1k=2n+1, prove that there exists a person who knows all others. 2) If k=2n+2k=2n+2, give an example of such a group in which no-one knows all others.
group theoryabstract algebragraph theorycombinatorics proposedcombinatorics
k-tastrophic functions

Source: French TST 2012

8/2/2012
Let k>1k>1 be an integer. A function f:N∗→N∗f:\mathbb{N^*}\to\mathbb{N^*} is called kk-tastrophic when for every integer n>0n>0, we have fk(n)=nkf_k(n)=n^k where fkf_k is the kk-th iteration of ff: fk(n)=f∘f∘⋯∘f⏟k times(n)f_k(n)=\underbrace{f\circ f\circ\cdots \circ f}_{k\text{ times}}(n) For which kk does there exist a kk-tastrophic function?
functionalgebra unsolvedalgebra