Each one of $2001$ children chooses a positive integer and writes down his number and names of some of other $2000$ children to his notebook. Let $A_c$ be the sum of the numbers chosen by the children who appeared in the notebook of the child $c$. Let $B_c$ be the sum of the numbers chosen by the children who wrote the name of the child $c$ into their notebooks. The number $N_c = A_c - B_c$ is assigned to the child $c$. Determine whether all of the numbers assigned to the children could be positive.
Problem
Source: Turkey TST 2001 - P1
Tags: function, graph theory, combinatorics proposed, combinatorics
17.04.2013 18:23
There exists a number assigned to a child which is not positive. First to translate the problem in graph theory language. Given a digraph $G$, to each vertex $v$ is assigned a positive integer $n(v)$. For a vertex $v$ , let denote by $O(v)$ the set of all vertices $u$ which are directly connected with $v$ and direction is from $v$ to $u$ , i.e. all vertices out of $v$ , and denote by $I(v)$ all vertices $u$ connected with $v$ such that the direction is from $u$ to $v$. Lets define a function $f : V(G) \to \mathbb{Z}$ , $f(v)= \sum_{u\in O(v)} n(u) - \sum_{u\in I(v)} n(u)$. Prove that there exists $v\in V(G)$ s.t. $f(v) \leq 0$. Consider first the case $n(v)=1,\, v\in V(G)$. In this case it is easy to see that $\sum_{v\in V(G)} f(v) =0$, so it is impossible all of $f(v)$'s to be positive. Now we have a digraphs $G$ with $\max_{v\in V(G)} n(v)>1$. Suppose on the contrary $\forall v\in V(G): f(v)>0$. We will apply consecutively a transformation $T$ on $G$ described as follows. Let $m=n(v_1) = \max_{v\in V(G)} n(v)$. We delete the vertex $v_1$ and replace it with $m$ new vertices $v'_1, v'_2, \ldots, v'_{m}$ with $n(v'_i)=1,\,i=1,2,\ldots, m$ and connect each $v'_i$ with directed edge $(v'_i, u)$ to every $u \in O(v_1)$, also we connect every $u\in I(v_1)$ with every $v'_i$ with directed edge $(u, v'_i)$. Here WLOG we can consider that $O(v_1) \cap I(v_1) = \emptyset$ , because otherwise we can delete all pairs $(u,v_1);(v_1,u)$ without changing $f$. So let $G_1=T(G)$ is the new graph. It can be checked that the following properties hold: (i) $ f(v) $ does not change for all vertices left intact. (ii) $f(v'_i)=f(v_1)>0, i=1,2,\ldots,m $ (iii) $ \sum_{v\in G_1} f(v) > \sum_{v\in G} f(v)$ Therefore $f(v) > 0,\, \forall v\in V(G_1)$. Applying consecutevely this transformation $T$ we get graphs: $G_1=T(G), G_2=T(G_1),\ldots$. Obviously after a finite number of steps we will reach a graph $G_n$ with $n(v)=1 \,\, \forall v\in V(G_n) $. Thus it holds: $\sum_{v\in G} f(v) < \sum_{v\in G_1} f(v) < \ldots < \sum_{v\in G_n} f(v) =0$ which implies $\sum_{v\in G} f(v)< 0$ and there will exist $v_1\in G ,\, f(v_1)<0$ which is a contradiction.
18.04.2013 02:43
What a great solution! What is the motivation to make the transformation?
27.01.2022 09:28
Baris, actually it is not. Let $1,2,…,2001$ be the numbers of children $c_1,c_2,…,c_2001$ respectively. Let $c_1 $ wrote her notebook $\{2,3,…,2001\} $; $c_{2k} $ wrote her notebook $\{2k+1\}$ and $c_{2k+1} $ wrote her notebook $\{2k\}$. It is obvious that $\sum N_c\neq0$.
06.10.2023 21:58
Let's denote the number held by the $i$th child as $a_i$. Let's denote the number given to the $i$th child as $N_i$. We'll call this number the $i$th child's score. In the problem, we are asked to show that at least one of the $N_i$'s will not be positive. Let's also define the weighted score of the $i$th child as $W_i = a_i N_i$. Since $a_i$ is positive, the signs of $W_i$ and $N_i$ will be the same. Let's imagine that child $i$ writes child $j$ to the notebook. $W_i = a_i\left((\dots + a_j + \cdots ) - ( \cdots )\right )$ and $W_j = a_j\left( (\cdots) - (\cdots + a_i + \cdots)\right )$, so $\sum_i\limits W_i = 0$ will hold. In this case, at least one $W_i$ is not positive. Therefore, at least one $N_i$ is not positive.
07.10.2023 22:51
This is just a rewriting of xeroxia's solution. Denote the initial numbers by $c_1,\dots,c_N$ and the lists of students by $L_1,\dots,L_N$ ($N=2001$). As xeroxia noted, sign of $c_i N_i$ is the same as that of $N_i$, so it suffices to show the same for $c_iN_i$. To that end, we prove $\textstyle \sum_i c_iN_i = 0$, yielding the conclusion. Note that \begin{align*} \sum_i c_iA_i &= \sum_i \sum_{j:j\in L_i}c_ic_j \\ \sum_i c_i B_i &= \sum_i \sum_{j:i\in L_j}c_ic_j. \end{align*}Note that the right hand sides above are identical. We thus have the conclusion, as \[ \sum_i c_iN_i = \sum_i c_i(A_i-B_i)=0. \]