high-quality questions. This test was created by multiple 130+ scorers, and we have tried our very best to produce the highest quality test possible. We've blended the question types in a good distribution, and maintained a realistic difficulty. (something most AOPS mocks fail at)
such that![\[f(x)+f(t)=f(y)+f(z)\]](http://latex.artofproblemsolving.com/7/e/c/7ecb395c1e56e6d9726fc45f1bc7a66d98333da2.png)
for all rational numbers 
that form an arithmetic progression. 
Y by dantx5, droid347, 62861, gamjawon, algebra_star1234, daniellionyang, anantmudgal09, fluffyclouds, HamstPan38825, icematrix2, megarnie, DCMaths, Adventure10, MS_asdfgzxcvb
Let 
, where 
. Each of the 
subsets of 
is to be colored red or blue. (The subset itself is assigned a color and not its individual elements.) For any set 
, we then write 
for the number of subsets of 
that are blue.
Determine the number of colorings that satisfy the following condition: for any subsets
and 
of , ![\[ f(T_1)f(T_2) = f(T_1 \cup T_2)f(T_1 \cap T_2). \]](//latex.artofproblemsolving.com/1/8/1/18184e9196e6c73601653d85f1cfd6d9798a8e43.png)
, where 
. Each of the 
subsets of 
is to be colored red or blue. (The subset itself is assigned a color and not its individual elements.) For any set 
, we then write 
for the number of subsets of 
that are blue.Determine the number of colorings that satisfy the following condition: for any subsets
and 
of , ![\[ f(T_1)f(T_2) = f(T_1 \cup T_2)f(T_1 \cap T_2). \]](http://latex.artofproblemsolving.com/1/8/1/18184e9196e6c73601653d85f1cfd6d9798a8e43.png)
This post has been edited 1 time. Last edited by v_Enhance, May 3, 2015, 11:55 AM
Reason: "colered"
Reason: "colered"
are integers between 
and 
.
was possible, since from that you can get statements about divisibility on the other side of the equation.
-
(by which we mean a coloring of the subsets of 
)![\[ \operatorname{supp}(\mathcal C) = \left\{ T \mid f(T) \neq 0 \right\}. \]](http://latex.artofproblemsolving.com/7/3/2/732ff943a7d7864fe734d2c2a83bb77dce115e5e.png)
Call a coloring nontrivial if 
(equivalently, the coloring is not all red). In that case, notice that
then necessarily both 
and 
are nonzero; and![\[ \operatorname{supp}(\mathcal C) = [X,S] \overset{\text{def}}{=} \left\{ T \mid X \subseteq T \subseteq S \right\} \]](http://latex.artofproblemsolving.com/3/d/c/3dc5252f44d0b9008fe272cc1d7de9456f43ea1e.png)
for some set 
(for example by letting 
(equivalently, 
is blue).
,
.![\[ f(T) = 2^{\left\lvert T \cap B \right\rvert} \]](http://latex.artofproblemsolving.com/d/4/7/d4776a52b45e656772fc9732e346cf2a8df7efa1.png)
which satisfies the condition by Inclusion-Exclusion. To see this extension is unique, note that 
is determined for each 
and we can then determine 
;
![$\operatorname{supp}(\mathcal C) = [X,S]$](http://latex.artofproblemsolving.com/c/2/1/c217289b2e6d142ce107be885e13f8b98f6e035c.png)
,
-
,
possible choices of 
.![\[ 1 + \sum_{k=0}^n \binom nk 2^k = \boxed{1 + 3^n}. \]](http://latex.artofproblemsolving.com/0/8/1/0813ee39eccab9f92169d9087904108fec44049d.png)
with small values of 
in the summation but prove everything else (also write the 1 in the summation but don't have it added in the final answer - so I ended up with 
oops), how many points would be deducted?
.
![$[R_1,R_2]$](http://latex.artofproblemsolving.com/7/e/f/7efa5b4a670872423b8c3fb64af0f527e4b3798a.png)
.
be the minimal blue set-if there's another minimal blue set we get a contradiction, so all blue sets are supersets of 
be the set of singletons which are blue, 
;
.![\[\prod_{i \in S \backslash A}f(A \cup \{i\}) = f(S)\]](http://latex.artofproblemsolving.com/b/a/5/ba5678cc63ee41d99eddb85901a4215d2d9d097d.png)
by the given condition, induction, and the fact that 
.
is always either 1 or 2, and let 
.
using a similar idea to the large product above. It follows pretty quickly that the set of blue sets is the set of all 
.
.
.
.
and so that means every subset of 
.
that was blue. Then consider any set 
which means every single subset not containing 
is minimal. We know that
such that 
,
and so that implies that all subsets of 
we color subsets 
.
and suppose that there are 
good elements in 
good elements in both ![\[f(T_1)f(T_2)=2^{a+x}\cdot 2^{b+x}=2^{a+b+x}\cdot 2^{x}=f(T_1\cup T_2)f(T_1\cap T_2),\]](http://latex.artofproblemsolving.com/2/4/c/24c823ced25566aabb9264b6763793940b08cb22.png)
as desired.
be the set of blue subsets. Let 
we have ![\[1\le f(A)f(T)=f(A\cap T)f(A\cup T).\]](http://latex.artofproblemsolving.com/5/f/5/5f525c789001e6eed776f8d54adba5ce4362e45b.png)
If 
then 
and there exists a subset of 
that is blue as 
,
.
,
.![\[(b+x)(t+x)=f(B)f(T)=f(B\cup T)f(B\cap T)=(b+t+x)x\]](http://latex.artofproblemsolving.com/b/b/9/bb973d9a973a17152b994635a27be9880084b616.png)
which gives 
which means all blue subsets of 
so if 
then 
ie 
.
.
is blue, then there are exactly 
,
is uniquely determined by 
.
is uniquely determined by 
.
holds. Conversely, if we put colors of 
arbitrarily, we get a coloring that satisfies the problem condition. Thus, the number of coloring is 
is minimal and let 
.
,
,
.
of 
,
,
.
be subsets of 
that don't include 
and 
,
.
.
and 
.
,
and realised the claim, but it took embarrasingly long time to prove, because I chose wrong approach to prove. I tried to prove the claim by using induction on 
or 
(obviously, if does not exist, then there is 
ways to color 
since then everything is red.)
is 
we have that 
so 
for all 
Then, we have for any disjoint sets 
and 
that
so
Now, let 
Then, we want to have
or
Notice that 
and 
so by PIE this is always true. Now, we need to find the number of ways to color the grid in such a way. Notice that it is always possible, and there is one way to do it. Thus, this case has 
options.
notice that for any pair of 
-
where 
we must have 
so either 
or 
Thus, we need at least 
of these 
since if there are less than 
then we can choose 
subsets 
with 
which gives us a contradiction. Let the one set colored blue with size 
Define 
Then, we see that for any set 
since 
and hence 
Then, 
so 
Now, we find the number of ways to color 
Consider the set
Then, by the first case we did, we have 
ways to color 
since 
satisfies the same rules as 
However, we also need to count the number of ways to choose 
which is 
giving 
in this case. Thus, overall, we have
is red. Note that a subset is blue if and only if all the elements are blue. Thus, there are 
elements.There can obviously be no more blue sets with 
or any sets that don't contain the smallest blue subset. Now, consider all subsets that have the smallest blue set as a subset. Then note that we can consider this as simply an 
elements. Thus, our final answer is
.
.
blue if 
is blue. Note that for any disjoint 
which is simply 
.
case is self-evident. Assuming it is true up to 
.
has 
,
proper subsets are blue. But 
in total, so 
,
.
is the smallest blue set. Then all of its proper subsets are red. Now since for disjoint 
,
are all red. Now consider all sets 
where 
and 
.![\[ 0 = f(P) (\{1, 2, \dots, k \} \cup Q)= f(P \cup Q) f(\{1, 2, \dots, k \}) = f(P \cup Q) \implies P \cup Q \text{ is red.} \]](http://latex.artofproblemsolving.com/b/9/f/b9fcb3e843e6aef8271708af0b02983479b797c9.png)
The only sets left to assign a color are those of the form 
.
.
,
we are doing this on 
.
ways to choose these colors. Now showing the constructions work is easily verifiable.
.![\[1 + 2^n + \sum_{k = 1}^n \binom{n}{k} 2^{n - k} = \boxed{3^n + 1}. \]](http://latex.artofproblemsolving.com/3/c/7/3c7fd9a8fb078316fec2edfab455377607005ffc.png)
for disjoint subsets 
.
for which an 
.
and we are done.
is blue, then 
and then for disjoint sets 
.
uniquely determines the rest of the colorings, giving 
then 
.
is 
is blue. Therefore 
which is obviously determined by the one element subsets.
for some integer 
,
blue subsets. Therefore, 
,
.
.
.
determine all of the subsets that contain a 
.
,
,
with a subset of that smallest blue subset, which determines the rest of the colors. We also need to include the case where there is 
by the binomial theorem.
,
for all 
represents the number of elements in 
is the blue set of minimal cardinality 
.
ways to select 
with 
gives![\[1 + \binom n0 \cdot 2^n + \ldots + \binom nn \cdot 2^0 = \boxed{3^n+1}. \quad \blacksquare\]](http://latex.artofproblemsolving.com/b/1/e/b1ecc50eda848971272ac20338aaa1fd8c9e7fa8.png)
,
-
.
.
.![\[ f(\{1, 2, \dots, k\})f(\{k+1\}) = f(\{1, 2, \dots, k+1\}). \]](http://latex.artofproblemsolving.com/4/4/e/44eabb35e83efaaf621d9102c8d32f8d65762cba.png)
is red, 
.
,
to be red.
.
is blue iff 
is. Along with 
,
is blue iff 
.
.
are 
.
blue elements with 
elements of overlap (i.e. 
has 
has 
blue elements), we get 
,
and 
are blue sets of minimal size 
.
has size less than 
,
with 
are red.
,
.
,
.
.
for each subset 
of 
and 
,
.
,
,
.
is not a superset of 
.
is also not a superset of 
.
,
-![\[\sum_{i = 1}^n 2^{n-i}\binom{n}{i} + 1 \]](http://latex.artofproblemsolving.com/0/4/8/04884a96385e531589fe8495e1bed3ac378072a9.png)
![\[= \sum_{i = 1}^n 2^{n-i}\binom{n}{n-i} + 1 \]](http://latex.artofproblemsolving.com/3/7/b/37b0c8fed780362b7887626199710b11a3126b7b.png)
![\[= \sum_{i = 0}^{n-1} 2^{i}\binom{n}{i} + 1 \]](http://latex.artofproblemsolving.com/4/b/0/4b08053f9fbec760d36c0bb457ba0102beb4b46b.png)
![\[= 3^n - 2^n + 1. \]](http://latex.artofproblemsolving.com/c/3/a/c3a6a2ed9e838cc99157972ab452cc1c425760cf.png)
ways. 
with lowercase ones.
,
for disjoint sets 
,
is the number of elements 
such that 
.
,
and now 
,
,
are the amount of elements that satisfy 
and are shared between both sequences and 
are the ones which only appear in one of the sequences. Check that: 
.
for all 
,
.
with base case 
clear.
.
,
,
.
and 
disjoint and so 
(if 
was blue or red for all 
ways to colour.
with minimal cardinality, then clearly 
and \textit{bad} otherwise.
and so 
,
,
are red.
,
,
has less cardinality than 
that contain 
,
,
are the sets of shared and individual \textit{good} elements and 
are the remaining ones, hence 
,
,
.
.
.
as 
.
,
and 
is a subset of 
.
for each 
,
is red or blue, respectively. We claim we can let 
(resp. 
)
for 
.
;
that are supersets of 
,
.![\[f(S) = f(X \cup A) f(X \cup B) = 2^{m},\]](http://latex.artofproblemsolving.com/c/c/e/cce4c79d8a88997d577d930acb012f29c8ba2a09.png)
so the 
blue subsets of 
possible colourings. Summing over all subsets ![\[1 + \sum_{i = 0}^n \binom ni 2^{n - i} = \boxed{1 + 3^n}\]](http://latex.artofproblemsolving.com/5/4/3/543352bd027de29197afa54281b9c4d8df2b0231.png)
colourings by the Binomial Theorem.
be the number of colorings total, and let 
be the number of colorings which satisfy 
By considering disjoint subsets 
Inductively, we get 
where 
are pairwise disjoint subsets of 
the number of blue subsets it has is uniquely determined by the number of blue subsets which 
has for each 
Clearly 
if 
Therefore, if 
This function 
If 
say 
then we see that 
,
)
is the number of subsets of 
for all subsets 
Then every proper subset of 
Now let 
then 
so 
Therefore, the only 
In this remainder, we can ignore the elements which are in 
and 
ways to choose 
to have size 
so we get 
Plugging in our values of 
and using the Binomial Theorem gives us our answer 
is coloured 
,
.
,so they would automatically be coloured Red, because
and 
so both sides become 
,so we can provide them any colour we want.
}
}
}
with 
}
}
}
to be coloured 
such that 
s
are "Disjoint subsets" with CARDINALITY 
sets whose 
"
First, if the empty set is blue, for any two disjoint subsets 
we have 
Therefore if 
is the set of blue singletons, 
So the coloring of the singletons uniquely determines the other colorings. And this works by the inclusion-exclusion principle as 
Hence there are 
so at least one of them is blue. Hence at most one singleton is red by considering all pairs. If there is a red singleton, WLOG 
for any 
So inductively we can see that all sets not containing 
colorings. This clearly works as for a set 
as 
does not contain 
So there are 
if there is a red doubleton. Continuing, we see that the answer is 
QED
.
.
or WLOG 
.
,
.
be the first group of subsets where a blue (and only one blue as we established) occurs. WLOG let the set 
be the set colored blue. Then note that there are two types of sets of size 
sets containing this blue set 
and there are 
sets not containing this blue set 
.
gives us a unique coloring of all subsets of 
.
does not contain 
that isn't 
.
,
and write 
.
Note that for any 
is blue then 
else 
.
where 
forces 
to be blue because 
blue subsets in 
,
then 
?
or 
and this expression must be true, so suppose 
.
the expression holds.
many colorings if we end up with exactly one blue subset of size 
colorings total.
.
