Let the graph $ G$ be defined as follows. Every person is a vertex. Two vertices are connected iff they are acquainted. The graph is a tree because it is connected and there are no loops. Let $ ||v||$ denote the real number associated with the vertex $ v$. We shall use the property that every tree has at least two vertices of degree 1. (i) If the vertex with degree 1 is a woman say $ w_1$:If the person acquainted to $ w_1$ is a man say $ m_1$, then we have $ ||w_1||=||m_1||$. We can now eliminate $ w_1$ from $ G$ and look out for the vertex with degree 1 in $ G$. If the person acquainted to $ w_1$ is a woman say $ w_2$ and if $ w_3,\dots,w_i,m_1,\dots,m_j$ are the acquainted to $ w_2$ ,then \[ (i+j+1)||w_2||=w_1 +\sum_{k=3}^{k=i}w_k+\sum_{k=1}^{k=j}m_k\] \[ or\quad (i+j)||w_2||=\sum_{k=3}^{k=i}w_k+\sum_{k=1}^{k=j}m_k\quad \dots \quad (1)\] Since $ w_1$ has nothing to do with $ G$ we may remove it and then look for the vertex with with degree 1. (ii) If the vertex with degree 1 is a man say $ m_1$: If the vertex acquainted to $ m_1$ is again a man, we may safely eliminate the vertex $ m_1$ as it is of no consequence and look out for the vertex with degree 1. If the vertex acquainted to $ m_1$ is a woman say $ w_1$ then $ ||w_1||=||m_1||$. We may eliminate the vertex $ m_1$ and look out for the vertex with degree 1. This process is ends after some time as the population is finite. In the last step we would determine the real number associated with some woman say $ w_i$ by using the calculation analogous to (1). Going back one step previous, we can now get the real number associated with $ w_j$ and so on to get the real number associated with every woman.

srikanth wrote: The graph is a tree because it is connected and there are no loops. Sorry, but I don't understand how you deduced this. Could you explain your method?

orl wrote: ... Every two citizens $ x$ and $ x'$ either know each other or do not know each other. Moreover, if they do not, then there exists a chain of citizens $ x = x_0, x_1, \ldots, x_n = x'$ for some integer $ n \geq 2$ such that $ x_{i-1}$ and $ x_i$ know each other. @cosinator: $ G$ has people as vertices and there is an edge between any two vertices if they are acquainted. Firstly, $ G$ is connected. Secondly there is no loop in the graph. If there existed a loop in the graph then there exists an element $ x_1$ which is connected to some $ x_k\neq x_1$ through two different ways. Let $ x_0$ and $ x_n$ be the first elements one encounters when moving from $ x_1$ to $ x_k$ in the two ways respectively. $ x_1$ is acquainted to $ x_0$.We may reach from $ x_1$ to $ x_0$ by looping through the second way that passes through $ x_n$. But the existence of the second way is contradicted by the statement in quote which says that "Every two citizens $ x$ and $ x'$ either know each other or do not know each other. Moreover, if they do not, then there exists a chain of citizens"

Thank you for the clarification.

srikanth wrote: But the existence of the second way is contradicted by the statement in quote which says that "Every two citizens $ x$ and $ x'$ either know each other or do not know each other. Moreover, if they do not, then there exists a chain of citizens" You are misunderstanding this sentence. It does not say that "$ x$ and $ x'$ are not acquainted if and only if there exists such a chain," rather it says that if $ x$ and $ x'$ are not acquainted then there is such a chain (but there could also be such a chain for some pair of acquainted vertices). This sentence gives you a connected graph; it does not give you a tree.

JBL wrote: but there could also be such a chain for some pair of acquainted vertices I would not agree with this. On the other hand, if the graph is not a tree then the proposotion does not hold. Consider the graph $ G'$(image titled 'nottree'). Then the system of equations does not have a solution. mathematica code: In[87]:= m={{2,-1,0,0,0},{-1,3,-1,0,-1},{0,-1,2,-1,0},{0,0,-1,2,-1},{0,-1,0,-1,2}} Out[87]= {{2,-1,0,0,0},{-1,3,-1,0,-1},{0,-1,2,-1,0},{0,0,-1,2,-1},{0,-1,0,-1,2}} In[88]:= m.{x,y,z,r,h}=={a,0,0,0,0} Out[88]= {2 x-y,-h-x+3 y-z,-r-y+2 z,-h+2 r-z,2 h-r-y}\[Equal]{a,0,0,0,0} In[89]:= Solve[%,{x,y,z,r}] Out[89]= {} I hope orl would tell us what the question actually intends.

I don't know what you told Mathematica to do, but I do know that the problem is perfectly fine for any kind of connected graph, not just trees . It all boils down to showing that a certain linear system with the same number of equaqtions and unknowns (namely the number $ k$ of female citizens) has a unique solution. Write this sistem as $ Ax = b$, where $ A$ is a $ k\times k$ real matrix and $ x$ and $ b$ are column vectors of length $ k$. Now, if $ Ax = 0$ has the unique solution $ x = 0$, then you're done: it follows that $ A$ is invertible, so $ Ax = b$ does indeed have a unique solution. Now use the connectedness of the graph and the fact that there is at least one male citizen to prove that $ Ax = 0$ has the unique solution $ x = 0$. In male/female citizens languange, this means: show that in the hypotheses of the problem, if all the males declare their ages to be $ 0$, then the ages of all citizens are $ 0$. This should be easy enough: assuming the maximal age is $ M > 0$, consider a female with age $ M$ and see what happens (its neighbors must also have age $ M$, then the neighbors' neighbors also have age $ M$, etc., until you reach a male citizen, whose age is $ 0 < M$; you got the desired contradiction); similarly, you can show that the minimal age is $ 0$ as well. Another way to state the problem: The discrete Dirichlet problem has a unique solution on a finite connected graph as long as the boundary is non-empty. Here the graph is the one we've all been working on, and the "boundary" is the (non-empty, according to the hypothesis) set of male citizens.

This may be trivial, but I think there is one more step to be made: we need $ A$ to be invertible and we need for each positive vector $ b$ that the solution $ x$ to $ Ax = b$ also be a positive vector. srikanth, I also don't understand what you were trying to get Mathematica to do, but whatever it was, it didn't work. If there's only one male citizen then it's trivial that at least one solution exists, when all residents have the same age.

I did forget that we were working with ages and so the solution has to be positive, but technically, we don't need to prove that. The problem asks to show that we can determine all ages given the ages of the males. We already know the solution exists and it's positive (the people have positive ages - that much we know), so we only need to prove the uniqueness. Admittedly, my "reformulation" of the problem isn't really an exact reformulation, but it's in the ballpark .

Here is a not-solution that is pretty amusing nonetheless: After converting everything to a connected graph $G$, view the men as voltage sources whose voltages whose potential is equal to their age, and view the edges of the graph as $1 \ \Omega$ resistors. We claim that the potential at each women is equal to the average of the potential of its neighbors. Indeed, $V=IR=I$, so by Kirchoff's junction rule, \[ \sum_{\text{neighbors}} V_{\text{neighbor}} - V_{\text{her}} = 0 \] and the claim follows. Now by the properties of the physical world, there is one equilibrium point, so we win.

Let a1, a2, . . . , am be the ages of the male citizens (m ≥ 1). We claim that the age of each female citizen can be expressed in the form c1a1+· · ·+cmam for some constants ci ≥ 0, and we will prove this by induction on the number n of female citizens. The claim is clear if n = 1. Suppose it holds for n and consider the case of n+1 female citizens. Choose any of them, say A of age x who knows k citizens (at least one male). By the induction hypothesis, the age of each of the other n females is expressible as c1a1 + · · · + cmam + c0x, where ci ≥ 0 and c0 + c1 + · · · + cm = 1. Consequently, the sum of ages of the k citizens who know A is kx = b1a1 + · · · + bmam + b0x for some constants bi ≥ 0 with sum k. But A knows at least one male citizen (who does not contribute to the coefficient of x), so b0 ≤ k−1. Hence x = b1a1+···+bmam/k-b0 and the claim follows.

vickymano wrote: Let a1, a2, . . . , am be the ages of the male citizens (m ≥ 1). We claim that the age of each female citizen can be expressed in the form c1a1+· · ·+cmam for some constants ci ≥ 0, and we will prove this by induction on the number n of female citizens. The claim is clear if n = 1. Suppose it holds for n and consider the case of n+1 female citizens. Choose any of them, say A of age x who knows k citizens (at least one male). By the induction hypothesis, the age of each of the other n females is expressible as c1a1 + · · · + cmam + c0x, where ci ≥ 0 and c0 + c1 + · · · + cm = 1. Consequently, the sum of ages of the k citizens who know A is kx = b1a1 + · · · + bmam + b0x for some constants bi ≥ 0 with sum k. But A knows at least one male citizen (who does not contribute to the coefficient of x), so b0 ≤ k−1. Hence x = b1a1+···+bmam/k-b0 and the claim follows. Why we need sum(ci)=1?

Let there be $n \geq 3$ female citizens (cases $n=1$ and $n=2$ can be checked directly). Let $f_i$ be the age of female citizen $i$. Let $a_{ij}=1$ if female citizens $i,j$ are connected and $a_{ij}=0$ otherwise. Then we have a system of equations of kind $p_if_i-a_{1i}f_1- \ldots -a_{ni}f_n=q_i$, where $p_i \geq a_{1i}+ \ldots +a_{ni}$. This system has a unique solution unless there is a linear combination of such equations with coefficients of all $f_i$ being $0$. Let such a linear combination exist where we multiply $i$-th equation by $c_i$, and not all of them $0$. Then take $j$ such that $|c_j|$ is largest. Then since $|c_jp_j| \geq |c_j(a_{1j}+ \ldots +a_{nj})| \geq |c_1a_{1j}+ \ldots +c_na_{nj}|$, so the coefficient of $f_j$ is not $0$ unless $|c_k|=|c_j|$ for all $k$ such that $a_{kj}=1$ and $j$th female isn't connected to any males. Then apply same logic to all her female friend, then to their friends and so on until we hit a female who is connected to a male (this will happen as there is at least one male and the graph is connected).

Nobody has this solution yet? the problem is quite concerning :eyes: The solution is that the age of each citizen is the expected value of the age of the first male citizen reached by following a random walk on the graph starting from them. Clearly, this works by states. We now show that this is unique. Consider a person $p$ with age $a_p$. Now, we "expand" $a_p$ in steps. In each step, we replace each $a_i$ in the expansion with the average of all its neighbors if $i$ is female, and don't change it if it is male. Thus, the coefficent of $a_i$ after $n$ steps is the probability of a random walk starting at $p$ and stopping on male being at $i$ after $n$ steps. In particular, such a walk reaches a male eventually with probability $1$ (e.g, if $d$ is the diameter of the graph, there is at least a $1$ in $n^d$ chance of winning every $d$ moves), so the limit of this expression is some linear combination of the ages of the males, and we are done as this means the solution is unique.