Find all positive integers $n \geq 3$ for which there exists a set $S$ which consists of rational numbers such that the following two conditions hold: 1) any rational number can be represented as the sum of at most $n$ elements of $S$ 2) there exists a rational number, which can not be represented as the sum of at most $n-1$ elements of $S$ (in the sum some elements can repeat) [i]M. Shutro, M. Zorka[/i]

Let $m_{1},m_{2},\ldots,m_{k}$ be integers with $2\leq m_{1}$ and $2m_{1}\leq m_{i+1}$ for all $i$. Show that for any integers $a_{1},a_{2},\ldots,a_{k}$ there are infinitely many integers $x$ which do not satisfy any of the congruences \[x\equiv a_{i}\ (\bmod \ m_{i}),\ i=1,2,\ldots k.\]

Find all pairs of positive integers $ x,y$ satisfying the equation \[ y^x \equal{} x^{50}\]

We call the $main$ $divisors$ of a composite number $n$ the two largest of its natural divisors other than $n$. Composite numbers $a$ and $b$ are such that the main divisors of $a$ and $b$ coincide. Prove that $a=b$.

Let $n{}$ be a positive integer. What is the smallest sum of digits that $5^n + 6^n + 2022^n$ can take?

Rothschild the benefactor has a certain number of coins. A man comes, and Rothschild wants to share his coins with him. If he has an even number of coins, he gives half of them to the man and goes away. If he has an odd number of coins, he donates one coin to charity so he can have an even number of coins, but meanwhile another man comes. So now he has to share his coins with two other people. If it is possible to do so evenly, he does so and goes away. Otherwise, he again donates a few coins to charity (no more than 3). Meanwhile, yet another man comes. This goes on until Rothschild is able to divide his coins evenly or until he runs out of money. Does there exist a natural number $N$ such that if Rothschild has at least $N$ coins in the beginning, he will end with at least one coin?

A pen costs $11$ € and a notebook costs $13$ €. Find the number of ways in which a person can spend exactly $1000$ € to buy pens and notebooks.

A subset $S$ of $\mathbb N$ is [i]eventually linear[/i] iff there are $k,N\in\mathbb N$ that for $n>N,n\in S\Longleftrightarrow k|n$. Let $S$ be a subset of $\mathbb N$ that is closed under addition. Prove that $S$ is eventually linear.

[b]p1.[/b] The case of Mr. Brown, Mr. Potter, and Mr. Smith is investigated. One of them has committed a crime. Everyone of them made two statements. Mr. Brown: I have not done it. Mr. Potter has not done it. Mr. Potter: Mr. Brown has not done it. Mr. Smith has done it. Mr. Smith: I have not done it. Mr. Brown has done it. It is known that one of them told the truth both times, one lied both times, and one told the truth one time and lied one time. Who has committed the crime? [b]p2.[/b] Is it possible to draw in a plane $1000001$ circles of the radius $1$ such that every circle touches exactly three other circles? [b]p3.[/b] Consider a circle of radius $R$ centered at the origin. A particle is “launched” from the $x$-axis at a distance, $d$, from the origin with $0 < d < R$, and at an angle, $\alpha$, with the $x$-axis. The particle is reflected from the boundary of the circle so that the [b]angle of incidence[/b] equals the [b]angle of reflection[/b]. Determine the angle $\alpha$ so that the path of the particle contacts the circle’s interior at exactly eight points. Please note that $\alpha$ should be determined in terms of the qunatities $R$ and $d$. [img]https://cdn.artofproblemsolving.com/attachments/e/3/b8ef9bb8d1b54c263bf2b68d3de60be5b41ad0.png[/img] [b]p4.[/b] Is it possible to find four different real numbers such that the cube of every number equals the square of the sum of the three others? [b]p5. [/b]The Fibonacci sequence $(1, 2, 3, 5, 8, 13, 21, . . .)$ is defined by the following formula: $f_n = f_{n-2} + f_{n-1}$, where $f_1 = 1$, $f_2 = 2$. Prove that any positive integer can be represented as a sum of different members of the Fibonacci sequence. [b]p6.[/b] $10,000$ points are arbitrary chosen inside a square of area $1$ m$^2$ . Does there exist a broken line connecting all these points, the length of which is less than $201$ m$^2? PS. You should use hide for answers.

Let $(a_n)_{n\ge 1}$ be a sequence given by $a_1 = 45$ and $$a_n = a^2_{n-1} + 15a_{n-1}$$ for $n > 1$. Prove that the sequence contains no perfect squares.

Let $a, b$ be positive integers such that $a^2 + ab + 1$ a multiple of $b^2 + ab + 1$. Prove that $a = b$.

Cynthia loves Pokemon and she wants to catch them all. In Victory Road, there are a total of $80$ Pokemon. Cynthia wants to catch as many of them as possible. However, she cannot catch any two Pokemon that are enemies with each other. After exploring around for a while, she makes the following two observations: 1. Every Pokemon in Victory Road is enemies with exactly two other Pokemon. 2. Due to her inability to catch Pokemon that are enemies with one another, the maximum number of the Pokemon she can catch is equal to $n$. What is the sum of all possible values of $n$?

Let $n$ be a positive integer. Prove that at least one of the integers $[2^n \cdot \sqrt2]$, $[2^{n+1} \cdot \sqrt2]$, $...$, $[2^{2n} \cdot \sqrt2]$ is even, where $[a]$ denotes the integer part of $a$.

It is given that for some $n \in \mathbb{N}$ there exists a natural number $a$, such that $a^{n-1} \equiv 1 \pmod{n}$ and that for any prime divisor $p$ of $n-1$ we have $a^{\frac{n-1}{p}} \not \equiv 1 \pmod{n}$. Prove that $n$ is a prime.

Prove that if $m$ and $s$ are integers with $ms=2000^{2001}$, then the equation $mx^2-sy^2=3$ has no integer solutions.

Let $p$ be a prime number and let $X$ be a finite set containing at least $p$ elements. A collection of pairwise mutually disjoint $p$-element subsets of $X$ is called a $p$-family. (In particular, the empty collection is a $p$-family.) Let $A$(respectively, $B$) denote the number of $p$-families having an even (respectively, odd) number of $p$-element subsets of $X$. Prove that $A$ and $B$ differ by a multiple of $p$.

Numbers from $1$ to $1000$ are arranged around a circle. Prove that it is possible to form $500$ non-intersecting line segments, each joining two such numbers, and so that in each case the difference between the numbers at each end (in absolute value) is not greater than $749$. (AA Razborov, Moscow)

Prove that for any n natural, the number \[ \sum \limits_{k=0}^{n} \binom{2n+1}{2k+1} 2^{3k} \] cannot be divided by $5$.

[b]p1.[/b] A rectangle $ABCD$ is cut from a piece of paper and folded along a straight line so that the diagonally opposite vertices $A$ and $C$ coincide. Find the length of the resulting crease in terms of the length ($\ell$) and width ($w$) of the rectangle. (Justify your answer.) [b]p2.[/b] The residents of Andromeda use only bills of denominations $\$3 $and $\$5$ . All payments are made exactly, with no change given. What whole-dollar payments are not possible? (Justify your answer.) [b]p3.[/b] A set consists of $21$ objects with (positive) weights $w_1, w_2, w_3, ..., w_{21}$ . Whenever any subset of $10$ objects is selected, then there is a subset consisting of either $10$ or $11$ of the remaining objects such that the two subsets have equal fotal weights. Find all possible weights for the objects. (Justify your answer.) [b]p4.[/b] Let $P(x) = x^3 + x^2 - 1$ and $Q(x) = x^3 - x - 1$ . Given that $r$ and $s$ are two distinct solutions of $P(x) = 0$ , prove that $rs$ is a solution of $Q(x) = 0$ [b]p5.[/b] Given: $\vartriangle ABC$ with points $A_1$ and $A_2$ on $BC$ , $B_1$ and $B_2$ on $CA$, and $C_1$ and $C_2$ on $AB$. $A_1 , A_2, B_1 , B_2$ are on a circle, $B_1 , B_2, C_1 , C_2$ are on a circle, and $C_1 , C_2, A_1 , A_2$ are on a circle. The centers of these circles lie in the interior of the triangle. Prove: All six points $A_1$ , $A_2$, $B_1$, $B_2$, $C_1$, $C_2$ are on a circle. [img]https://cdn.artofproblemsolving.com/attachments/7/2/2b99ddf4f258232c910c062e4190d8617af6fa.png[/img] PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Find all the positive integers $a,b,c$ such that $3ab= 2c^2$ and $a^3+b^3+c^3$ is the double of a prime number.

A $x>2$ real number is given. Bob has got $1997$ labels and writes one of the numbers $"x^0, x^1, x^2 ,\dotsm x^{1995}, x^{1996}"$ each labels such that all labels has distinct numbers. Bob puts some labels to right pocket, some labels to left pocket. Prove that sum of numbers of the right pocket never equal to sum of numbers of the left pocket.

Let $a$, $b$, and $c $ be integers greater than zero. Show that the numbers $$2a ^ 2 + b ^ 2 + 3 \,\,, 2b ^ 2 + c ^ 2 + 3\,\,, 2c ^ 2 + a ^ 2 + 3 $$ cannot be all perfect squares.

Let $ n$ be a positive integer and $ [ \ n ] = a.$ Find the largest integer $ n$ such that the following two conditions are satisfied: $ (1)$ $ n$ is not a perfect square; $ (2)$ $ a^{3}$ divides $ n^{2}$.

Let $x_0, x_1, x_2, \ldots$ be the sequence defined by $x_i= 2^i$ if $0 \leq i \leq 2003$ $x_i=\sum_{j=1}^{2004} x_{i-j}$ if $i \geq 2004$ Find the greatest $k$ for which the sequence contains $k$ consecutive terms divisible by 2004.

Find the sum of all integers $m$ with $1 \le m \le 300$ such that for any integer $n$ with $n \ge 2$, if $2013m$ divides $n^n-1$ then $2013m$ also divides $n-1$. [i]Proposed by Evan Chen[/i]