I think that's correct, and it's quite nice.

http://rmm.lbi.ro/index.php?id=solutions_math

There's also a nice solution using inclusion-exclusion principle. Let $D_i$ be the set of sets of boys where none of them is in acqauintance of i-th girl. $|D_1 \cup .. \cup D_d| \equiv_2 \sum |D_{i_1} \cap ... D_{i_k}|$ and one can see that LHS is number of not sociable set of boys which of course has the same parity as the number of sociable sets of boys and $2\mid |D_{i_1} \cap ... D_{i_k}|$ iff set of girls $i_1, ..., i_k$ is not sociable, because $|D_{i_1} \cap ... D_{i_k}|=2^b$ where $b$ is the number of boys such that any of that girls is in acquaintance with any of that boys .

Say non-empty set of girls $G_i$ is not-connected with non-empty set of boys $B_j$ if no member of $G_i$ knows a member of $B_j$(then also $B_j$ is not-connected with $G_i$). Number of sociable sets of girls is the same parity as number of sociable sets of boys if and only if number of unsociable sets of girls is the same parity as number of unsociable sets of boys. Easy to see that unsociable $G_i$ is not connected with an odd number of sets $B_j$. But also number of unsociable $B_i$ is not connected with an odd number of sets $G_j$. So numbers of unsociable sets must have the same parity. And so QED.

This solution was found in collaboration with proglote (who is studying hard for RMM to represent Brazil well ). Given a boy $a$ and a girl $b$, define $f(a,b) = 0$ if $a,b$ know each other and $1$ otherwise. Let $A$ be the set of boys and $B$ the set of girls. Then the set $A' \subseteq A$ is sociable iff: \[\prod_{b \in B}\left ( \left ( \prod_{a \in A'} f(a,b) \right ) + 1 \right ) \equiv 1 \pmod{2}\] Thus it follows the number of sociable set of boys is congruent modulo $2$ to: \[\sum_{A' \subseteq A} \prod_{b \in B}\left ( \left ( \prod_{a \in A'} f(a,b) \right ) + 1 \right )\] Now, remark that: \[\prod_{b \in B}\left ( \left ( \prod_{a \in A'} f(a,b) \right ) + 1 \right ) = \sum_{B' \subseteq B} \prod_{b \in B'} \prod_{a \in A'} f(a,b)\] It follows the number of sociable set of boys modulo $2$ is \[\sum_{A' \subseteq A} \sum_{B' \subseteq B} \prod_{b \in B'} \prod_{a \in A'} f(a,b)\] As this expression is symmetric with respect to $A,B$ it follows the number of sociable sets have the same parity for both genders and thus we are done.

Let $ B $ be set of boys and $G$ be set of girls. Let $V$ be a set containing only one boy and let $g$ be set of girls that boy $V$ knows. Let $T=G-g$ and let $S=B-V$. For $X$ a set of boys and $Y$ a set of girls, $ f(X\rightarrow Y)$ denotes the number of subsets of $X$ such that every girl in $Y$ knows a boy in that subset, and define $f(Y \rightarrow X)$ similarly. Note that if $(X,Y) \neq (B, G)$, by induction on $|B|+|G|$ we can assume $f(X \rightarrow Y) \equiv f(Y \rightarrow X) $ (mod $2$). So $f(B \rightarrow G) = f(S \rightarrow T) + f(S \rightarrow G)$ (to the first sets, we add $V$ and to the other ones we don't). And $f(G \rightarrow B) = f(G \rightarrow S) - f(T \rightarrow S)$. this denotes the number of sets of girls that know all boys except maybe $V$, minus the number of sets of girls that know all boys except $V$. Using induction hypothesis we finish.

Let the set $A$ be the set of boys and set $B$ be the set of girls. We will induct on $|A|+|B|$. The base case is trivial. Now let the proposition hold for $|A| = a$ and $|B| = b$. We will prove that it will hold for $|A| = a+1$. Let the boys be $X_i$ and the girls be $Y_i$. Now let $Y_1,Y_2,..., Y_k$ be the $k$ acquaintances of the new boy $X_{a+1}$. Firstly, let $M$ be the original number of sociable set of boys, and let $N$ be the number of sociable set of boys which include $X_{a+1}$. Now clearly the number of sociable set of boys must be $M+N$. Next, let $K$ be the number of sociable set of girls which include at least one of $Y_1,Y_2,..., Y_k$ and $L$ be the original number of the sociable set of girls. The number of sociable set of girls then must be $K$. Now $L-K$ can also be interpreted as the number of sociable set of girls from $Y_{k+1},...,Y_b$ to $X_1,X_2,...,X_a$. Also, $N$ can also be interpreted as the number of sociable set of boys from $X_1,X_2,...,X_a$ to $Y_{k+1},...,Y_b$, since if we add $X_{a+1}$ to it we will get a sociable set of boys. By induction, their parity is the same, then $M+N$ and $K$ must also have the same parity.

Why is this true? How one find something like this? dinoboy wrote: ... Now, remark that: \[\prod_{b \in B}\left ( \left ( \prod_{a \in A'} f(a,b) \right ) + 1 \right ) = \sum_{B' \subseteq B} \prod_{b \in B'} \prod_{a \in A'} f(a,b)\]...

meagain wrote: Why is this true? How one find something like this? dinoboy wrote: \[\prod_{b \in B}\left ( \left ( \prod_{a \in A'} f(a,b) \right ) + 1 \right ) = \sum_{B' \subseteq B} \prod_{b \in B'} \prod_{a \in A'} f(a,b)\] It's if fact this: \[ \prod_{b \in B}\left ( g(b) + 1 \right ) = \sum_{B' \subseteq B} \prod_{b \in B'} g(b) \]E.g. $B = \{x,y,z\}$, $g(t) \equiv t$: $$ (x+1)(y+1)(z+1) = \underbrace{xyz}_{B} + \underbrace{xy + xz + yz}_{2\text{-element subsets}} + \underbrace{x + y + z}_{1\text{-element subsets}} + \underbrace{1}_{\varnothing}. $$

Lots of possible solutions here. We use the bipartite graph formulation, and proceed by induction on the number of edges and vertices. The base case goes of $0$ edges can be checked by casework on whether there is at least one boy and whether there is at least one girl. Now consider a boy $b$ and a girl $g$ who know each other. Among all remaining boys, let $B'$ denote the friends of $g$ and $B$ denote the non-friends of $g$. Among all remaining girls, let $G'$ denote the friends of $b$ and $G$ denote the non-friends of $b$. Now imagine what happens when we delete edge $bg$ (e.g. they break up). Then certain sets cease to be sociable; let us describe them. A set $X$ of boys ceases to be sociable if: $X$ contained $b$, $X$ did not contain any element of $B'$ (hence $X \setminus \{b\} \subseteq B$), and Every girl in $G$ knows some boy in $A$. Hence $X$ corresponds naturally to sociable set of boys in the sub-graph on $B \sqcup G$. Similarly, sets of girls ceasing to be sociable correspond to sociable sets of girls in the same sub-graph on $B \sqcup G$. By induction hypothesis, these are equal modulo $2$, so done. Remark: If the base case is not actually checked carefully, then the above becomes a fake proof that the number of sociable sets is actually equal. (Indeed, one might carelessly write ``in the base case, there are no sociable sets at all''.) I find this hilarious for no reason whatsoever.

Let's induct on the number of edges. Let Justin and Hailey be the boy and girl we are looking at. For a set to be sociable before Justin and Hailey breaks up but not sociable after Justin and Hailey break up, the set had to had contain Justin / Hailey. Since the boy sociable group we are looking at already has Justin, Justin's girlfriends are already covered. Also, note that Hailey's boyfriends cannot be part of this set because otherwise, regardless of whether Justin and Hailey break up, this set will remain sociable. So, this ex-sociable, now not set only contains Justin and Hailey's strangers. Hailey's strangers should cover all of Justin's strangers. Similarly, for the girl sociable groups, Justin's strangers should cover all of Hailey's strangers. Therefore, by the induction hypothesis, the difference of parity between girl and guys sociable groups should be preserved.

Very nice! Let $S$ be the set of girls, $T$ be the set of boys, and $G = S \sqcup T$ be the bipartite graph where we connect a girl and a boy iff they are friends. Additionally, let $S' \subseteq S$ and $T' \subseteq T$. We define $f(S', T')$ as the number of subsets of $S'$ which dominate $T'$. The desired conclusion is then equivalent to $f(S, T) \equiv f(T, S) \pmod{2}$. We henceforth suppose that $\min(|S|, |T|) > 0$ (or else the problem is vacuous). We proceed by strong induction on $|G|$, with the base case $|G| = 2$ trivial. Now, let $s \in S$ be a vertex, and let $N(s)$ be the neighbor set of $S$. Additionally, let $S'$ be a subset of $S$ which dominates $T$. Call $S'$ good if $s \in S'$ and $S'\setminus\{s\}$ doesn't dominates $S$, and call $S'$ bad otherwise. We claim that the number of bad subsets is even. Indeed, for each bad subset $S'$ containing $s$, we construct the pair $(S', S' \setminus\{s\})$; each bad subset is clearly in exactly one pair, implying that the number of bad subsets is even. This is enough to imply that $f(S, T)$ has the same parity as the number of good subsets. We now claim that the number of good subsets is $f(S\setminus\{s\}, T\setminus N(s)) - f(S\setminus\{s\}, T)$. Indeed, let $S'$ be a good subset. Since $S'\setminus\{s\}$ dominates $T \setminus N(s)$ but not $T$, it follows that there are $f(S\setminus\{s\}, T\setminus N(s)) - f(S\setminus\{s\}, T)$ possible $S'\setminus\{s\}$, which implies that the number of good subsets is $f(S\setminus\{s\}, T\setminus N(s)) - f(S\setminus\{s\}, T)$. Therefore, we have $f(S, T) \equiv f(S\setminus\{s\}, T\setminus N(s)) - f(S\setminus\{s\}, T) \pmod{2}$. Now, we have \begin{align*} f(S, T) &\equiv f(T, S) \pmod{2} \\ \iff f(S\setminus\{s\}, T\setminus N(s)) - f(S\setminus\{s\}, T) &\equiv f(T, S) \pmod{2} \\ \iff f(S\setminus\{s\}, T) - f(T, S) &\equiv f(S\setminus\{s\}, T\setminus N(s)) \pmod{2} \\ \iff f(T, S\setminus\{s\}) - f(T, S) &\equiv f(T\setminus N(s), S\setminus\{s\}) \pmod{2}, \end{align*}where the final equality is due to the inductive hypothesis. We claim that the last equality in fact holds over $\mathbb{Z}$! Indeed, note that $f(T, S\setminus\{s\}) - f(T, S)$ counts the number of subsets of $T$ which dominate $S\setminus\{s\}$ but not $S$. Note that none of these subsets can intersect with $N(s)$; hence, these subsets are the same as the subsets of $T\setminus N(s)$ which dominate $S\setminus\{s\}$. Thus, $f(T, S\setminus\{s\}) - f(T, S) = f(T\setminus N(s), S\setminus\{s\})$, and we are done! $\Box$

Similar to @valentinodante: Let $B$ and $G$ be sets of boys and girls respectively. Let $|B|=m$ and $|G|=n$. We induct by $m+n$. The base is trivial. Suppose it holds for $m+n\leq l$. Let`s prove it for $m+n=l+1$. Pick any boy $A$ and his girl-friends ( ) $G_1,G_2,...,G_i$.The main idea is to find the difference of parities of sociable sets of boys and girls respectively. We will easily do it by our induction assumption. Let $k$ denotes the number of sociable sets of boys without the boy $A$. Notice that if we add the boy $A$ in any of these sets we will get another sociable set of boys. So we will get $k$ more sociable sets. Let $z$ denotes the number of subsets of these boys such that the boys in any of these subsets have as friends all girls from $G$/{$G_{i_1},G_{i_2},...,G_{i_j}$} $j<i$. Then note that if we add $A$ to any of these subsets we will get another sociable set, so we will have $z$ more sociable sets of boys. So the total number of sociable sets of boys is $2k+z$. $(1)$ Now let`s count the total number of sociable sets of girls. Let`s forget for a second about $A$. Let $q$ be the number of social sets of girls in these left $l$ people and let $b$ be the amount of the subsets of these $q$ social sets that don`t include any girl from {$B_1,B_2,...,B_i$}. Now let`s return $A$. So, obviously (you can check it by yourself) we will have that total number of social sets of girls is $q-b$. $(2)$ And now consider the set $D$ = $B/A\cup\ {G}$ / {$G_1,G_2,...,G_i$}. But then note that in this set $D$ - $b$ is the number of sociable sets of girls (it is obvious from the definition of $b$) and the number of sociable sets of boys in $D$ is $z+k$ because $z$ is the total number of subsets of $B/A$ that have as friends all girls from $G$ / {$G_{i_1},G_{i_2},...,G_{i_j}$} but do not have as a friend at least one girl from {$G_1,G_2,..,G_i$} and $k$ is the total number of subsets of $B/A$ that have as friends all girls from $G$ / {$G_{i_1},G_{i_2},...,G_{i_j}$} as well as all girls from {$G_1,G_2,..,G_i$}, so the result follows. But by the assumption of induction we get that $z+k\equiv b\mod 2$. Also note that by assumption of induction we get $k\equiv q\mod 2$ From $(1)$ and $(2)$ we need to prove that $2k+z+q-b$ is even, thus we will get that $2k+z$ and $q-b$ are both even or both odd. But $2k+z+q-b$ = $(k+q)+(z+k-b)$ = even + even = even - $Q.E.D.$. $\blacksquare$

We will induct on the number of edges. If there are no edges (base case), then it is easy to check that the number of sociable sets of boys or girls must be either $0$ or a power of $2$ greater than $1$, hence even. Choose a boy $B$ and a girl $G$ who are friends, and let them break up. Call sets that were sociable before the breakup but not after the breakup broken. It suffices to show that the number of broken boy sets and girl sets are the same. Define $X$ as the union of the non-friends of $G$ and the non-friends of $B$. Let's characterize the number of broken boy sets. Obviously a broken boy set $S$ must include $B$, and $B$ must be the only member of the set who is friends with $G$. Since all of the non-girlfriends of $B$ must be friends with some other member of $S$ to be sociable in the first place, we find that the number of broken boy sets is equal to the number of sociable boy sets of $X$. Similarly the number of broken girl sets is equal to the number of sociable girl sets of $X$. By inductive hypothesis these must have the same parity, as desired.

What a weird solution. Suppose there are $n$ boys and $m$ girls. When $\min(n,m)=0$ the problem is trivial. Assume $m,n\geq1$ from now on. Let $S_i$ denote the set of all subsets of boys that are NOT friends with the $i$th girl. Then, the number of non-sociable sets of boys (which is the same parity as the number of sociable sets) is $$|S_1\cup \cdots S_m|.$$We will now use the PIE. Since we are working in mod 2, we can ignore all of the sign alternations, so it is just $$\sum_{subsets~P~of~1~to~m}(Size~of~intersection~of~S_i~with~i~in~P).$$However, by definition of $S_i$, the size of the set of intersection of $S_i$ for all $i\in P$ is $2^a$, where $a$ is the number of boys that are not friends with any of the girls in set $P$. Thus, a subset $P$ creates a odd summand if and only if $a=0$, which is exactly equivalent to the condition that the subset of girls is sociable, so we are done.

Solved with AdhityaMV: We shall use the following known result : link for an amazing proof of this Quote: The number of dominating sets of any finite graph is odd. We consider the bipartite graph on the set of boys $B$ and set of girls $G$ and then add edges between every 2 boys and every 2 girls. Let the number of dominating subsets of $B$ be $d_B$, the number of dominating subsets of $G$ be $d_G$ and let the number of remaining dominating subsets be $d_{BG}$. By the above result, $d_B + d_G + d_{BG}$ is odd. Also, by counting, $d_{BG} = (2^{|B|}-1)(2^{|G|}-1)$ which is odd. Hence $d_B,d_G$ have the same parity and we are done.

I realize that the direct counting solution to this problem is never posted here, so here we go. Let $B,G$ be the set of all boys and the set of all girls. The main claim is the following. Claim: Let $n$ be the number of pairs of sets $(S, T)$ such that $S\subseteq B$ and $T\subseteq G$ and no boys in $S$ know any girls in $T$. Then $n$ is equivalent to the number of sociable sets of boys in modulo $2$. Proof. We fix set $S$ and count the number of working $T$. If $f(S)$ is the set of all girls which does not know anyone in $S$, then the number of $T$ is $2^{\lvert f(S)\rvert}$, which is odd precisely when $f(S)$ is the empty set, i.e. when $S$ is a sociable set of boys. Hence we are done. $\blacksquare$ By the claim, $n$ is also equivalent to the number of sociable sets of girls in modulo $2$ so we are done.

Siddharth03 wrote: Quote: The number of dominating sets of any finite graph is odd. bro solved 10USATST6 to solve a RMM1 :skull:

We proceed with induction on the number of edges, with our base case of 0 edges being easy to handle. Use bipartite graph with just boy-girl edges based on acquaintance. Take an arbitrary acquainted pair $b_1$ and $g_1$, and consider the outcome of deleting the edge between them. We would like to show the differences in socialable sets for boys and girls are the same parity. A socialable set of boys $S$ in our original graph will become non-socialable $\iff$ $b_1$ is in this set but no other acquaintance $b_k$ of $g_1$ is also in the set. Thus the number of socialable sets which become non-socialable after removing edge $b_1 g_1$ is equal to the number of socialable sets in the bipartite subgraph containing vertices which are not nor are acquainted with $b_i$ or $g_i$. A symmetric argument holds with the socialable sets of girls, from which we invoke our inductive hypothesis. $\blacksquare$

If two people are acquainted with each other, then we will denote them as \textit{friends}, and we will refer to the according acquaintance as a friendship. Since friendship between two boys and between two girls do not matter in the problem statement, we can reduce the problem to a bipartite graph with boy-girl edges based on whether the pair are friends. Then, we will prove the desired statement using induction on the amount of edges in our graph. The base case of $0$ edges implies that there exist no friendships. As such, the number of sociable set of boys is either $0$ if there are no boys or a nonzero amount of boys and girls, or $2^k$ if there are $k$ boys and no girls. Regardless, the amount is even, and we can use a similar process on the girls to see that there are an even amount of sociable sets of girls. Take an arbitrary pair $b_1$ and $g_1$ that are friends. Then, among the other boys, let $B$ be the set of boys that are not friends with $g_1$ and let $B'$ be the set of boys that are friends with $g_1$. Similarly, let $G$ be the set of girls (that aren't $g_1$) that are not friends with $b_1$ and let $G$ be the set of girls that are friends with $b_1$. Consider the number of sets of boys such that if the edge $b_1g_1$ were deleted, it would cease to be sociable. Suppose that one such set is denoted as $S$. Obviously, $S$ needs to contain $b_1$. Moreover, $S$ cannot contain any boy in $B'$ because that would cause $g_1$ to be friends with some boy in $S$, contradicting the fact that $S$ ceases to be sociable after $b_1g_1$ is deleted. Finally, all the girls in $G$ are friends with someone in $S$ in order for $S$ to be sociable before the edge is deleted. More specifically, every girl in $G$ must be friends with at least one boy in $B$ since $S$ does not contain any boys in $B'$. As a result, all of the possible sets $S$ correspond with the sociable sets on the subgraph $B \cup G$ under the mapping $S \to S \setminus \{b_1\}$. Likewise, the sociable set of girls that cease to be sociable after the deletion of $b_1g_1$ correspond to the sociable set of girls on $B \cup G$. These two values have the same parity due to our induction hypothesis, so we are done. $\blacksquare$