Found problems: 800
You are given a set of $n$ blocks, each weighing at least $1$; their total weight is $2n$. Prove that for every real number $r$ with $0 \leq r \leq 2n-2$ you can choose a subset of the blocks whose total weight is at least $r$ but at most $r + 2$.
Infinitely many math beasts stand in a line, all six feet apart, wearing masks, and with clean hands. Grogg starts at the front of the line, holding $n$ pieces of candy, $ n \ge 1,$ and everyone else has none. He passes his candy to the beasts behind him, one piece each to the next $n$ beasts in line. Then, Grogg leaves the line. The other beasts repeat this process: the beast in front, who has $k$ pieces of candy, passes one piece each to the next $k$ beasts in line, and then leaves the line. For some values of $n,$ another beast, besides Grogg, temporarily holds all the candy. For which values of $n$ does this occur?
Let $ a_1$, $ a_2$, $ \ldots$, $ a_n$ be distinct positive integers, $ n\ge 3$. Prove that there exist distinct indices $ i$ and $ j$ such that $ a_i \plus{} a_j$ does not divide any of the numbers $ 3a_1$, $ 3a_2$, $ \ldots$, $ 3a_n$.
[i]Proposed by Mohsen Jamaali, Iran[/i]
A sequence of real numbers $a_1,a_2,\ldots$ satisfies the relation
$$a_n=-\max_{i+j=n}(a_i+a_j)\qquad\text{for all}\quad n>2017.$$
Prove that the sequence is bounded, i.e., there is a constant $M$ such that $|a_n|\leq M$ for all positive integers $n$.
Find all positive integers $n \geqslant 2$ for which there exist $n$ real numbers $a_1<\cdots<a_n$ and a real number $r>0$ such that the $\tfrac{1}{2}n(n-1)$ differences $a_j-a_i$ for $1 \leqslant i<j \leqslant n$ are equal, in some order, to the numbers $r^1,r^2,\ldots,r^{\frac{1}{2}n(n-1)}$.
For each positive integer $k$, denote by $\tau(k)$ the number of all positive divisors of $k$, including $1$ and $k$. Let $a$ and $b$ be positive integers such that $\tau(\tau(an)) = \tau(\tau(bn))$ for all positive integers $n$. Prove that $a=b$.
A physicist encounters $2015$ atoms called usamons. Each usamon either has one electron or zero electrons, and the physicist can't tell the difference. The physicist's only tool is a diode. The physicist may connect the diode from any usamon $A$ to any other usamon $B$. (This connection is directed.) When she does so, if usamon $A$ has an electron and usamon $B$ does not, then the electron jumps from $A$ to $B$. In any other case, nothing happens. In addition, the physicist cannot tell whether an electron jumps during any given step. The physicist's goal is to isolate two usamons that she is sure are currently in the same state. Is there any series of diode usage that makes this possible?
[i]Proposed by Linus Hamilton[/i]
At a party, $25$ elves give each other presents. No elf gives a present to herself. Each elf gives a present to at least one other elf, but no elf gives a present to all other elves.
Show that it is possible to choose a group of three elves including at least two elves who give a present to exactly one of the other two elves in the group.
Functions $f,g:\mathbb{Z}\to\mathbb{Z}$ satisfy $$f(g(x)+y)=g(f(y)+x)$$ for any integers $x,y$. If $f$ is bounded, prove that $g$ is periodic.
A hunter and an invisible rabbit play a game on an infinite square grid. First the hunter fixes a colouring of the cells with finitely many colours. The rabbit then secretly chooses a cell to start in. Every minute, the rabbit reports the colour of its current cell to the hunter, and then secretly moves to an adjacent cell that it has not visited before (two cells are adjacent if they share an edge). The hunter wins if after some finite time either:[list][*]the rabbit cannot move; or
[*]the hunter can determine the cell in which the rabbit started.[/list]Decide whether there exists a winning strategy for the hunter.
[i]Proposed by Aron Thomas[/i]
Let $C[-1,1]$ be the space of continuous real functions on the interval $[-1,1]$ with the usual supremum norm, and let $V{}$ be a closed, finite-codimensional subspace of $C[-1,1].$ Prove that there exists a polynomial $p\in V$ with norm at most one, which satisfies $p'(0)>2023.$
Assign to each positive real number a color, either red or blue. Let $D$ be the set of all distances $d>0$ such that there are two points of the same color at distance $d$ apart. Recolor the positive reals so that the numbers in $D$ are red and the numbers not in $D$ are blue. If we iterate the recoloring process, will we always end up with all the numbers red after a finite number of steps?
Let $S$ be a set of integers (not necessarily positive) such that
(a) there exist $a,b \in S$ with $\gcd(a,b)=\gcd(a-2,b-2)=1$;
(b) if $x$ and $y$ are elements of $S$ (possibly equal), then $x^2-y$ also belongs to $S$.
Prove that $S$ is the set of all integers.
On a $999\times 999$ board a [i]limp rook[/i] can move in the following way: From any square it can move to any of its adjacent squares, i.e. a square having a common side with it, and every move must be a turn, i.e. the directions of any two consecutive moves must be perpendicular. A [i]non-intersecting route[/i] of the limp rook consists of a sequence of pairwise different squares that the limp rook can visit in that order by an admissible sequence of moves. Such a non-intersecting route is called [i]cyclic[/i], if the limp rook can, after reaching the last square of the route, move directly to the first square of the route and start over.
How many squares does the longest possible cyclic, non-intersecting route of a limp rook visit?
[i]Proposed by Nikolay Beluhov, Bulgaria[/i]
Find the least positive integer \(M\) for which there exist a positive integer \(n\) and polynomials \(P_1(x)\), \(P_2(x)\), \(\ldots\), \(P_n(x)\) with integer coefficients satisfying \[Mx=P_1(x)^3+P_2(x)^3+\cdots+P_n(x)^3.\]
[i]Proposed by Karthik Vedula[/i]
Let $a,b$ be two positive integers and $a>b$.We know that $\gcd(a-b,ab+1)=1$ and $\gcd(a+b,ab-1)=1$. Prove that $(a-b)^2+(ab+1)^2$ is not a perfect square.
Determine all integers $ n\geq 2$ having the following property: for any integers $a_1,a_2,\ldots, a_n$ whose sum is not divisible by $n$, there exists an index $1 \leq i \leq n$ such that none of the numbers $$a_i,a_i+a_{i+1},\ldots,a_i+a_{i+1}+\ldots+a_{i+n-1}$$ is divisible by $n$. Here, we let $a_i=a_{i-n}$ when $i >n$.
[i]Proposed by Warut Suksompong, Thailand[/i]
Consider those functions $ f: \mathbb{N} \mapsto \mathbb{N}$ which satisfy the condition
\[ f(m \plus{} n) \geq f(m) \plus{} f(f(n)) \minus{} 1
\]
for all $ m,n \in \mathbb{N}.$ Find all possible values of $ f(2007).$
[i]Author: Nikolai Nikolov, Bulgaria[/i]
Let $H = \{ \lfloor i\sqrt{2}\rfloor : i \in \mathbb Z_{>0}\} = \{1,2,4,5,7,\dots \}$ and let $n$ be a positive integer. Prove that there exists a constant $C$ such that, if $A\subseteq \{1,2,\dots, n\}$ satisfies $|A| \ge C\sqrt{n}$, then there exist $a,b\in A$ such that $a-b\in H$. (Here $\mathbb Z_{>0}$ is the set of positive integers, and $\lfloor z\rfloor$ denotes the greatest integer less than or equal to $z$.)
Let $m, n \ge 2$ be integers. Carl is given $n$ marked points in the plane and wishes to mark their centroid.* He has no standard compass or straightedge. Instead, he has a device which, given marked points $A$ and $B$, marks the $m-1$ points that divide segment $\overline{AB}$ into $m$ congruent parts (but does not draw the segment).
For which pairs $(m,n)$ can Carl necessarily accomplish his task, regardless of which $n$ points he is given?
*Here, the [i]centroid[/i] of $n$ points with coordinates $(x_1, y_1), \dots, (x_n, y_n)$ is the point with coordinates $\left( \frac{x_1 + \dots + x_n}{n}, \frac{y_1 + \dots + y_n}{n}\right)$.
[i]Proposed by Holden Mui and Carl Schildkraut[/i]
Let $n=p_1^{a_1}p_2^{a_2}\cdots p_t^{a_t}$ be the prime factorisation of $n$. Define $\omega(n)=t$ and $\Omega(n)=a_1+a_2+\ldots+a_t$. Prove or disprove:
For any fixed positive integer $k$ and positive reals $\alpha,\beta$, there exists a positive integer $n>1$ such that
i) $\frac{\omega(n+k)}{\omega(n)}>\alpha$
ii) $\frac{\Omega(n+k)}{\Omega(n)}<\beta$.
A [i]perfect number[/i] is an integer that equals half the sum of its positive divisors. For example, because $2 \cdot 28 = 1 + 2 + 4 + 7 + 14 + 28$, $28$ is a perfect number.
[list]
[*] [b](a)[/b] A [i]square-free[/i] integer is an integer not divisible by a square of any prime number. Find all square-free integers that are perfect numbers.
[*] [b](b)[/b] Prove that no perfect square is a perfect number.[/list]
Define a function $f(n)$ from the positive integers to the positive integers such that $f(f(n))$ is the number of positive integer divisors of $n$. Prove that if $p$ is a prime, then $f(p)$ is prime.
Let $a, b, c, x$ and $y$ be positive real numbers such that $ax + by \leq bx + cy \leq cx + ay$.
Prove that $b \leq c$.
Prove that the set of positive integers cannot be partitioned into three nonempty subsets such that, for any two integers $x$, $y$ taken from two different subsets, the number $x^{2}-xy+y^{2}$ belongs to the third subset.