10 guests came to visit and each left a pair of galoshes in the hallway. All pairs of galoshes are of different sizes. The guests began to leave one by one, putting on any pair of galoshes that they could fit into (i.e., each guest could put on a pair of galoshes not smaller than their own). At some point, it was discovered that none of the remaining guests could find a pair of galoshes to leave. What is the maximum number of guests that could have remained?
If there are more than five guests left, then the guest with the smallest size of galoshes among the remaining guests can put on the largest of the remaining galoshes.

## Solution

Let's number the guests and their pairs of galoshes from 1 to 10 in ascending order of the size of the galoshes. Suppose there are 6 guests left (and accordingly 6 pairs of galoshes). Then the smallest number of the remaining guests is no more than 5, and the largest number of the remaining pairs of galoshes is no less than 6, so the guest with the smallest number can put on the galoshes with the largest number. Contradiction. On the other hand, if guests with numbers $1,2,3,4,5$ left sequentially and put on galoshes with numbers $10,9,8,7,6$ respectively, then none of the remaining five guests will be able to put on any of the remaining pairs of galoshes.

## Answer

5.00