Found problems: 5802
Can there be drawn on a circle of radius $1$ a number of $1975$ distinct points, so that the distance (measured on the chord) between any two points (from the considered points) is a rational number?
Suppose $ \,G\,$ is a connected graph with $ \,k\,$ edges. Prove that it is possible to label the edges $ 1,2,\ldots ,k\,$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to 1.
[b]Note: Graph-Definition[/b]. A [b]graph[/b] consists of a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of vertices $ \,u,v\,$ belongs to at most one edge. The graph $ G$ is connected if for each pair of distinct vertices $ \,x,y\,$ there is some sequence of vertices $ \,x \equal{} v_{0},v_{1},v_{2},\cdots ,v_{m} \equal{} y\,$ such that each pair $ \,v_{i},v_{i \plus{} 1}\;(0\leq i < m)\,$ is joined by an edge of $ \,G$.
The sequence $a_1 = 1$, $a_2, a_3, \cdots$ is defined as follows: if $a_n - 2$ is a natural number not already occurring on the board, then $a_{n+1} = a_n-2$; otherwise, $a_{n+1} = a_n + 3$. Prove that every nonzero perfect square occurs in the sequence as the previous term increased by $3$.
A plane has a special point $O$ called the origin. Let $P$ be a set of 2021 points in the plane such that
[list]
[*] no three points in $P$ lie on a line and
[*] no two points in $P$ lie on a line through the origin.
[/list]
A triangle with vertices in $P$ is [i]fat[/i] if $O$ is strictly inside the triangle. Find the maximum number of fat triangles.
For some positive integer $n,$ Elmo writes down the equation
\[x_1+x_2+\dots+x_n=x_1+x_2+\dots+x_n.\]
Elmo inserts at least one $f$ to the left side of the equation and adds parentheses to create a valid functional equation. For example, if $n=3,$ Elmo could have created the equation
\[f(x_1+f(f(x_2)+x_3))=x_1+x_2+x_3.\]
Cookie Monster comes up with a function $f: \mathbb{Q}\to\mathbb{Q}$ which is a solution to Elmo's functional equation. (In other words, Elmo's equation is satisfied for all choices of $x_1,\dots,x_n\in\mathbb{Q})$. Is it possible that there is no integer $k$ (possibly depending on $f$) such that $f^k(x)=x$ for all $x$?
[i]Srinivas Arun[/i]
Consider a binary matrix $M$(all entries are $0$ or $1$) on $r$ rows and $c$ columns, where every row and every column contain at least one entry equal to $1$. Prove that there exists an entry $M(i,j) = 1$, such that the corresponding row-sum $R(i)$ and column-sum $C(j)$ satisfy $r R(i)\ge c C(j)$.
(Proposed by Gerhard Woeginger, Austria)
A set $P$ consists of $2005$ distinct prime numbers. Let $A$ be the set of all possible products of $1002$ elements of $P$ , and $B$ be the set of all products of $1003$ elements of $P$ . Find a one-to-one correspondance $f$ from $A$ to $B$ with the property that $a$ divides $f (a)$ for all $a \in A.$
In a regular 100-gon, 41 vertices are colored black and the remaining 59 vertices are colored white. Prove that there exist 24 convex quadrilaterals $Q_{1}, \ldots, Q_{24}$ whose corners are vertices of the 100-gon, so that
[list]
[*] the quadrilaterals $Q_{1}, \ldots, Q_{24}$ are pairwise disjoint, and
[*] every quadrilateral $Q_{i}$ has three corners of one color and one corner of the other color.
[/list]
The number $1$ is written on the blackboard. After that a sequence of numbers is created as follows: at each step each number $a$ on the blackboard is replaced by the numbers $a - 1$ and $a + 1$; if the number $0$ occurs, it is erased immediately; if a number occurs more than once, all its occurrences are left on the blackboard. Thus the blackboard will show $1$ after $0$ steps; $2$ after $1$ step; $1, 3$ after $2$ steps; $2, 2, 4$ after $3$ steps, and so on. How many numbers will there be on the blackboard after $n$ steps?
Let $R^+$ be the set of positive real numbers. Determine all functions $f:R^+$ $\rightarrow$ $R^+$ such that for all positive real numbers $x$ and $y:$
\[f(x+f(xy))+y=f(x)f(y)+1\]
[i]Ukraine[/i]
Let there be an integer $n\geq2$. In a chess tournament $n$ players play between each other one game. No game ended in a draw. Show that after the end of the tournament the players can be arranged in a list: $P_1, P_2, P_3,\ldots,P_n$ such that for every $i (1\leq i\leq n-1)$ the player $P_i$ won against player $P_{i+1}$.
Let $n$ be a positive integer. We have $n$ boxes where each box contains a non-negative number of pebbles. In each move we are allowed to take two pebbles from a box we choose, throw away one of the pebbles and put the other pebble in another box we choose. An initial configuration of pebbles is called [i]solvable[/i] if it is possible to reach a configuration with no empty box, in a finite (possibly zero) number of moves. Determine all initial configurations of pebbles which are not solvable, but become solvable when an additional pebble is added to a box, no matter which box is chosen.
For a positive integer $n$, define $f(n)$ to be the number of sequences $(a_1,a_2,\dots,a_k)$ such that $a_1a_2\cdots a_k=n$ where $a_i\geq 2$ and $k\ge 0$ is arbitrary. Also we define $f(1)=1$. Now let $\alpha>1$ be the unique real number satisfying $\zeta(\alpha)=2$, i.e $ \sum_{n=1}^{\infty}\frac{1}{n^\alpha}=2 $
Prove that
[list]
(a) \[ \sum_{j=1}^{n}f(j)=\mathcal{O}(n^\alpha) \]
(b) There is no real number $\beta<\alpha$ such that
\[ \sum_{j=1}^{n}f(j)=\mathcal{O}(n^\beta) \]
[/list]
A $2^{2014} + 1$ by $2^{2014} + 1$ grid has some black squares filled. The filled black squares form one or more snakes on the plane, each of whose heads splits at some points but never comes back together. In other words, for every positive integer $n$ greater than $2$, there do not exist pairwise distinct black squares $s_1$, $s_2$, \dots, $s_n$ such that $s_i$ and $s_{i+1}$ share an edge for $i=1,2, \dots, n$ (here $s_{n+1}=s_1$).
What is the maximum possible number of filled black squares?
[i]Proposed by David Yang[/i]
Let $A$ be the sequence of zeroes and ones (binary sequence). The sequence can be modified by the following operation: we may pick a block or a contiguous subsequence where there are an unequal number of zeroes and ones, and then flip their order within the block (so block $a_1, a_2, \ldots, a_r$ becomes $a_r, a_{r-1}, \ldots, a_1$).
As an example, let $A$ be the sequence $1,1,0,0,1$. We can pick block $1,0,0$ and flip it, so the sequence $1,\boxed{1,0,0},1$ becomes $1,\boxed{0,0,1},1$. However, we cannot pick block $1,1,0,0$ and flip their order since they contain the same number of $1$s and $0$s.
Two sequences $A$ and $B$ are called [i]related[/i] if $A$ can be transformed into $B$ using a finite number the operation mentioned above.
Determine the largest natural number $n$ for which there exists $n$ different sequences $A_1, A_2, \ldots, A_n$ where each sequence consists of 2022 digits, and for every index $i \neq j$, the sequence $A_i$ is not related to $A_j$.
Let $X$ be a non empty subset of $\mathbb{N} = \{1,2,\ldots \}$. Suppose that for all $x \in X$, $4x \in X$ and $\lfloor \sqrt{x} \rfloor \in X$. Prove that $X=\mathbb{N}$.
Let $ T$ denote the set of all ordered triples $ (p,q,r)$ of nonnegative integers. Find all functions $ f: T \rightarrow \mathbb{R}$ satisfying
\[ f(p,q,r) = \begin{cases} 0 & \text{if} \; pqr = 0, \\
1 + \frac{1}{6}(f(p + 1,q - 1,r) + f(p - 1,q + 1,r) & \\
+ f(p - 1,q,r + 1) + f(p + 1,q,r - 1) & \\
+ f(p,q + 1,r - 1) + f(p,q - 1,r + 1)) & \text{otherwise} \end{cases}
\]
for all nonnegative integers $ p$, $ q$, $ r$.
There are $ n$ websites $ 1,2,\ldots,n$ ($ n \geq 2$). If there is a link from website $ i$ to $ j$, we can use this link so we can move website $ i$ to $ j$.
For all $ i \in \left\{1,2,\ldots,n - 1 \right\}$, there is a link from website $ i$ to $ i+1$.
Prove that we can add less or equal than $ 3(n - 1)\log_{2}(\log_{2} n)$ links so that for all integers $ 1 \leq i < j \leq n$, starting with website $ i$, and using at most three links to website $ j$. (If we use a link, website's number should increase. For example, No.7 to 4 is impossible).
Sorry for my bad English.
Find all functions $f: \mathbb{N}\to \mathbb{N}$ such that for all $n\in \mathbb{N}$: \[f(f(f(n)))+f(f(n))+f(n)=3n.\]
The sequence $ \{x_{n}\}_{n \ge 1}$ is defined by
\[ x_{1} \equal{} 2, x_{n \plus{} 1} \equal{} \frac {2 \plus{} x_{n}}{1 \minus{} 2x_{n}}\;\; (n \in \mathbb{N}).
\] Prove that
a) $ x_{n}\not \equal{} 0$ for all $ n \in \mathbb{N}$,
b) $ \{x_{n}\}_{n \ge 1}$ is not periodic.
A sequence $(a_n)$ of real numbers is defined by $a_0=1$, $a_1=2015$ and for all $n\geq1$, we have
$$a_{n+1}=\frac{n-1}{n+1}a_n-\frac{n-2}{n^2+n}a_{n-1}.$$
Calculate the value of $\frac{a_1}{a_2}-\frac{a_2}{a_3}+\frac{a_3}{a_4}-\frac{a_4}{a_5}+\ldots+\frac{a_{2013}}{a_{2014}}-\frac{a_{2014}}{a_{2015}}$.
Geoff has an infinite stock of sweets, which come in $n$ flavours. He arbitrarily distributes some of the sweets amongst $n$ children (a child can get sweets of any subset of all flavours, including the empty set). Call a distribution $k-\textit{nice}$ if every group of $k$ children together has sweets in at least $k$ flavours. Find all subsets $S$ of $\{ 1, 2, \dots, n \}$ such that if a distribution of sweets is $s$-nice for all $s \in S$, then it is $s$-nice for all $s \in \{ 1, 2, \dots, n \}$.
[i]Proposed by Kyle Hess, USA[/i]
In a regular 100-gon, 41 vertices are colored black and the remaining 59 vertices are colored white. Prove that there exist 24 convex quadrilaterals $Q_{1}, \ldots, Q_{24}$ whose corners are vertices of the 100-gon, so that
[list]
[*] the quadrilaterals $Q_{1}, \ldots, Q_{24}$ are pairwise disjoint, and
[*] every quadrilateral $Q_{i}$ has three corners of one color and one corner of the other color.
[/list]
Find, with proof, all real numbers $x$ satisfying $x = 2\left( 2 \left( 2\left( 2\left( 2x-1 \right)-1 \right)-1 \right)-1 \right)-1$.
[i]Proposed by Evan Chen[/i]
For a prime $p$, a subset $S$ of residues modulo $p$ is called a [i]sum-free multiplicative subgroup[/i] of $\mathbb F_p$ if
$\bullet$ there is a nonzero residue $\alpha$ modulo $p$ such that $S = \left\{ 1, \alpha^1, \alpha^2, \dots \right\}$ (all considered mod $p$), and
$\bullet$ there are no $a,b,c \in S$ (not necessarily distinct) such that $a+b \equiv c \pmod p$.
Prove that for every integer $N$, there is a prime $p$ and a sum-free multiplicative subgroup $S$ of $\mathbb F_p$ such that $\left\lvert S \right\rvert \ge N$.
[i]Proposed by Noga Alon and Jean Bourgain[/i]