Let $P(x)=x^{2000}-x^{1000}+1$. Prove that there don't exist 8002 distinct positive integers $a_1,\dots,a_{8002}$ such that $a_ia_ja_k|P(a_i)P(a_j)P(a_k)$ for all $i\neq j\neq k$. [I]Proposed by A. Baranov[/i]

Given two integers $m\geq 2$ and $n\geq 2$ we consider two types of sequences of length $m\cdot n$ formed exclusively by $0$ and $1$ TYPE 1 sequences are all those that verify the following two conditions: $\bullet$ $a_ka_{k+m} = 0$ for all $k = 1, 2, 3, ...$ $\bullet$ If $a_ka_{k+1} = 1$, then $k$ is a multiple of $m$. TYPE 2 sequences are all those that verify the following two conditions: $\bullet$ $a_ka_{k+n} = 0$ for all $k = 1, 2, 3, ...$ $\bullet$ If $a_ka_{k+1} = 1$, then $k$ is a multiple of $n$. Prove that the number of sequences of type 1 is equal to the number of sequences of type 2.

Find all positive integers $a$ and $b$ such that \[ {a^2+b\over b^2-a}\quad\mbox{and}\quad{b^2+a\over a^2-b} \] are both integers.

[b]p1.[/b] (a) Show that for every set of three integers, we can find two of them whose average is also an integer. (b) Show that for every set of $5$ integers, there is a subset of three of them whose average is an integer. [b]p2.[/b] Let $f(x) = x^2 + ax + b$ and $g(x) = x^2 + cx + d$ be two different quadratic polynomials such that $f(7) + f(11) = g(7) + g(11)$. (a) Show that $f(9) = g(9)$. (b) Show that $x = 9$ is the only value of $x$ where $f(x) = g(x)$. [b]p3.[/b] Consider a rectangle $ABCD$ and points $E$ and $F$ on the sides $BC$ and $CD$, respectively, such that the areas of the triangles $ABE$, $ECF$, and $ADF$ are $11$, $3$, and $40$, respectively. Compute the area of rectangle $ABCD$. [img]https://cdn.artofproblemsolving.com/attachments/f/0/2b0bb188a4157894b85deb32d73ab0077cd0b7.png[/img] [b]p4.[/b] How many ways are there to put markers on a $8 \times 8$ checkerboard, with at most one marker per square, such that each of the $8$ rows and each of the $8$ columns contain an odd number of markers? [b]p5.[/b] A robot places a red hat or a blue hat on each person in a room. Each person can see the colors of the hats of everyone in the room except for his own. Each person tries to guess the color of his hat. No communication is allowed between people and each person guesses at the same time (so no timing information can be used, for example). The only information a person has is the color of each other person’s hat. Before receiving the hats, the people are allowed to get together and decide on their strategies. One way to think of this is that each of the $n$ people makes a list of all the possible combinations he could see (there are $2^{n-1}$ such combinations). Next to each combination, he writes what his guess will be for the color of his own hat. When the hats are placed, he looks for the combination on his list and makes the guess that is listed there. (a) Prove that if there are exactly two people in the room, then there is a strategy that guarantees that always at least one person gets the right answer for his hat color. (b) Prove that if you have a group of $2008$ people, then there is a strategy that guarantees that always at least $1004$ people will make a correct guess. (c) Prove that if there are $2009$ people, then there is no strategy that guarantees that always at least $1005$ people will make a correct guess. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let \( A \) and \( B \) be positive integers, and let \( S \) be a set of positive integers with the following properties: (1) For every non-negative integer $k$, $\text{ } A^k \in S$; (2) If a positive integer $ n \in S$, then every positive divisor of $ n$ is in $S$; (3) If $m ,n \in S$ and $m,n$ are coprime, then $mn \in S$; (4) If $n \in S$, then $An + B \in S$. Prove that all positive integers coprime to \( B \) are in \( S \).

Let $(a_n)_{n \in \mathbb{N}}$ be a sequence of integers. Define $a_n^{(0)} = a_n$ for all $n \in \mathbb{N}$. For all $M \geq 0$, we define $(a_n^{(M + 1)})_{n \in \mathbb{N}}:\, a_n^{(M + 1)} = a_{n + 1}^{(M)} - a_n^{(M)}, \forall n \in \mathbb{N}$. We say that $(a_n)_{n \in \mathbb{N}}$ is $\textrm{(M + 1)-self-referencing}$ if there exists $k_1$ and $k_2$ fixed positive integers such that $a_{n + k_1} = a_{n + k_2}^{(M + 1)}, \forall n \in \mathbb{N}$. (a) Does there exist a sequence of integers such that the smallest $M$ such that it is $\textrm{M-self-referencing}$ is $M = 2022$? (a) Does there exist a stricly positive sequence of integers such that the smallest $M$ such that it is $\textrm{M-self-referencing}$ is $M = 2022$?

Prove that some (or one) of any $100$ integers can always be chosen so that the sum of the chosen integers is divisible by $100$.

Find the smallest positive integer $x$ such that [list] [*] $x$ is $1$ more than a multiple of $3$, [*] $x$ is $3$ more than a multiple of $5$, [*] $x$ is $5$ more than a multiple of $7$, [*] $x$ is $9$ more than a multiple of $11$, and [*] $x$ is $2$ more than a multiple of $13$.[/list]

Prove that for any given number $a_k, 1 \le k \le 5$, there are $\lambda_k \in \{-1, 0, 1\}, 1 \le k \le 5$, which are not all equal zero, such that $11 | \lambda_1a_1^2+\lambda_2a_2^2+\lambda_3a_3^2+\lambda_4a_4^2+\lambda_5a_5^2$

Solve in the integers the diophantine equation $$x^4-6x^2+1 = 7 \cdot 2^y.$$

Find the remainder when $3^{2007}$ is divided by $2007$.

Find all pairs of integers $(a,b)$ such that $a^2+ab+1\mid b^2+ab+a+b-1$.

To every natural number $k, k \geq 2$, there corresponds a sequence $a_n(k)$ according to the following rule: \[a_0 = k, \qquad a_n = \tau(a_{n-1}) \quad \forall n \geq 1,\] in which $\tau(a)$ is the number of different divisors of $a$. Find all $k$ for which the sequence $a_n(k)$ does not contain the square of an integer.

a) Let $m$ and $n$ be natural numbers. For some nonnegative integers $k_1, k_2, ... , k_n$ the number $$2^{k_1}+2^{k_2}+...+2^{k_n}$$ is divisible by $(2^m-1)$. Prove that $n \ge m$. b) Can you find a number, divisible by $111...1$ ($m$ times "$1$"), that has the sum of its digits less than $m$?

Let $p$ be a prime and $Q(x)$ be a polynomial with integer coefficients such that $Q(0) = 0, \ Q(1) = 1$ and the remainder of $Q(n)$ is either $0$ or $1$ when divided by $p$, for every $n \in \mathbb{N}$. Prove that $Q(x)$ is of degree at least $p - 1$.

Let $a$, $b$ be positive integers such that $b^n+n$ is a multiple of $a^n+n$ for all positive integers $n$. Prove that $a=b$. [i]Proposed by Mohsen Jamali, Iran[/i]

If $p$ is a prime and $n$ an integer such that $1<n \le p$, then \[\phi \left( \sum_{k=0}^{p-1}n^{k}\right) \equiv 0 \; \pmod{p}.\]

Prove that there are infinitely many positive integers $ n$ for which all the prime divisors of $ n^{2}\plus{}n\plus{}1$ are not more then $ \sqrt{n}$. [hide] Stronger one. Prove that there are infinitely many positive integers $ n$ for which all the prime divisors of $ n^{3}\minus{}1$ are not more then $ \sqrt{n}$.[/hide]

Write down $f(n)$ for the greatest odd divisor of $n \in N_0$. (a) Determine $f (n + 1) + f (n + 2) + ... + f(2n)$. (b) Determine $f(1) + f(2) + f(3) + ... + f(2n)$.

We say that three positive integers $a$, $b$ and $c$ form a [i]family[/i] if the following two conditions are satisfied: [list] [*]$a + b + c = 900$. [*]There exists an integer $n$, with $n \geqslant 2$, such that $$\frac{a}{n-1}=\frac{b}{n}=\frac{c}{n+1}.$$ [/list] Determine the number of such families.

Consider two coprime integers $p{}$ and $q{}$ which are greater than $1{}$ and differ from each other by more than $1{}$. Prove that there exists a positive integer $n{}$ such that \[\text{lcm}(p+n, q+n)<\text{lcm}(p,q).\]

A four-element set $\{a, b, c, d\}$ of positive integers is called [i]good[/i] if there are two of them such that their product is a mutiple of the greatest common divisor of the remaining two. For example, the set $\{2, 4, 6, 8\}$ is good since the greatest common divisor of $2$ and $6$ is $2$, and it divides $4\times 8=32$. Find the greatest possible value of $n$, such that any four-element set with elements less than or equal to $n$ is good. [i]Proposed by Victor and Isaías de la Fuente[/i]

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$.

Let $\tau(n)$ denote the number of positive divisors of the positive integer $n$. Prove that there exist infinitely many positive integers $a$ such that the equation $ \tau(an)=n $ does not have a positive integer solution $n$.

Find all pair of integers $(m,n)$ and $m \ge n$ such that there exist a positive integer $s$ and a) Product of all divisor of $sm, sn$ are equal. b) Number of divisors of $sm,sn$ are equal.