Alternating T-shirt Colors


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.


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