MathDB

3

Part of 2014 China National Olympiad

Problems(2)

China Mathematical Olympiad P3

Source: China Nanjing 21 Dec 2013

12/21/2013
Prove that: there exists only one function f:N∗→N∗f:\mathbb{N^*}\to\mathbb{N^*} satisfying: i) f(1)=f(2)=1f(1)=f(2)=1; ii)f(n)=f(f(n−1))+f(n−f(n−1))f(n)=f(f(n-1))+f(n-f(n-1)) for n≥3n\ge 3. For each integer m≥2m\ge 2, find the value of f(2m)f(2^m).
functioninductionalgebra proposedalgebra
Addition of subsets

Source: China Mathematical Olympiad 2014 Q6

12/22/2013
For non-empty number sets S,TS, T, define the sets S+T={s+t∣s∈S,t∈T}S+T=\{s+t\mid s\in S, t\in T\} and 2S={2s∣s∈S}2S=\{2s\mid s\in S\}. Let nn be a positive integer, and A,BA, B be two non-empty subsets of {1,2…,n}\{1,2\ldots,n\}. Show that there exists a subset DD of A+BA+B such that 1) D+D⊆2(A+B)D+D\subseteq 2(A+B), 2) ∣D∣≥∣A∣⋅∣B∣2n|D|\geq\frac{|A|\cdot|B|}{2n}, where ∣X∣|X| is the number of elements of the finite set XX.
pigeonhole principleceiling functioncombinatorics proposedcombinatorics