Found problems: 17
2002 Tournament Of Towns, 4
The spectators are seated in a row with no empty places. Each is in a seat which does not match the spectator's ticket. An usher can order two spectators in adjacent seats to trade places unless one of them is already seated correctly. Is it true that from any initial arrangement, the spectators can be brought to their correct seats?
2008 Mongolia Team Selection Test, 1
How many ways to fill the board $ 4\times 4$ by nonnegative integers, such that sum of the numbers of each row and each column is 3?
2013 Canadian Mathematical Olympiad Qualification Repechage, 4
Four boys and four girls each bring one gift to a Christmas gift exchange. On a sheet of paper, each boy randomly writes down the name of one girl, and each girl randomly writes down the name of one boy. At the same time, each person passes their gift to the person whose name is written on their sheet. Determine the probability that [i]both[/i] of these events occur:
[list]
[*] (i) Each person receives exactly one gift;
[*] (ii) No two people exchanged presents with each other (i.e., if $A$ gave his gift to $B$, then $B$ did not give her gift to $A$).[/list]
2011 CentroAmerican, 1
Consider a cube with a fly standing at each of its vertices. When a whistle blows, each fly moves to a vertex in the same face as the previous one but diagonally opposite to it. After the whistle blows, in how many ways can the flies change position so that there is no vertex with 2 or more flies?
1987 IMO, 1
Let $p_n(k)$ be the number of permutations of the set $\{1,2,3,\ldots,n\}$ which have exactly $k$ fixed points. Prove that $\sum_{k=0}^nk p_n(k)=n!$.
1987 IMO Longlists, 21
Let $p_n(k)$ be the number of permutations of the set $\{1,2,3,\ldots,n\}$ which have exactly $k$ fixed points. Prove that $\sum_{k=0}^nk p_n(k)=n!$.[i](IMO Problem 1)[/i]
[b][i]Original formulation [/i][/b]
Let $S$ be a set of $n$ elements. We denote the number of all permutations of $S$ that have exactly $k$ fixed points by $p_n(k).$ Prove:
(a) $\sum_{k=0}^{n} kp_n(k)=n! \ ;$
(b) $\sum_{k=0}^{n} (k-1)^2 p_n(k) =n! $
[i]Proposed by Germany, FR[/i]
2008 Moldova Team Selection Test, 4
Find the number of even permutations of $ \{1,2,\ldots,n\}$ with no fixed points.
1987 IMO Shortlist, 16
Let $p_n(k)$ be the number of permutations of the set $\{1,2,3,\ldots,n\}$ which have exactly $k$ fixed points. Prove that $\sum_{k=0}^nk p_n(k)=n!$.[i](IMO Problem 1)[/i]
[b][i]Original formulation [/i][/b]
Let $S$ be a set of $n$ elements. We denote the number of all permutations of $S$ that have exactly $k$ fixed points by $p_n(k).$ Prove:
(a) $\sum_{k=0}^{n} kp_n(k)=n! \ ;$
(b) $\sum_{k=0}^{n} (k-1)^2 p_n(k) =n! $
[i]Proposed by Germany, FR[/i]
2010 Today's Calculation Of Integral, 602
Prove the following inequality.
\[\frac{e-1}{n+1}\leqq\int^e_1(\log x)^n dx\leqq\frac{(n+1)e+1}{(n+1)(n+2)}\ (n=1,2,\cdot\cdot\cdot) \]
1994 Kyoto University entrance exam/Science
2013 India IMO Training Camp, 1
Let $n \ge 2$ be an integer. There are $n$ beads numbered $1, 2, \ldots, n$. Two necklaces made out of some of these beads are considered the same if we can get one by rotating the other (with no flipping allowed). For example, with $n \ge 5$, the necklace with four beads $1, 5, 3, 2$ in the clockwise order is same as the one with $5, 3, 2, 1$ in the clockwise order, but is different from the one with $1, 2, 3, 5$ in the clockwise order.
We denote by $D_0(n)$ (respectively $D_1(n)$) the number of ways in which we can use all the beads to make an even number (resp. an odd number) of necklaces each of length at least $3$. Prove that $n - 1$ divides $D_1(n) - D_0(n)$.
2007 Stanford Mathematics Tournament, 9
Let $d_n$ denote the number of derangements of the integers $1, 2, \ldots n$ so that no integer $i$ is in the $i^{th}$ position. It is possible to write a recurrence relation $d_{n}=f(n)d_{n-1}+g(n)d_{n-2}$; what is $f(n)+g(n)$?
2014 Korea National Olympiad, 2
How many one-to-one functions $f : \{1, 2, \cdots, 9\} \rightarrow \{1, 2, \cdots, 9\}$ satisfy (i) and (ii)?
(i) $f(1)>f(2)$, $f(9)<9$.
(ii) For each $i=3, 4, \cdots, 8$, if $f(1), \cdots, f(i-1)$ are smaller than $f(i)$, then $f(i+1)$ is also smaller than $f(i)$.
1982 Canada National Olympiad, 4
Let $p$ be a permutation of the set $S_n = \{1, 2, \dots, n\}$. An element $j \in S_n$ is called a fixed point of $p$ if $p(j) = j$. Let $f_n$ be the number of permutations having no fixed points, and $g_n$ be the number with exactly one fixed point. Show that $|f_n - g_n| = 1$.
2000 Korea Junior Math Olympiad, 8
$n$ men and one woman are in the meeting room with $n+1$ chairs, each of them having their own seat. Show that the following two number of cases are equal.
(1) Number of cases to choose one man to get out of the room, and make the left $n-1$ men to sit to each other's chair.
(2) Number of cases to make $n+1$ people to sit to each other's chair.
2013 India IMO Training Camp, 1
Let $n \ge 2$ be an integer. There are $n$ beads numbered $1, 2, \ldots, n$. Two necklaces made out of some of these beads are considered the same if we can get one by rotating the other (with no flipping allowed). For example, with $n \ge 5$, the necklace with four beads $1, 5, 3, 2$ in the clockwise order is same as the one with $5, 3, 2, 1$ in the clockwise order, but is different from the one with $1, 2, 3, 5$ in the clockwise order.
We denote by $D_0(n)$ (respectively $D_1(n)$) the number of ways in which we can use all the beads to make an even number (resp. an odd number) of necklaces each of length at least $3$. Prove that $n - 1$ divides $D_1(n) - D_0(n)$.
2011 ELMO Shortlist, 6
Let $Q(x)$ be a polynomial with integer coefficients. Prove that there exists a polynomial $P(x)$ with integer coefficients such that for every integer $n\ge\deg{Q}$,
\[\sum_{i=0}^{n}\frac{!i P(i)}{i!(n-i)!} = Q(n),\]where $!i$ denotes the number of derangements (permutations with no fixed points) of $1,2,\ldots,i$.
[i]Calvin Deng.[/i]
2011 ELMO Shortlist, 6
Let $Q(x)$ be a polynomial with integer coefficients. Prove that there exists a polynomial $P(x)$ with integer coefficients such that for every integer $n\ge\deg{Q}$,
\[\sum_{i=0}^{n}\frac{!i P(i)}{i!(n-i)!} = Q(n),\]where $!i$ denotes the number of derangements (permutations with no fixed points) of $1,2,\ldots,i$.
[i]Calvin Deng.[/i]