Found problems: 5802
Beto plays the following game with his computer: initially the computer randomly picks $30$ integers from $1$ to $2015$, and Beto writes them on a chalkboard (there may be repeated numbers). On each turn, Beto chooses a positive integer $k$ and some if the numbers written on the chalkboard, and subtracts $k$ from each of the chosen numbers, with the condition that the resulting numbers remain non-negative. The objective of the game is to reduce all $30$ numbers to $0$, in which case the game ends. Find the minimal number $n$ such that, regardless of which numbers the computer chooses, Beto can end the game in at most $n$ turns.
Find all functions $f$ defined on all real numbers and taking real values such that \[f(f(y)) + f(x - y) = f(xf(y) - x),\] for all real numbers $x, y.$
Let $ Z$ and $ R$ denote the sets of integers and real numbers, respectively.
Let $ f: Z \rightarrow R$ be a function satisfying:
(i) $ f(n) \ge 0$ for all $ n \in Z$
(ii) $ f(mn)\equal{}f(m)f(n)$ for all $ m,n \in Z$
(iii) $ f(m\plus{}n) \le max(f(m),f(n))$ for all $ m,n \in Z$
(a) Prove that $ f(n) \le 1$ for all $ n \in Z$
(b) Find a function $ f: Z \rightarrow R$ satisfying (i), (ii),(iii) and $ 0<f(2)<1$ and $ f(2007) \equal{} 1$
Does there exist a function $f:\mathbb N\to\mathbb N$ such that
$$
f(f(n+1))=f(f(n))+2^{n-1}
$$
for any positive integer $n$? (As usual, $\mathbb N$ stands for the set of positive integers.)
[i](I. Gorodnin)[/i]
On a planet there are $3\times2005!$ aliens and $2005$ languages. Each pair of aliens communicates with each other in exactly one language. Show that there are $3$ aliens who communicate with each other in one common language.
For what values of $ n$ does there exist an $ n \times n$ array of entries -1, 0 or 1 such that the $ 2 \cdot n$ sums obtained by summing the elements of the rows and the columns are all different?
Determine all functions $f\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ such that, for all positive integers $a$ and $b$,
\[
f^{bf(a)}(a+1)=(a+1)f(b).
\]
Prove that for all positive integers $n\geq 1$ the number $\prod^n_{k=1} k^{2k-n-1}$ is also an integer number.
[i]Laurentiu Panaitopol[/i].
Prove that the Fibonacci sequence $\{F_n\}^\infty_{n=1}$ defined by $F_1 = F_2 = 1$ and $F_{n+2} = F_{n+1}+F_n$ for all $n \geq 1$ is a divisibility sequence, that is, if $m\mid n$ then $F_m \mid F_n$ for all positive integers $m$ and $n$.
Let $ m, n $ natural numbers with $ m\ge 2,n\ge 3. $ Prove that there exist $ m $ distinct multiples of $ n-1, $ namely, $ a_1,a_2,a_3,...,a_m, $ such that:
$$ \frac{1}{n} =\sum_{i=1}^m \frac{(-1)^{i-1}}{a_i} . $$
Let $G$ be a simple connected graph with $2016$ vertices and $k$ edges. We want to choose a set of vertices where there is no edge between them and delete all these chosen vertices (we delete both the vertices and all edges of these vertices) such that the remaining graph becomes unconnected. If we can do this task no matter how these $k$ edges are arranged (by making the graph connected), find the maximal value of $k$.
Let $f$ and $g$ be two nonzero polynomials with integer coefficients and $\deg f>\deg g$. Suppose that for infinitely many primes $p$ the polynomial $pf+g$ has a rational root. Prove that $f$ has a rational root.
Let $\mathbb{N} = \{1,2,3, \ldots\}$. Determine if there exists a strictly increasing function $f: \mathbb{N} \mapsto \mathbb{N}$ with the following properties:
(i) $f(1) = 2$;
(ii) $f(f(n)) = f(n) + n, (n \in \mathbb{N})$.
Let $A$ be an $n$x$n$ matrix with integer entries and $b_{1},b_{2},...,b_{k}$ be integers satisfying $detA=b_{1}\cdot b_{2}\cdot ...\cdot b_{k}$. Prove that there exist $n$x$n$-matrices $B_{1},B_{2},...,B_{k}$ with integers entries such that $A=B_{1}\cdot B_{2}\cdot ...\cdot B_{k}$ and $detB_{i}=b_{i}$ for all $i=1,...,k$.
[b]p1.[/b] Let $f$ be a function such that $f(x + y) = f(x) + f(y)$ for all $x$ and $y$. Assume $f(5) = 9$. Compute $f(2015)$.
[b]p2.[/b] There are six cards, with the numbers $2, 2, 4, 4, 6, 6$ on them. If you pick three cards at random, what is the probability that you can make a triangles whose side lengths are the chosen numbers?
[b]p3. [/b]A train travels from Berkeley to San Francisco under a tunnel of length $10$ kilometers, and then returns to Berkeley using a bridge of length $7$ kilometers. If the train travels at $30$ km/hr underwater and 60 km/hr above water, what is the train’s average speed in km/hr on the round trip?
[b]p4.[/b] Given a string consisting of the characters A, C, G, U, its reverse complement is the string obtained by first reversing the string and then replacing A’s with U’s, C’s with G’s, G’s with C’s, and U’s with A’s. For example, the reverse complement of UAGCAC is GUGCUA. A string is a palindrome if it’s the same as its reverse. A string is called self-conjugate if it’s the same as its reverse complement. For example, UAGGAU is a palindrome and UAGCUA is self-conjugate. How many six letter strings with just the characters A, C, G (no U’s) are either palindromes or self-conjugate?
[b]p5.[/b] A scooter has $2$ wheels, a chair has $6$ wheels, and a spaceship has $11$ wheels. If there are $10$ of these objects, with a total of $50$ wheels, how many chairs are there?
[b]p6.[/b] How many proper subsets of $\{1, 2, 3, 4, 5, 6\}$ are there such that the sum of the elements in the subset equal twice a number in the subset?
[b]p7.[/b] A circle and square share the same center and area. The circle has radius $1$ and intersects the square on one side at points $A$ and $B$. What is the length of $\overline{AB}$ ?
[b]p8. [/b]Inside a circle, chords $AB$ and $CD$ intersect at $P$ in right angles. Given that $AP = 6$, $BP = 12$ and $CD = 15$, find the radius of the circle.
[b]p9.[/b] Steven makes nonstandard checkerboards that have $29$ squares on each side. The checkerboards have a black square in every corner and alternate red and black squares along every row and column. How many black squares are there on such a checkerboard?
[b]p10.[/b] John is organizing a race around a circular track and wants to put $3$ water stations at $9$ possible spots around the track. He doesn’t want any $2$ water stations to be next to each other because that would be inefficient. How many ways are possible?
[b]p11.[/b] In square $ABCD$, point $E$ is chosen such that $CDE$ is an equilateral triangle. Extend $CE$ and $DE$ to $F$ and $G$ on $AB$. Find the ratio of the area of $\vartriangle EFG$ to the area of $\vartriangle CDE$.
[b]p12.[/b] Let $S$ be the number of integers from $2$ to $8462$ (inclusive) which does not contain the digit $1,3,5,7,9$. What is $S$?
[b]p13.[/b] Let x, y be non zero solutions to $x^2 + xy + y^2 = 0$. Find $\frac{x^{2016} + (xy)^{1008} + y^{2016}}{(x + y)^{2016}}$ .
[b]p14.[/b] A chess contest is held among $10$ players in a single round (each of two players will have a match). The winner of each game earns $2$ points while loser earns none, and each of the two players will get $1$ point for a draw. After the contest, none of the $10$ players gets the same score, and the player of the second place gets a score that equals to $4/5$ of the sum of the last $5$ players. What is the score of the second-place player?
[b]p15.[/b] Consider the sequence of positive integers generated by the following formula
$a_1 = 3$, $a_{n+1} = a_n + a^2_n$ for $n = 2, 3, ...$
What is the tens digit of $a_{1007}$?
[b]p16.[/b] Let $(x, y, z)$ be integer solutions to the following system of equations
$x^2z + y^2z + 4xy = 48$
$x^2 + y^2 + xyz = 24$
Find $\sum x + y + z$ where the sum runs over all possible $(x, y, z)$.
[b]p17.[/b] Given that $x + y = a$ and $xy = b$ and $1 \le a, b \le 50$, what is the sum of all a such that $x^4 + y^4 - 2x^2y^2$ is a prime squared?
[b]p18.[/b] In $\vartriangle ABC$, $M$ is the midpoint of $\overline{AB}$, point $N$ is on side $\overline{BC}$. Line segments $\overline{AN}$ and $\overline{CM}$ intersect at $O$. If $AO = 12$, $CO = 6$, and $ON = 4$, what is the length of $OM$?
[b]p19.[/b] Consider the following linear system of equations.
$1 + a + b + c + d = 1$
$16 + 8a + 4b + 2c + d = 2$
$81 + 27a + 9b + 3c + d = 3$
$256 + 64a + 16b + 4c + d = 4$
Find $a - b + c - d$.
[b]p20.[/b] Consider flipping a fair coin $ 8$ times. How many sequences of coin flips are there such that the string HHH never occurs?
PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].
Find all real-coefficient polynomials $f(x)$ which satisfy the following conditions:
[b]i.[/b] $f(x) = a_0 x^{2n} + a_2 x^{2n - 2} + \cdots + a_{2n - 2}
x^2 + a_{2n}, a_0 > 0$;
[b]ii.[/b] $\sum_{j=0}^n a_{2j} a_{2n - 2j} \leq \left(
\begin{array}{c}
2n\\
n\end{array} \right) a_0 a_{2n}$;
[b]iii.[/b] All the roots of $f(x)$ are imaginary numbers with no real part.
There is a queue of $n{}$ girls on one side of a tennis table, and a queue of $n{}$ boys on the other side. Both the girls and the boys are numbered from $1{}$ to $n{}$ in the order they stand. The first game is played by the girl and the boy with the number $1{}$ and then, after each game, the loser goes to the end of their queue, and the winner remains at the table. After a while, it turned out that each girl played exactly one game with each boy. Prove that if $n{}$ is odd, then a girl and a boy with odd numbers played in the last game.
[i]Proposed by A. Gribalko[/i]
Prove that for all $a, b$ and $x_0$ positive integers, in the sequence $x_1, x_2, x_3, \cdots$ defined by
$$x_{n+1}=ax_n+b, n\geq 0$$
Exist an $x_i$ that is not prime for some $i\geq 1$
Let $\{a_n\}_{n \geq 1}$ be a sequence in which $a_1=1$ and $a_2=2$ and
\[a_{n+1}=1+a_1a_2a_3 \cdots a_{n-1}+(a_1a_2a_3 \cdots a_{n-1} )^2 \qquad \forall n \geq 2.\]
Prove that
\[\lim_{n \to \infty} \biggl( \frac{1}{a_1}+\frac{1}{a_2}+\frac{1}{a_3}+\cdots + \frac{1}{a_n} \biggr) =2\]
Show that there is no function $f:{{\mathbb{R}}^{+}}\to {{\mathbb{R}}^{+}}$ such that $f(x+y)>f(x)(1+yf(x))$
for all $x,y\in {{\mathbb{R}}^{+}}$.
Let $A$ be the $n\times n$ matrix whose entry in the $i$-th row and $j$-th column is \[\frac1{\min(i,j)}\] for $1\le i,j\le n.$ Compute $\det(A).$
Prove that every infinite sequence $S$ of distinct positive integers contains either an infinite subsequence such that for every pair of terms, neither term ever divides the other, or an infinite subsequence such that in every pair of terms, one always divides the other.
For a given positive integer $n,$ find
$$\sum_{k=0}^{n} \left(\frac{\binom{n}{k} \cdot (-1)^k}{(n+1-k)^2} - \frac{(-1)^n}{(k+1)(n+1)}\right).$$
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]
Let \( A \) be a \( 2 \times 2 \) matrix with integer entries and \(\det A \neq 0\). If the sequence \(\operatorname{tr}(A^n)\), for \( n = 1, 2, 3, \ldots \), is bounded, show that
\[
A^{12} = I \quad \text{or} \quad (A^2 - I)^2 = O.
\]
Here, \( I \) and \( O \) denote the identity and zero matrices, respectively, and \(\operatorname{tr}\) denotes the trace of the matrix (the sum of the elements on the main diagonal).