Problem Archive

Here are the problems from previous fortnights:

Problem 1: An Apple & Pear Orchard

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?

Problem 2: Sages with Distinct Hats

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?

Problem 3: Balanced Pairwise Sums

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?

Problem 4: A Balanced Partition of the Naturals

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?

Problem 5: Polynomials with Concentrated Roots

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

Problem 6: Representing Integers with Unique Sums

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

Problem 7: A Covering System Characterization

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

Problem 8: Sages Figuring Out a Sum

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”).

Problem 9: Snowing on Subsets

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?

Problem 10: Sets with Related Sums of Powers

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

Problem 11: A Random Coin with Random Randomness

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?

Problem 12: Nontrivial Linear Functions Modulo 1

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?

Problem 13: Sages with Secret Agents

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?

Problem 14: An Opaque Quadratic Form

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?