Sort the children by height. Now start at (0,0) and make an up-step of (1,1) for each girl and a down-step (1,-1) for each boy arriving at (2n,0). The recorded numbers are the heights at the end of up-steps and the beginning of down-steps. But these can be paired off easily. Above the horizontal axis, pair off an up-step with the first down-step of the same height to its right, below, pair off a down-step with the first up-step of the same height to its right (these exist because of the eventual return to the axis). The pairs clearly correspond to a boy and a girl and have the same number.

Suppose that Evan walks into the class and arrange $2n$ kids on the points $(0,0), (1,0), (2,0),\hdots,(2n-1,0)$ in the coordinate plane from shortest to tallest. Then Evan stand at $(0,0)$ and walk to $(2n,0)$ with the following rules. On the $i$-th move, if the kid standing at $(i-1,0)$ is a boy, he moves from $(x,y)$ to $(x+1,y+1)$, formed an up-segment. Otherwise, he moves from $(x,y)$ to $(x+1,y-1)$, formed a down segment. Then, Evan peek at that kid's slip and write down his/her number on the segment he just formed. Moreover, Evan color the region enclosed by his path and the $x$-axis red and color everything else blue. Clearly, the numbers written on each segment is the $y$-coordinate of the lower end. It suffices to prove that in for each $k$, the number of up-segment and down-segment having $y$-coordinate on both ends $k$ and $k+1$ are equal. To prove that, Evan walks back to $(k+0.5,0)$ and fires a laser parallel to $x$-axis. The laser must encounter an up-segment during a transition from blue to red region and it must penetrate a down-segment during a transition from red to blue. As the laser eventually ends up in the blue region, the number of up-segments and down-segments are equal so we are done.

XbenX wrote: There are $n$ boys and $n$ girls in a school class, where $n$ is a positive integer. The heights of all the children in this class are distinct. Every girl determines the number of boys that are taller than her, subtracts the number of girls that are taller than her, and writes the result on a piece of paper. Every boy determines the number of girls that are shorter than him, subtracts the number of boys that are shorter than him, and writes the result on a piece of paper. Prove that the numbers written down by the girls are the same as the numbers written down by the boys (up to a permutation). Nice problem! Solution: Arrange all the students in the increasing order of height. Consider the sequence obtained by putting all the numbers calculated by the students side by side. Observe that if a boy and a girl appear side by side, the numbers calculated by each of them will be the same. If two girls appear consecutively the later will be $1$ less than the previous number. Lastly, if two boys appear side by side the later will be $1$ more than the previous number. It indeed suffices to prove that any number in the sequence appears even number of times. Now we will induct on $n$. The base case $n=1$ is trivial. Suppose that it's true for $n$. We will prove that it's true for $n+1$. Observe that in the original boy-girl sequence at-least one pair of a boy and a girl must appear side by side. Notice that removing the very first such pair will not damage the sequence: $$\underbrace{B}_{i} \quad \underbrace{B}_{i+1}\quad \underbrace{G}_{i+1} \quad \underbrace{G/B}_{i/i+1}$$$$\underbrace {G}_{i}\quad \underbrace {G}_{i-1}\quad \underbrace {B}_{i-1}\quad \underbrace {B/G}_{i/i-1}$$Thus deleting the $B,G$ pair in the middle pair will simply delete two $i+1/i-1$'s from the sequence creating a new sequence with $2(n+1)-2=2n$ terms. But by induction hypothesis, there is an even number of each terms in this sequence. Thus there was an even number of each elements in our original sequence with $2(n+1)$ terms. $\blacksquare$

We use induction on $n$. Consider the students are standing in increasing order from left to right. Let $\mathcal{G}_n$ and $\mathcal{B}_n$ be the girl and boy respectively with maximum height. Suppose the students are standing in order $\dots \dots \mathcal{G}_n,b_1,b_2,\dots b_s,\mathcal{B}_n$. Let us assume for sometime that $\mathcal{G}_n$ and $\mathcal{B}_n$ wears a invisible jacket which makes them invisible. So now $b_s=\mathcal{B}_{n-1}$=boy with maximum height It is easy to see that $b_s$ writes $n-(n-1)=1$ $b_{s-1}$ writes $n-(n-2)=2$...... $b_1$ writes $s$. By induction hypothesis there are girls $g_{b_1},g_{b_2}\dots g_{b_s}$ who writes $s,s-1,s-2,\dots 1$ in this order. Now suppose that $\mathcal{G}_n$ and $\mathcal{B}_n$ takes off their invisible jacket. (1)Observe that no girls in the left of $\mathcal{G}_n$ can change their number as exactly one boy and exactly one girl taller than them are joining. (2)No boy in the left of $\mathcal{G}_n$ change their number. (3)$b_1$ changes his number to $s+1$,$b_2$ changes his number to $s$$\dots\dots\dots$ $b_s$ changes his number to $2$.In one word each of $b_1\dots b_s$ increase their number by $1$. (4)$\mathcal{G}_n$ writes $s+1$. (5)$\mathcal{B}_n$ writes $1$. In this time we are done since there are already girls $g_{b_1},g_{b_2}\dots g_{b_s}$ with $s,s-1,s-2,\dots 1$ as their list which is same as the list of $\mathcal{B}_n,b_s,b_{s-1}\dots b_2$ and $\mathcal{G}_n,b_1$ has same number. For the case when the order will be $\dots \dots \mathcal{B}_n,g_1,g_2,\dots g_s,\mathcal{B}_n$ the calculation will same but according to rule.Hence we are done.$\blacksquare$

induction

The Base Case: So $n=1$, either both children write down $0$ or $1$. For the induction, assume that the children are standing in a row in order of height, tallest first. Consider a boy and a girl standing next to each other. If $b$ boys and $g$ girls are taller than these two, then either both write down $$b-g=(n-g-1)-(n-b-1) \quad \textrm{or}\quad (b+1)-g=(n-g)-(n-b-1)$$depending on whether the girl or boy is taller respectively. Removing this pair does not affect the other children's numbers. Thus we are done by the induction hypothesis.