Source

I got this problem from Rustan Leino, who got it from Vladislav Shcherbina, but changed gloves into T-shirts to emphasize the people rather than the spaces between them.

I solved it and wrote up my solution.

Problem

Each of ten friends goes into a private dressing room where that friend chooses either a white T-shirt or a black T-shirt to wear. Then, the other T-shirt is taken away and they're given a hat with a real number written on it. Before selecting their T-shirt, each friend is given a list of the other nine friends; next to each name on that list is what that friend's hat number will be. All ten hats will have different numbers.

The friends then put on their hats and T-shirts and gather in a room. They may not remove or exchange hats or T-shirts, but must immediately line up in order of hat number. The desired property is that the T-shirt colors alternate.

The friends are allowed to decide on a strategy before walking into their dressing rooms, but may not otherwise communicate. Design a strategy that lets the friends always end up with alternating T-shirt colors.

Solution
Reveal

Call a pair of friends *correctly ordered* if their names are in the
same order as their hat numbers. For instance, since "David" comes before
"Helena" alphabetically, David and Helena are correctly ordered if and only if
David's number is less than Helena's number. Let $C$ be the total number of
correctly-ordered pairs. (Incidentally, since there are 45 ways to pair the
ten friends, $0 \leq C \leq 45$.)

Each friend makes an estimate about what $C$ is. They can mostly figure this out, except they can't tell whether pairs that include themselves are correctly ordered. So, when each friend is estimating, they assume that their hat number is less than everyone else's (as if their hat said $-\infty$). Each friend whose estimate is odd chooses a white T-shirt, and each friend whose estimate is even chooses a black T-shirt.

The reason this works is as follows.

Each friend will make a certain number of mistakes when evaluating the correctly-orderedness of pairs. They will never make mistakes for pairs that don't include themselves, since their list tells them both the numbers in such pairs. For pairs that do include themselves, they'll make a mistake if and only if the other friend in that pair has a hat number less than their hat's number.

This means that the number of mistakes each friend makes is equal to the number of friends with lower hat numbers. The friend with the lowest hat number will make 0 mistakes, the friend with the second-lowest hat number will make 1 mistake, the friend with the third-lowest hat number will make 2 mistakes, etc. Thus, when they line up, they'll be lining up in order of number of mistakes made.

Each mistake induces an error of $+1$ or $-1$ in the estimate. Thus, mistakes can cancel, but only in pairs. As a result, the error in each estimate will have the same parity as the number of mistakes. In other words, friends with odd mistake counts will have odd errors and friends with even mistake counts will have even errors.

Since a friend's mistake count differs by one from the people they'll stand next to, their mistake count must have a different parity than each of those neighbors' mistake counts. Thus, any two neighbors' errors must also have different parities from each other. All the friends are trying to estimate the same quantity, $C$, so if their errors have different parities then their estimates have different parities. Thus, friends standing next to each other will have selected different T-shirt colors. $\Box$