Admittedly, this post is ripping off a conversation that happened on a work Slack channel the other week. Here’s the general idea: If you count in a particular way, there are 12 options for how to put on your underwear, and 12 (ordered) options for putting on socks and shoes. Since there are the same number of options, we can create a bijection between the two scenarios. In other words, each choice of underwear arrangement will correspond to exactly one choice for socks and shoes.
The question is what bijection is “natural”, for whatever definition of natural you choose to have in this strange scenario. Let’s explore it a bit.
Counting Underwear
Let’s get this one out of the way. You’ll have to accept the liberties taken about how underwear works. The person who came up with this is a rather fun individual, and this is what went through their head.
First, consider whether your underwear will be worn inside-out. That is 2 options. For each of those options, you have 3 options for where your waist goes (assuming, of course, your waist can fit through the left or right holes.) That gives us 2\times 3 = 6 options so far. Finally, once you have your waist hole chosen, there are two ways to place your legs. You can imagine this as wearing your underwear “forwards” or “backwards”. So, we’re up to 6\times 2 = 12 options, as promised.
Counting Socks and Shoes
This is clearer, and only depends on order. The goal is to get your socks on your feet, and your shoes on top of your socks. We’re also assuming your socks are not matched to a foot. In other words, we can say you have a blue sock and a green sock, and they could go on either foot.
No matter what, you must start by putting on a sock. So, choose one of your 2 feet, and a color for that sock. That immediately gets us to 2\times 2 = 4 choices. Then, you can either choose to put a shoe on, or another sock.
If you put a shoe on, it’s on the foot with the sock. So, there’s only one way forward from here. So, there are 4 total options where we put on a sock, then a shoe.
If instead you chose to put on your other sock, you have 2 options for the order you put your shoes on. This is true for each of the 4 choices of initial foot and sock color, so there are 4\times 2 = 8 options when we put on two socks, then our shoes.
This gives a total of 4+8 = 12 options overall.
Bijections
As stated at the beginning, if you have two groups with the same number of items, there is always a way to map each item from the first group to a single other item in the other group, without missing any of the items. In fact, this is how mathematicians define when two sets are the same size: if such a map exists. Such a map is called a bijection.
We’re interested in a bijection that feels “natural”. What we really mean is a bijection that reflects the way we counted on group onto the other group.
Notice how we counted each group differently. For underwear, we used a multiplication argument where we made a series of choices, each one branching off from the next. For socks and shoes, we added at some point, because we hit a roadblock: Do we put on a sock second, or a shoe? This caused us to separately count up each case, and add them together.
A good bijection can help us see the socks and shoes in a different light, where we could have counted multiplicatively.
Let’s explore the similarities between the situations. When counting our underwear options, notice that at two points we had 2 choices: (inside, outside), and (forwards, backwards). Finally, we had a spot with 3 choices, (waist hole, left hole, right hole), if you will. We’ll abbreviate this as \{I,O\},\ \{ F, B\},\ \{W, L, R\}. So, a single option of underwear is represented as a group of three letters, one from each set, such as O,B,L.
When counting our socks and shoes, we also have two points with 2 choices! We can pick the left foot or right foot to start, and we can pick where blue and green go. I’ll abbreviate this as \{\ell, r\},\ \{b, g\}. This implies there should be a way to view the situation where we have exactly 3 choices left after choosing initial sock color and placement.
If we look back at how we counted, this is indeed the case. We count putting a shoe over the initial sock as one option. If we don’t do that, we must have put on the other sock. So, the remaining two options are which shoe we put on first. In all, our group of three options to finish with are (1) Put on a shoe immediately, (2) Put on the left shoe after both socks are on, or (3) Put on the right shoe after both socks are on. I’ll abbreviate these three options as \{s, L_s, R_s\}.
Now we can see one of the several natural bijections. We can say that choosing left sock or right sock corresponds to choosing inside or outside; choosing blue or red corresponds to choosing backwards or forwards; and choosing waist, left, or right holes correspond to immediate shoe, sock then left shoe, or sock then right shoe. We could loosely show this graphically like this:
\begin{aligned}
\{I, O\} &\to \{\ell, r\}\\
\{ F, B\} & \to \{b, g\}\\
\{W, L, R\} & \to \{s, L_s, R_s\}
\end{aligned}Of course this isn’t perfect. There is only one humanly natural way that the underwear is configured, while there are several ways to “naturally” put your two socks on, then two shoes on. However, there is a nice symmetry here, and it’s a good toy example to begin exploring why bijections are both fascinating and useful.