Maths Olympiad Prep

Library / /9 of 33

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Turkey

Let A={1,2,,2012}A = \{1, 2, \dots, 2012\}, B={1,2,,19}B = \{1, 2, \dots, 19\} and SS be the set of all subsets of AA. Determine the number of functions f:SBf : S \to B satisfying the condition f(A1A2)=min{f(A1),f(A2)}f(A_1 \cap A_2) = \min\{f(A_1), f(A_2)\} for all A1,A2SA_1, A_2 \in S.

Solution

The answer is 12012+22012++1920121^{2012} + 2^{2012} + \dots + 19^{2012}.

We first observe that the minimum element of UVU \cup V is the minimum of the minimum elements of UU and VV for all finite sets UU and VV of integers.

Let the value of f(A)f(A) be nn. Then by the given property of ff we have f(X)nf(X) \le n for all XSX \in S. Note that there are n2012n^{2012} different ways to determine the values of f(X)f(X) for all sets XX in SS of size 20112011. We will prove that the values of ff for the remaining sets are uniquely determined.

We apply induction on kk to prove that
f(A{a1,a2,,ak})=min{f(A{a1}),f(A{a2}),,f(A{ak})}() f(A \setminus \{a_1, a_2, \dots, a_k\}) = \min\{f(A \setminus \{a_1\}), f(A \setminus \{a_2\}), \dots, f(A \setminus \{a_k\})\} \quad (*)
for all a1,a2,,akBa_1, a_2, \dots, a_k \in B.

For k=1k=1, it is trivial and the case for k=2k=2 results from the condition on ff.

f(A{a1,a2,,ak+1})=min{f(A{a1,a2,,ak}),f(A{ak+1})}. f(A \setminus \{a_1, a_2, \dots, a_{k+1}\}) = \min\{f(A \setminus \{a_1, a_2, \dots, a_k\}), f(A \setminus \{a_{k+1}\})\}.

Using the induction hypothesis and the observation above we can conclude that the claim is true for k+1k+1 as well.

On the other hand, by (*) and the observation above it can be easily verified that the condition on ff is satisfied for all A1,A2SA_1, A_2 \in S. Therefore, as 1n191 \le n \le 19 we obtain that there are 12012+22012++1920121^{2012} + 2^{2012} + \dots + 19^{2012} such functions.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.