Found problems: 5802
Let $M,a,b,r$ be non-negative integers with $a,r\ge 2$, and suppose there exists a function $f:\mathbb{Z}\rightarrow\mathbb{Z}$ satisfying the following conditions:
(1) For all $n\in \mathbb{Z}$, $f^{(r)}(n)=an+b$ where $f^{(r)}$ denotes the composition of $r$ copies of $f$
(2) For all $n\ge M$, $f(n)\ge 0$
(3) For all $n>m>M$, $n-m|f(n)-f(m)$
Show that $a$ is a perfect $r$-th power.
Prove that $(2+\sqrt{3})^{2n}+(2-\sqrt{3})^{2n}$ is an even integer and that $(2+\sqrt{3})^{2n}-(2-\sqrt{3})^{2n}=w\sqrt{3}$ for some positive integer $w$, for all integers $n \geq 1$.
Let $n$ be a positive integer. We start with $n$ piles of pebbles, each initially containing a single pebble. One can perform moves of the following form: choose two piles, take an equal number of pebbles from each pile and form a new pile out of these pebbles. Find (in terms of $n$) the smallest number of nonempty piles that one can obtain by performing a finite sequence of moves of this form.
For a ring $ A, $ and an element $ a $ of it, define $ s_a,d_a:A\longrightarrow A, s_a(x)=ax,d_a=xa.$
[b]a)[/b] Prove that if $ A $ is finite, then $ s_a $ is injective if and only if $ d_a $ is injective.
[b]b)[/b] Give example of a ring which has an element $ b $ for which $ s_b $ is injective and $ d_b $ is not, or, conversely, $ s_b $ is not injective, but $ d_b $ is.
Determine all composite positive integers $n$ for which it is possible to arrange all divisors of $n$ that are greater than 1 in a circle so that no two adjacent divisors are relatively prime.
$n$ being a given integer, find all functions $f\colon \mathbb{Z} \to \mathbb{Z}$, such that for all integers $x,y$ we have $f\left( {x + y + f(y)} \right) = f(x) + ny$.
Prove that for any finite set $A$ of positive integers, there exists a subset $B$ of $A$ satisfying the following conditions:
[list][*]if $b_1,b_2\in B$ are distinct, then neither $b_1$ and $b_2$ nor $b_1+1$ and $b_2+1$ are multiples of each other, and
[*] for any $a\in A$, we can find a $b\in B$ such that $a$ divides $b$ or $b+1$ divides $a+1$.[/list]
You are cheating at a trivia contest. For each question, you can peek at each of the $n > 1$ other contestants' guesses before writing down your own. For each question, after all guesses are submitted, the emcee announces the correct answer. A correct guess is worth $0$ points. An incorrect guess is worth $-2$ points for other contestants, but only $-1$ point for you, since you hacked the scoring system. After announcing the correct answer, the emcee proceeds to read the next question. Show that if you are leading by $2^{n - 1}$ points at any time, then you can surely win first place.
[i]Linus Hamilton[/i]
Find all functions $f : Z \to Z$ satisfying $f(m + n) + f(mn -1) = f(m)f(n) + 2$ for all $m, n \in Z$.
Prove that there is no function $f$ from the set of non-negative integers into itself such that $f(f(n))=n+1987$ for all $n$.
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]
Let $G=G(V,E)$ be a simple graph with vertex set $V$ and edge set $E$. Suppose $|V|=n$. A map $f:\,V\rightarrow\mathbb{Z}$ is called good, if $f$ satisfies the followings:
(1) $\sum_{v\in V} f(v)=|E|$;
(2) color arbitarily some vertices into red, one can always find a red vertex $v$ such that $f(v)$ is no more than the number of uncolored vertices adjacent to $v$.
Let $m(G)$ be the number of good maps. Prove that if every vertex in $G$ is adjacent to at least one another vertex, then $n\leq m(G)\leq n!$.
In a company of people some pairs are enemies. A group of people is called [i]unsociable[/i] if the number of members in the group is odd and at least $3$, and it is possible to arrange all its members around a round table so that every two neighbors are enemies. Given that there are at most $2015$ unsociable groups, prove that it is possible to partition the company into $11$ parts so that no two enemies are in the same part.
[i]Proposed by Russia[/i]
For any two different real numbers $x$ and $y$, we define $D(x,y)$ to be the unique integer $d$ satisfying $2^d\le |x-y| < 2^{d+1}$. Given a set of reals $\mathcal F$, and an element $x\in \mathcal F$, we say that the [i]scales[/i] of $x$ in $\mathcal F$ are the values of $D(x,y)$ for $y\in\mathcal F$ with $x\neq y$. Let $k$ be a given positive integer.
Suppose that each member $x$ of $\mathcal F$ has at most $k$ different scales in $\mathcal F$ (note that these scales may depend on $x$). What is the maximum possible size of $\mathcal F$?
Let $n\geqslant 1$ be an integer, and let $x_0,x_1,\ldots,x_{n+1}$ be $n+2$ non-negative real numbers that satisfy $x_ix_{i+1}-x_{i-1}^2\geqslant 1$ for all $i=1,2,\ldots,n.$ Show that \[x_0+x_1+\cdots+x_n+x_{n+1}>\bigg(\frac{2n}{3}\bigg)^{3/2}.\][i]Pakawut Jiradilok and Wijit Yangjit, Thailand[/i]
Let $ S$ be a finite set of points in the plane such that no three of them are on a line. For each convex polygon $ P$ whose vertices are in $ S$, let $ a(P)$ be the number of vertices of $ P$, and let $ b(P)$ be the number of points of $ S$ which are outside $ P$. A line segment, a point, and the empty set are considered as convex polygons of $ 2$, $ 1$, and $ 0$ vertices respectively. Prove that for every real number $ x$ \[\sum_{P}{x^{a(P)}(1 \minus{} x)^{b(P)}} \equal{} 1,\] where the sum is taken over all convex polygons with vertices in $ S$.
[i]Alternative formulation[/i]:
Let $ M$ be a finite point set in the plane and no three points are collinear. A subset $ A$ of $ M$ will be called round if its elements is the set of vertices of a convex $ A \minus{}$gon $ V(A).$ For each round subset let $ r(A)$ be the number of points from $ M$ which are exterior from the convex $ A \minus{}$gon $ V(A).$ Subsets with $ 0,1$ and 2 elements are always round, its corresponding polygons are the empty set, a point or a segment, respectively (for which all other points that are not vertices of the polygon are exterior). For each round subset $ A$ of $ M$ construct the polynomial
\[ P_A(x) \equal{} x^{|A|}(1 \minus{} x)^{r(A)}.
\]
Show that the sum of polynomials for all round subsets is exactly the polynomial $ P(x) \equal{} 1.$
[i]Proposed by Federico Ardila, Colombia[/i]
Find all integers $n$, $n \ge 1$, such that $n \cdot 2^{n+1}+1$ is a perfect square.
A sequence of real numbers $ \{a_{n}\}$ is defineds by $ a_{0}\neq 0,1$, $ a_1\equal{}1\minus{}a_0$,$ a_{n\plus{}1}\equal{}1\minus{}a_n(1\minus{}a_n)$, $ n\equal{}1,2,...$.
Prove that for any positive integer $ n$, we have
$ a_{0}a_{1}...a_{n}(\frac{1}{a_0}\plus{}\frac{1}{a_1}\plus{}...\plus{}\frac{1}{a_n})\equal{}1$
For $n$ an odd positive integer, the unit squares of an $n\times n$ chessboard are coloured alternately black and white, with the four corners coloured black. A it tromino is an $L$-shape formed by three connected unit squares. For which values of $n$ is it possible to cover all the black squares with non-overlapping trominos? When it is possible, what is the minimum number of trominos needed?
The numbers from $1$ through $100$ are written in some order on a circle.
We call a pair of numbers on the circle [i]good [/i] if the two numbers are not neighbors on the circle and if at least one of the two arcs they determine on the circle only contains numbers smaller then both of them. What may be the total number of good pairs on the circle.
A positive integer $n$ is [i]Mozart[/i] if the decimal representation of the sequence $1, 2, \ldots, n$ contains each digit an even number of times.
Prove that:
1. All Mozart numbers are even.
2. There are infinitely many Mozart numbers.
Let $S$ be an infinite set of positive integers and define:
$T=\{ x+y|x,y \in S , x \neq y \} $
Suppose that there are only finite primes $p$ so that:
1.$p \equiv 1 \pmod 4$
2.There exists a positive integer $s$ so that $p|s,s \in T$.
Prove that there are infinity many primes that divide at least one term of $S$.
Determine all pairs $ (x,y)$ of positive integers satisfying the equation
\[ x!\plus{}y!\equal{}x^{y}.\]
A polynomial $P(x, y, z)$ in three variables with real coefficients satisfies the identities
$$P(x, y, z)=P(x, y, xy-z)=P(x, zx-y, z)=P(yz-x, y, z).$$
Prove that there exists a polynomial $F(t)$ in one variable such that
$$P(x,y,z)=F(x^2+y^2+z^2-xyz).$$
A [i]short-sighted[/i] rook is a rook that beats all squares in the same column and in the same row for which he can not go more than $60$-steps.
What is the maximal amount of short-sighted rooks that don't beat each other that can be put on a $100\times 100$ chessboard.