Found problems: 429
Suppose $a$ and $b$ are two positive real numbers such that the roots of the cubic equation $x^3 - ax + b = 0$ are all real. If $\alpha$ is a root of this cubic with minimal absolute value, prove that \[ \dfrac{b}{a} < \alpha < \dfrac{3b}{2a}. \]
An $ (n, k) \minus{}$ tournament is a contest with $ n$ players held in $ k$ rounds such that:
$ (i)$ Each player plays in each round, and every two players meet at most once.
$ (ii)$ If player $ A$ meets player $ B$ in round $ i$, player $ C$ meets player $ D$ in round $ i$, and player $ A$ meets player $ C$ in round $ j$, then player $ B$ meets player $ D$ in round $ j$.
Determine all pairs $ (n, k)$ for which there exists an $ (n, k) \minus{}$ tournament.
[i]Proposed by Carlos di Fiore, Argentina[/i]
Is it possible to place the numbers $0,1,2,\dots,9$ on a circle so that the sum of any three consecutive numbers is a) 13, b) 14, c) 15?
The Fibonacci numbers $F_0, F_1, F_2, . . .$ are defined inductively by $F_0=0, F_1=1$, and $F_{n+1}=F_n+F_{n-1}$ for $n \ge 1$. Given an integer $n \ge 2$, determine the smallest size of a set $S$ of integers such that for every $k=2, 3, . . . , n$ there exist some $x, y \in S$ such that $x-y=F_k$.
[i]Proposed by Croatia[/i]
In a simple graph $G$, we call $t$ pairwise adjacent vertices a $t$[i]-clique[/i]. If a vertex is connected with all other vertices in the graph, we call it a [i]central[/i] vertex. Given are two integers $n,k$ such that $\dfrac {3}{2} \leq \dfrac{1}{2} n < k < n$. Let $G$ be a graph on $n$ vertices such that
[b](1)[/b] $G$ does not contain a $(k+1)$-[i]clique[/i];
[b](2)[/b] if we add an arbitrary edge to $G$, that creates a $(k+1)$-[i]clique[/i].
Find the least possible number of [i]central[/i] vertices in $G$.
In a sports league, each team uses a set of at most $t$ signature colors. A set $S$ of teams is[i] color-identifiable[/i] if one can assign each team in $S$ one of their signature colors, such that no team in $S$ is assigned any signature color of a different team in $S$.
For all positive integers $n$ and $t$, determine the maximum integer $g(n, t)$ such that: In any sports league with exactly $n$ distinct colors present over all teams, one can always find a color-identifiable set of size at least $g(n, t)$.
The $\underline{\text{path number}}$ of a graph is the minimum number of paths we need to partition the vertices of a graph. Given a connected graph with the independence number $k > 1$, what is the maximum possible value for the path number in this graph? Find the answer in terms of $k$.
The independence number of a graph $\textbf{G}$ is the maximum possible number $k$, such that there exist $k$ pairwise non-adjacent vertices in $\textbf{G}$.
The Fibonacci numbers $F_0, F_1, F_2, . . .$ are defined inductively by $F_0=0, F_1=1$, and $F_{n+1}=F_n+F_{n-1}$ for $n \ge 1$. Given an integer $n \ge 2$, determine the smallest size of a set $S$ of integers such that for every $k=2, 3, . . . , n$ there exist some $x, y \in S$ such that $x-y=F_k$.
[i]Proposed by Croatia[/i]
Consider a checkered $3m\times 3m$ square, where $m$ is an integer greater than $1.$ A frog sits on the lower left corner cell $S$ and wants to get to the upper right corner cell $F.$ The frog can hop from any cell to either the next cell to the right or the next cell upwards.
Some cells can be [i]sticky[/i], and the frog gets trapped once it hops on such a cell. A set $X$ of cells is called [i]blocking[/i] if the frog cannot reach $F$ from $S$ when all the cells of $X$ are sticky. A blocking set is [i] minimal[/i] if it does not contain a smaller blocking set.[list=a][*]Prove that there exists a minimal blocking set containing at least $3m^2-3m$ cells.
[*]Prove that every minimal blocking set containing at most $3m^2$ cells.
In an $m\times n$ rectangular grid, where m and n are odd integers, $1\times 2$ dominoes are initially placed so as to exactly cover all but one of the $1\times 1$ squares at one corner of the grid.
It is permitted to slide a domino towards the empty square, thus exposing another square.
Show that by a sequence of such moves, we can move the empty square to any corner of the rectangle.
[i]A. Shapovalov[/i]
Let $S$ be an infinite set of positive integers, such that there exist four pairwise distinct $a,b,c,d \in S$ with $\gcd(a,b) \neq \gcd(c,d)$. Prove that there exist three pairwise distinct $x,y,z \in S$ such that $\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)$.
Unit cubes are made into beads by drilling a hole through them along a diagonal. The beads are put on a string in such a way that they can move freely in space under the restriction that the vertices of two neighboring cubes are touching. Let $ A$ be the beginning vertex and $ B$ be the end vertex. Let there be $ p \times q \times r$ cubes on the string $ (p, q, r \geq 1).$
[i](a)[/i] Determine for which values of $ p, q,$ and $ r$ it is possible to build a block with dimensions $ p, q,$ and $ r.$ Give reasons for your answers.
[i](b)[/i] The same question as (a) with the extra condition that $ A \equal{} B.$
One wants to distribute $n$ same sized cakes between $k$ people equally by cutting every cake at most once. If the number of positive divisors of $n$ is denoted as $d(n)$, show that the number of different values of $k$ which makes such distribution possible is $n+d(n)$
Let $n$ be a positive integer and let $S$ be a set of $2^n+1$ elements. Let $f$ be a function from the set of two-element subsets of $S$ to $\{0, \dots, 2^{n-1}-1\}$. Assume that for any elements $x, y, z$ of $S$, one of $f(\{x,y\}), f(\{y,z\}), f(\{z, x\})$ is equal to the sum of the other two. Show that there exist $a, b, c$ in $S$ such that $f(\{a,b\}), f(\{b,c\}), f(\{c,a\})$ are all equal to 0.
Prove that for arbitary integer $ n > 16$, there exists the set $ S$ that contains $ n$ positive integers and has the following property:if the subset $ A$ of $ S$ satisfies for arbitary $ a,a'\in A, a\neq a', a \plus{} a'\notin S$ holds, then $ |A|\leq4\sqrt n.$
Let $\mathbb{Z}_{>0}$ denote the set of positive integers. Consider a function $f: \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}$. For any $m, n \in \mathbb{Z}_{>0}$ we write $f^n(m) = \underbrace{f(f(\ldots f}_{n}(m)\ldots))$. Suppose that $f$ has the following two properties:
(i) if $m, n \in \mathbb{Z}_{>0}$, then $\frac{f^n(m) - m}{n} \in \mathbb{Z}_{>0}$;
(ii) The set $\mathbb{Z}_{>0} \setminus \{f(n) \mid n\in \mathbb{Z}_{>0}\}$ is finite.
Prove that the sequence $f(1) - 1, f(2) - 2, f(3) - 3, \ldots$ is periodic.
[i]Proposed by Ang Jie Jun, Singapore[/i]
Prove that if a graph $\mathcal{G}$ on $n\ge 3$ vertices has a unique $3$-coloring, then $\mathcal{G}$ has at least $2n-3$ edges.
(A graph is $3$-colorable when there exists a coloring of its vertices with $3$ colors such that no two vertices of the same color are connected by an edge. The graph can be $3$-colored uniquely if there do not exist vertices $u$ and $v$ of the graph that are painted different colors in one $3$-coloring, yet are colored the same in another.)
$\pi(n)$ is the number of primes that are not bigger than $n$. For $n=2,3,4,6,8,33,\dots$ we have $\pi(n)|n$. Does exist infinitely many integers $n$ that $\pi(n)|n$?
Let $N$ be a positive integer, and consider an $N \times N$ grid. A [i]right-down path[/i] is a sequence of grid cells such that each cell is either one cell to the right of or one cell below the previous cell in the sequence. A [i]right-up path[/i] is a sequence of grid cells such that each cell is either one cell to the right of or one cell above the previous cell in the sequence.
Prove that the cells of the $N \times N$ grid cannot be partitioned into less than $N$ right-down or right-up paths. For example, the following partition of the $5 \times 5$ grid uses $5$ paths.
[asy]
size(4cm);
draw((5,-1)--(0,-1)--(0,-2)--(5,-2)--(5,-3)--(0,-3)--(0,-4)--(5,-4),gray+linewidth(0.5)+miterjoin);
draw((1,-5)--(1,0)--(2,0)--(2,-5)--(3,-5)--(3,0)--(4,0)--(4,-5),gray+linewidth(0.5)+miterjoin);
draw((0,0)--(5,0)--(5,-5)--(0,-5)--cycle,black+linewidth(2.5)+miterjoin);
draw((0,-1)--(3,-1)--(3,-2)--(1,-2)--(1,-4)--(4,-4)--(4,-3)--(2,-3)--(2,-2),black+linewidth(2.5)+miterjoin);
draw((3,0)--(3,-1),black+linewidth(2.5)+miterjoin);
draw((1,-4)--(1,-5),black+linewidth(2.5)+miterjoin);
draw((4,-3)--(4,-1)--(5,-1),black+linewidth(2.5)+miterjoin);
[/asy]
[i]Proposed by Zixiang Zhou, Canada[/i]
$\definecolor{A}{RGB}{255,0,0}\color{A}\fbox{A6.}$ Let $ P (x)$ be a polynomial with real coefficients such that $\deg P \ge 3$ is an odd integer. Let $f : \mathbb{R}\rightarrow\mathbb{Z}$ be a function such that
$$\definecolor{A}{RGB}{0,0,200}\color{A}\forall_{x\in\mathbb{R}}\ f(P(x)) = P(f(x)).$$
$\definecolor{A}{RGB}{255,150,0}\color{A}\fbox{(a)}$ Prove that the range of $f$ is finite.
$\definecolor{A}{RGB}{255,150,0}\color{A}\fbox{(b)}$ Show that for any positive integer $n$, there exist $P$, $f$ that satisfies the above condition and also that the range of $f$ has cardinality $n$.
[i]Proposed by [/i][b][color=#419DAB]ltf0501[/color][/b].
[color=#3D9186]#1735[/color]
Given $5$ points in a plane, no three of them being collinear. Each two of these $5$ points are joined with a segment, and every of these segments is painted either red or blue; assume that there is no triangle whose sides are segments of equal color.
[b]a.)[/b] Show that:
[i](1)[/i] Among the four segments originating at any of the $5$ points, two are red and two are blue.
[i](2)[/i] The red segments form a closed way passing through all $5$ given points. (Similarly for the blue segments.)
[b]b.)[/b] Give a plan how to paint the segments either red or blue in order to have the condition (no triangle with equally colored sides) satisfied.
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}$.
Let $ n \geq 3$ and consider a set $ E$ of $ 2n \minus{} 1$ distinct points on a circle. Suppose that exactly $ k$ of these points are to be colored black. Such a coloring is [b]good[/b] if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly $ n$ points from $ E$. Find the smallest value of $ k$ so that every such coloring of $ k$ points of $ E$ is good.
A tournament is a directed graph for which every (unordered) pair of vertices has a single directed edge from one vertex to the other. Let us define a proper directed-edge-coloring to be an assignment of a color to every (directed) edge, so that for every pair of directed edges $\overrightarrow{uv}$ and $\overrightarrow{vw}$, those two edges are in different colors. Note that it is permissible for $\overrightarrow{uv}$ and $\overrightarrow{uw}$ to be the same color. The directed-edge-chromatic-number of a tournament is defined to be the minimum total number of colors that can be used in order to create a proper directed-edge-coloring. For each $n$, determine the minimum directed-edge-chromatic-number over all tournaments on $n$ vertices.
[i]Proposed by Po-Shen Loh[/i]
There are $n$ triangles inscribed in a circle and all $3n$ of their vertices are different. Prove that it is possible to put a boy in one of the vertices in each triangle, and a girl in the other, so that boys and girls alternate on a circle.