Found problems: 1782
Let $A$ be an infinite set of positive integers such that every $n \in A$ is the product of at most $1987$ prime numbers. Prove that there is an infinite set $B \subset A$ and a number $p$ such that the greatest common divisor of any two distinct numbers in $B$ is $p.$
Given 2005 distinct numbers $a_1,\,a_2,\dots,a_{2005}$. By one question, we may take three different indices $1\le i<j<k\le 2005$ and find out the set of numbers $\{a_i,\,a_j,\,a_k\}$ (unordered, of course). Find the minimal number of questions, which are necessary to find out all numbers $a_i$.
Show that $ \frac{1}{2^2} +\frac{1}{3^2} +...+\frac{1}{n^2} <\frac{2}{3}$ for all $n \ge 2 $.
Let $n$ to be a positive integer. Given a set $\{ a_1, a_2, \ldots, a_n \} $ of integers, where $a_i \in \{ 0, 1, 2, 3, \ldots, 2^n -1 \},$ $\forall i$, we associate to each of its subsets the sum of its elements; particularly, the empty subset has sum of its elements equal to $0$. If all of these sums have different remainders when divided by $2^n$, we say that $\{ a_1, a_2, \ldots, a_n \} $ is [i]$n$-complete[/i].
For each $n$, find the number of [i]$n$-complete[/i] sets.
Is $\cos 1^\circ$ rational? Prove.
Let $m$ and $n$ be positive integers. If $x_1$, $x_2$, $\cdots$, $x_m$ are positive integers whose arithmetic mean is less than $n+1$ and if $y_1$, $y_2$, $\cdots$, $y_n$ are positive integers whose arithmetic mean is less than $m+1$, prove that some sum of one or more $x$'s equals some sum of one or more $y$'s.
In a badminton tournament, each of $n$ players play all the other $n-1$ players. Each game results in either a win, or a loss. The players then write down the names of those whom they defeated, and also of those who they defeated. For example, if $A$ beats $B$ and $B$ beats $C,$ then $A$ writes the names of both $B$ and $C$. Show that there will be one person, who has written down the names of all the other $n-1$ players.
[hide="Clarification"]
Consider a game between $A,B,C,D,E,F,G$ where $A$ defeats $B$ and $C$ and $B$ defeats $E,F$, $C$ defeats $E.$ Then $A$'s list will have $(B,C,E,F)$, and will not include $G.$
[/hide]
Prove that the elements of any natural power of a $ 2\times 2 $ special linear integer matrix are pairwise coprime, with the possible exception of the pairs that form the diagonals.
[i]Vasile Pop[/i]
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.)
How many ways are there to line up $19$ girls (all of different heights) in a row so that no girl has a shorter girl both in front of and behind her?
For a positive integer $n$ consider any partition of the set $\{ 1,2,\ldots ,2n \}$ into $n$ two-element subsets $P_1,P_2\ldots,P_n$. In each subset $P_i$, let $p_i$ be the product of the two numbers in $P_i$. Prove that
\[\frac{1}{p_1}+\frac{1}{p_2}+\ldots + \frac{1}{p_n}<1 \]
Consider a directed graph $G$ with $n$ vertices, where $1$-cycles and $2$-cycles are permitted. For any set $S$ of vertices, let $N^{+}(S)$ denote the out-neighborhood of $S$ (i.e. set of successors of $S$), and define $(N^{+})^k(S)=N^{+}((N^{+})^{k-1}(S))$ for $k\ge2$.
For fixed $n$, let $f(n)$ denote the maximum possible number of distinct sets of vertices in $\{(N^{+})^k(X)\}_{k=1}^{\infty}$, where $X$ is some subset of $V(G)$. Show that there exists $n>2012$ such that $f(n)<1.0001^n$.
[i]Linus Hamilton.[/i]
For any integer $k\ge1$, let $p(k)$ be the smallest prime which does not divide $k$. Define the integer function $X(k)$ to be the product of all primes less than $p(k)$ if $p(k)>2$, and $X(k)=1$ if $p(k)=2$. Let $\{x_n\}$ be the sequence defined by $x_0=1$, and $x_{n+1}X(x_n)=x_np(x_n)$ for $n\ge0$. Find the smallest positive integer, $t$ such that $x_t=2090$.
Consider a directed graph $G$ with $n$ vertices, where $1$-cycles and $2$-cycles are permitted. For any set $S$ of vertices, let $N^{+}(S)$ denote the out-neighborhood of $S$ (i.e. set of successors of $S$), and define $(N^{+})^k(S)=N^{+}((N^{+})^{k-1}(S))$ for $k\ge2$.
For fixed $n$, let $f(n)$ denote the maximum possible number of distinct sets of vertices in $\{(N^{+})^k(X)\}_{k=1}^{\infty}$, where $X$ is some subset of $V(G)$. Show that there exists $n>2012$ such that $f(n)<1.0001^n$.
[i]Linus Hamilton.[/i]
$a_1, a_2, ..., a_{95}$ are positive reals. Show that
$\displaystyle \sum_{k=1}^{95}{a_k} \le 94+ \prod_{k=1}^{95}{\max{\{1,a_k\}}}$
Let $m$ and $n$ denote integers greater than $1$, and let $\nu (n)$ be the number of primes less than or equal to $n$. Show that if the equation $\frac{n}{\nu(n)}=m$ has a solution, then so does the equation $\frac{n}{\nu(n)}=m-1$.
Let $ M$ be the set of those positive integers which are not divisible by $ 3$. The sum of $ 2n$ consecutive elements of $ M$ is $ 300$. Determine $ n$.
Let $f(n)=\sum_{k=0}^{n-1}x^ky^{n-1-k}$ with, $x$, $y$ real numbers. If $f(n)$, $f(n+1)$, $f(n+2)$, $f(n+3)$, are integers for some $n$, prove $f(n)$ is integer for all $n$.
Let $ \theta$ be an angle in the interval $ (0,\pi/2)$. Given that $ \cos \theta$ is irrational, and that $ \cos k \theta$ and $ \cos[(k \plus{} 1)\theta ]$ are both rational for some positive integer $ k$, show that $ \theta \equal{} \pi/6$.
The sequence of polynomials $(a_n)$ is defined by $a_0=0$, $ a_1=x+2$ and $a_n=a_{n-1}+3a_{n-1}a_{n-2} +a_{n-2}$ for $n>1$.
(a) Show for all positive integers $k,m$: if $k$ divides $m$ then $a_k$ divides $a_m$.
(b) Find all positive integers $n$ such that the sum of the roots of polynomial $a_n$ is an integer.
The sequence $\{a_n\}_{n\geq 0}$ of real numbers satisfies the relation:
\[ a_{m+n} + a_{m-n} - m + n -1 = \frac12 (a_{2m} + a_{2n}) \]
for all non-negative integers $m$ and $n$, $m \ge n$. If $a_1 = 3$ find $a_{2004}$.
Let $\{a_n\}_{n\geq 0}$ be a non-decreasing, unbounded sequence of non-negative integers with $a_0=0$. Let the number of members of the sequence not exceeding $n$ be $b_n$. Prove that \[ (a_0 + a_1 + \cdots + a_m)( b_0 + b_1 + \cdots + b_n ) \geq (m + 1)(n + 1). \]
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.
A bookshelf contains $n$ volumes, labelled $1$ to $n$, in some order. The librarian wishes to put them in the correct order as follows. The librarian selects a volume that is too far to the right, say the volume with label $k$, takes it out, and inserts it in the $k$-th position. For example, if the bookshelf contains the volumes $1,3,2,4$ in that order, the librarian could take out volume $2$ and place it in the second position. The books will then be in the correct order $1,2,3,4$.
(a) Show that if this process is repeated, then, however the librarian makes the selections, all the volumes will eventually be in the correct order.
(b) What is the largest number of steps that this process can take?
We call an integer $ n > 1$ [i]good[/i] if, for any natural numbers $ 1 \le b_1, b_2, \ldots , b_{n\minus{}1} \le n \minus{} 1$ and any $ i \in \{0, 1, \ldots , n \minus{} 1\}$, there is a subset $ I$ of $ \{1, \ldots , n \minus{} 1\}$ such that $ \sum_{k\in I} b_k \equiv i \pmod n$. (The sum over the empty set is zero.) Find all good numbers.