Found problems: 75
A group of $16$ people will be partitioned into $4$ indistinguishable $4$-person committees. Each committee will have one chairperson and one secretary. The number of different ways to make these assignments can be written as $3^r M,$ where $r$ and $M$ are positive integers and $M$ is not divisible by $3.$ What is $r?$
$\textbf{(A) }5 \qquad\textbf{(B) }6\qquad\textbf{(C) }7\qquad\textbf{(D) }8\qquad\textbf{(E) }9$
A fancy bed and breakfast inn has $5$ rooms, each with a distinctive color-coded decor. One day $5$ friends arrive to spend the night. There are no other guests that night. The friends can room in any combination they wish, but with no more than $2$ friends per room. In how many ways can the innkeeper assign the guests to the rooms?
$\textbf{(A) }2100\qquad
\textbf{(B) }2220\qquad
\textbf{(C) }3000\qquad
\textbf{(D) }3120\qquad
\textbf{(E) }3125\qquad$
How many $ 15$-letter arrangements of $ 5$ A's, $ 5$ B's, and $ 5$ C's have no A's in the first $ 5$ letters, no B's in the next $ 5$ letters, and no C's in the last $ 5$ letters?
$ \textbf{(A)}\ \sum_{k\equal{}0}^5\binom{5}{k}^3 \qquad
\textbf{(B)}\ 3^5\cdot 2^5 \qquad
\textbf{(C)}\ 2^{15} \qquad
\textbf{(D)}\ \frac{15!}{(5!)^3} \qquad
\textbf{(E)}\ 3^{15}$
Given eight distinguishable rings, let $n$ be the number of possible five-ring arrangements on the four fingers (not the thumb) of one hand. The order of rings on each finger is significant, but it is not required that each finger have a ring. Find the leftmost three nonzero digits of $n.$
How many natural number triples $(x,y,z)$ are there such that $xyz = 10^6$?
$
\textbf{(A)}\ 568
\qquad\textbf{(B)}\ 784
\qquad\textbf{(C)}\ 812
\qquad\textbf{(D)}\ 816
\qquad\textbf{(E)}\ 824
$
Let $N$ be the number of ways of distributing $52$ identical balls into $4$ distinguishable boxes such that no box is empty and the difference between the number of balls in any two of the boxes is not a multiple of $6$ If $N=100a+b$, where $a,b$ are positive integers less than $100$, find $a+b.$
There are $5$ yellow pegs, $4$ red pegs, $3$ green pegs, $2$ blue pegs, and $1$ orange peg on a triangular peg board. In how many ways can the pegs be placed so that no (horizontal) row or (vertical) column contains two pegs of the same color?
[asy]
unitsize(20);
dot((0,0));
dot((1,0));
dot((2,0));
dot((3,0));
dot((4,0));
dot((0,1));
dot((1,1));
dot((2,1));
dot((3,1));
dot((0,2));
dot((1,2));
dot((2,2));
dot((0,3));
dot((1,3));
dot((0,4));[/asy]
$\text{(A)}\ 0\qquad\text{(B)}\ 1\qquad\text{(C)}\ 5!\cdot4!\cdot3!\cdot2!\cdot1!\qquad\text{(D)}\ \frac{15!}{5!\cdot4!\cdot3!\cdot2!\cdot1!}\qquad\text{(E)}\ 15!$
We define the [i]Fibonacci sequence[/i] $\{F_n\}_{n\ge0}$ by $F_0=0$, $F_1=1$, and for $n\ge2$, $F_n=F_{n-1}+F_{n-2}$; we define the [i]Stirling number of the second kind[/i] $S(n,k)$ as the number of ways to partition a set of $n\ge1$ distinguishable elements into $k\ge1$ indistinguishable nonempty subsets.
For every positive integer $n$, let $t_n = \sum_{k=1}^{n} S(n,k) F_k$. Let $p\ge7$ be a prime. Prove that \[ t_{n+p^{2p}-1} \equiv t_n \pmod{p} \] for all $n\ge1$.
[i]Proposed by Victor Wang[/i]
An auditorium has two rows of seats, with $50$ seats in each row. $100$ indistinguishable people sit in the seats one at a time, subject to the condition that each person, except for the first person to sit in each row, must sit to the left or right of an occupied seat, and no two people can sit in the same seat. In how many ways can this process occur?
Rabbits Peter and Pauline have three offspring—Flopsie, Mopsie, and Cotton-tail. These five rabbits are to be distributed to four different pet stores so that no store gets both a parent and a child. It is not required that every store gets a rabbit. In how many different ways can this be done?
$\textbf{(A)} \ 96 \qquad \textbf{(B)} \ 108 \qquad \textbf{(C)} \ 156 \qquad \textbf{(D)} \ 204 \qquad \textbf{(E)} \ 372 $
Erin the ant starts at a given corner of a cube and crawls along exactly $7$ edges in such a way that she visits every corner exactly once and then finds that she is unable to return along an edge to her starting point. How many paths are there meeting these conditions?
$ \textbf{(A) }\text{6}\qquad\textbf{(B) }\text{9}\qquad\textbf{(C) }\text{12}\qquad\textbf{(D) }\text{18}\qquad\textbf{(E) }\text{24} $
In an election between $\text{A}$ and $\text{B}$, during the counting of the votes, neither candidate was more than $2$ votes ahead, and the vote ended in a tie, $6$ votes to $6$ votes. Two votes for the same candidate are indistinguishable. In how many orders could the votes have been counted? One possibility is $\text{AABBABBABABA}$.
Sophie has $20$ indistinguishable pairs of socks in a laundry bag. She pulls them out one at a time. After pulling out $30$ socks, the expected number of unmatched socks among the socks that she has pulled out can be expressed in simplest form as $\tfrac{m}{n}$. Find $m+n$.
There are $ 11$ coins, which are indistinguishable by sight. Nevertheless, among them there are $ 10$ geniune coins ( of weight $ 20$ g each) and one counterfeit (of weight $ 21$ g). You have a two-pan scale which is blanced when the weight in the left-hand pan is twice as much as the weight in the right-hand one. Using this scale only, find the false coin by three weighings.
A bug starts at a vertex of an equilateral triangle. On each move, it randomly selects one of the two vertices where it is not currently located, and crawls along a side of the triangle to that vertex. Given that the probability that the bug moves to its starting vertex on its tenth move is $m/n,$ where $m$ and $n$ are relatively prime positive integers, find $m+n.$
In how many distinguishable rearrangements of the letters ABCCDEEF does the A precede both C's, the F appears between the 2 C's, and the D appears after the F?
Each face of a regular tetrahedron is painted either red, white or blue. Two colorings are considered indistinguishable if two congruent tetrahedra with those colorings can be rotated so that their appearances are identical. How many distinguishable colorings are possible?
$ \textbf{(A)}\ 15 \qquad \textbf{(B)}\ 18 \qquad \textbf{(C)}\ 27 \qquad \textbf{(D)}\ 54 \qquad \textbf{(E)}\ 81$
Let $K_1, K_2, K_3, K_4, K_5$ be 5 distinguishable keys, and let $D_1, D_2, D_3, D_4, D_5$ be $5$ distinguishable doors. For $1 \leq i \leq 5$, key $K_i$ opens doors $D_{i}$ and $D_{i+1}$ (where $D_6 = D_1$) and can only be used once. The keys and doors are placed in some order along a hallway. Key\$ha walks into the hallway, picks a key and opens a door with it, such that she never obtains a key before all the doors in front of it are unlocked. In how many orders can the keys and doors be placed such that Key\$ha can open all of the doors?
[i]Author: Mitchell Lee[/i]
[hide="Clarifications"]
[list=1][*]The doors and keys are in series. In other words, the doors aren't lined up along the side of the hallway. They are blocking Key\$ha's path to the end, and the only way she can get past them is by getting the appropriate keys along the hallway.
[*]The doors and keys appear consecutively along the hallway. For example, she might find $K_1 D_1 K_2 D_2 K_3 D_3 K_4 D_4 K_5 D_5$ down the hallway in that order. Also, by "she never obtains a key before all the doors in front of it are unlocked," we mean that she cannot obtain a key before all the doors appearing before the key are unlocked. In essence, it merely states that locked doors cannot be passed.
[*]The doors and keys do not need to alternate down the hallway.[/list][/hide]
We define the [i]Fibonacci sequence[/i] $\{F_n\}_{n\ge0}$ by $F_0=0$, $F_1=1$, and for $n\ge2$, $F_n=F_{n-1}+F_{n-2}$; we define the [i]Stirling number of the second kind[/i] $S(n,k)$ as the number of ways to partition a set of $n\ge1$ distinguishable elements into $k\ge1$ indistinguishable nonempty subsets.
For every positive integer $n$, let $t_n = \sum_{k=1}^{n} S(n,k) F_k$. Let $p\ge7$ be a prime. Prove that \[ t_{n+p^{2p}-1} \equiv t_n \pmod{p} \] for all $n\ge1$.
[i]Proposed by Victor Wang[/i]
Seven boys and three girls are playing basketball. I how many different ways can they make two teams of five players so that both teams have at least one girl?
For a polynomial $ P(x)$ with integer coefficients, $ r(2i \minus{} 1)$ (for $ i \equal{} 1,2,3,\ldots,512$) is the remainder obtained when $ P(2i \minus{} 1)$ is divided by $ 1024$. The sequence
\[ (r(1),r(3),\ldots,r(1023))
\]
is called the [i]remainder sequence[/i] of $ P(x)$. A remainder sequence is called [i]complete[/i] if it is a permutation of $ (1,3,5,\ldots,1023)$. Prove that there are no more than $ 2^{35}$ different complete remainder sequences.
Find the number of triples of sets $(A, B, C)$ such that:
(a) $A, B, C \subseteq \{1, 2, 3, \dots , 8 \}$.
(b) $|A \cap B| = |B \cap C| = |C \cap A| = 2$.
(c) $|A| = |B| = |C| = 4$.
Here, $|S|$ denotes the number of elements in the set $S$.
In how many ways can the integers from $1$ to $2006$ be divided into three non-empty disjoint sets so that none of these sets contains a pair of consecutive integers?
Thee tiles are marked $ X$ and two other tiles are marked $ O$. The five tiles are randomly arranged in a row. What is the probability that the arrangement reads $ XOXOX$?
$ \textbf{(A)}\ \frac{1}{12}\qquad
\textbf{(B)}\ \frac{1}{10}\qquad
\textbf{(C)}\ \frac{1}{6}\qquad
\textbf{(D)}\ \frac{1}{4}\qquad
\textbf{(E)}\ \frac{1}{3}$
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 [i]stone moves[/i], 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, 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?