Found problems: 5802
An [i]$n$-city[/i] is an $n \times n$ grid of positive integers such that every entry greater than 1 is
the sum of an entry in the same row and an entry in the same column. Shown below is an
example $3$-city.
$$\begin{pmatrix}
1 & 1 & 2 \\
2 & 3 & 1 \\
6 & 4 & 1
\end{pmatrix}$$
(a) Construct a $5$-city that includes some entry that is at least $150$. (It is acceptable simply to write the $5$-city. You do not need to explain how you found it.)
(b) Show that for all $n \ge 1$, the largest entry in an $n$-city is at most $3^{\binom{n}{2}}$.
Let $a > 1$ be a positive integer and $d > 1$ be a positive integer coprime to $a$. Let $x_1=1$, and for $k\geq 1$, define
$$x_{k+1} = \begin{cases}
x_k + d &\text{if } a \text{ does not divide } x_k \\
x_k/a & \text{if } a \text{ divides } x_k
\end{cases}$$
Find, in terms of $a$ and $d$, the greatest positive integer $n$ for which there exists an index $k$ such that $x_k$ is divisible by $a^n$.
The integers $a_0, a_1, a_2, a_3,\ldots$ are defined as follows:
$a_0 = 1$, $a_1 = 3$, and $a_{n+1} = a_n + a_{n-1}$ for all $n \ge 1$.
Find all integers $n \ge 1$ for which $na_{n+1} + a_n$ and $na_n + a_{n-1}$ share a common factor greater than $1$.
You are given a set of $n$ blocks, each weighing at least $1$; their total weight is $2n$. Prove that for every real number $r$ with $0 \leq r \leq 2n-2$ you can choose a subset of the blocks whose total weight is at least $r$ but at most $r + 2$.
At a party with $n$ people, it is known that among any $4$ people, there are either $3$ people who all know one another or $3$ people none of which knows another. Show that the $n$ people can be separated into two rooms, so that everyone in one room knows one another and no two people in the other room know each other.
Consider a $100\times 100$ square unit lattice $\textbf{L}$ (hence $\textbf{L}$ has $10000$ points). Suppose $\mathcal{F}$ is a set of polygons such that all vertices of polygons in $\mathcal{F}$ lie in $\textbf{L}$ and every point in $\textbf{L}$ is the vertex of exactly one polygon in $\mathcal{F}.$ Find the maximum possible sum of the areas of the polygons in $\mathcal{F}.$
[i]Michael Ren and Ankan Bhattacharya, USA[/i]
A student wrote down the following sequence of numbers : the first number is 1, the second number is 2, and after that, each number is obtained by adding together all the previous numbers. Determine the 12th number in the sequence.
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 natural numbers $n$ the product of whose decimal digits is $n^2-10n-22$.
Find $f: \mathbb{Z}_+ \rightarrow \mathbb{Z}_+$, such that for any $x,y \in \mathbb{Z}_+$, $$f(f(x)+y)\mid x+f(y).$$
Find all roots of the equation :-
$1-\frac{x}{1}+\frac{x(x-1)}{2!} - \cdots +(-1)^n\frac{x(x-1)(x-2)...(x-n+1)}{n!}=0$.
Let $A$ and $B$ points in the plane and $C$ a point in the perpendiclar bisector of $AB$. It is constructed a sequence of points $C_1,C_2,\dots, C_n,\dots$ in the following way: $C_1=C$ and for $n\geq1$, if $C_n$ does not belongs to $AB$, then $C_{n+1}$ is the circumcentre of the triangle $\triangle{ABC_n}$.
Find all the points $C$ such that the sequence $C_1,C_2,\dots$ is defined for all $n$ and turns eventually periodic.
Note: A sequence $C_1,C_2, \dots$ is called eventually periodic if there exist positive integers $k$ and $p$ such that $C_{n+p}=c_n$ for all $n\geq{k}$.
Basketball star Shanille O'Keal's team statistician keeps track of the number, $S(N),$ of successful free throws she has made in her first $N$ attempts of the season. Early in the season, $S(N)$ was less than 80% of $N,$ but by the end of the season, $S(N)$ was more than 80% of $N.$ Was there necessarily a moment in between when $S(N)$ was exactly 80% of $N$?
Find the number of partitions of the set $\{1, 2, \cdots, n\}$ into three subsets $A_1,A_2,A_3$, some of which may be empty, such that the following conditions are satisfied:
$(i)$ After the elements of every subset have been put in ascending order, every two consecutive elements of any subset have different parity.
$(ii)$ If $A_1,A_2,A_3$ are all nonempty, then in exactly one of them the minimal number is even .
[i]Proposed by Poland.[/i]
The functions $f_0, f_1, f_2, ...$ are defined on the reals by $f_0(x) = 8$ for all $x$, $f_{n+1}(x) = \sqrt{x^2 + 6f_n(x)}$. For all $n$ solve the equation $f_n(x) = 2x$.
Prove that for $n\geq 2$, \[\underbrace{2^{2^{\cdots^{2}}}}_{n\text{ terms}}\equiv \underbrace{2^{2^{\cdots^{2}}}}_{n-1\text{ terms}}\; \pmod{n}.\]
Let $A$ and $B$ infinite sets of positive real numbers such that:
1. For any pair of elements $u \ge v$ in $A$, it follows that $u+v$ is an element of $B$.
2. For any pair of elements $s>t$ in $B$, it follows that $s-t$ is an element of $A$.
Prove that $A=B$ or there exists a real number $r$ such that $B=\{2r, 3r, 4r, 5r, \dots\}$.
Let $p$ be a prime number, $n$ a natural number which is not divisible by $p$, and $\mathbb{K}$ is a finite field, with $char(K) = p, |K| = p^n, 1_{\mathbb{K}}$ unity element and $\widehat{0} = 0_{\mathbb{K}}.$ For every $m \in \mathbb{N}^{*}$ we note
$ \widehat{m} = \underbrace{1_{\mathbb{K}} + 1_{\mathbb{K}} + \ldots + 1_{\mathbb{K}}}_{m \text{ times}} $ and define the polynomial
\[
f_m = \sum_{k = 0}^{m} (-1)^{m - k} \widehat{\binom{m}{k}} X^{p^k} \in \mathbb{K}[X].
\]
a) Show that roots of $f_1$ are $ \left\{ \widehat{k} | k \in \{0,1,2, \ldots , p - 1 \} \right\}$.
b) Let $m \in \mathbb{N}^{*}.$ Determine the set of roots from $\mathbb{K}$ of polynomial $f_{m}.$
Let $a$ and $k$ be positive integers. Prove that for every positive integer $d$ there exists a positive integer $n$ such that $d$ divides $ka^n + n.$
Define a sequence called the $2020$-nacci sequence. It is defined as follows: If $n \le 2020$ then $S_n=1,$ if $n>2020$ then $S_n=\sum_{i=n-2020}^{n-1} S_i.$ Find the last two digits of $S_{4040}.$
In Lineland there are $n\geq1$ towns, arranged along a road running from left to right. Each town has a [i]left bulldozer[/i] (put to the left of the town and facing left) and a [i]right bulldozer[/i] (put to the right of the town and facing right). The sizes of the $2n$ bulldozers are distinct. Every time when a left and right bulldozer confront each other, the larger bulldozer pushes the smaller one off the road. On the other hand, bulldozers are quite unprotected at their rears; so, if a bulldozer reaches the rear-end of another one, the first one pushes the second one off the road, regardless of their sizes.
Let $A$ and $B$ be two towns, with $B$ to the right of $A$. We say that town $A$ can [i]sweep[/i] town $B$ [i]away[/i] if the right bulldozer of $A$ can move over to $B$ pushing off all bulldozers it meets. Similarly town $B$ can sweep town $A$ away if the left bulldozer of $B$ can move over to $A$ pushing off all bulldozers of all towns on its way.
Prove that there is exactly one town that cannot be swept away by any other one.
Let be a natural number $ n. $ Solve in the set of $ 2\times 2 $ complex matrices the equation
$$ \begin{pmatrix} -2& 2007\\ 0&-2 \end{pmatrix} =X^{3n}-3X^n. $$
[i]Petru Vlad[/i]
We have a $2\times n$ rectangle. We call each $1\times1$ square a room and we show the room in the $i^{th}$ row and $j^{th}$ column as $(i,j)$. There are some coins in some rooms of the rectangle. If there exist more than $1$ coin in each room, we can delete $2$ coins from it and add $1$ coin to its right adjacent room OR we can delete $2$ coins from it and add $1$ coin to its up adjacent room. Prove that there exists a finite configuration of allowable operations such that we can put a coin in the room $(1,n)$.
Given a four digit string $ k=\overline{abcd} $, $ a, b, c, d\in \{0, 1, \cdots, 9\} $, prove that there exist a $n<20000$ such that $2^n$ contains $k$ as a substring when written in base $10$.
[Extra: Can you give a better bound? Mine is $12517$]
For any $h = 2^{r}$ ($r$ is a non-negative integer), find all $k \in \mathbb{N}$ which satisfy the following condition: There exists an odd natural number $m > 1$ and $n \in \mathbb{N}$, such that $k \mid m^{h} - 1, m \mid n^{\frac{m^{h}-1}{k}} + 1$.