How many different names are possible from combining There are N cities with N different names. Every city has their own population. The government ended up combining those cities together until only one is left.
It is done by combining any 2 cities at random - and taking the name of one of the 2 cities with the larger population.
How many different names are possible if
a) N=8 and the populations of the 8 cities are 2, 50, 24, 21, 1, 9, 15, 5?
b) N=100 and the population of a city x is x^2?
 A: For (a), call the cities $A,B,\ldots,H$ with populations $1,2,5,9,15,21,24,50$.  We will say that city $X$ "absorbs" city $Y$ if combining them gives a city named $X$.  For example $F$ can absorb $E$ giving a population of $36$ for $F$, and this new $F$ can then absorb $G$.
Now $A$ cannot ever absorb any other city so it will lose its name as soon as it is combined.  $B$ can absorb $A$ for a total population of $3$, but then nothing else.  $C$ can only absorb $B$ and $A$ to make a total of $8$, then nothing else.  So these names cannot be the final name.
However all the others are possible.  $D$ can absorb $C,B,A$ giving population $17$; this enables it to absorb $E$, then $F$, then $G$, then $H$, making one city called $D$.  The same goes for those higher on the list.
So there are five possible final names: $D,E,F,G,H$.
Doing (b) in the same way, suppose $A,B,C,\ldots$ have populations $1,4,9,\ldots\,$.  Then $A$ will be absorbed, $B$ can only absorb $A$ for a population of $5$, $C$ can only get up to at most $14$.  But $D$ could absorb $C,B,A$ to get to $30$, then it can absorb $E$, and all the rest one by one.  Once the city with population $x^2$ has been absorbed, the city created has population greater than $2x^2$, which is greater than $(x+1)^2$, so the next city gets absorbed too, and so on.  So all names are possible for the final combined city, except for $A,B,C$.
