Found problems: 5802
There are 2002 towns in a kingdom. Some of the towns are connected by roads in such a manner that, if all roads from one city closed, one can still travel between any two cities. Every year, the kingdom chooses a non-self-intersecting cycle of roads, founds a new town, connects it by roads with each city from the chosen cycle, and closes all the roads from the original cycle. After several years, no non-self-intersecting cycles remained. Prove that at that moment there are at least 2002 towns, exactly one road going out from each of them.
If $a>1$ and $b>2$ are positive integers, show that $a^{b}+1 \geq b(a+1)$, and determine when equality holds.
A midpoint plotter is an instrument which draws the exact mid point of two point previously drawn. Starting off two points $1$ unit of distance apart and using only the midpoint plotter, you have to get two point which are strictly at a distance between $\frac{1}{2017}$ and $\frac{1}{2016}$ units, drawing the minimum amount of points. ¿Which is the minimum number of times you will need to use the midpoint plotter and what strategy should you follow to achieve it?
A grasshopper rests on the point $(1,1)$ on the plane. Denote by $O,$ the origin of coordinates. From that point, it jumps to a certain lattice point under the condition that, if it jumps from a point $A$ to $B,$ then the area of $\triangle AOB$ is equal to $\frac 12.$
$(a)$ Find all the positive integral poijnts $(m,n)$ which can be covered by the grasshopper after a finite number of steps, starting from $(1,1).$
$(b)$ If a point $(m,n)$ satisfies the above condition, then show that there exists a certain path for the grasshopper to reach $(m,n)$ from $(1,1)$ such that the number of jumps does not exceed $|m-n|.$
Let $a_1<a_2<a_3<a_4<\cdots$ be an infinite sequence of real numbers in the interval $(0,1)$. Show that there exists a number that occurs exactly once in the sequence
\[ \frac{a_1}{1},\frac{a_2}{2},\frac{a_3}{3},\frac{a_4}{4},\ldots.\]
[i]Merlijn Staps[/i]
Let $N_0=\{0, 1, 2 \cdots \}$. Find all functions: $N_0 \to N_0$ such that:
(1) $f(n) < f(n+1)$, all $n \in N_0$;
(2) $f(2)=2$;
(3) $f(mn)=f(m)f(n)$, all $m, n \in N_0$.
For each integer $n\ge 1,$ compute the smallest possible value of \[\sum_{k=1}^{n}\left\lfloor\frac{a_k}{k}\right\rfloor\] over all permutations $(a_1,\dots,a_n)$ of $\{1,\dots,n\}.$
[i]Proposed by Shahjalal Shohag, Bangladesh[/i]
What is the largest possible number of edges in a graph on $2n$ nodes, if there exists exactly one way to split its nodes into $n$ pairs so that the nodes from each pair are connected by an edge?
[i]Proposed by Anton Trygub[/i]
Let $f:[0,1]\to\mathbb{R}$ be a function for which there exists a constant $K>0$ such that $|f(x)-f(y)|\le K|x-y|$ for all $x,y\in [0,1].$ Suppose also that for each rational number $r\in [0,1],$ there exist integers $a$ and $b$ such that $f(r)=a+br.$ Prove that there exist finitely many intervals $I_1,\dots,I_n$ such that $f$ is a linear function on each $I_i$ and $[0,1]=\bigcup_{i=1}^nI_i.$
The numbers $x_1,...x_{100}$ are written on a board so that $ x_1=\frac{1}{2}$ and for every $n$ from $1$ to $99$, $x_{n+1}=1-x_1x_2x_3*...*x_{100}$. Prove that $x_{100}>0.99$.
For all $n$, $t_{n+1} = 2(t_n)^2 - 1$. Prove that gcd $(t_n,t_m) = 1$ if $n \ne m$.
Find all functions $f: \mathbb{N}\to \mathbb{N}$ such that for all $n\in \mathbb{N}$: \[f(n+1) > f(f(n)).\]
For any positive integer $n$, let $\tau (n)$ denote the number of its positive divisors (including 1 and itself). Determine all positive integers $m$ for which there exists a positive integer $n$ such that $\frac{\tau (n^{2})}{\tau (n)}=m$.
Determine all integers $ n\geq 2$ having the following property: for any integers $a_1,a_2,\ldots, a_n$ whose sum is not divisible by $n$, there exists an index $1 \leq i \leq n$ such that none of the numbers $$a_i,a_i+a_{i+1},\ldots,a_i+a_{i+1}+\ldots+a_{i+n-1}$$ is divisible by $n$. Here, we let $a_i=a_{i-n}$ when $i >n$.
[i]Proposed by Warut Suksompong, Thailand[/i]
Find the minimum real $x$ that satisfies
$$\lfloor x \rfloor <\lfloor x^2 \rfloor <\lfloor x^3 \rfloor < \cdots < \lfloor x^n \rfloor < \lfloor x^{n+1} \rfloor < \cdots$$
Find all polynomials $P$ with integer coefficients such that for all positive integers $x,y$, $$\frac{P(x)-P(y)}{x^2+y^2}$$ evaluates to an integer (in particular, it can be zero).
Determine all polynomials $P(x) \in \mathbb R[x]$ satisfying the following two conditions :
(a) $P(2017) = 2016$ and
(b) $(P(x) + 1)^2 = P(x^2 + 1)$ for all real numbers $x$.
[i]proposed by Walther Janous[/i]
Find all positive integers such that $3^{2n}+3n^2+7$ is a perfect square.
Let $n$ be an integer greater than or equal to 3. Prove that there is a set of $n$ points in the plane such that the distance between any two points is irrational and each set of three points determines a non-degenerate triangle with a rational area.
Given a sequence of prime numbers $p_1, p_2,\cdots$ , with the following property:
$p_{n+2}$ is the largest prime divisor of $p_n+p_{n+1}+2018$
Show that the set $\{p_i\}_{i\in \mathbb{N}}$ is finite.
Let $k \geq 2, 1 < n_1 < n_2 < \ldots < n_k$ are positive integers, $a,b \in \mathbb{Z}^+$ satisfy \[ \prod^k_{i=1} \left( 1 - \frac{1}{n_i} \right) \leq \frac{a}{b} < \prod^{k-1}_{i=1} \left( 1 - \frac{1}{n_i} \right) \]
Prove that: \[ \prod^k_{i=1} n_i \geq (4 \cdot a)^{2^k - 1}. \]
An infinite sequence of positive integers $a_1, a_2, \dots$ is called $good$ if
(1) $a_1$ is a perfect square, and
(2) for any integer $n \ge 2$, $a_n$ is the smallest positive integer such that $$na_1 + (n-1)a_2 + \dots + 2a_{n-1} + a_n$$ is a perfect square.
Prove that for any good sequence $a_1, a_2, \dots$, there exists a positive integer $k$ such that $a_n=a_k$ for all integers $n \ge k$.
[size=75](reposting because the other thread didn't get moved)[/size]
In the following, a [i]word[/i] will mean a finite sequence of letters "$a$" and "$b$". The [i]length[/i] of a word will mean the number of the letters of the word. For instance, $abaab$ is a word of length $5$. There exists exactly one word of length $0$, namely the empty word.
A word $w$ of length $\ell$ consisting of the letters $x_1$, $x_2$, ..., $x_{\ell}$ in this order is called a [i]palindrome[/i] if and only if $x_j=x_{\ell+1-j}$ holds for every $j$ such that $1\leq j\leq\ell$. For instance, $baaab$ is a palindrome; so is the empty word.
For two words $w_1$ and $w_2$, let $w_1w_2$ denote the word formed by writing the word $w_2$ directly after the word $w_1$. For instance, if $w_1=baa$ and $w_2=bb$, then $w_1w_2=baabb$.
Let $r$, $s$, $t$ be nonnegative integers satisfying $r + s = t + 2$. Prove that there exist palindromes $A$, $B$, $C$ with lengths $r$, $s$, $t$, respectively, such that $AB=Cab$, if and only if the integers $r + 2$ and $s - 2$ are coprime.
The sequence $ u_n$, $ n\equal{}0,1,2,...$ is defined by $ u_0\equal{}0, u_1\equal{}1$ and for each $ n \ge 1$, $ u_{n\plus{}1}$ is the smallest positive integer greater than $ u_n$ such that $ \{ u_0,u_1,...,u_{n\plus{}1} \}$ contains no three elements in arithmetic progression. Find $ u_{100}$.
Each of the six boxes $B_1$, $B_2$, $B_3$, $B_4$, $B_5$, $B_6$ initially contains one coin. The following operations are allowed
Type 1) Choose a non-empty box $B_j$, $1\leq j \leq 5$, remove one coin from $B_j$ and add two coins to $B_{j+1}$;
Type 2) Choose a non-empty box $B_k$, $1\leq k \leq 4$, remove one coin from $B_k$ and swap the contents (maybe empty) of the boxes $B_{k+1}$ and $B_{k+2}$.
Determine if there exists a finite sequence of operations of the allowed types, such that the five boxes $B_1$, $B_2$, $B_3$, $B_4$, $B_5$ become empty, while box $B_6$ contains exactly $2010^{2010^{2010}}$ coins.
[i]Proposed by Hans Zantema, Netherlands[/i]