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 he chooses either a white T-shirt or a black T-shirt to wear. Then, the other T-shirt is taken away and he's given a hat with a real number written on it. Before selecting his T-shirt, he's 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 will make an estimate about what $C$ is. He can mostly figure this out, except he can't tell whether pairs that include himself are correctly ordered. So, for his estimate, he'll assume that his hat number is less than everyone else's (as if his hat said $-\infty$). If his estimate is odd, he chooses a white T-shirt. If his estimate is even, he 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. He will never make mistakes for pairs that don't include himself, since his list tells him both the numbers in such pairs. For pairs that do include himself, he'll make a mistake if and only if the other friend in that pair has a hat number less than his 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 person with the lowest hat number will make 0 mistakes, the person with the second-lowest hat number will make 1 mistake, the person with the third-lowest hat number will make 2 mistakes, etc. Thus, when they line up they will 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 the estimate will have the same parity as the number of mistakes. In other words, a friend's error will be odd if his mistake count is odd, and it will be even if his mistake count is even.

Since a friend's mistake count differs by one from the people he'll stand next to, it must have a different parity than theirs. Thus, his error must have a different parity than theirs. They're all 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$