Let $A=\{1,2,\ldots,2012\}, \: B=\{1,2,\ldots,19\}$ and $S$ be the set of all subsets of $A.$ Find the number of functions $f : S\to B$ satisfying $f(A_1\cap A_2)=\min\{f(A_1),f(A_2)\}$ for all $A_1, A_2 \in S.$
Problem
Source: Turkish TST 2012 Problem 1
Tags: function, induction, combinatorics proposed, combinatorics
02.04.2012 08:55
By the condition the function is only determined by the subsets which have 2011 elements. So the answer is $19^{2012}$
06.04.2012 22:20
Actually, according to official solution the answer is 1+2^(2012)+3^(2012)+...+19^2012 .
09.04.2012 11:17
zhaobin wrote: By the condition the function is only determined by the subsets which have 2011 elements. So the answer is $19^{2012}$ why?
09.04.2012 12:01
First, we have 19 ways to determine the value of $f(A)$. Suppose the value of $f(A)$ is $n$, then the value of $f(X)$ for all sets $X \subset A$ is not greater than $n$. There are $n^{2012}$ ways to determine the values of $f(X)$ for all set $X$ whose cardinality is 2011. We will prove that the values of $f$ for the remaining sets are uniquely determined. We can apply induction to prove that $f(A - \{a_1, a_2, \ldots, a_i\}) = \min\{f(A - \{a_1\}), f(A - \{a_2\}), \ldots, f(A - \{a_i\})\}$. For $i = 1$ and $i = 2$, it's trivial. Suppose this is true for $i = k \le 2011$. Then for $i = k+1$, $f(A - \{a_1, a_2, \ldots, a_{k+1}\}) = \min\{f(A - \{a_1, a_2, \ldots, a_k\}), f(A - \{a_{k+1}\})\}$ by the given property of $f$. Applying the induction hypothesis and using the property that $\min\{\min\{x_1, x_2, \ldots, x_y\}, x_{y+1}\} = \min\{x_1, x_2, \ldots, x_y, x_{y+1}\}$, we have the induction claim. Hence by induction, the above claim is proven. Because we have determine the values of $f(X)$ for all set $X$ whose cardinality is 2011 and 2012, by the induction claim, we uniquely determine the values of $f$ for the entire domain. Hence, the sought value is the summation of the values $n^{2012}$ for all $n = 1,2,\ldots,19$; that is, $\boxed{1^{2012} + 2^{2012} + \ldots + 19^{2012}}$.