Library / /1357 of 1394

, 2023

Combinatorics Difficulty 6.2 National Olympiad Prove it United States

Problem:

Elbert and Yaiza each draw 10 cards from a 20-card deck with cards numbered $1,2,3, \ldots, 20$ . Then, starting with the player with the card numbered $1$ , the players take turns placing down the lowest-numbered card from their hand that is greater than every card previously placed. When a player cannot place a card, they lose and the game ends.

Given that Yaiza lost and $5$ cards were placed in total, compute the number of ways the cards could have been initially distributed. (The order of cards in a player's hand does not matter.)

Solution

Solution:

Put each card in order and label them based on if Elbert or Yaiza got them. We will get a string of $E$ 's and $Y$ 's like $EEYYYE\ldots$ , and consider the "blocks" of consecutive letters. It is not hard to see that only the first card of each block is played, and the number of cards played is exactly the number of blocks. Thus, it suffices to count the ways to distribute $10$ cards to each player to get exactly $5$ blocks.

Note that since Yaiza lost, Elbert must have the last block, and since blocks alternate in player, Elbert also has the first block. Then a card distribution is completely determined by where Yaiza's blocks are relative to Elbert's cards (e.g. one block is between the $4$ th and $5$ th card), as well as the number of cards in each block. Since Elbert has $10$ cards, there are $\binom{9}{2}$ ways to pick the locations of the blocks, and $9$ ways to distribute $10$ cards between two blocks. This gives a total answer of $9\binom{9}{2}=324$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.