#### Combinatorics

###### back to index

Ten people form a line, among which two are Chinese and two are Americans. Find the probability that both Chinese will stand in front of both Americans (not necessarily immediately in the front).

Steve is piling $m \geq 1$ indistinguishable stones on the squares of an $n\times n$ grid. Each square can have an arbitrarily high pile of stones. After he finished piling his stones in some manner, he can then perform stone moves, defined as follows. Consider any four grid squares, which are corners of a rectangle, i.e. in positions $(i, k), (i, l), (j, k), (j, l)$ for some $1\leq i, j, k, l \leq n$, such that $i < j$ and $k < l$. A stone move consists of either removing one stone from each of $(i, k)$ and $(j, l)$ and moving them to $(i, l)$ and $(j, k)$ respectively,j or removing one stone from each of $(i, l)$ and $(j, k)$ and moving them to $(i, k)$ and $(j, l)$ respectively. Two ways of piling the stones are equivalent if they can be obtained from one another by a sequence of stone moves. How many different non-equivalent ways can Steve pile the stones on the grid?

The nine delegates to the Economic Cooperation Conference include $2$ officials from Mexico, $3$ officials from Canada, and $4$ officials from the United States. During the opening session, three of the delegates fall asleep. Assuming that the three sleepers were determined randomly, find the probability that exactly two of the sleepers are from the same country.

In a drawer Sandy has $5$ pairs of socks, each pair a different color. On Monday Sandy selects two individual socks at random from the $10$ socks in the drawer. On Tuesday Sandy selects $2$ of the remaining $8$ socks at random and on Wednesday two of the remaining $6$ socks at random. Find the probability that Wednesday is the first day Sandy selects matching socks.

Consider all $1000$-element subsets of the set $\{1, 2, 3, ... , 2015\}$. From each such subset choose the least element. Find the arithmetic mean of all of these least elements.

In a new school $40$ percent of the students are freshmen, $30$ percent are sophomores, $20$ percent are juniors, and $10$ percent are seniors. All freshmen are required to take Latin, and $80$ percent of the sophomores, $50$ percent of the juniors, and $20$ percent of the seniors elect to take Latin. Find the probability that a randomly chosen Latin student is a sophomore.

Two unit squares are selected at random without replacement from an $n \times n$ grid of unit squares. Find the least positive integer $n$ such that the probability that the two selected unit squares are horizontally or vertically adjacent is less than $\frac{1}{2015}$.

Call a permutation $a_1, a_2, \ldots, a_n$ of the integers $1, 2, \ldots, n$ quasi-increasing if $a_k \leq a_{k+1} + 2$ for each $1 \leq k \leq n-1$. For example, $53421$ and $14253$ are quasi-increasing permutations of the integers $1$, $2$, $3$, $4$, $5$, but $45123$ is not. Find the number of quasi-increasing permutations of the integers $1$, $2$, $\ldots$, $7$.

There are $2^{10} = 1024$ possible $10$-letter strings in which each letter is either an $A$ or a $B$. Find the number of such strings that do not have more than $3$ adjacent letters that are identical.

An urn contains $4$ green balls and $6$ blue balls. A second urn contains $16$ green balls and $N$ blue balls. A single ball is drawn at random from each urn. The probability that both balls are of the same color is $0.58$. Find $N$.

Find the number of rational numbers $r$, $0 < r < 1$, such that when $r$ is written as a fraction in lowest terms, the numerator and the denominator have a sum of $1000$.

A token starts at the point $(0,0)$ of an $xy$-coordinate grid and then makes a sequence of six moves. Each move is 1 unit in a direction parallel to one of the coordinate axes. Each move is selected randomly from the four possible directions and independently of the other moves. Find the probability the token ends at a point on the graph of $|y|=|x|$.

Let $A={1,2,3,4}$, and $f$ and $g$ be randomly chosen (not necessarily distinct) functions from $A$ to $A$. Find the probability that the range of $f$ and the range of $g$ are disjoint.

Arnold is studying the prevalence of three health risk factors, denoted by $A$, $B$, and $C$, within a population of men. For each of the three factors, the probability that a randomly selected man in the population has only this risk factor (and none of the others) is $0.1$. For any two of the three factors, the probability that a randomly selected man has exactly these two risk factors (but not the third) is $0.14$. The probability that a randomly selected man has all three risk factors, given that he has $A$ and $B$ is $\frac{1}{3}$. Find the probability that a man has none of the three risk factors given that he does not have risk factor $A$.

Charles has two six-sided die. One of the die is fair, and the other die is biased so that it comes up six with probability $\frac{2}{3}$ and each of the other five sides has probability $\frac{1}{15}$. Charles chooses one of the two dice at random and rolls it three times. Given that the first two rolls are both sixes, find the probability that the third roll will also be a six.

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.$

Find the number of five-digit positive integers, $n$, that satisfy the following conditions:

• the number $n$ is divisible by $5$,
• the first and last digits of $n$ are equal, and
• the sum of the digits of $n$ is divisible by $5$.

In the array of 13 squares shown below, 8 squares are colored red, and the remaining 5 squares are colored blue. If one of all possible such colorings is chosen at random, the probability that the chosen colored array appears the same when rotated 90 degrees around the central square is $\frac{1}{n}$ , where n is a positive integer. Find n.

Melinda has three empty boxes and $12$ textbooks, three of which are mathematics textbooks. One box will hold any three of her textbooks, one will hold any four of her textbooks, and one will hold any five of her textbooks. If Melinda packs her textbooks into these boxes in random order, find the probability that all three mathematics textbooks end up in the same box.

Let $N$ be the number of ordered triples $(A,B,C)$ of integers satisfying the conditions:

• $0\le A < B < C \le 99$,
• there exist integers $a$, $b$, and $c$, and prime $p$ where $0\le b < a < c < p$,
• $p$ divides $(A-a)$, $(B-b)$, and $(C-c)$, and
• each ordered triple $(A,B,C)$ and each ordered triple $(b,a,c)$ form arithmetic sequences.

Find $N$.

A $7\times 1$ board is completely covered by $m\times 1$ tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the board. Each tile is either red, blue, or green. Let $N$ be the number of tilings of the $7\times 1$ board in which all three colors are used at least once. For example, a $1\times 1$ red tile followed by a $2\times 1$ green tile, a $1\times 1$ green tile, a $2\times 1$ blue tile, and a $1\times 1$ green tile is a valid tiling. Note that if the $2\times 1$ blue tile is replaced by two $1\times 1$ blue tiles, this results in a different tiling. Find $N$.

Find the number of positive integers with three not necessarily distinct digits, $abc$, with $a \neq 0$ and $c \neq 0$ such that both $abc$ and $cba$ are multiples of $4$.

Nine people sit down for dinner where there are three choices of meals. Three people order the beef meal, three order the chicken meal, and three order the fish meal. The waiter serves the nine meals in random order. Find the number of ways in which the waiter could serve the meal types to the nine people so that exactly one person receives the type of meal ordered by that person.

A frog begins at $P_0 = (0,0)$ and makes a sequence of jumps according to the following rule: from $P_n = (x_n, y_n),$ the frog jumps to $P_{n+1},$ which may be any of the points $(x_n + 7, y_n + 2),$ $(x_n + 2, y_n + 7),$ $(x_n - 5, y_n - 10),$ or $(x_n - 10, y_n - 5).$ There are $M$ points $(x, y)$ with $|x| + |y| \le 100$ that can be reached by a sequence of such jumps. Find $M$.

At a certain university, the division of mathematical sciences consists of the departments of mathematics, statistics, and computer science. There are two male and two female professors in each department. A committee of six professors is to contain three men and three women and must also contain two professors from each of the three departments. Find the number of possible committees that can be formed subject to these requirements.