Prove that $\sum \frac{1}{i_1i_2 \ldots i_k} = n$ is taken over all non-empty subsets $\left\{i_1,i_2, \ldots, i_k\right\}$ of $\left\{1,2,\ldots,n\right\}$. (The $k$ is not fixed, so we are summing over all the $2^n-1$ possible nonempty subsets.)

Three different pairs of shoes are placed in a row so that no left shoe is next to a right shoe from a different pair. In how many ways can these six shoes be lined up? $ \textbf{(A) }60\qquad \textbf{(B) }72\qquad \textbf{(C) }90\qquad \textbf{(D) }108\qquad \textbf{(E) }120\qquad $

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?

Let $n$ be a positive integer. Prove that the number of ways to express $n$ as a sum of distinct positive integers (up to order) and the number of ways to express $n$ as a sum of odd positive integers (up to order) are the same.

Students are in classroom with $n$ rows. In each row there are $m$ tables. It's given that $m,n \geq 3$. At each table there is exactly one student. We call neighbours of the student students sitting one place right, left to him, in front of him and behind him. Each student shook hands with his neighbours. In the end there were $252$ handshakes. How many students were in the classroom?

A parking lot has $ 16$ spaces in a row. Twelve cars arrive, each of which requires one parking space, and their drivers chose spaces at random from among the available spaces. Auntie Em then arrives in her SUV, which requires $ 2$ adjacent spaces. What is the probability that she is able to park? $ \textbf{(A)} \ \frac {11}{20} \qquad \textbf{(B)} \ \frac {4}{7} \qquad \textbf{(C)} \ \frac {81}{140} \qquad \textbf{(D)} \ \frac {3}{5} \qquad \textbf{(E)} \ \frac {17}{28}$

Three persons $A,B,C$, are playing the following game: A $k$-element subset of the set $\{1, . . . , 1986\}$ is randomly chosen, with an equal probability of each choice, where $k$ is a fixed positive integer less than or equal to $1986$. The winner is $A,B$ or $C$, respectively, if the sum of the chosen numbers leaves a remainder of $0, 1$, or $2$ when divided by $3$. For what values of $k$ is this game a fair one? (A game is fair if the three outcomes are equally probable.)

4. There are 5 tables in a classroom. Each table has 4 chairs with a child sitting on it. All the children get up and randomly sit in a seat. Two people that sat at the same table before are not allowed to sit at the same table again. Assuming tables and chairs are distinguishable, if the number of different classroom arrangements can be written as $2^a3^b5^c$, what is $a+b+c$? [i]Proposed by Tragic[/i]

A box contains $p$ white balls and $q$ black balls. Beside the box there is a pile of black balls. Two balls are taken out of the box. If they have the same color, a black ball from the pile is put into the box. If they have different colors, the white ball is put back into the box. This procedure is repeated until the last two balls are removed from the box and one last ball is put in. What is the probability that this last ball is white?

Find all finite sequences $(x_0, x_1, \ldots,x_n)$ such that for every $j$, $0 \leq j \leq n$, $x_j$ equals the number of times $j$ appears in the sequence.

In town $ A,$ there are $ n$ girls and $ n$ boys, and each girl knows each boy. In town $ B,$ there are $ n$ girls $ g_1, g_2, \ldots, g_n$ and $ 2n \minus{} 1$ boys $ b_1, b_2, \ldots, b_{2n\minus{}1}.$ The girl $ g_i,$ $ i \equal{} 1, 2, \ldots, n,$ knows the boys $ b_1, b_2, \ldots, b_{2i\minus{}1},$ and no others. For all $ r \equal{} 1, 2, \ldots, n,$ denote by $ A(r),B(r)$ the number of different ways in which $ r$ girls from town $ A,$ respectively town $ B,$ can dance with $ r$ boys from their own town, forming $ r$ pairs, each girl with a boy she knows. Prove that $ A(r) \equal{} B(r)$ for each $ r \equal{} 1, 2, \ldots, n.$

A permutation $ \{x_1, x_2, \ldots, x_{2n}\}$ of the set $ \{1,2, \ldots, 2n\}$ where $ n$ is a positive integer, is said to have property $ T$ if $ |x_i \minus{} x_{i \plus{} 1}| \equal{} n$ for at least one $ i$ in $ \{1,2, \ldots, 2n \minus{} 1\}.$ Show that, for each $ n$, there are more permutations with property $ T$ than without.

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

Find all pairs \((m,n)\) of positive integers such that there exists a polyhedron, with all faces being regular polygons, such that each vertex of the polyhedron is the vertex of exactly three faces, two of them having \(m\) sides, and the other having \(n\) sides.

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]

Six ants simultaneously stand on the six vertices of a regular octahedron, with each ant at a different vertex. Simultaneously and independently, each ant moves from its vertex to one of the four adjacent vertices, each with equal probability. What is the probability that no two ants arrive at the same vertex? $ \textbf{(A)}\ \frac {5}{256} \qquad \textbf{(B)}\ \frac {21}{1024} \qquad \textbf{(C)}\ \frac {11}{512} \qquad \textbf{(D)}\ \frac {23}{1024} \qquad \textbf{(E)}\ \frac {3}{128}$

Determine the number of permutations $a_1, a_2, \dots, a_n$ of $1, 2, \dots, n$ such that for every positive integer $k$ with $1 \le k \le n$, there exists an integer $r$ with $0 \le r \le n - k$ which satisfies \[ 1 + 2 + \dots + k = a_{r+1} + a_{r+2} + \dots + a_{r+k}. \]

Four students from Harvard, one of them named Jack, and five students from MIT, one of them named Jill, are going to see a Boston Celtics game. However, they found out that only $ 5$ tickets remain, so $ 4$ of them must go back. Suppose that at least one student from each school must go see the game, and at least one of Jack and Jill must go see the game, how many ways are there of choosing which $ 5$ people can see the game?

Let $M, k>0$ integers. Let $X(M,k)$ the (infinite) set of all integers that can be factored as ${p_1}^{e_1} \cdot {p_2}^{e_2} \cdot \ldots \cdot {p_r}^{e_r}$ where each $p_i$ is not smaller than $M$ and also each $e_i$ is not smaller than $k$. Let $Z(M,k,n)$ the number of elements of $X(M,k)$ not bigger than $n$. Show that there are positive reals $c(M,k)$ and $\beta(M,k)$ such that $$\lim_{n \rightarrow \infty}{\frac{Z(M,k,n)}{n^{\beta(M,k)}}} = c(M,k)$$ and find $\beta(M,k)$

A rectangle is partitioned into 5 regions as shown. Each region is to be painted a solid color - red, orange, yellow, blue, or green - so that regions that touch are painted different colors, and colors can be used more than once. How many different colorings are possible? [asy] size(5.5cm); draw((0,0)--(0,2)--(2,2)--(2,0)--cycle); draw((2,0)--(8,0)--(8,2)--(2,2)--cycle); draw((8,0)--(12,0)--(12,2)--(8,2)--cycle); draw((0,2)--(6,2)--(6,4)--(0,4)--cycle); draw((6,2)--(12,2)--(12,4)--(6,4)--cycle); [/asy] $\textbf{(A) }120\qquad\textbf{(B) }270\qquad\textbf{(C) }360\qquad\textbf{(D) }540\qquad\textbf{(E) }720$

Within an arithmetic progression of length $ 2005, $ find the number of arithmetic subprogressions of length $ 501 $ that don't contain the $ \text{1000-th} $ term of the progression.

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 $

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 $

Let $n \geq 1$ be an integer. A [b]path[/b] from $(0,0)$ to $(n,n)$ in the $xy$ plane is a chain of consecutive unit moves either to the right (move denoted by $E$) or upwards (move denoted by $N$), all the moves being made inside the half-plane $x \geq y$. A [b]step[/b] in a path is the occurence of two consecutive moves of the form $EN$. Show that the number of paths from $(0,0)$ to $(n,n)$ that contain exactly $s$ steps $(n \geq s \geq 1)$ is \[\frac{1}{s} \binom{n-1}{s-1} \binom{n}{s-1}.\]

For a positive integer $n$ let $t_n$ be the number of unordered triples of non-empty and pairwise disjoint subsets of a given set with $n$ elements. For example, $t_3 = 1$. Find a closed form formula for $t_n$ and determine the last digit of $t_{2022}$. (I also give here that $t_4 = 10$, for a reader to check his/her understanding of the problem statement.)