# Combinatorics Problem List for AIME

This is a collection of combinatorics and probability problems that have appeared in AIME.

1. Two dice appear to be standard dice with their faces numbered from $1$ to $6$, but each die is weighted so that the probability of rolling the number $k$ is directly proportional to $k$. The probability of rolling a $7$ with this pair of dice is $\tfrac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m + n$. (2016, AIME I, 2)
2. A regular icosahedron is a $20$-faced solid where each face is an equilateral triangle and five triangles meet at every vertex. The regular icosahedron shown below has one vertex at the top, one vertex at the bottom, an upper pentagon of five vertices all adjacent to the top vertex and all in the same horizontal plane, and a lower pentagon of five vertices all adjacent to the bottom vertex and all in another horizontal plane. Find the number of paths from the top vertex to the bottom vertex such that each part of a path goes downward or horizontally along an edge of the icosahedron, and no vertex is repeated. (2016, AIME I, 3)

3. For a permutation $p = (a_1,a_2,\ldots,a_9)$ of the digits $1,2,\ldots,9$, let $s(p)$ denote the sum of the three $3$-digit numbers $a_1a_2a_3$, $a_4a_5a_6$, and $a_7a_8a_9$. Let $m$ be the minimum value of $s(p)$ subject to the condition that the units digit of $s(p)$ is $0$. Let $n$ denote the number of permutations $p$ with $s(p) = m$. Find $|m - n|$. (2016, AIME I, 8)
4. Freddy the frog is jumping around the coordinate plane searching for a river, which lies on the horizontal line $y = 24$. A fence is located at the horizontal line $y = 0$. On each jump Freddy randomly chooses a direction parallel to one of the coordinate axes and moves one unit in that direction. When he is at a point where $y=0$, with equal likelihoods he chooses one of three directions where he either jumps parallel to the fence or jumps away from the fence, but he never chooses the direction that would have him cross over the fence to where $y < 0$. Freddy starts his search at the point $(0, 21)$ and will stop once he reaches a point on the river. Find the expected number of jumps it will take Freddy to reach the river. (2016, AIME I, 13)
5. There is a $40\%$ chance of rain on Saturday and a $30\%$ of rain on Sunday. However, it is twice as likely to rain on Sunday if it rains on Saturday than if it does not rain on Saturday. The probability that it rains at least one day this weekend is $\frac{a}{b}$, where $a$ and $b$ are relatively prime positive integers. Find $a+b$.
6. For positive integers $N$ and $k$, define $N$ to be $k$-nice if there exists a positive integer $a$ such that $a^k$ has exactly $N$ positive divisors. Find the number of positive integers less than $1000$ that are neither $7$-nice nor $8$-nice.
7. The figure below shows a ring made of six small sections which you are to paint on a wall. You have four paint colors available and will paint each of the six sections a solid color. Find the number of ways you can choose to paint each of the six sections if no two adjacent section can be painted with the same color.

8. Beatrix is going to place six rooks on a $6\times6$ chessboard where both the rows and columns are labelled $1$ to $6$; the rooks are placed so that no two rooks are in the same row or the same column. The value of a square is the sum of its row number and column number. The score of an arrangement of rooks is the least value of any occupied square. The average score over all valid configurations is $\frac{p}{q}$, where $p$ and $q$ are relatively prime positive integers. Find $p+q$.