For teachers / Printable sets /Stage 5 · Combinatorics

Stage 5 · Combinatorics

10 problems · AIME late · mathsolympiadprep.com

Print or save as PDF The answer key prints on its own page at the end.

1. Teresa the bunny has a fair 8-sided die. Seven of its sides have fixed labels $1, 2, \ldots, 7$, and the label on the eighth side can be changed and begins as $1$. She rolls it several times, until each of $1, 2, \ldots, 7$ appears at least once. After each roll, if $k$ is the smallest positive integer that she has not rolled so far, she relabels the eighth side with $k$. The probability that $7$ is the last number she rolls is $\frac{a}{b}$, where $a$ and $b$ are relatively prime positive integers. Compute $100a + b$.

   HMMT Spring 2021

   Combinatorics Solution and answer checking →

2. Paul Erdős was one of the most prolific mathematicians of all time and was renowned for his many collaborations. The Erdős number of a mathematician is defined as follows. Erdős has an Erdős number of $0$, a mathematician who has coauthored a paper with Erdős has an Erdős number of $1$, a mathematician who has not coauthored a paper with Erdős, but has coauthored a paper with a mathematician with Erdős number $1$ has an Erdős number of $2$, etc. If no such chain exists between Erdős and another mathematician, that mathematician has an Erdős number of infinity. Of the mathematicians with a finite Erdős number (including those who are no longer alive), what is their average Erdős number according to the Erdős Number Project? If the correct answer is $X$ and you write down $A$, your team will receive $\max (25-\lfloor 100|X-A|\rfloor, 0)$ points where $\lfloor x\rfloor$ is the largest integer less than or equal to $x$.

   Harvard-MIT November Tournament

   Combinatorics Solution and answer checking →

3. There are 1024 players, ranked from 1 (most skilled) to 1024 (least skilled), participating in a single elimination tournament. In each of the 10 rounds, the remaining players are paired uniformly at random. In each match, the player with a lower rank always wins, and the loser is eliminated from the tournament.

   For each positive integer $n \in [1,1024]$, let $f(n)$ be the expected number of rounds that the participant with rank $n$ participates in. Estimate the minimum positive integer $N$ such that $f(N)<2$.

   Submit a positive integer $E$. If the correct answer is $A$, you will receive max $\left(0,20-\left\lfloor\frac{|E-A|}{2}\right\rfloor\right)$ points.

   HMMT November 2024

   Combinatorics Solution and answer checking →

4. We wish to color the integers $1,2,3, \ldots, 10$ in red, green, and blue, so that no two numbers $a$ and $b$, with $a-b$ odd, have the same color. (We do not require that all three colors be used.) In how many ways can this be done?

   HMMT February

   Combinatorics Solution and answer checking →

5. Let $N$ denote the sum of the decimal digits of $\binom{1000}{100}$. Estimate the value of $N$.

   HMMT February

   Combinatorics Solution and answer checking →

6. A small fish is holding 17 cards, labeled 1 through 17, which he shuffles into a random order. Then, he notices that although the cards are not currently sorted in ascending order, he can sort them into ascending order by removing one card and putting it back in a different position (at the beginning, between some two cards, or at the end). In how many possible orders could his cards currently be?

   HMMT November

   Combinatorics Solution and answer checking →

7. There are 5 students on a team for a math competition. The math competition has 5 subject tests. Each student on the team must choose 2 distinct tests, and each test must be taken by exactly two people. In how many ways can this be done?

   HMMT February

   Combinatorics Solution and answer checking →

8. Count the number of functions $f: \mathbb{Z} \rightarrow\{$ 'green', 'blue' $\}$ such that $f(x)=f(x+22)$ for all integers $x$ and there does not exist an integer $y$ with $f(y)=f(y+2)=$ 'green'.

   HMMT February

   Combinatorics Solution and answer checking →

9. In how many ways can we enter numbers from the set $\{1,2,3,4\}$ into a $4 \times 4$ array so that all of the following conditions hold? (a) Each row contains all four numbers. (b) Each column contains all four numbers. (c) Each "quadrant" contains all four numbers. (The quadrants are the four corner $2 \times 2$ squares.)

   HMMT February

   Combinatorics Solution and answer checking →

10. In each cell of a $4 \times 4$ grid, one of the two diagonals is drawn uniformly at random. Compute the probability that the resulting 32 triangular regions can be colored red and blue so that any two regions sharing an edge have different colors.

    HMMT February

    Combinatorics Solution and answer checking →

Answer key — Stage 5 · Combinatorics

Worked solutions for every problem are on the site, one page per problem.

1. $104$ open
2. $4.65$ open
3. $350$ open
4. $186$ open
5. $621$ open
6. $256$ open
7. $2040$ open
8. $39601$ open
9. $288$ open
10. $\frac{1}{512}$ open

Problems belong to the competitions that set them. Each question on this sheet names the competition it came from, and the licences the material is used under are listed below. Free to copy for classroom use.

CC-BY-4.0 · Apache-2.0