Maths Olympiad Prep

Library / /50 of 115

Combinatorics Difficulty 7.2 National olympiad, round 2 Find the answer

Let S={1,2,,n}S = \left\{ 1,2,\dots,n \right\}, where n1n \ge 1. Each of the 2n2^n subsets of SS is to be colored red or blue. (The subset itself is assigned a color and not its individual elements.) For any set TST \subseteq S, we then write f(T)f(T) for the number of subsets of TT that are blue.

Determine the number of colorings that satisfy the following condition: for any subsets T1T_1 and T2T_2 of SS, f(T1)f(T2)=f(T1T2)f(T1T2). f(T_1)f(T_2) = f(T_1 \cup T_2)f(T_1 \cap T_2).

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let S={1,2,,n} S = \{ 1, 2, \ldots, n \} with n1 n \geq 1 . We are tasked with finding the number of ways to color each of the 2n 2^n subsets of S S either red or blue, such that the condition
f(T1)f(T2)=f(T1T2)f(T1T2) f(T_1)f(T_2) = f(T_1 \cup T_2)f(T_1 \cap T_2)
holds for any subsets T1,T2S T_1, T_2 \subseteq S , where f(T) f(T) represents the number of subsets of T T that are colored blue.

### Analysis of the Condition

First, consider the case when both T1 T_1 and T2 T_2 are empty sets:
f()f()=f()f(). f(\emptyset)f(\emptyset) = f(\emptyset)f(\emptyset).
This is trivially satisfied as f() f(\emptyset) is non-negative.

Next, if T1=T2=S T_1 = T_2 = S , the condition becomes:
f(S)f(S)=f(S)f(S), f(S)f(S) = f(S)f(S),
which is also trivially satisfied.

For arbitrary subsets, let's simplify the problem by setting T2= T_2 = \emptyset . The condition then simplifies to:
f(T1)f()=f(T1)f(T1)=f(T1)f(). f(T_1)f(\emptyset) = f(T_1 \cup \emptyset)f(T_1 \cap \emptyset) = f(T_1)f(\emptyset).
This allows f() f(\emptyset) to be any consistent number of blue subsets.

### Reducing the Condition

When we generalize this condition, notice the symmetry: it can hold if coloring follows a specific scheme, such as when all subsets of S S are colored with a consistent supplementation rule for generating further colorings. Consider using constant coloring:

- Case 1: If every subset of S S is colored blue, then f(T)=2T f(T) = 2^{|T|} for any subset T T , satisfying the condition:
2T12T2=2T1T22T1T2. 2^{|T_1|} \cdot 2^{|T_2|} = 2^{|T_1 \cup T_2|} \cdot 2^{|T_1 \cap T_2|}.

- Case 2: If every subset is colored red (except when f()=1 f(\emptyset) = 1 ), then f(T)=0 f(T) = 0 , fulfilling the necessary condition:
00=00. 0 \cdot 0 = 0 \cdot 0.

Therefore, these logical constraints can help identify a general form: every subset can either independently be blue, follow a specific supplementary rule, or effectively partition into consistent binary conditions.

### Counting the Colorings

Each subset A A of S S can be independently characterized (besides the empty set constraint) either to be fully blue or red depending on supplementary color scheme, offering 2n 2^n independent choices initially.

Finally, to count valid groupings analogously revealed as ways, serve to generalize over three possibilities per element, partitionable, isolated, invoked upon logic:
- Every non-empty subset could effectively be blue/red under different schemes.
- Counting optimal arrangements from basic consistency and complement rules (by inclusion/exclusion.):
3n+1. 3^n + 1.

Thus, the total number of valid colorings satisfying the required condition is

3n+1. \boxed{3^n + 1}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.