
ZOJ Problem Set  1495
One of the most common children's toys is a stacking tower, which consists of a series of rings of dierent sizes and a tapered rod which can hold the rings. The rings and rod are designed so that when the rings are placed in descending order by size, they fit exactly on the rod. Further, each ring, if placed by itself on the rod will go no lower than its position when all rings are on the rod. The diagram on the left shows an example of this toy which uses five rings, numbered 1 (smallest) to 5 (largest) Unless endowed with supergenius mental faculties, most infants will place the rings in a random order on the rod, which results in some rings sticking over the top of the rod. The above diagram on the right shows the result of one such random placement. Your job will be to determine the number of rings which sit above the rod given a random ordering of the rings. You may assume that the rings may be stacked arbitrarily high without falling over.
0 Source: East Central North America 2002 