We are going to have to pretend that I am demographically nonexistent. I am an ageless, sexless cipher. Once the census details start rolling in our minds go active pigeonholing every person we meet. Pigeonholes are for pigeons and well, maybe mathematicians...
The Pigeonhole Principle also known as:
Yes, it sounds better when you scream it. I recommend you do it right now. The more Germans around the better. I'll let you explain why you are screaming about your drawers.
If you've had a pile of socks in the dryer, you've probably used the pigeonhole principle. And I'm guessing you are the most popular flavor of awesomesauce, so you knew exactly what you were doing and you wrote a proof when you were done. But just in case, let's get back to socks. You have your big pile of black and blue socks, an equal number of each. And you aren't like me, you actually care that they match. How many socks do you pull out of the dryer before you are guaranteed a match? Lets assume worst case scenario. 1-Sock ONE...blue 2-Sock TWO...black 3-On the third sock you are guaranteed a pair of either color. Mathematicians like to generalize things. So the Pigeonhole Principle says if you have n things and you want to put them in m pigeonholes and n>m then at least one pigeonhole will contain more than one thing. The dude who came up with this stuff is Johann Peter Gustav Lejeune Dirichlet. He has a helluva name. So let's pretend we are 10 years old and make fun of it. If you have two pigeonholes. One for first names and one for last names and you have to organize Mr Dirichlet's complicated moniker, how many names would be in each pigeonhole. Well we have n = 5 names and m = 2 pigeonholes, you tell me.
You lost me somewhere along the way...
ReplyDeleteBut when I am trying to chose matching socks, I usually have to pull four or five out before I find a pair that matches. And I lose socks after a while. I'll have one bright green neon sock, and the other will have vanished permanently. Some days my sock matching skills only go so far as to make sure I'm wearing the same type of sock on each foot - luckily I prefer ankle socks- and that's about the best it can get.
The sock problem is an illustration really. In order for it to work, we have to use the simplest case. Even numbers of black and blue socks.
ReplyDeleteOnce you get a dryer full of uneven numbers, various shapes and sizes and mystery neon socks we are looking and complex probabilities. All guarantees go out the window. Although that sounds like an interesting problem that might distract me from homework for several hours.
So back to our simple model black and blue socks only, an even number of each...
1st sock we pull out is blue or black. We only have one sock, no pairs, no guarantees. Because we use an even number of each we are equally likely to pull a blue sock as a black sock.
2nd sock black or blue - We might have a pair we might not. Its helpful to think of the combinations that are possible (first sock, second sock): [(blue, black), (black,blue),(black,black),(blue,blue)] all equally likely. We can see that there are no guarantees yet. We might have a pair, but we might not.
3rd sock is where the magic happens. On the second draw we had either a pair or one of each color. When we pull out the third sock we absolutely have a pair. We might have already gotten a pair on our second draw, but we are guaranteed a pair of matching socks on our third.
Does that help?