[I received this puzzle from Vladislav Shcherbina, but I changed gloves into T-shirts to emphasize the people rather than the spaces between them.]

Ten friends walk into a room where each one of them receives a hat. On each hat is written a real number; no two hats have the same number. Each person can see the numbers written on his friends’ hats, but cannot see his own. The friends then go into individual rooms where they are each given the choice between a white T-shirt and a black T-shirt. Wearing the respective T-shirts they selected, the friends gather again and are lined up in the order of their hat numbers. The desired property is that the T-shirts colors now alternate.

The friends are allowed to decide on a strategy before walking into the room with the hats, but they are not otherwise allowed to communicate with each other (except that they can see each other’s hat numbers). Design a strategy that lets the friends always end up with alternating T-shirt colors.

August 2010