Found problems: 5802
An integer $N \ge 2$ is given. A collection of $N(N + 1)$ soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove $N(N - 1)$ players from this row leaving a new row of $2N$ players in which the following $N$ conditions hold:
($1$) no one stands between the two tallest players,
($2$) no one stands between the third and fourth tallest players,
$\;\;\vdots$
($N$) no one stands between the two shortest players.
Show that this is always possible.
[i]Proposed by Grigory Chelnokov, Russia[/i]
Find all positive integers $a$ so that for any $\left \lfloor \frac{a+1}{2} \right \rfloor$-digit number that is composed of only digits $0$ and $2$ (where $0$ cannot be the first digit) is not a multiple of $a$.
Let $q=p^r$ for a prime number $p$ and positive integer $r$. Let $\zeta = e^{\frac{2\pi i}{q}}$. Find the least positive integer $n$ such that
\[\sum_{\substack{1\leq k\leq q\\ \gcd(k,p)=1}} \frac{1}{(1-\zeta^k)^n}\]
is not an integer. (The sum is over all $1\leq k\leq q$ with $p$ not dividing $k$.)
[i]Victor Wang[/i]
Let $\{x_{n}\}_{n\ge0}$ and $\{y_{n}\}_{n\ge0}$ be two sequences defined recursively as follows \[x_{0}=1, \; x_{1}=4, \; x_{n+2}=3 x_{n+1}-x_{n},\] \[y_{0}=1, \; y_{1}=2, \; y_{n+2}=3 y_{n+1}-y_{n}.\] [list=a][*] Prove that ${x_{n}}^{2}-5{y_{n}}^{2}+4=0$ for all non-negative integers. [*] Suppose that $a$, $b$ are two positive integers such that $a^{2}-5b^{2}+4=0$. Prove that there exists a non-negative integer $k$ such that $a=x_{k}$ and $b=y_{k}$.[/list]
Let $n \geq 5$ be a given integer. Determine the greatest integer $k$ for which there exists a polygon with $n$ vertices (convex or not, with non-selfintersecting boundary) having $k$ internal right angles.
[i]Proposed by Juozas Juvencijus Macys, Lithuania[/i]
The Fibonacci sequence $F_n$ is defined by $F_1=F_2=1$ and the recurrence relation $F_n=F_{n-1}+F_{n-2}$ for all integers $n\geq3$.
Let $m,n\geq1$ be integers. Find the minimal degree $d$ for which there exists a polynomial $f(x)=a_dx^d+a_{d-1}x^{d-1}+\dots+a_1x+a_0$, which satisfies $f(k)=F_{m+k}$ for all $k=0,1,...,n$.
Let $n$ be a positive integer and let $a_k = \dfrac{1}{\binom{n}{k}}, b_k = 2^{k-n},\ (k=1..n)$.
Show that $\sum_{k=1}^n \dfrac{a_k-b_k}{k} = 0$.
Find all functions $f: \mathbb{R} \rightarrow \mathbb{R}$ such that
$$f(x^2 + y) \ge (\frac{1}{x} + 1)f(y)$$
holds for all $x \in \mathbb{R} \setminus \{0\}$ and all $y \in \mathbb{R}$.
$F_n$ is the Fibonacci sequence $F_0 = F_1 = 1$, $F_{n+2} = F_{n+1} + F_n$. Find all pairs $m > k \geq 0$ such that the sequence $x_0, x_1, x_2, ...$ defined by $x_0 = \frac{F_k}{F_m}$ and $x_{n+1} = \frac{2x_n - 1}{1 - x_n}$ for $x_n \not = 1$, or $1$ if $x_n = 1$, contains the number $1$
For a fixed natural number $m \geq 2$, prove that
[b]a.)[/b] There exists integers $x_1, x_2, \ldots, x_{2m}$ such that \[x_i x_{m + i} = x_{i + 1} x_{m + i - 1} + 1, i = 1, 2, \ldots, m \hspace{2cm}(*)\]
[b]b.)[/b] For any set of integers $\lbrace x_1, x_2, \ldots, x_{2m}$ which fulfils (*), an integral sequence $\ldots, y_{-k}, \ldots, y_{-1}, y_0, y_1, \ldots, y_k, \ldots$ can be constructed such that $y_k y_{m + k} = y_{k + 1} y_{m + k - 1} + 1, k = 0, \pm 1, \pm 2, \ldots$ such that $y_i = x_i, i = 1, 2, \ldots, 2m$.
Let $\alpha$ and $\beta$ be the roots of $x^{2} - qx + 1$, where $q$ is a rational number larger than $2$. Let $s_1 = \alpha + \beta$, $t_1 = 1$, and for all integers $n \geq 2$:
$s_n = \alpha^n + \beta^n$
$t_n = s_{n-1} + 2s_{n-2} + \cdot \cdot \cdot + (n - 1)s_{1} + n$
Prove that, for all odd integers $n$, $t_n$ is the square of a rational number.
Find all functions $f: \mathbb{N} \rightarrow \mathbb {N}$ such that for all positive integers $m, n$, $f(m+n)\mid f(m)+f(n)$ and $f(m)f(n) \mid f(mn)$.
Let $\mathbb{N}^2$ denote the set of ordered pairs of positive integers. A finite subset $S$ of $\mathbb{N}^2$ is [i]stable[/i] if whenever $(x,y)$ is in $S$, then so are all points $(x',y')$ of $\mathbb{N}^2$ with both $x'\leq x$ and $y'\leq y$.
Prove that if $S$ is a stable set, then among all stable subsets of $S$ (including the empty set and $S$ itself), at least half of them have an even number of elements.
[i]Ashwin Sah and Mehtaab Sawhney[/i]
Let $n$ be an integer greater than $1$ and let $X$ be an $n$-element set. A non-empty collection of subsets $A_1, ..., A_k$ of $X$ is tight if the union $A_1 \cup \cdots \cup A_k$ is a proper subset of $X$ and no element of $X$ lies in exactly one of the $A_i$s. Find the largest cardinality of a collection of proper non-empty subsets of $X$, no non-empty subcollection of which is tight.
[i]Note[/i]. A subset $A$ of $X$ is proper if $A\neq X$. The sets in a collection are assumed to be distinct. The whole collection is assumed to be a subcollection.
For a set $S$, let $|S|$ denote the number of elements in $S$. Let $A$ be a set of positive integers with $|A| = 2001$. Prove that there exists a set $B$ such that
(i) $B \subseteq A$;
(ii) $|B| \ge 668$;
(iii) for any $u, v \in B$ (not necessarily distinct), $u+v \not\in B$.
Let \( n \geq 4 \). Proof that
\[
(2^x - 1)(5^x - 1) = y^n
\]
have no positive integer solution \((x, y)\).
Prove that for every positive integer $ n$,
$ n^n \le (n!)^2 \le \left( \frac{(n\plus{}1)(n\plus{}2)}{6} \right) ^n.$
Let $ a_0$, $ a_1$, $ a_2$, $ \ldots$ be a sequence of positive integers such that the greatest common divisor of any two consecutive terms is greater than the preceding term; in symbols, $ \gcd (a_i, a_{i \plus{} 1}) > a_{i \minus{} 1}$. Prove that $ a_n\ge 2^n$ for all $ n\ge 0$.
[i]Proposed by Morteza Saghafian, Iran[/i]
For a set \(S\) of positive integers and a positive integer \(n\), consider the game of [i]\((n,S)\)-nim[/i], which is as follows. A pile starts with \(n\) watermelons. Two players, Deric and Erek, alternate turns eating watermelons from the pile, with Deric going first. On any turn, the number of watermelons eaten must be an element of \(S\). The last player to move wins. Let \(f(S)\) denote the set of positive integers \(n\) for which Deric has a winning strategy in \((n,S)\)-nim.
Let \(T\) be a set of positive integers. Must the sequence \[T, \; f(T), \; f(f(T)), \;\ldots\] be eventually constant?
[i]Proposed by Brandon Wang and Edward Wan[/i]
Find all polynomials $P$ such that $P(x)+3P(x+2)=3P(x+1)+P(x+3)$ for all real numbers $x$.
Let $\mathbb{Z}_{\ge 0}$ be the set of all nonnegative integers. Find all the functions $f: \mathbb{Z}_{\ge 0} \rightarrow \mathbb{Z}_{\ge 0} $ satisfying the relation
\[ f(f(f(n))) = f(n+1 ) +1 \]
for all $ n\in \mathbb{Z}_{\ge 0}$.
Determine the least possible value of $f(1998),$ where $f:\Bbb{N}\to \Bbb{N}$ is a function such that for all $m,n\in {\Bbb N}$,
\[f\left( n^{2}f(m)\right) =m\left( f(n)\right) ^{2}. \]
Let $A$ be a set of positive integers such that
a) if $a\in A$, the all the positive divisors of $a$ are also in $A$;
b) if $a,b\in A$, with $1<a<b$, then $1+ab \in A$.
Prove that if $A$ has at least 3 elements, then $A$ is the set of all positive integers.
We are given $3n$ points $A_1,A_2, \ldots , A_{3n}$ in the plane, no three of them collinear. Prove that one can construct $n$ disjoint triangles with vertices at the points $A_i.$
Let $n\geq2$ be an integer. An $n$-tuple $(a_1,a_2,\dots,a_n)$ of not necessarily different positive integers is [i]expensive[/i] if there exists a positive integer $k$ such that $$(a_1+a_2)(a_2+a_3)\dots(a_{n-1}+a_n)(a_n+a_1)=2^{2k-1}.$$
a) Find all integers $n\geq2$ for which there exists an expensive $n$-tuple.
b) Prove that for every odd positive integer $m$ there exists an integer $n\geq2$ such that $m$ belongs to an expensive $n$-tuple.
[i]There are exactly $n$ factors in the product on the left hand side.[/i]