A few years ago, during undergrad days, myself and friend Ramani during our lazy 75 paise mini canteen tea outing, were discussing a small riddle. It was motivated from a real world experience from our computer center in NIT Calicut (REC Calicut). In REC those days, we students almost exclusively used rubber slippers (Yes, those Paraqon brand which used to cost 20 rupees or so), usually called by the name ‘chappels’. With that, we were not only comfortable while walking and running around, but we’re equally at ease playing cricket and badminton with the very same foot support; and many other things too, including jogging. Those thin hard rubber slippers used to last an year or more without giving much trouble, other than perhaps an occasional tearing of the rubber tie. In all, we were at peace with that.
But there was an issue, not exclusively for this brand, but for chappals in general (shoes were a luxury of sort in the campus;atleast it wasnt very common). Not for everyone though! If and only if you were fancied of visiting the computer center! Well, computer center wasn’t all that fanciful then, since we were provided with only graphics less Unix terminals (no colour monitors!). You might wonder, huh! what age am I talking about? Besides, Internet and Emails were only taking shape then. Chats and browsing were not quite there yet;Unless you felt a touch inferior to the computer wizkid around, that was not a compelling centre de visite. As, ‘would be‘ electronics and communication engineers we had that occasional inferiority complex!. Computer center was air conditioned and was strictly slippers free. We were expected to keep our valuable slippers outside (no clock room luxury! well that was not a necessity either) before entering to that cooler room, filled with monochromatic terminals. Since most of the chappals dropped outside were alike (in size and also sometimes color) there was a good chance that at the time return, we ended up with a different pair of slippers (Some folks found happy for themselves by a visit to the computer center, just for a pair change, often to an improved lot!). Sometimes, we ended up having differently colored ones, say left foot white and right foot blue. That wasn’t a problem socially either, as long as you stayed within the campus. It was socially accepted within the walls!
Anyway, coming back to the riddle we were busy conjecturing on. We wanted to automate a clock room. The idea then would be to just deposit the chappals there at random. The clock room work automatically. Upon asking (at the time of return, say) it will select a pair at random and give it to you. Sorry, you cant have a choice. Just accept and hope for the best. We asked the questions:
1) What is the probability that everyone gets their own chappals
2) What is the probability that none of them get their submitted pairs
Assume number of people (and hence pairs). We can assume that, a pair is a single entity (say both left and right slippers are tied and submitted as one) . This simplified the problem to people slipper scenario. A simplistic model assumeed that all people submit their slippers at the same time. We wanted to build that great randomized clocker machine! And we wanted that to work for any , which means, the algorithm had to be implementable and to work well in expectation!
We had thought and pondered about it for a while, then. In the end, we had found that the first one is easy, but the second one a little harder to generalize for beyond or something. As busy undergrads, we left the problem after an hour of discussion, probably until we had finished sipping the tea. Aside, we were busy with many other extra curricular activities including a 3 hour daily cricket match at the lush green international hostel ground. The megadeth team, as we proudly grouped ourselves, the electronics and communication batch hardly missed those cricket matches. We were electronics engineers and had taken pride in ourselves by not really bothered to ask any fellow discrete math or combinatorics folks! That perhaps helped in some sense. Ramani found management more interesting than those technical details of counting. I am sure he took the right career. Anyway…too much digressing already!
Now, it turns out that, the very same problem is akin to a well known problem in combinatorics. It is called the Hatcheck lady problem. It is fairly easy to solve it using the inclusion exclusion principle. The proof outline is shown below. As I type, memory fetches that discussion, sitting leg-folded on the cement bench at the REC mini-canteen, perhaps an occasional cool breeze around too.
The inclusion exclusion principle is the following:
The Hatchek lady problem can be stated with a similar story as the random clocker machine. (From Harris, Mossinghoff, Hirst’s book on Combinatorics and Graph Theory)
A lazy professor gives a quiz to a class of students, then collects the papers, shuffles them, and redistribute them randomly to the class for grading. The professor would prefer that no student receives his or her own paper to grade. What is the probability that this occurs? This indeed is an equivalent statement of the well known Hatcheck lady problem (I guess the exact name come from a hatcheck lady who collects hats and absentmindedly return them)
For Hatcheck lady problem, the probability .
When gets larger and larger it converges asymptotically to a constant!