Found problems: 5802
A collection of $2n$ letters contains $2$ each of $n$ different letters. The collection is partitioned into $n$ pairs, each pair containing $2$ letters, which may be the same or different. Denote the number of distinct partitions by $u_n$. (Partitions differing in the order of the pairs in the partition or in the order of the two letters in the pairs are not considered distinct.) Prove that $u_{n+1}=(n+1)u_n - \frac{n(n-1)}{2} u_{n-2}.$
[i]Similar Problem :[/i]
A pack of $2n$ cards contains $n$ pairs of $2$ identical cards. It is shuffled and $2$ cards are dealt to each of $n$ different players. Let $p_n$ be the probability that every one of the $n$ players is dealt two identical cards. Prove that $\frac{1}{p_{n+1}}=\frac{n+1}{p_n} + \frac{n(n-1)}{2p_{n-2}}.$
The sequence $ \{a_n\}$ of integers is defined by
\[ a_1 \equal{} 2, a_2 \equal{} 7
\]
and
\[ \minus{} \frac {1}{2} < a_{n \plus{} 1} \minus{} \frac {a^2_n}{a_{n \minus{} 1}} \leq \frac {}{}, n \geq 2.
\]
Prove that $ a_n$ is odd for all $ n > 1.$
Let $T$ a set with 2007 points on the plane, without any 3 collinear points.
Let $P$ any point which belongs to $T$.
Prove that the number of triangles that contains the point $P$ inside and
its vertices are from $T$, is even.
Let $p$ be a given odd prime. Find the largest integer $k'$ such that it is possible to partition $\{1,2,\cdots,p-1\}$ into two sets $X,Y$ such that for any $k$ with $0 \le k \le k'$,
$$\sum_{a \in X}a^k \equiv \sum_{b \in Y}b^k \pmod p$$
[i]houkai[/i]
Find the maximal number of edges a connected graph $G$ with $n$ vertices may have, so that after deleting an arbitrary cycle, $G$ is not connected anymore.
The function $ F$ is defined on the set of nonnegative integers and takes nonnegative integer values satisfying the following conditions: for every $ n \geq 0,$
(i) $ F(4n) \equal{} F(2n) \plus{} F(n),$
(ii) $ F(4n \plus{} 2) \equal{} F(4n) \plus{} 1,$
(iii) $ F(2n \plus{} 1) \equal{} F(2n) \plus{} 1.$
Prove that for each positive integer $ m,$ the number of integers $ n$ with $ 0 \leq n < 2^m$ and $ F(4n) \equal{} F(3n)$ is $ F(2^{m \plus{} 1}).$
Let $f$ be a function defined on the set of positive integers , and with values in the same set, which satisfies:
$\bullet$ $f (n + f (n)) = 1$ for all $n\ge 1$.
$\bullet$ $f (1998) = 2$
Find the lowest possible value of the sum $f (1) + f (2) +... + f (1999)$, and find the formula of $f$ for which this minimum is satisfied,
Let $n$ be a given positive integer. Sisyphus performs a sequence of turns on a board consisting of $n + 1$ squares in a row, numbered $0$ to $n$ from left to right. Initially, $n$ stones are put into square $0$, and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with $k$ stones, takes one of these stones and moves it to the right by at most $k$ squares (the stone should say within the board). Sisyphus' aim is to move all $n$ stones to square $n$.
Prove that Sisyphus cannot reach the aim in less than
\[ \left \lceil \frac{n}{1} \right \rceil + \left \lceil \frac{n}{2} \right \rceil + \left \lceil \frac{n}{3} \right \rceil + \dots + \left \lceil \frac{n}{n} \right \rceil \]
turns. (As usual, $\lceil x \rceil$ stands for the least integer not smaller than $x$. )
Let $f\colon\mathbb{N}\rightarrow\mathbb{N}^{\ast}$ be a strictly increasing function. Prove that:
[list=a]
[*]There exists a decreasing sequence of positive real numbers, $(y_{n})_{n\in\mathbb{N}}$, converging to $0$, such that $y_{n}\leq2y_{f(n)}$, for all $n\in\mathbb{N}$.
[*]If $(x_{n})_{n\in\mathbb{N}}$ is a decreasing sequence of real numbers, converging to $0$, then there exists a decreasing sequence of real numbers $(y_{n})_{n\in\mathbb{N}}$, converging to $0$, such that $x_{n}\leq y_{n} \leq2y_{f(n)}$, for all $n\in\mathbb{N}$.[/list]
Is there a triangle with angles in ratio of $ 1: 2: 4$ and the length of its sides are integers with at least one of them is a prime number?
[i]Nanang Susyanto, Jogjakarta[/i]
Find all pairs of function $ f: \mathbb{N} \rightarrow \mathbb{N}$ and polynomial with integer coefficients $ p$ such that:
(i) $ p(mn) \equal{} p(m)p(n)$ for all positive integers $ m,n > 1$ with $ \gcd(m,n) \equal{} 1$, and
(ii) $ \sum_{d|n}f(d) \equal{} p(n)$ for all positive integers $ n$.
Given is a sequence $a_1, a_2, \ldots$, such that $a_1=1$ and $a_{n+1}=\frac{9a_n+4}{a_n+6}$ for any $n \in \mathbb{N}$. Which terms of this sequence are positive integers?
Let $\mathbb{Z}_{>0}$ be the set of positive integers. Find all functions $f : \mathbb{Z}_{>0} \rightarrow \mathbb{Z}_{>0}$ such that, for all $m, n \in \mathbb{Z}_{>0 }$:
$$f(mf(n)) + f(n) | mn + f(f(n)).$$
Let $S$ be a finite set of points in the plane. A linear partition of $S$ is an unordered pair $\{A,B\}$ of subsets of $S$ such that $A\cup B=S,\ A\cap B=\emptyset,$ and $A$ and $B$ lie on opposite sides of some straight line disjoint from $S$ ($A$ or $B$ may be empty). Let $L_{S}$ be the number of linear partitions of $S.$ For each positive integer $n,$ find the maximum of $L_{S}$ over all sets $S$ of $n$ points.
The $100$ vertices of a prism, whose base is a $50$-gon, are labeled with numbers $1, 2, 3, \ldots, 100$ in any order. Prove that there are two vertices, which are connected by an edge of the prism, with labels differing by not more than $48$.
Note: In all the triangles the three vertices do not lie on a straight line.
Let $ \mathcal{P}$ be a square and let $ n$ be a nonzero positive integer for which we denote by $ f(n)$ the maximum number of elements of a partition of $ \mathcal{P}$ into rectangles such that each line which is parallel to some side of $ \mathcal{P}$ intersects at most $ n$ interiors (of rectangles). Prove that
\[ 3 \cdot 2^{n\minus{}1} \minus{} 2 \le f(n) \le 3^n \minus{} 2.\]
In a language$,$ an alphabet with $25$ letters is used$;$ words are exactly all sequences of $($ not necessarily different $)$ letters of length $17.$ Two ends of a paper strip are glued so that the strip forms a ring$;$ the strip bears a sequence of $5^{18}$ letters$.$ Say that a word is singular if one can cut a piece bearing exactly that word from the strip$,$ but one cannot cut out two such non-overlapping pieces$.$ It is known that one can cut out $5^{16}$ non-overlapping pieces each containing the same word$.$ Determine the largest possible number of singular words$.$
[i](Bogdanov I.)[/i]
Given positive integers $k, m, n$ such that $1 \leq k \leq m \leq n$. Evaluate
\[\sum^{n}_{i=0} \frac{(-1)^i}{n+k+i} \cdot \frac{(m+n+i)!}{i!(n-i)!(m+i)!}.\]
For each positive integer $n$, write the sum $\sum_{m=1}^n 1/m$ in the form $p_n/q_n$, where $p_n$ and $q_n$ are relatively prime positive integers. Determine all $n$ such that 5 does not divide $q_n$.
Let $ n$ and $ k$ be positive integers. Say that a permutation $ \sigma$ of $ \{1,2,\dots n\}$ is $ k$-[i]limited[/i] if $ |\sigma(i)\minus{}i|\le k$ for all $ i.$ Prove that the number of $ k$-limited permutations of $ \{1,2,\dots n\}$ is odd if and only if $ n\equiv 0$ or $ 1\pmod{2k\plus{}1}.$
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.)
A finite set $S$ of positive integers has the property that, for each $s \in S,$ and each positive integer divisor $d$ of $s$, there exists a unique element $t \in S$ satisfying $\text{gcd}(s, t) = d$. (The elements $s$ and $t$ could be equal.)
Given this information, find all possible values for the number of elements of $S$.
Let $n$ be an integer greater than 2. A positive integer is said to be [i]attainable [/i]if it is 1 or can be obtained from 1 by a sequence of operations with the following properties:
1.) The first operation is either addition or multiplication.
2.) Thereafter, additions and multiplications are used alternately.
3.) In each addition, one can choose independently whether to add 2 or $n$
4.) In each multiplication, one can choose independently whether to multiply by 2 or by $n$.
A positive integer which cannot be so obtained is said to be [i]unattainable[/i].
[b]a.)[/b] Prove that if $n\geq 9$, there are infinitely many unattainable positive integers.
[b]b.)[/b] Prove that if $n=3$, all positive integers except 7 are attainable.
A figure $\Phi$ composed of unit squares has the following property: if the squares of an $m \times n$ rectangle ($m,n$ are fixed) are filled with numbers whose sum is positive, the figure $\Phi$ can be placed within the rectangle (possibly after being rotated) so that the sum of the covered numbers is also positive. Prove that a number of such figures can be put on the $m\times n$ rectangle so that each square is covered by the same number of figures.
Find all positive integers $ n$ having the following properties:in two-dimensional Cartesian coordinates, there exists a convex $ n$ lattice polygon whose lengths of all sides are odd numbers, and unequal to each other. (where lattice polygon is defined as polygon whose coordinates of all vertices are integers in Cartesian coordinates.)