Found problems: 526
For any positive integer $n$, define the subset $S_n$ of natural numbers as follow
$$ S_n = \left\{x^2+ny^2 : x,y \in \mathbb{Z} \right\}.$$
Find all positive integers $n$ such that there exists an element of $S_n$ which [u]doesn't belong[/u] to any of the sets $S_1, S_2,\dots,S_{n-1}$.
[i]Proposed by Yahya Motevassel[/i]
Let $a>1$ be a positive integer and $f\in \mathbb{Z}[x]$ with positive leading coefficient. Let $S$ be the set of integers $n$ such that
\[n \mid a^{f(n)}-1.\]
Prove that $S$ has density $0$; that is, prove that $\lim_{n\rightarrow \infty} \frac{|S\cap \{1,...,n\}|}{n}=0$.
[b]p1.[/b] Joe owns stock. On Monday morning on October $20$th, $2008$, his stocks were worth $\$250,000$. The value of his stocks, for each day from Monday to Friday of that week, increased by $10\%$, increased by $5\%$, decreased by $5\%$, decreased by $15\%$, and decreased by $20\%$, though not necessarily in that order. Given this information, let $A$ be the largest possible value of his stocks on that Friday evening, and let $B$ be the smallest possible value of his stocks on that Friday evening. What is $A - B$?
[b]p2.[/b] What is the smallest positive integer $k$ such that $2k$ is a perfect square and $3k$ is a perfect cube?
[b]p3.[/b] Two competitive ducks decide to have a race in the first quadrant of the $xy$ plane. They both start at the origin, and the race ends when one of the ducks reaches the line $y = \frac12$ . The first duck follows the graph of $y = \frac{x}{3}$ and the second duck follows the graph of $y = \frac{x}{5}$ . If the two ducks move in such a way that their $x$-coordinates are the same at any time during the race, find the ratio of the speed of the first duck to that of the second duck when the race ends.
[b]p4.[/b] There were grammatical errors in this problem as stated during the contest. The problem should have said:
You play a carnival game as follows: The carnival worker has a circular mat of radius 20 cm, and on top of that is a square mat of side length $10$ cm, placed so that the centers of the two mats coincide. The carnival worker also has three disks, one each of radius $1$ cm, $2$ cm, and $3$ cm. You start by paying the worker a modest fee of one dollar, then choosing two of the disks, then throwing the two disks onto the mats, one at a time, so that the center of each disk lies on the circular mat. You win a cash prize if the center of the large disk is on the square AND the large disk touches the small disk, otherwise you just lost the game and you get no money. How much is the cash prize if choosing the two disks randomly and then throwing the disks randomly (i.e. with uniform distribution) will, on average, result in you breaking even?
[b]p5.[/b] Four boys and four girls arrive at the Highball High School Senior Ball without a date. The principal, seeking to rectify the situation, asks each of the boys to rank the four girls in decreasing order of preference as a prom date and asks each girl to do the same for the four boys. None of the boys know any of the girls and vice-versa (otherwise they would have probably found each other before the prom), so all eight teenagers write their rankings randomly. Because the principal lacks the mathematical chops to pair the teenagers together according to their stated preference, he promptly ignores all eight of the lists and randomly pairs each of the boys with a girl. What is the probability that no boy ends up with his third or his fourth choice, and no girl ends up with her third or fourth choice?
[b]p6.[/b] In the diagram below, $ABCDEFGH$ is a rectangular prism, $\angle BAF = 30^o$ and $\angle DAH = 60^o$. What is the cosine of $\angle CEG$?
[img]https://cdn.artofproblemsolving.com/attachments/a/1/1af1a7d5d523884703b9ff95aaf301bcc18140.png[/img]
[b]p7.[/b] Two cows play a game where each has one playing piece, they begin by having the two pieces on opposite vertices of an octahedron, and the two cows take turns moving their piece to an adjacent vertex. The winner is the first player who moves its piece to the vertex occupied by its opponent’s piece. Because cows are not the most intelligent of creatures, they move their pieces randomly. What is the probability that the first cow to move eventually wins?
[b]p8.[/b] Find the last two digits of $$\sum^{2008}_{k=1}k {2008 \choose k}.$$
PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].
Let $k \in \mathbb{Z}^+$ and set $n=2^k+1.$ Prove that $n$ is a prime number if and only if the following holds: there is a permutation $a_{1},\ldots,a_{n-1}$ of the numbers $1,2, \ldots, n-1$ and a sequence of integers $g_{1},\ldots,g_{n-1},$ such that $n$ divides $g^{a_i}_i - a_{i+1}$ for every $i \in \{1,2,\ldots,n-1\},$ where we set $a_n = a_1.$
[i]Proposed by Vasily Astakhov, Russia[/i]
Let $n > 1$ be a given integer. Prove that infinitely many terms of the sequence $(a_k )_{k\ge 1}$, defined by \[a_k=\left\lfloor\frac{n^k}{k}\right\rfloor,\] are odd. (For a real number $x$, $\lfloor x\rfloor$ denotes the largest integer not exceeding $x$.)
[i]Proposed by Hong Kong[/i]
What is the units digit of $13^{2012}$ ?
$\textbf{(A)}\hspace{.05in}1 \qquad \textbf{(B)}\hspace{.05in}3 \qquad \textbf{(C)}\hspace{.05in}5 \qquad \textbf{(D)}\hspace{.05in}7 \qquad \textbf{(E)}\hspace{.05in}9 $
A fractional number $x$ is called [i][b]pretty[/b][/i] if it has finite expression in base$-b$ numeral system, $b$ is a positive integer in $[2;2022]$. Prove that there exists finite positive integers $n\geq 4$ that with every $m$ in $(\frac{2n}{3}; n)$ then there is at least one pretty number between $\frac{m}{n-m}$ and $\frac{n-m}{m}$
For any $h = 2^{r}$ ($r$ is a non-negative integer), find all $k \in \mathbb{N}$ which satisfy the following condition: There exists an odd natural number $m > 1$ and $n \in \mathbb{N}$, such that $k \mid m^{h} - 1, m \mid n^{\frac{m^{h}-1}{k}} + 1$.
Let $n$ be a positive integer. $S$ is the set of nonnegative integers $a$ such that $1<a<n$ and $a^{a-1}-1$ is divisible by $n$. Prove that if $S=\{ n-1 \}$ then $n=2p$ where $p$ is a prime number.
[i]Mihai Cipu and Nicolae Ciprian Bonciocat[/i]
Suppose $P(x)$ is a degree $n$ monic polynomial with integer coefficients such that $2013$ divides $P(r)$ for exactly $1000$ values of $r$ between $1$ and $2013$ inclusive. Find the minimum value of $n$.
Let $f$ be a non-constant function from the set of positive integers into the set of positive integer, such that $a-b$ divides $f(a)-f(b)$ for all distinct positive integers $a$, $b$. Prove that there exist infinitely many primes $p$ such that $p$ divides $f(c)$ for some positive integer $c$.
[i]Proposed by Juhan Aru, Estonia[/i]
Prove that there exist $C>0$, which satisfies the following conclusion:
For any infinite positive arithmetic integer sequence $a_1, a_2, a_3,\cdots$, if the greatest common divisor of $a_1$ and $a_2$ is squarefree, then there exists a positive integer $m\le C\cdot {a_2}^2$, such that $a_m$ is squarefree.
Note: A positive integer $N$ is squarefree if it is not divisible by any square number greater than $1$.
[i]Proposed by Qu Zhenhua[/i]
Form the infinite graph $A$ by taking the set of primes $p$ congruent to $1\pmod{4}$, and connecting $p$ and $q$ if they are quadratic residues modulo each other. Do the same for a graph $B$ with the primes $1\pmod{8}$. Show $A$ and $B$ are isomorphic to each other.
[i]Linus Hamilton.[/i]
Consider the base 27 number
\[
n = ABCDEFGHIJKLMNOPQRSTUVWXYZ ,
\]
where each letter has the value of its position in the alphabet. What remainder do you get when you divide $n$ by 100? (The remainder is an integer between 0 and 99, inclusive.)
Does there exist a set $ M$ with the following properties?
[i](i)[/i] The set $ M$ consists of 1992 natural numbers.
[i](ii)[/i] Every element in $ M$ and the sum of any number of elements have the form $ m^k$ $ (m, k \in \mathbb{N}, k \geq 2).$
Let $m,n$ be positive integers greater than $1$. We define the sets $P_m=\left\{\frac{1}{m},\frac{2}{m},\cdots,\frac{m-1}{m}\right\}$ and $P_n=\left\{\frac{1}{n},\frac{2}{n},\cdots,\frac{n-1}{n}\right\}$.
Find the distance between $P_m$ and $P_n$, that is defined as
\[\min\{|a-b|:a\in P_m,b\in P_n\}\]
Find all functions $g:\mathbb{N}\rightarrow\mathbb{N}$ such that \[\left(g(m)+n\right)\left(g(n)+m\right)\] is a perfect square for all $m,n\in\mathbb{N}.$
[i]Proposed by Gabriel Carroll, USA[/i]
Let $\mathbb R$ be the set of real numbers. We denote by $\mathcal F$ the set of all functions $f\colon\mathbb R\to\mathbb R$ such that
$$f(x + f(y)) = f(x) + f(y)$$
for every $x,y\in\mathbb R$ Find all rational numbers $q$ such that for every function $f\in\mathcal F$, there exists some $z\in\mathbb R$ satisfying $f(z)=qz$.
Does there exist a nonzero polynomial $P(x)$ with integer coefficients satisfying both of the following conditions?
[list]
[*]$P(x)$ has no rational root;
[*]For every positive integer $n$, there exists an integer $m$ such that $n$ divides $P(m)$.
[/list]
Let $a$ be a positive integer. We say that a positive integer $b$ is [i]$a$-good[/i] if $\tbinom{an}{b}-1$ is divisible by $an+1$ for all positive integers $n$ with $an \geq b$. Suppose $b$ is a positive integer such that $b$ is $a$-good, but $b+2$ is not $a$-good. Prove that $b+1$ is prime.
Suppose that the set $\{1,2,\cdots, 1998\}$ has been partitioned into disjoint pairs $\{a_i,b_i\}$ ($1\leq i\leq 999$) so that for all $i$, $|a_i-b_i|$ equals $1$ or $6$. Prove that the sum \[ |a_1-b_1|+|a_2-b_2|+\cdots +|a_{999}-b_{999}| \] ends in the digit $9$.
Matt has somewhere between $1000$ and $2000$ pieces of paper he's trying to divide into piles of the same size (but not all in one pile or piles of one sheet each). He tries $2$, $3$, $4$, $5$, $6$, $7$, and $8$ piles but ends up with one sheet left over each time. How many piles does he need?
Let $P(x)$ and $Q(x)$ be two polynomials with integer coefficients, such that no nonconstant polynomial with rational coefficients divides both $P(x)$ and $Q(x).$ Suppose that for every positive integer $n$ the integers $P(n)$ and $Q(n)$ are positive, and $2^{Q(n)}-1$ divides $3^{P(n)}-1.$ Prove that $Q(x)$ is a constant polynomial.
[i]Proposed by Oleksiy Klurman, Ukraine[/i]
Let $a > 1$ be a positive integer and $d > 1$ be a positive integer coprime to $a$. Let $x_1=1$, and for $k\geq 1$, define
$$x_{k+1} = \begin{cases}
x_k + d &\text{if } a \text{ does not divide } x_k \\
x_k/a & \text{if } a \text{ divides } x_k
\end{cases}$$
Find, in terms of $a$ and $d$, the greatest positive integer $n$ for which there exists an index $k$ such that $x_k$ is divisible by $a^n$.
A point $ P$ of integer coordinates in the Cartesian plane is said [i]visible[/i] if the segment $ OP$ does not contain any other points with integer coordinates (except its ends). Prove that for any $ n\in\mathbb{N}^*$ there exists a visible point $ P_{n}$, at distance larger than $ n$ from any other visible point.
[b]Dan Schwarz[/b]