Found problems: 5802
Let the irrational number
\[\alpha =1-\cfrac{1}{2a_1-\cfrac{1}{2a_2-\cfrac{1}{2a_3-\cdots}}}\]
where coefficients $a_1, a_2, \ldots$ are positive integers, infinitely many of which are greater than $1$. Prove that for every positive integer $N$ at least half of the numbers $\lfloor \alpha\rfloor, \lfloor 2\alpha\rfloor, \ldots, \lfloor N\alpha\rfloor$ are even.
[i]Proposed by Géza Kós, Budapest[/i]
Evaluate $ \int_0^1 (1 \plus{} x \plus{} x^2 \plus{} \cdots \plus{} x^{n \minus{} 1})\{1 \plus{} 3x \plus{} 5x^2 \plus{} \cdots \plus{} (2n \minus{} 3)x^{n \minus{} 2} \plus{} (2n \minus{} 1)x^{n \minus{} 1}\}\ dx.$
A partition of a set \( A \) is a family of non-empty subsets of \( A \), such that any two distinct subsets in the family are disjoint, and the union of all subsets equals \( A \). We say that a partition of a set of integers \( B \) is [i]separated[/i] if each subset in the partition does [b]not[/b] contain consecutive integers. Prove that, for every positive integer \( n \), the number of partitions of the set \( \{1, 2, \dots, n\} \) is equal to the number of separated partitions of the set \( \{1, 2, \dots, n+1\} \).
For example, \( \{\{1,3\}, \{2\}\} \) is a separated partition of the set \( \{1,2,3\} \). On the other hand, \( \{\{1,2\}, \{3\}\} \) is a partition of the same set, but it is not separated since \( \{1,2\} \) contains consecutive integers.
Let $n$ be a positive integer. Find the number of permutations $a_1$, $a_2$, $\dots a_n$ of the
sequence $1$, $2$, $\dots$ , $n$ satisfying
$$a_1 \le 2a_2\le 3a_3 \le \dots \le na_n$$.
Proposed by United Kingdom
Let $I \subset \mathbb{R}$ be a nonempty open interval and let $f: I \cap \mathbb{Q} \to \mathbb{R}$ be a function such that for all $x, y \in I \cap \mathbb{Q}$,
\[ 4f\left(\frac{3x + y}{4}\right)+ 4f\left(\frac{x + 3y}{4}\right) \le f(x) + 6f\left(\frac{x + y}{2}\right)+ f(y). \] Show that $f$ can be continuously extended to $I$.
Find all positive integers $n$ such that $4^n+6^n+9^n$ is a square.
[i]David Yang, Alex Zhu.[/i]
Two positive integers $p,q \in \mathbf{Z}^{+}$ are given. There is a blackboard with $n$ positive integers written on it. A operation is to choose two same number $a,a$ written on the blackboard, and replace them with $a+p,a+q$. Determine the smallest $n$ so that such operation can go on infinitely.
Let $ G$ be a simple graph with $ 2 \cdot n$ vertices and $ n^{2}+1$ edges. Show that this graph $ G$ contains a $ K_{4}-\text{one edge}$, that is, two triangles with a common edge.
If $a_1, a_2, \ldots$ is a sequence of real numbers such that for all $n$,
$$\sum_{k = 1}^n a_k \left( \frac{k}{n} \right)^2 = 1,$$
find the smallest $n$ such that $a_n < \frac{1}{2018}$.
Let $a$ and $b$ be distinct integers greater than $1$. Prove that there exists a positive integer $n$ such that $(a^n-1)(b^n-1)$ is not a perfect square.
[i]Proposed by Mongolia[/i]
$ 2^n $ coins are given to a couple of kids. Interchange of the coins occurs when some of the kids has at least half of all the coins. Then from the coins of one of those kids to the all other kids are given that much coins as the kid already had. In case when all the coins are at one kid there is no possibility for interchange. What is the greatest possible number of consecutive interchanges? ($ n $ is natural number)
Lisa and Bart are playing a game. A round table has $n$ lights evenly spaced around its circumference. Some of the lights are on and some of them off; the initial configuration is random. Lisa wins if she can get all of the lights turned on; Bart wins if he can prevent this from happening.
On each turn, Lisa chooses the positions at which to flip the lights, but before the lights are flipped, Bart, knowing Lisa’s choices, can rotate the table to any position that he chooses (or he can leave the table as is). Then the lights in the positions that Lisa chose are flipped: those that are off are turned on and those that are on are turned off.
Here is an example turn for $n = 5$ (a white circle indicates a light that is on, and a black
circle indicates a light that is off):
[asy]
size(250); defaultpen(linewidth(1)); picture p = new picture;
real r = 0.2; pair s1=(0,-4), s2=(0,-8); int[][] filled = {{1,2,3},{1,2,5},{2,3,4,5}};
draw(p,circle((0,0),1));
for(int i = 0; i < 5; ++i) {
pair P = dir(90-72*i); filldraw(p,circle(P,r),white); label(p,string(i+1),P,2*P,fontsize(10));
}
add(p); add(shift(s1)*p); add(shift(s2)*p);
for(int j = 0; j < 3; ++j)
for(int i = 0; i < filled[j].length; ++i)
filldraw(circle(dir(90-72*(filled[j][i]-1))+j*s1,r));
label("$\parbox{15em}{Initial Position.}$", (-4.5,0));
label("$\parbox{15em}{Lisa says ``1,3,4.'' \\ Bart rotates the table one \\ position counterclockwise. }$", (-4.5,0)+s1);
label("$\parbox{15em}{Lights in positions 1,3,4 are \\ flipped.}$", (-4.5,0)+s2);[/asy]
Lisa can take as many turns as she needs to win, or she can give up if it becomes clear
to her that Bart can prevent her from winning.
(a) Show that if $n = 7$ and initially at least one light is on and at least one light is off,
then Bart can always prevent Lisa from winning.
(b) Show that if $n = 8$, then Lisa can always win in at most 8 turns.
Let $(a_n)_{n \geq 0}$ be the sequence of integers defined recursively by $a_0 = 0, a_1 = 1, a_{n+2} = 4a_{n+1} + a_n$ for $n \geq 0.$ Find the common divisors of $a_{1986}$ and $a_{6891}.$
Given $n$ integers $a_1 = 1, a_2,..., a_n$ such that $a_i \le a_{i+1} \le 2a_i$ ($i = 1, 2, 3,..., n - 1$) and whose sum is even. Find whether it is possible to divide them into two groups so that the sum of numbers in one group is equal to the sum of numbers in the other group.
Let $f$ be the function of the set of positive integers into itself, defi ned by $f(1) = 1$,
$f(2n) = f(n)$ and $f(2n + 1) = f(n) + f(n + 1)$. Show that, for any positive integer $n$, the
number of positive odd integers m such that $f(m) = n$ is equal to the number of positive
integers[color=#0000FF][b] less or equal to [/b][/color]$n$ and coprime to $n$.
[color=#FF0000][mod: the initial statement said less than $n$, which is wrong.][/color]
Find all natural numbers $n$ for which there is a permutation $\sigma$ of $\{1,2,\ldots, n\}$ that satisfies:
\[
\sum_{i=1}^n \sigma(i)(-2)^{i-1}=0
\]
For an integer $m\geq 1$, we consider partitions of a $2^m\times 2^m$ chessboard into rectangles consisting of cells of chessboard, in which each of the $2^m$ cells along one diagonal forms a separate rectangle of side length $1$. Determine the smallest possible sum of rectangle perimeters in such a partition.
[i]Proposed by Gerhard Woeginger, Netherlands[/i]
Determine all positive integers $n$, $n\ge2$, such that the following statement is true:
If $(a_1,a_2,...,a_n)$ is a sequence of positive integers with $a_1+a_2+\cdots+a_n=2n-1$, then there is block of (at least two) consecutive terms in the sequence with their (arithmetic) mean being an integer.
Let $n$ be a positive integer and let $x_1\le x_2\le\cdots\le x_n$ be real numbers.
Prove that
\[
\left(\sum_{i,j=1}^{n}|x_i-x_j|\right)^2\le\frac{2(n^2-1)}{3}\sum_{i,j=1}^{n}(x_i-x_j)^2.
\]
Show that the equality holds if and only if $x_1, \ldots, x_n$ is an arithmetic sequence.
For integers $n>1$, define $f(n)$ to be the sum of all postive divisors of $n$ that are less than $n$. Prove that for any positive integer $k$, there exists a positive integer $n>1$ such that $n<f(n)<f^2(n)<\cdots<f^k(n)$, where $f^i(n)=f(f^{i-1}(n))$ for $i>1$ and $f^1(n)=f(n)$.
Let $d(n)$ be the number of positive divisors of a positive integer $n$. Let $\mathbb{N}$ be the set of all positive integers. Say that a function $F$ from $\mathbb{N}$ to $\mathbb{N}$ is [i]divisor-respecting[/i] if $d(F(mn)) = d(F(m)) d(F(n))$ for all positive integers $m$ and $n$, and $d(F(n)) \le d(n)$ for all positive integers $n$. Find all divisor-respecting functions. Justify your answer.
Find all ordered pairs of positive integers $(m,n)$ for which there exists a set $C=\{c_1,\ldots,c_k\}$ ($k\ge1$) of colors and an assignment of colors to each of the $mn$ unit squares of a $m\times n$ grid such that for every color $c_i\in C$ and unit square $S$ of color $c_i$, exactly two direct (non-diagonal) neighbors of $S$ have color $c_i$.
[i]David Yang.[/i]
Let $\mathbb{Z}$ and $\mathbb{Q}$ be the sets of integers and rationals respectively.
a) Does there exist a partition of $\mathbb{Z}$ into three non-empty subsets $A,B,C$ such that the sets $A+B, B+C, C+A$ are disjoint?
b) Does there exist a partition of $\mathbb{Q}$ into three non-empty subsets $A,B,C$ such that the sets $A+B, B+C, C+A$ are disjoint?
Here $X+Y$ denotes the set $\{ x+y : x \in X, y \in Y \}$, for $X,Y \subseteq \mathbb{Z}$ and for $X,Y \subseteq \mathbb{Q}$.
Gleb picked positive integers $N$ and $a$ ($a < N$). He wrote the number $a$ on a blackboard. Then each turn he did the following: he took the last number on the blackboard, divided the number $N$ by this last number with remainder and wrote the remainder onto the board. When he wrote the number $0$ onto the board, he stopped. Could he pick $N$ and $a$ such that the sum of the numbers on the blackboard would become greater than $100N$ ?
Ivan Mitrofanov
Two people, $A$ and $B$, play the following game with a deck of 32 cards. With $A$ starting, and thereafter the players alternating, each player takes either 1 card or a prime number of cards. Eventually all of the cards are chosen, and the person who has none to pick up is the loser. Who will win the game if they both follow optimal strategy?