Problem Archive

Is it possible to have an orchard consisting of finitely many apple trees and pear trees, such that

• for every apple tree in the orchard, the circle of radius $10$ meters centered at its base has exactly $10$ pear trees on its boundary, and
• the orchard contains strictly more apple trees than pear trees overall?

The empress decides to give $100$ of her sages the following test.

The sages will stand in a line, each one behind another, so that the last person in line sees everyone else ahead of them.

The empress has $101$ different hats, each having a distinct color (and the sages know all of these colors). The empress selects $100$ out of these $101$ hats and places them on the sages. Each sage sees the hats of all those in front of them, but does not see their own hat or any of the hats of the sages behind them.

The sages then go one by one and each guess their own hat color out loud. The sages pass the test if

• every sage guesses a different color, and
• at least $99$ out of the $100$ sages guess their hat colors correctly.

The sages are allowed to meet the day before test and agree on a strategy. However, during the test they are not allowed to communicate in any way (outside of their guesses for their hats, which are heard by all the sages).

Is there a strategy that guarantees the sages will pass the test?

Let $n$ be a positive integer.

Suppose $S$ is a finite set of positive integers with $|S| > 1$, such that when two distinct elements of $S$ are selected uniformly at random, the remainder when their sum is divided by $2^n$ is equal to each of the possible numbers $0, 1, \dots, 2^n-1$ with equal probability.

What is the smallest possible size $|S|$ of such a set?

Is it possible to partition the nonnegative integers into two sets $A$ and $B$ such that for every positive integer $n$, the number of ways to write $n$ as a sum of two distinct elements of $A$ equals the number of ways to write $n$ as a sum of two distinct elements of $B$?

Additionally: if such a partition exists, must it be unique?

Is there a polynomial $P$ of degree $1000$ such that

• every coefficient of $P$ is an integer,
• the leading coefficient of $P$ is $1$,
• the roots of $P$ are pairwise distinct, and
• there exists a disk of radius $0.99$ in the complex plane containing all the roots of $P$?

Does there exist a set $S$ of rational numbers with the following property: for every integer $n$, there is a unique, nonempty, finite subset of $S$ whose elements sum to $n$?

An infinite integer arithmetic progression is a set of the form $\{a + dn\mid n\in\mathbb{Z}\}$, for some choice of integers $a$ and $d$. Let $\mathcal{A}$ be the union of $10$ distinct infinite integer arithmetic progressions. Prove that if $\mathcal{A}$ contains some set of $1024$ consecutive integers, then in fact it contains every integer (that is, we necessarily have $\mathcal{A} = \mathbb{Z}$).

There are $3$ sages sitting around a round table, each with a hat on their head. A positive integer is written on each sage’s hat. No sage knows the number on their own hat (and they cannot see it) but everyone can see everyone else’s number.

The empress reveals $3$ distinct positive integers on a board for all the sages to see, and announces (truthfully) that one of these integers is the sum of the numbers written on all the hats.

Then the empress asks one of the sages, “Do you know the sum of the numbers on the hats?”

If the answer is “Yes”, the empress stops asking questions and her test for the sages is over. Otherwise, if the answer is “No”, then the empress asks the next sage (the neighbor to the right of the sage the empress just asked) the same question, and repeats this process.

Suppose the sages are intelligent and honest with their responses. Prove that the above test eventually concludes (i.e., some sage eventually answers “Yes”).

The town of Cambridge, Mathlandia contains precisely $1023$ houses, each labeled with a distinct nonempty subset of $\{1, 2, \dots, 10\}$.

One night, a blizzard enters Cambridge, and snow begins to fall upon the houses of the town in the following strange manner. Each hour, a uniform random house is picked from those not yet covered by snow (at the beginning of the night, none of the houses have snow). If the chosen house is labeled with the set $S$, then it and all houses labeled with subsets of $S$ become covered with snow.

What is the expected number of hours it takes before all houses in Cambridge are covered by snow?

Let $A$ and $B$ be two finite sets of positive real numbers, such that $$\left\{ \sum_{a\in A} a^n \mid n\in\mathbb{N} \right\} \subseteq \left\{ \sum_{b\in B} b^n \mid n\in\mathbb{N} \right\}$$

Prove that there must exist some positive integer $k$ such that $$A = \left\{b^k \mid b\in B\right\}.$$

Consider the following experiment. We pick a uniform random real $p\in [0,1]$. Then we build a coin that comes up heads with probability $p$ and tails with probability $1-p$. Finally, we flip this coin $1000$ times.

Assuming different flips of the coin have independent results, what is the probability this coin comes up heads exactly $500$ times in our experiment?

Is there a function $f : \mathbb{Q}\to \mathbb{Q}$ such that

• for all rationals $x$ and $y$, the quantity $f(x+y)-f(x)-f(y)$ is an integer, and
• for every constant $c$, there exists a rational $x$ such that $f(x) - cx$ is not an integer?

The empress decides to give her sages the following test.

A group of $200$ sages will stand in line, each one behind the other, so that the last person in line sees everyone else ahead of them. Among them, $100$ are secret agents enlisted by the empress. The remaining $100$ sages know that there $100$ agents among them, but do not know which sages are secret agents.

The empress places a hat on each sage’s hat. Each hat is either cyan or magenta, and each sage only sees the hats on sages standing in front of them. The sages then take turns (starting from the back of the line, with the sage who sees everyone else’s hats) announcing guesses of their own hat color.

All $200$ sages are allowed to meet the day before the test and agree on a strategy. However, during the test they are not allowed to communicate in any way (outside of the guesses for their hats, which are heard by all sages). Also, during the test, secret agents can behave however they want, and might not follow the strategy that the rest of the sages agreed to.

What is the maximum number of sages who can be guaranteed to correctly guess their own hat color?

Let $n$ be a fixed positive integer.

Do there exist reals $a_1, a_2, \dots, a_n$ such that

$$\sum_{1\le i,j\le n} \frac{a_{i}a_{j}}{i+j}$$

is negative?

The empress invites 2015 of her sages to a festival. Some of the sages are honest and the rest are evil. The honest sages always tell the truth, whereas the evil ones are free to say whatever they want. The sages know who is who, but the empress does not.

During the festival, the empress asks every sage a yes-or-no question. Then she expels one of the sages from her kingdom. The expelled sage leaves through a magic door, which reveals to the empress whether that sage was evil or not. After this, the empress starts the next round of questions and expels another sage. The empress continues the rounds until she decides to stop.

Is it always possible for the empress to expel all the evil sages, while guaranteeing at most one honest sage gets expelled?

Do there exist distinct sets of reals $A$ and $B$ such that

• we have $|A| = |B| = 1025$, and
• for every real $x$, the number of ways to represent $x$ as a sum of two distinct elements from $A$ is the same as the number of ways to represent $x$ as the sum of two distinct elements from $B$?

Does there exist an equiangular $729$-gon, whose sides have lengths $1, 2, \dots, 729$ in some order? Similarly, does there exist an equiangular $730$-gon, whose sides have lengths $1, 2, \dots, 730$ in some order?

Let $P$ be a regular polygon (i.e. an equiangular, equilateral polygon with at least three vertices). The vertices of $P$ are partitioned into a collection $\mathcal{C}$ of at least two sets $S$, with the property that the vertices in any such set $S$ can be connected to form a regular polygon. Prove that either $\mathcal{C}$ has only one set, or there exist two distinct sets in $\mathcal{C}$ of the same size.

In other words, prove that if a regular polygon can be decomposed into multiple smaller regular polygons, than at least two of the smaller regular polygons must have the same number of vertices.

Find all sets $X$ of exactly $17$ distinct integers, with the property that there exists an infinite set of integers $Y$ such that every integer $z$ can be written uniquely in the form $$z = x + y$$ for some integers $x\in X$ and $y\in Y$.

In other words, characterize all sets of $17$ integers which can be used to tile all of $\mathbb{Z}$.

The Fibonacci sequence $(F_n)$ is defined by setting $F_0 = F_1 = 1$, and then taking $$F_{n} = F_{n-1} + F_{n-2}$$ for all integers $n\ge 2$. We further define the sequence of Fibonacci factorials $(f_n)$ by taking $$f_n = \prod_{m=0}^n F_m$$ for each integer $n\ge 0$. Prove that for all nonnegative integers $a$ and $b$, the quantity $$\frac{f_{a+b}}{f_af_b}$$ is an integer.

We call a function $g$ an “exponential function” if it is of the form $g(n) = a^{Q(n)}$, where $a$ is a positive integer and $Q$ is a polynomial with integer coefficients which sends positive integers to positive integers. We call a function an “exponential polynomial” if it is a sum of products of exponential functions.

Does there exist an exponential polynomial $f$ and a non-constant polynomial $P$ with integer coefficients such that $P(n) \mid f(n)$ for all positive integers $n$?

A cake is prepared for a dinner party, to which either $p$ people or $q$ people will end up coming, for some positive integers $p$ and $q$. What is the minimum number of pieces into which the cake must be cut in advance to ensure that, in either case, the cake can be evenly distributed among the people who end up attending the party?

We have one hundred safes and one hundred keys. Each key is capable of unlocking exactly one of the safes, and no two keys unlock the same safe. We uniformly at random place one key into each safe. Then we close and lock ninety of the safes, again chosen uniformly at random. What is the probability that from this configuration, we can unlock all the safes and retrieve all the keys?

For any positive integers $n$ and $k$, let $\varphi_k(n)$ denote the number of positive integer divisors $d$ of $n$ such that $d-k$ is a multiple of four. Prove that the number of ways to write $n$ as a sum of squares of two integers is equal to $$4\left(\varphi_1(n) - \varphi_3(n)\right).$$

Let $f$ be a nonzero polynomial with integer coefficients, and let $z$ be a complex number such that $f(z) = 0$ and $|z| = 1$. Does there necessarily exist a positive integer $m$ such that $z^m = 1$?

What if we know that every complex number $w$ satisfying $f(w) = 0$ has $|w| = 1$. In this case, if $f(z) = 0$ and $|z| = 1$, must there exist a positive integer $m$ such that $z^m = 1$?

Let $\mathcal{P}_1, \mathcal{P}_2, \dots, \mathcal{P}_n$ be convex polygons in the plane. We say a line cleanly separates these polygons if the line does not intersect any of the $\mathcal{P}_i$, and there exist indices $i\neq j$ such that the polygons $\mathcal{P}_i$ and $\mathcal{P}_j$ are on different halfplanes determined by the line (i.e., the line has polygons to both of its sides).

Let $\ell_i$ denote the perimeter of $\mathcal{P}_i$. Prove that if there is no line which cleanly separates $\mathcal{P}_1, \mathcal{P}_2, \dots, \mathcal{P}_n$, then these polygons can be enclosed in a single polygon of perimeter at most $$\ell_1 + \ell_2 + \dots + \ell_n.$$

Does there exist an infinite sequence of complex numbers $a_1, a_2, \dots$ such that for any positive integer $p$, the sum

$$\sum_{n=1}^{\infty} a_n^p$$

converges if and only if $p$ is prime?

Let $H_1$ be a convex 97-gon, with vertices $v_0, \dots, v_{96}$ in clockwise order. For each positive integer $k$, we define a new 97-gon $H_{k+1}$ on the same vertex set as $H_k$ as follows. For each index $j = 0, \dots, 96$, vertex $v_j$ in $H_{k+1}$ is the reflection of vertex $v_j$ from $H_k$ in vertex $v_{j+k}$ from $H_k$, where indices are taken modulo 97.

Prove that $H_{96}$ and $H_1$ are similar polygons.

A positive integer is called downhill if the digits in its decimal representation form a (not necessarily strictly) decreasing sequence from left to right. Let $P$ be a polynomial with rational coefficients with the property that, if $n$ is a downhill integer, then $P(n)$ is an integer. Is it necessarily the case that $P(n)$ is an integer for every integer $n$?

Prove that for all sufficiently large positive integers $n$, any graph on $n$ vertices with at least $n + n^{0.51}$ edges necessarily contains at least one thousand simple cycles of equal length.

A thousand coins, labeled $1$ through $1000$, are arranged in a line in some order. We say two coins labeled with integers $i$ and $j$ form an inversion if $i < j$, but coin $i$ appears to the right of coin $j$ in the linear arrangement.

Consider the following procedure: for each $i = 1, 2, \dots, 1000$ in that order, we move coin $i$ from its current position to its opposite, position reflected in the middle of the sequence (i.e., if coin $i$ currently has exactly $c$ coins to its left, then we place it in a new position so that it now has exactly $c$ coins to its right). Prove that after this procedure is completed, the new arrangement has the same number of pairs of coins forming inversions that the original ordering had.

Prove that for any distinct positive integers $m$ and $n$, the polynomials $$P(x) = 1 + 2x + \dots + mx^{m-1}$$ and $$Q(x) = 1 + 2x + … + nx^{n-1}$$ are relatively prime.