It is not a full solution, but I noted the following:

Well I don't know but it is very easy to prove for trees (it is a strong induction basically). Then I was hoping that there'd be a way to like bridge the gap between that and a graph that has cycles.

Same here; I proved it for all vertices of degree at most 2, and then remarked that mathematicians don't normally have more than 2 friends. Clearly the hardest problem on the USAMO this year.

We'll prove that if there exists a good configuration, then the number of good configurations is a power of two. Here's a basic sketch of it.

Here is a full solution:

Hm...I wonder are we allowed to submit alternate solutions to the USAMO people? My partial work for #6 was the first half of this, which will get much more credit I think if they know it can be finished with the same ideas. EDIT: Interestingly, the induction for the official solution is similar to a well-known process in algebraic graph theory called rank-two reduction of a binary adjacency matrix. It can be found in Algebraic Graph Theory by Godsil and Royle, p. 183. This was somewhat annoying as I was aware of this but didn't really remember the process, and also wasn't sure it would work...but it seems to be more or less the same spirit of induction.

K81o7 wrote: We'll prove that if there exists a good configuration, then the number of good configurations is a power of two. Here's a basic sketch of it.

That is a pretty interesting application of group theory to a combinatorics problem. I was wondering where you learned about such applications of group theory. Do you know of any resources that teach about applications of group theory to elementary combinatorics problems?

@Jacob: As always, you are king of linear algebra. This is why I think you really deserve to make the IMO: you're interested in the math itself more than most people. A lot of people didn't really pursue the problem after the competition. @calc rulz: I learned basically all of the group theory I know from the book Topics in Algebra (Herstein), I read about half of the group theory chapter. As for applying it to combinatorics problems, I don't know...I kinda just played around with some stuff and noticed the group structure. Once you have a set of things with a certain property (especially if those things are functions which create maps between objects of a certain kind, like this case), and a binary operation, if you have associativity, an identity, and the ability to invert, you might feel the group-ness and check if the thing is closed. That was quite a run on.

K81o7 wrote: @Jacob: As always, you are king of linear algebra. This is why I think you really deserve to make the IMO: you're interested in the math itself more than most people. A lot of people didn't really pursue the problem after the competition. Forgive me being negative, but it seems to me there are better things to do than go to the IMO if the math is all you're interested in. In recent times the IMO seems to emphasize techniques and preparation over the math, like with everyone trivializing 2007/5 by "Vieta jumping" or whatever. That said, I thought he was going to make the IMO because he's good at these kinds of problems anyway.

Well, I haven't failed to make the IMO team *yet*. Let's wait until we see the black MOP cutoff before we jump to conclusions.

JSteinhardt wrote: Well, I haven't failed to make the IMO team *yet*. Let's wait until we see the black MOP cutoff before we jump to conclusions. How did you do actually?

I solved 1 and 4 pretty definitely. Number 5 I tried to prove for all reals instead of non-negative, so my proof was something like "in the special case that $ r_1,r_2,r_3 > 0$, we can do this...then in all other cases, (insert bogus proof)". The consensus seems to be that it's worth a 7 anyways. And number 6 I have what is said in this thread, and probably about 2 points of partial credit out of 2 and 3...so probably a 25ish.

Jacob, I'm honestly still wondering why you didn't make Intel Finalist. You're clearly as qualified as the math kids I met there Anyway, there are some great ideas in this thread. The only interesting one I had: one way to interpret the partition we desire is as a partition into two graphs with Eulerian circuits.

JSteinhardt wrote: Well, I haven't failed to make the IMO team *yet*. Let's wait until we see the black MOP cutoff before we jump to conclusions. Who's jumping to conclusions here? Anyways, I hear Lars solved this on the test itself, I wonder if he has the same solution as the official solution (which I haven't read yet, I want to find a combinatorial solution myself when I get time)... And did he get all 6 then I wonder?

t0rajir0u wrote: Jacob, I'm honestly still wondering why you didn't make Intel Finalist. You're clearly as qualified as the math kids I met there Anyway, there are some great ideas in this thread. The only interesting one I had: one way to interpret the partition we desire is as a partition into two graphs with Eulerian circuits. Well it's possible that my project wasn't interesting enough...I mean it was pretty much just a random problem I came up with that was interesting and tangentially related to some current research. I think the problem I'm working on now might have worked better, but alas I'm half a year too late (it has to do with a conjecture on the chromatic number of a certain infinite graph, and I got to use all sorts of high-powered stuff to prove that there exists no finite coloring...although it's only 5 pages instead of 20, so who it might have looked kind of silly next to all of the 20-page papers...I kind of wish I was still eligible for Intel so that I could see what would have happened). Also, in response to Krishanu: Quote: That said, I thought he was going to make the IMO because he's good at these kinds of problems anyway. The past tense there seems to imply that he doesn't still think I will make it. But I could be misinterpreting. Anyways it would be cool to make the IMO team still, though I'd be happy with just going to MOP again.

JSteinhardt wrote: Quote: That said, I thought he was going to make the IMO because he's good at these kinds of problems anyway. The past tense there seems to imply that he doesn't still think I will make it. Who's jumping to conclusions now? Don't worry about it Jacob, I'm sure you'll do fine.

t0rajir0u wrote: Jacob, I'm honestly still wondering why you didn't make Intel Finalist. You're clearly as qualified as the math kids I met there Siemens Finalists have a history of not being chosen by Intel, don't they?

Tell that to Isha Jain I'm honestly not sure what to think about the Intel judging process. The most optimistic answer I can give is that the Siemens and Intel competitions aren't looking for quite the same thing.

Okay so I'm trying to understand this with my limited linear algebra background... JSteinhardt wrote: Make the obvious re-interpretation as a graph. Let $ f : G \to \{0,1\}$ be an indicator function with $ f(v) = 0$ if a vertex is in the first partition and $ f(v) = 1$ otherwise (this corresponds, in the actual problem, to putting a mathematician in the first or second room). Then look at $ f$ as a function into the field with two elements, $ F_2$. I don't get what you mean by field here. Then again, my knowledge of fields amounts to the information gleaned from the wikipedia article that I just skimmed. For it to be a field, don't we need two operators "+" and "*" ? + 0 1 0 0 1 1 1 0 * 0 1 0 0 0 1 0 1 The * operator could make sense in terms of adjacency matrices but I don't get how a function going into a field is saying anything. I don't understand what these operations mean in the context of the problem... JSteinhardt wrote: Let $ V$ be the vector space of all such functions. I don't see what is going on here. What do you mean by 'all functions' If it is a vector space, what are the + and * operations? JSteinhardt wrote: Define the linear operator $ A : V \to V$ as $ (Af)(v) = \sum_{v \sim w} f(v) - f(w)$ where $ \sim$ denotes adjacency. How is A a linear operator? What does Af mean? Since I'm not understanding what is going on at all, I'll stop here and look at the rest of the proof once I understand the notations, etc.

Altheman wrote: I don't get what you mean by field here. Then again, my knowledge of fields amounts to the information gleaned from the wikipedia article that I just skimmed. For it to be a field, don't we need two operators "+" and "*" ? The field with two elements is isomorphic to the integers $ \bmod 2$ with addition $ \bmod 2$ and multiplication $ \bmod 2$. Altheman wrote: JSteinhardt wrote: Let $ V$ be the vector space of all such functions. I don't see what is going on here. What do you mean by 'all functions' If it is a vector space, what are the + and * operations? Both are the usual operations. (I believe the field of scalars is just $ F_2$.) "All functions" means exactly what it says - all functions satisfying the above properties. Altheman wrote: JSteinhardt wrote: Define the linear operator $ A : V \to V$ as $ (Af)(v) = \sum_{v \sim w} f(v) - f(w)$ where $ \sim$ denotes adjacency. How is A a linear operator? What does Af mean? $ (Af)(v)$ is the function (of $ v$) that the operation $ A$ takes $ f(v)$ to. A linear operator satisfies $ A(cf + dg) = c Af + d Ag$. The fundamental notion here is that of a function space.

Lemma: Let $A\in\mathbb{F}_2^{n\times n}$ be symmetric, and let $d=\mathrm{diag}A\in\mathbb{F}_2^n$ be the diagonal of $A$. Then, $\mathrm{diag} A\in\mathrm{im} A$. Proof of Lemma: We show that $d\in(\mathrm{null}A)^\perp=\mathrm{im}A$. Suppose $Ax=0$. We want to show $d\cdot x=0$. Let $I=\{i:x_i=1\}$, and let $B$ be the restriction of $A$ on to $I$. We have that $B1=0$ where $1$ us the all $1$s vector. Adding up all the rows of the equation $B1=0$, we see that the off diagonal terms cancel because $B$ is symmetric and we are working mod $2$, so we see that $d'\cdot 1=0$ where $d'$ is the restriction of $d$ on to $I$, so we have $d\cdot x=0$, as desired. Thus, the claim, and the problem are proven. $\blacksquare$ Let $L$ be the laplacian of the friend graph. It is not hard to see that the problem is equivalent to showing that the number of solutions to $Lv=d$ in $\mathbb{F}_2$ is a power of $2$, where $d$ is the vector of degrees. By the lemma, we have that there is at least one solution, call it $v_0$. Therefore, $L(v-v_0)=d$. Let the dimension of $\mathrm{ker}(L)$ be $k$. It is clear that the number of solutions is then $2^k$. Note that $(1,\ldots,1)\in\mathrm{ker}(L)$, so $k\ge 1$, so the problem is complete. $\blacksquare$

Similar to this 2003 Tuymaada problem. https://artofproblemsolving.com/community/c6h1837571p12329351

Interpret the problem as a graph. Consider the adjacency matrix of the graph, and then on $a_{i,i}$ change it from a $0$ to a $1$ if the degree of vertex $i$. Call this matrix $A$. Now, consider a vector $v$, where the ith entry is $1$ if the ith mathematician is in the first room, and $0$ otherwise. Clearly if $v$ was a working distribution, then $Av$ is equal to the main diagonal of $A$, call this main diagonal vector $u$. Therefore, $Av = u$, where $A,u$ are fixed. By grobber's lemma, there exists such a $v$. Furthermore, if we let $S$ be the kernel of $A$, then for any $t\in S$, we have $v + t$ is also a working solution; all solutions must be generated this way. By taking the basis of this kernel, we clearly get that the number of solutions is a power of $2$.

How do you motivate the inductive step for the first part

Suppose that the mathematicians are named $1,2,\ldots,n$. Name the two rooms "room 1" and "room 310", and let $x_i$ be the indicator that $i$ is in room 1. Work in $\mathbb{F}_2$. Let $S_i$ be the set of $i$'s friends. Consider the system of $n$ equations of the form $\sum_{j\in S_i}(x_i+x_j)=|S_i|$; note that if they are simultaneously satisfied, we have a valid construction. Since the set of solutions is an affine subspace of $\mathbb{F}_2^n$, either we have no solutions or we are done (at least two solutions exist, if any, by swapping the rooms). Suppose FTSOC that some linear combination of our equations sum to $0=1$. This means that there exists a subset $V$ of the friendship graph such that every vertex outside of $V$ is adjacent to an even number of vertices in $V$, and the number of edges between $V$ and other vertices is odd (every edge within $V$ is counted twice), which fails mod $2$.

I realize that nobody ever posted the combo-only solution (avoiding linear algebra altogether). I am copy-pasting what I have from the official USAMO 2008 solutions file. Let n be the number of participants at the conference. We proceed by induction on n. If n = 1, then we have one participant who can eat in either room; that gives us total of 2 = 21 options. Let n ≥ 2. The case in which some participant, P , has no friends is trivial. In this case, P can eat in either of the two rooms, so the total number of ways to split n participants is wice as many as the number of ways to split (n − 1) participants besides the participant P . By induction, the latter number is a power of two, $2^k$, hence the number of ways to split n participants is $2 \cdot 2^k = 2^{k+1}$, also a power of two. So we assume from here on that every participant has at least one friend. We consider two different cases separately: the case when some participant has an odd number of friends, and the case when each participant has an even number of friends. --------------------------------------------------------- Case 1: Some participant, Z, has an odd number of friends. Remove Z from consideration and for each pair (X, Y) of Z’s friends, reverse the relationship between X and Y (from friends to strangers or vice versa). CLAIM. The number of possible seatings is unchanged after removing Z and reversing the relationship between X and Y in each pair (X, Y) of Z’s friends. Proof of the claim. Suppose we have an arrangement prior to Z’s departure. By assumption, Z has an even number of friends in the room with him. If this number is 0, the room composition is clearly still valid after Z leaves the room. If this number is positive, let X be one of Z’s friends in the room with him. By assumption, person X also has an even number of friends in the same room. Remove Z from the room; then X will have an odd number of friends left in the room, and there will be an odd number of Z’s friends in this room besides X. Reversing the relationship between X and each of Z’s friends in this room will therefore restore the parity to even. The same reasoning applies to any of Z’s friends in the other dining room. Indeed, there will be an odd number of them in that room, hence each of them will reverse relationships with an even number of individuals in that room, preserving the parity of the number of friends present. Moreover, a legitimate seating without Z arises from exactly one arrangement including Z, because in the case under consideration, only one room contains an even number of Z’s friends. Thus, we have to double the number of seatings for (n − 1) participants which is, by the induction hypothesis, a power of 2. Consequently, for n participants we will get again a power of 2 for the number of different arrangements. --------------------------------------------------------- Case 2: Each participant has an even number of friends. In this case, each valid split of participants in two rooms gives us an even number of friends in either room. Let (A, B) be any pair of friends. Remove this pair from consideration and for each pair (C, D), where C is a friend of A and D is a friend of B, change the relationship between C and D to the opposite; do the same if C is a friend of B and D is a friend of A. Note that if C and D are friends of both A and B, their relationship will be reversed twice, leaving it unchanged. Consider now an arbitrary participant X different from A and B and choose one of the two dining rooms. (Note that in the case under consideration, the total number of participants is at least 3, so such a triplet (A, B; X) can be chosen.) Let A have m friends in this room and let B have n friends in this room; both m and n are even. When the pair (A, B) is removed, X’s relationship will be reversed with either n, or m, or m + n − 2k (for k the number of mutual friends of A and B in the chosen room), or 0 people within the chosen room (depending on whether he/she is a friend of only A, only B, both, or neither). Since m and n are both even, the parity of the number of X’s friends in that room will be therefore unchanged in any case. Again, a legitimate seating without A and B will arise from exactly one arrangement that includes the pair (A, B): just add each of A and B to the room with an odd number of the other’s friends, and then reverse all of the relationships between a friend of A and a friend of B. In this way we create a one-to-one correspondence between all possible seatings before and after the (A, B) removal. Since the number of arrangements for n participants is twice as many as that for (n − 2) participants, and that number for (n − 2) participants is, by the induction hypothesis, a power of 2, we get in turn a power of 2 for the number of arrangements for n participants. The problem is completely solved. This problem was suggested by Sam Vandervelde.

Here is our proof for why it is always possible to split the mathematicians between the two rooms: https://calimath.org/pdf/USAMO2008-6-corollary.pdf And we uploaded the solution with motivation to: https://youtu.be/rR3iyhQGZ6E Next week, we will upload the finished proof for the full problem on our website and our Youtube channel.

Here is our solution: https://calimath.org/pdf/USAMO2008-6.pdf And we uploaded the solution with motivation to: https://youtu.be/A5w90STbHec The operation described in the second step of the solution @2above is equivalent to$\,\oplus_A w \ominus A \ominus B \ominus w$.

v_Enhance wrote: Since the number of arrangements for n participants is twice as many as that for (n − 2) participants, and that number for (n − 2) participants is, by the induction hypothesis, a power of 2, we get in turn a power of 2 for the number of arrangements for n participants. The problem is completely solved. I think the number of arrangements for $n$ participants should be equal to that for $(n - 2)$ participants.

Let the rooms be "hall of arts" and "stever lounge", and number the mathematicians $1$ through $n$. Work in $\mathbb{F}_2$; let $x_i=1$ iff mathematician $i$ is in hall of arts. Then the problem is equivalent to showing that the following system of $n$ equations has $2^k$ solutions for some $k \geq 1$. This system is described as follows: if some mathematician $i$ has an even number of friends, then $\sum_{i,j\text{ friends}} x_j=0$, and if $i$ has an odd number of friends, then $x_i+\sum_{i,j\text{ friends}}x_j=1$. For "linear algebra reasons", the number of solutions is automatically a power of $2$ or zero, and furthermore solutions come in pairs by swapping the rooms, so it suffices to show that a solution exists. If no solution exists, some nonzero sum of some of the equations must yield $0=1$; in particular, we must sum an odd number of "odd friends" equations. Take the obvious graph theoretic interpretation and call a subset $S$ of the vertices janitorial if, when we add all of the edges adjacent to all of the vertices $S$ with multiplicity, every vertex is adjacent to an even number of edges. It is clear that finding an aforementioned nonzero sum is equivalent to finding a janitorial subset with an odd number of odd-degree vertices; I will prove that no such set exists. First off, any such set must have at most $n-2$ vertices: clearly the set with $n$ vertices (i.e. all of them) must contain an even number of odd-degree vertices by double-counting, and if a set with $n-1$ vertices exists, it therefore must exclude an odd degree vertex. But this odd degree vertex is adjacent to each of its edges once, hence adjacent to an odd number of edges: contradiction. If some set $S$ exists, we may then take two vertices $v \neq w$ not in it. Now, delete $v$, and take all of the edges connected to $v$ (of which there are an even number), and attach them to $w$. Then reduce edges "modulo 2": if some pair of vertices has more than $1$ edge between then, subtract an even number, so that there are either $0$ or $1$ edges between any pair of vertices. It is not hard to see that $S$ is still a janitorial set with an odd number of odd-degree vertices of the resulting graph after these changes. Since clearly no such set exists when $n=1$, by downwards induction we obtain the desired contradiction. $\blacksquare$ Remark: I don't think the immediate parity contradiction from "odd number of edges + every vertex has even number of adjacencies" is valid? Among other doubts I have, on the graph which is a triangle and an extra vertex with degree $1$, by taking one vertex of degree $1$ and one of degree $2$ we find a set producing an odd number edges such that there are $2$ vertices with an even number of adjacencies and $2$ with an odd number of adjacencies. Unless the parity argument is deeper, this should be "indistinguishable" from all four vertices having an even number of adjacencies.

It's grobbin time. Represent mathematicians as elements of the adjacency matrix $M$ in ${\mathbb F}_2^{n^2}$. Define the matrix \[ N = \begin{bmatrix} m_0 & 0 & \dots & 0 \\ 0 & m_1 & \dots & 0 \\ \vdots & \vdots & \ddots & 0 \\ 0 & 0 & 0 & m_n \end{bmatrix} \]where $m_i$ is the $i$th element of $M \cdot 1$. In other words, $N = M \cdot 1 \cdot \operatorname{id}$. Then we claim that $v \in {\mathbb F}_2^n$ is a valid assignment of mathematicians to rooms if and only if \[ (M + N) \cdot v = M \cdot 1. \]Let $A$ represent the room of $1$s in $v$. Elementwise, this follows since $M \cdot v$ calculates the number of friends $\pmod{2}$ that are in $A$, and $N \cdot v$ is the total number of friends when not in $A$ and else $0$. Since $M \cdot 1$ is the diagonal of $(M + N)$, it follows by grobber's lemma that at least one solution $s_0$ exists. Then, if $S$ is the solution set, it then follows that $\{s - s_0 \mid s \in S\}$ forms a vector space and thus has $2^k$ elements as desired.

It's not grobbin time Assume the are $n$ mathematicians, represent the $i$'th mathematician $M_i$ as a vector in $v_i \in \mathbb{F}_2^n$. The $j$'th entry in $v_i$ is $1$ iff $M_i$ and $M_j$ are friends, and the $i$'th entry in $v_i$ is $1$ iff $M_i$ has an odd number of friends. Waiving some detail, we can get all arrangements of mathematicians by subsets adding $v_1,v_2, \ldots, v_n$ to the vector $0$, and a set of vectors work if they add up to $0$. But, all the sets of vectors that add up to $0$ create an $\mathbb{F}_2$ vector space $V$ and thus have magnitude some power of $2$, assuming it is non-empty. So, all that is left is to show $V$ is non-empty. To say, there is at least one way to arrange the mathematicians so that each mathematician has an even number of other mathematicians in their room. We induct on the number of mathematicians. For basis, if we have $1$ mathematician then it is trivial. For the inductive step, assume we have some graph $G$ of $k$ mathematicians and we want to add one new mathematician to the graph $m$. We can do this by splitting into two cases. Case 1: Some vertex of $G \cup \{m\}$ has odd degree. Remove that vertex, arrange the mathematicians into the two rooms that work which we can do by the hypothesis, and then add the removed mathematician back. There will always be a room for the removed mathematician since one room has an even number of friends of the removed mathematician while the other has an odd number of friends of the removed mathematician. Case 2: No vertex of $G \cup \{m\}$ has odd degree. We can just put all mathematicians in the same room So, we are done. $\blacksquare$

trivel by gallai's theorem and basic algebraic graph theory first sol essentially reproves gallai's theorem Solution 1. Let $G=(V,E)$ be a graph. Let $\mathcal{V}:=\mathcal{V}(G)$, $\mathcal{E}:=\mathcal{E}(G)$, $\mathcal{C}:=\mathcal{C}(G)$, and $\mathcal{C}^*:=\mathcal{C}^*(G)$ be the vertex, edge, cycle, and cut space, respectively. Let $\psi(G)$ be the set of cuts $E(A,B)\in\mathcal{C}^*$ with $E(G[A]),E(G[B])\in\mathcal{C}$. Note that the problem essentially states that $|\psi(G)|$ is a power of $2$ for all $G$ ($|\psi(G)|$ is actually $2$ times the quantity in the problem). Lemma. If every vertex of $G$ has even degree, then $\psi(G)$ is a power of $2$. Proof. Note that if $E(A,B)\in\mathcal{C}^*$ is a cut, then $E(G[A])+E(G[B])=E+E(A,B)$ is in $\mathcal{C}$ if and only if $E(A,B)\in\mathcal{C}$. Thus $\psi(G)=\mathcal{C}\cap\mathcal{C}^*$ has cardinality a power of $2$. $\square$ We prove $|\psi(G)|$ is a power of $2$ by induction on $|G|$ with the base case trivial. If there are no vertices of odd degree, we are done by Lemma. So let $v\in G$ be a vertex of odd degree. Let $K$ be the complete graph on $N(v)$. Let $G'$ be the graph on $V(G)\setminus\{v\}$ with edge set being the symmetric difference of $E$ and $E(K)$. Then $|G'|=|G|-1$ so by the induction hypothesis, $|\psi(G')|$ is a power of $2$. Consider the map $M:\psi(G)\rightarrow\psi(G')$ given by \[ E_G(A,B)\mapsto E_{G'}(A\setminus\{v\},B) \]where (WLOG) $v\in A$. It is not hard to check this is a valid map. Consider the cut $D':=E_{G'}(X,Y)\in\psi(G')$ with $E(G'[X]),E(G'[Y])\in\mathcal{C}(G')$. The only candidates in $\psi(G)$ that $M$ could map to $D'$ are $E_G(X\cup\{v\},Y)$ and $E_G(X,Y\cup\{v\})$. Since $d_G(v)$ is odd, exactly one of $|N_G(v)\cap X|$ and $|N_G(v)\cap Y|$ is odd. WLOG $|N_G(v)\cap X|$ is odd. Then $v$ has odd degree in $G[X\cup\{v\}]$ so $E_G(X\cup\{v\},Y)\not\in\psi(G)$. It is not hard to check that $E(G[X]),E(G[Y\cup\{v\}])\in\mathcal{C}$ so $D:=E_G(X,Y\cup\{v\})$ is the unique element of $\psi(G)$ mapping to $D'$. It follows that $M$ is a bijection so $|\psi(G)|=|\psi(G')|$ is a power of $2$. $\square$ Easier solution: Solution 2. Let $B$ be the incidence matrix of $G$. Note that $B^\top(\mathcal{V})$ is precisely $\mathcal{C}^*$. So we are solving $BB^\top v=B(E)$. By Gallai (exercise 1.39 in Diestel Graph Theory, 4th Edition), there exists a solution $u$ so $BB^\top u=B(E)$. Thus we are solving $BB^\top(v-u)=0$, which has solution set $u+\mathrm{ker}(BB^\top)$. This has cardinality a power of $2$, as desired. $\square$

I think no big difference to the combi proof, but here is the linear algebra solution: First if there exists a cycle delete them all and the answer don't change, so WLOG the graph is a tree. Let $\mathcal M\in\mathbb F_2^{n\times n}$ be the incidence matrix, where $m_{i,i}=1$ and $m_{i,j}=1$ iff $i\sim j.$ We need to calculate the number of $V$ such that $\mathcal M\cdot V=\begin{pmatrix}1\\1\\\ddots\\1\end{pmatrix}:=I.$ Note that the number of $V$ to $M\cdot V=J$ is $0$ or another value. This is because if $MV=J_1,MV=J_2$ both have solution and the number of first one is more, then $J_1-J_2$ have at least one solution $V_0,$ therefore consider $V-V_0$ ($V$ is the solution of $MV=J_1$) we get contradiction. Since the linear combination vectors that have solution also have solution, the number of $J$ that have solution is power of $2.$ So now we only need to prove $MV=I$ have at least one solution. This is because the graph have no cycle, so expanding $\det M$ there is only $m_{1,1}\cdots m_{n,n}$ is nonzero, so $\det M\neq 0,$ done.$\Box$

Wow, I did not expect such heavy linear algebra problem to appear in contest. It certainly amazes me. There are already full linear algebra solutions above that is clear and precise. So I'll write some motivations. The result that there are $2^k$ is weird. Maybe one would try inducting or double-counting, but it feels natural to use group theory to show that the valid configuration forms a "subgroup" of all 2-colorings to directly get the result that there are $2^k$ of them, or alternatively do it in a linear algebra way, that is, solving system of equations. (I haven't tried group theory yet, but I would certain do it later!) So trying many small cases, like considering permutations of vertices that preserves validity of any 2-coloring configurations, and see how each subgroups of permutation acts on what exact 2-colorings, you would see permutations that preserves some $k$ vertices $v_1, v_2, ..., v_k$ are always acting on all configurations with exactly $m$ vertices that are colored, say, in red, with $m \leq k$. This is trivial, but what is not is that one of $m=0$, $m=k$ or when a vertex's coloring is fixed, $m= {n \choose k}$ for all odd/even $k$ must hold. This agrees with the result that the number of configurations is some power of $2$. In the last case, the condition that holds for all odd/even $k$ doesn't feel natural, it feels more like the vertex colors are "constrained" by some condition. I formed the constrains using variables and matrices over $aR+bB$, $a,b \in Z/2Z$ where $R, B$ are the variables that represent color red and blue, then system of equation can be represented and thus, if any solution exists, there must be $2^k$ of them. After reading the solutions I feel stupid that I missed out the most important fact that the solution must exist for the proof to work. Indeed, we do not have to consider vector space over $aR+bB$, $a,b \in Z/2Z$, we can instead just use the field $\mathbb{F}_2$ and reform questions into $$(A + diag(u))v = u.$$$A$ is the adjacency matrix, $diag(u)$ denotes the matrix with diagonal $u$. Notice that $A$ has diagonal entries all $0$. By properties of inner product space one can deduce that a solution must exist.