Twenty children, ten boys and ten girls, are standing in a line. Each boy counted the number of children standing to the right of him. Each girl counted the number of children standing to the left of her. Prove that the sums of numbers counted by the boys and the girls are the same.
Problem
Source:
Tags: Sum, algebra
18.04.2021 12:18
Replace $10$ with $n$ and proceed by induction on $n$, the base case being trivial. Now we assume that the statement is true for $n$ and prove it for $n+1$. Let us start with an initial line of $n$ boys and $n$ girls and randomly add one extra boy, labelled $B$, and one extra girl, labelled $G$ so that there are now $n+1$ girls and $n+1$ boys in the new line. We want to prove that the number of extra (that is, new) people each boy counts is equal to the number of extra people each girl counts (and finish using the inductive hypothesis). Denoting the number of extra people that the girls count by $X$ and the number of extra people that the boys count by $Y$, we want to prove that $X=Y$. We treat two cases. Case 1. $B$ stands to the right of $F$. Let $g_{1}$ and $b_{1}$ be the number of girls and boys respectively who stand to the left of $F$ in line. Let $g_{2}$ and $b_{2}$ be the number of girls and boys respectively who stand between $F$ and $B$. Finally, let $g_{3}$ and $b_{3}$ be the number of girls and boys respectively standing to the right of $B$ in line. The $g_{3}$ girls each count $B$ and $F$ in addition to what they had already counted, whereas the $b_{3}$ boys count nothing extra. This makes $X$ increase by $2g_{3}$ and $Y$ increase by nothing. The $g_{2}$ girls count each count $F$ in addition to what they had already counted, while the $b_{2}$ boys each count $B$ in addition to what they had already counted. This makes $X$ increase by $g_{2}$ and $Y$ increase by $b_{2}$. The $g_{1}$ girls count nothing extra, while the $b_{1}$ boys each count $B$ and $F$ in addition to what they had already counted. This makes $X$ increase by nothing and $Y$ increase by $2b_{1}$. What's left is looking at the number of people that $B$ and $F$ themselves count. Clearly, $F$ counts the $g_{1}+b_{1}$ people to her left, making $X$ increase by this amount, while $B$ counts the $g_{3}+b_{3}$, people to his right, making $Y$ increase by this amount. We now have to prove that $X=Y\Leftrightarrow 2g_{3}+g_{2}+g_{1}+b_{1}=b_{2}+2b_{1}+g_{3}+b_{3}$ or equivalently $g_{1}+g_{2}+g_{3}=b_{1}+b_{2}+b_{3}$ which is clearly true, as both sides are equal to $n$. Case 2. $F$ stands to the right of $B$. To treat this case, we can simply mirror the first one (figuratively switching the direction in which each person counts). This ends our inductive argument and finishes the proof.