While this solution is overkill, it made me happy. Construct a graph $G$ with members as vertices and edges iff people are friends. WLOG we assume that each person initially has 0 dollars. For each person $k = 1, \dots, 2011$, construct a vector $v_k \in \mathbb{Z}^{2011}$ describing the money change when person $k$ makes a move and also set $u_k = -v_k$. It is clear that $v_1 + \dots + v_{2011} = 0$. Then, the possible distributions are given by integer combinations of $v_1, \dots, v_{2011}$; i.e. \[a_1 v_1 + \dots + a_{2011} v_{2011}\]for $a_1, \dots, a_{2011} \in \mathbb{Z}$. If the problem condition holds, the set of such vectors must be $S = \{(x_1, \dots, x_{2011}) \in \mathbb{Z}^{2011} \mid x_1 + \dots + x_{2011} = 0\}$, and thus $v_1, \dots, v_{2011}$ must generate a subspace of dimension $\ge 2010$. However, since $v_1 + \dots + v_{2011} = 0$, the dimension must be $< 2011$, so it is exactly $2010$. This means the map $\mathbb{Z}^{2011} \to S$ given by \[(a_1, \dots, a_{2011}) \to a_1v_1 + \dots + a_{2011}v_{2011}\]is bijective. As a consequence, the map $\mathbb{Z}^{2010} \to S$ given by \[(a_1, \dots, a_{2010}) \to a_1v_1 + \dots + a_{2011}v_{2011} \quad \text{where} \; a_{2011} = -a_1 - \dots - a_{2010}\]is bijective too. Let $A = \begin{pmatrix} u_1 \\ \vdots \\ u_{2011} \\ \end{pmatrix}$. This is the Laplacian matrix for $G$, and by Kirchhoff's theorem, the determinant of the matrix $A'$ obtained by deleting the final row/column from $A$ is the number of spanning trees of $G$. However, as a consequence of the bijectivity from above, $|\det A'| = \pm 1$, so $G$ has exactly one spanning tree. Thus $G$ is a tree itself, finishing the proof. Similarly, in general, given a connected $G$ with $t$ spanning trees, the density of money distributions that can be achieved is $\tfrac{1}{t}$.

I know that the above works, but can one directly ascribe a dimension to a submodule (as opposed to subspace)?

Why $| \det A' |=1 $ ?

Anyone ???

A "linear map" from $\mathbb Z^n$ to itself is well-known to be bijective iff its determinant is $\pm 1$. In particular, if such a map did not have a determinant of $1$, there would be a prime $p$ (specifically one diving the determinant) such that the mod-$p$ reduction of said map would not be a bijection from $\mathbb F_p^n$ to itself, an obvious contradiction.

I do not undersrand... “Determinant of linear map”? How is that possbile? Who are the rows and columns ? Come on, guys, this is how the olympiad solutions are written?

Think, for example, in $\mathbb{Z}^2$. Let's think of a linear map $(x, y) \rightarrow (ax+by, cx+dy)$. The determinant of this map is trivially $ad-bc$. For this map to be bijective, $|ad-bc|$ must equal to $1$. Otherwise, take a prime $p$ dividing this determinant. Look at this map in $\pmod {p}$. This map cannot be injective as $p|ad-bc$. So this map cannot be injective in $\mathbb{Z}^2$.

But why bijective in Z^2 implies bijective in (Z/pZ)^2 for every prime p ?surjectivity follows, but how to prove injectivity ?

Function on N to N is injective but not injective in N/2N: f(4k)=4k+1,f(4k+1)=4k,f(4k+2)=4k+2,f(4k+3)=4k+3.

I think the argument is wrong...

dragonx111 wrote: Function on N to N is injective but not injective in N/2N: f(4k)=4k+1,f(4k+1)=4k,f(4k+2)=4k+2,f(4k+3)=4k+3. Quote: linear

meaning ? oh i see that my function is not linear but i still do not get the following: Literally, I see that if I have a bijective linear map from $\mathbb Z^n$ to itself, then it must be bijective in $\mathbb Z _p^n$ as well. Why ?

The technically best definition would probably be along the lines of "morphism of $\mathbb Z$-modules from $\mathbb Z^n$ to $\mathbb Z^n$", although this coincides with the more useful definition "linear map (aka morphism of vector spaces) from $\mathbb Q^n\to \mathbb Q^n$ for which a basis is pre-chosen, and under which the set of vectors with integer coordinates maps into itself." To answer the question, $\mathbb F_p^n$ is finite, so any map from it to itself is surjective iff it is injective iff it is bijective.

But i rkm0959 post, i do not see how he gets at p| ad bc implies noninjectivity. I am 16 and I am not aware of that higher algebra. A more elementary explanation

Probably not The idea is that if the determinant is zero over $\mathbb F_p$, then the kernel is nontrivial, violating injectivity. Edit: For what it's worth, Evan Chen's Napkin contains a fairly approachable exposition of linear algebra.

okay, thank you. EDIT: since yesterday(8.56 am) to today(3.44 pm), there's been an increment of at least 500 in the number of views of this thread.

CantonMathGuy wrote: Let $A = \begin{pmatrix} u_1 \\ \vdots \\ u_{2011} \\ \end{pmatrix}$. This is the Laplacian matrix for $G$, and by Kirchhoff's theorem, the determinant of the matrix $A'$ obtained by deleting the final row/column from $A$ is the number of spanning trees of $G$. Back to the problem. Kirchoff theorem applies for connected graphs only. How do we know that $G$ is connected ? If $G$ is connected, why is it connected ? NB If $G$ is not connected, it can be formed by a $K_{n-1}$ and an isolated vertex. And there are many other examples.

@dragonx 111 We can prove that the graph is connected. Use the condition about redistributing.

dragonx111 wrote: Back to the problem. Kirchoff theorem applies for connected graphs only. How do we know that $G$ is connected ? If $G$ is connected, why is it connected ? NB If $G$ is not connected, it can be formed by a $K_{n-1}$ and an isolated vertex. And there are many other examples. Suppose $G$ is not connected, then suppose it has two components $G_1$ and $G_2$. Suppose at the start the sum of balances in the two components are $s_1$ and $s_2$. Then obviously $s_1$ and $s_2$ are invariant under the moves, which violates the condition that any configuration is achievable.