[/quote]
,
be three positive reals such that 
.![\[ \frac { x^5-x^2 }{x^5+y^2+z^2} + \frac {y^5-y^2}{x^2+y^5+z^2} + \frac {z^5-z^2}{x^2+y^2+z^5} \geq 0 . \]](http://latex.artofproblemsolving.com/a/1/4/a14adf0f1e35df57c734c7df701d5a67da22dc3c.png)
be a triangle with altitude 
.
-
at 
,
and 
.
and 
on lines 
and 
such that quadrilateral 
is a rhombus.
or the NCSSM Math Club Competition. All middle schoolers in North Carolina can register. (You can have up to a team of 4) It will be held virtually on May 10th. Here is the 
be an integer. Two players, Alice and Bob, play the following game on the complete graph 
:
,![\[
\left( \frac{1}{4} - \varepsilon \right) n^2 + n.
\]](http://latex.artofproblemsolving.com/a/9/c/a9cca00e87c643af32eb75a2501b59060f3504fb.png)
such that the following inequality holds for all 
:![\[
ab + bc + ca \leq \frac{(a + b + c)^2}{3} + k \cdot \max \{ (a - b)^2, (b - c)^2, (c - a)^2 \} \leq a^2 + b^2 + c^2
\]](http://latex.artofproblemsolving.com/1/c/e/1ce66163068b499383adb4a4ecec86c5f4edaec3.png)
be positive real numbers such that : 
. Prove that : 
where 
are lengths of parallel sides and 
are other two sides.
,
,
,
,
in some order.
board that is entirely covered by dominoes, with no overlap. He jumps along the vertical lines of the board, always going from the midpoint of the vertical segment of a 
square to another midpoint of the vertical segment, according to the rules:
When the domino is horizontal, the cricket jumps to the opposite vertical segment (such as from 
to 
)
When the domino is vertical downwards in relation to its position, the cricket jumps diagonally downwards (such as from 
to 
When the domino is vertically upwards relative to its position, the cricket jumps diagonally upwards (such as from 
)
board.
Prove that
candies. A starts first. On a move, if in the box there are 
candies, the player chooses positive integer 
so that 
and 
,
.
for Girls, PRISMS Online Math Meet for Girls, is happening this spring! 
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 
;
.![\[\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 
is blue.
and 
,
'
be the number of blue 
'
'
.
.
is blue, but some elements' singletons 
are red. Now split the set into 
and 
,
is 
,
,
is red, since its size is 
.
is 0, but 
is non-zero, contradiction.
,
red, then colour one set of size 
.
sparkling sets.)
the number of ways to put 
boxes, so the answer is 
.
.
and 
to discover that 
.
.
as 
(because their intersection has size at most 
)![$[0, n]$](http://latex.artofproblemsolving.com/a/5/8/a585433224883cbcd304f34129a152b97d5ed96e.png)
(or just not exist so we must add ![\[1 + \sum_{k = 0}^{k = n} \binom{n}{k} 2^{n-k} = 3^n +1\]](http://latex.artofproblemsolving.com/7/e/b/7eb60e4281f1df7634849a561124e508ce8ed9e9.png)
since this is just the binomial expansion of 
.
we color subsets 
.
and suppose that there are 
good elements in ![\[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 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 
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 
.
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 
,
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 
,
.
,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 
"
