smc

Question

Suppose that 13 cards numbered 1, 2, 3, , 13 are arranged in a row. The task is to pick them up in numerically increasing order, working repeatedly from left to right. In the example below, cards 1, 2, 3 are picked up on the first pass, 4 and 5 on the second pass, 6 on the third pass, 7, 8, 9, 10 on the fourth pass, and 11, 12, 13 on the fifth pass. For how many of the 13! possible orderings of the cards will the 13 cards be picked up in exactly two passes? FIGURE

Accepted Answer

For 1 k 12, suppose that cards 1, 2, , k are picked up on the first pass. It follows that cards k+1,k+2,,13 are picked up on the second pass. Once we pick the spots for the cards on the first pass, there is only one way to arrange all 13 cards. For each value of k, there are 13k-1 ways to pick the k spots for the cards on the first pass: We exclude the arrangement FIGURE in which the first pass consists of all 13 cards. Therefore, the answer is _k=1^12[13k-1] = [_k=1^1213k]-12 = [_k=0^1313k]-14 = 2^13 - 14 = 8178.