<p>Ten adults enter a room, remove their shoes, and toss their shoes into a pile. Later, a child randomly pairs each left shoe with a right shoe without regard to which shoes belong together. The probability that for every positive integer <img alt="$k<5$" height="13" src="https://latex.artofproblemsolving.com/6/4/0/640828fdfe1e34bc6bdaacffae98d55b439f3a72.png" width="43" />, no collection of <img alt="$k$" height="12" src="https://latex.artofproblemsolving.com/8/c/3/8c325612684d41304b9751c175df7bcc0f61f64f.png" width="9" /> pairs made by the child contains the shoes from exactly <img alt="$k$" height="12" src="https://latex.artofproblemsolving.com/8/c/3/8c325612684d41304b9751c175df7bcc0f61f64f.png" width="9" /> of the adults is <img alt="$\frac{m}{n}$" height="33" src="https://latex.artofproblemsolving.com/2/7/f/27f583697295fc6f723862c13228ee55107c33ca.png" width="18" />, where m and n are relatively prime positive integers. Find <img alt="$m+n.$" height="12" src="https://latex.artofproblemsolving.com/5/d/b/5db26f75f6218a382840f0ed34f5d36bcff61d33.png" width="52" /></p>

Question No: 387

Ten adults enter a room, remove their shoes, and toss their shoes into a pile. Later, a child randomly pairs each left shoe with a right shoe without regard to which shoes belong together. The probability that for every positive integer $k<5$ , no collection of $k$ pairs made by the child contains the shoes from exactly $k$ of the adults is $\frac{m}{n}$ , where m and n are relatively prime positive integers. Find $m+n.$

Editorial

Tags: Combinatorics Probability

Question Details