[Question] What are the best elementary math problems you know?

[Ege Erdil]

I’m looking for math problems of a specific kind. Here are the conditions I hope the problems satisfy:

• A good mathematician who hasn’t seen the problem before should take anywhere from 30 minutes to 2 hours to solve it.

• The solution should only involve undergraduate level maths. Difficult Putnam problems are a good benchmark for what kind of maths background should be required to solve the problems. The background required can be much less than this, but it shouldn’t be more.

• For whatever reason you think the problem should be more widely known. The reason is completely up to you: the solution might include some insight which you find useful, it might be particularly elegant, it might involve some surprising elements that you wouldn’t expect to appear in the context of the problem, et cetera.

• It’s fine if the problem is well known, your examples don’t have to be original or obscure.

Here are some examples:

• If a polynomial with rational coefficients defines an injective map $Q\to Q$, must it also define an injective map $R\to R$? If yes then prove this is true, if no then find an explicit counterexample.

• Prove that $\mathrm{Hom}({\prod }_{k\in N}Z,Z)\cong {⨁}_{k\in N}Z$. In words, prove that homomorphisms of abelian groups from the direct product of countably many copies of $Z$ to $Z$ themselves form a group that’s isomorphic to the direct sum of countably many copies of $Z$.

• If $f:R\to R$ is a continuous function such that the sequence $f\left(\alpha \right),f\left(2\alpha \right),f\left(3\alpha \right),\dots$ converges to $0$ for every $\alpha >0$, must it be the case that ${lim}_{x\to \infty }f\left(x\right)=0$? If yes then prove this is true, if no then find an explicit counterexample.

They are all relatively famous but they should give a sense of the flavor of what I’m looking for.

[Jacob_Hilton]

A magician asks you to choose any infinite sequence of 0s and 1s, and to start reciting it until they say stop. They will then make a prediction of the form “p% of the next n digits will be 0”, and they will be correct to within 1% at least 99% of the times they perform the trick. How is the trick done?

h/​t Alex Arkhipov

[paulfchristiano]

A solution:

We’ll describe a strategy for the magician that stops you sometime within the first $2^k$ bits and gets an expected squared error of exactly $1/k$ regardless of your string. If we pick $k={10}^6$, the strategy has a squared error of at most ${10}^{-6}$, and so gets within 1% at least 99% of the time. This requires the magician to wait for up to $2^{{10}^6}$ bits. I suspect that’s roughly optimal but haven’t checked the construction carefully.

The strategy is to pick a random $0\le \ell \le k$, then pick a random $1\le m\le 2^{k-l-1}$. Then the magician stops you after $(2m+1)2^{\ell }$ steps, and guesses that the next $2^{\ell }$ bits will have the same average as the preceding $2^{\ell }$ bits.

(Probably it would also work to pick a random multiple of $2^{\ell }$ instead of an odd multiple, and it would probably work to just pick the horizon and stopping point at random from suitable distributions. The exact choices here were just to make the analysis work out, and it may be an artifact of me being more comfortable with boolean fourier analysis than real fourier analysis.)

The intuition is that you can try to trick the magician in many ways, but you can’t do all of them at once:

• If the magician guesses that the next bit will be equal to the last, then to fool you could make each bit different from the last.

• But if your bitstring were to flip a lot of the time, then it would average to ¹⁄₂ over any long time period.

• So to stymie that, you’d need to ensure that you also include some “low frequency” variation where the most common symbol flips from 0 to 1 every 1000 steps (say).

• But then the magician could zoom out to every million steps, and the average would be closer to 50-50. So we need even-lower-frequency variation.

• But we only have so much variance to go around. So eventually the magician is guaranteed to be OK—if they choose from at least a million exponentially decreasing frequencies, and then guess that their can’t be much oscillation at that frequency, they will be roughly correct.

OK, now the actual analysis. Let’s consider your first $2^k$ numbers as a function $f:{\{0,1\}}^k\to \{-1,1\}$ (note that we’ve replaced 0 with −1 just to make things balanced, I think that’s just personal preference). Define $\hat{f}$ as the fourier transform of $f$, i.e. $\hat{f}\left(y\right)=\frac{1}{2^n}{\sum }_x{(-1)}^{x\cdot y}f\left(x\right)$. Then it’s easy to see that $f\left(x\right)={\sum }_y(-1{)}^{x\cdot y}\hat{f}(y)$.

The fact that “there is only so much variance to go around” is captured by the following calculation: ${\sum }_y\hat{f}(y{)}^2={\sum }_y{\left(\frac{1}{2^k}{\sum }_x\right(-1{)}^{x\cdot y}f\left(x\right))}^2=\frac{1}{2^{2k}}{\sum }_y{\sum }_x{\sum }_{x^{\prime }}(-1{)}^{(x+x^{\prime })\cdot y}f\left(x\right)f\left(x^{\prime }\right)$. Then we can flip the order of the sum over $x$ and $y$, and note that ${\sum }_y(-1{)}^{(x+x^{\prime })\cdot y}=0$ unless $x=x^{\prime }$. Thus ${\sum }_y\hat{f}(y{)}^2=\frac{1}{2^k}{\sum }_{x}f(x{)}^2=1$.

If we write down the magician’s loss in terms of the fourier coefficients, we’ll get just the bounds we wanted. This is a lot of symbols but it’s all pretty mechanical and standard.

If the magician picks $m$ and $\ell$, then their guess will be the average value of $f$ over all bitstrings that start with $m0$. Then that guess will be compared to the average of $f$ over all bitstrings that start with $m1$. I’m going to ignore factors of 2 in the error for simplicity. Then their squared error is: ${\left(\frac{1}{2^{\ell }}{\sum }_{z\in {\{0,1\}}^{\ell }}f\right(m0z)-\frac{1}{2^{\ell }}{\sum }_{z\in {\{0,1\}}^{\ell }}f(m1z\left)\right)}^2$. We can expand each appearance of $f$ in terms of the fourier transform $\hat{f}$, and group together like terms, to get: ${\left(\frac{1}{2^{\ell }}{\sum }_{z\in {\{0,1\}}^{\ell }}{\sum }_y\hat{f}\right(y\left)\left(\right(-1{)}^{m0z\cdot y}-(-1{)}^{m1z\cdot y})\right)}^2$.

Now we can flip the order of summation of $y$ and $z$. When we sum over $z$, the innermost term $(-1{)}^{m0z\cdot y}-(-1{)}^{m1z\cdot y}$ usually disappears. The two terms are opposite unless $y$ has a 1 in the ${(\ell +1)}^{\text{st}}$ coordinate. And the summation over $z$ will cancel everything out if $y$ has any non-zero terms in positions after $\ell +1$. So this is non-zero if and only if the final 1 in $y$ is in position $\ell +1$. For such $y$, it is equal to $2^{\ell }(-1{)}^{m{0}^{k-\ell }\cdot y}$ .

Write $Y_{\ell }$ for the set of $y$ which have their last 1 in position $\ell +1$, and write $m\cdot y$ for $m{0}^{k-\ell }\cdot y$. Then we can write the squared loss as ${\sum }_{y\in Y_{\ell }}{\sum }_{y^{\prime }\in Y_{\ell }}\hat{f}\left(y\right)\hat{f}\left(y^{\prime }\right)(-1{)}^{m\cdot (y+y^{\prime })}$. If we now take the average over the $2^{k-\ell }$ different values of $m$, we get $\frac{1}{2^{k-\ell }}{\sum }_m{\sum }_{y\in Y_{\ell }}{\sum }_{y^{\prime }\in Y_{\ell }}\hat{f}\left(y\right)\hat{f}\left(y^{\prime }\right)(-1{)}^{m\cdot (y+y^{\prime })}$. Again, we can reverse the order of summation, and the inner sum adds up to 0 unless $y=y^{\prime }$. So we get ${\sum }_{y\in Y_t}\hat{f}(y{)}^2$.

Now if we draw $\ell$ at random, we get an expected squared error of $\frac{1}{k}{\sum }_{\ell }{\sum }_{y\in Y_{\ell }}\hat{f}(y{)}^2=\frac{1}{k}{\sum }_y\hat{f}(y{)}^2=\frac{1}{k}$. QED.

(I sorted of cheated in that I promised exactly $1/k$ error but then dropped some factors of 2. I think those factors exactly cancel with the difference between predicting $\pm 1$ and predicting $\{0,1\}$, but don’t hold me to that.)

[paulfchristiano]

I found this puzzle fun and I feel like I learned something useful about math when you gave it to me a few years ago.

[acgt]

Curious what the solution to this one is? Couldn’t figure it out

[paulfchristiano]

I posted it in another reply.

[Ege Erdil]

I’ll be thinking about this problem for the next hour or so unless something comes up, so I’ll be writing my thoughts down here if I think they are important.

A couple of preliminary observations:

• The magician must be playing a mixed strategy. This is easy to see since otherwise a copy of the magician playing against him could know when he stops and could know his prediction and deliberately falsify it no matter what.

• It’s not enough for the prediction after the stopping to be random, the stopping time itself must also be random. This is because if I knew when the magician would stop then from that moment on I would just randomize my bit string to be either all 1s or all 0s, and the magician couldn’t win with a probability above 50% no matter what.

• The naive intuition that “it’s impossible because the magician can’t gain information about the future of an arbitrary bit string” is wrong, because the magician doesn’t actually need to gain information in a technical sense to be able to make this prediction. Obviously if the bit strings are sampled randomly from the Cantor set then the magician could just guess that 50% of the next 1 million digits would be 0 and he would win even though he has no information about the string at all.

[Ege Erdil]

I don’t have a solution, but I’ve done some analysis to try to make a strategy of the following form work: pick the number of steps at which you halt from a distribution $\sim 1/k^{1+\epsilon }$ and then guess that the mean of the next $k$ terms will be equal to the mean of the last $k$ terms. I tried to get a cancellation in some $L^2$ error sum but unfortunately it went nowhere.

I think this strategy doesn’t work and I’m not even sure if it’s a good idea to not have $k$ depend on the sequence the magician has seen so far, but I couldn’t see a simple argument for why it would be impossible so I tried to make it work anyway.

[paulfchristiano]

This seems like it nearly works, but

The magician needs to separately pick “how long a horizon to look over” and “when to stop.” Otherwise I can just have a string with exponentially increasing runs of 0s and 1s, and you’ll usually be pretty wrong if you use the first $k$ to predict the next $k$.

[philip_b]

Is the following a correct reformulation of your problem?

Say that a magician’s pure strategy is a function on finite bitstrings which returns either “go on” or “stop” with a positive integer $n$ and a frequency $f$ of zeros.

A magician’s mixed strategy is a probability distribution over magician’s pure strategies. (Btw, I’m not sure what kind of sigma-algebra is suitable here.)

A player’s mixed strategy is a probability distribution over infinite bitstrings.

A magician’s mixed strategy together with a player’s mixed strategy define, in the obvious way, a probability distribution over outcomes “magician wins” (i.e., the magician’s prediction was within 1%) and “player wins”.

You’re claiming that there is a magician’s mixed strategy s.t. for every player’s mixed strategy, magician wins with probability at least 0.99.

[paulfchristiano]

I think you can slightly simplify to say: the magician has a probability distribution over strategies, such that for every sequence the magician wins with probability 0.99.

[philip_b]

Yes, indeed.

[Yair Halberstadt]

A countably infinite number of people are each assigned a hat that is either red or blue.

Without communication, they must each guess the color of their hat. The cannot know of each others guesses.

Show that there exists a strategy by which only a finite number of people will guess incorrectly.

[philip_b]

I’ve formalized this problem in Coq with mathcomp. Yeah, idk why I decided to do this.

From mathcomp Require Import all_ssreflect.
Set Implicit Arguments.
Unset Strict Implicit.
Unset Printing Implicit Defensive.

Definition hats_assignment : Type := nat -> bool.

Definition policy_of_one_person (n : nat) : Type :=
  {policy : hats_assignment -> bool &
   forall ha : hats_assignment,
     let ha' := fun m => if m == n is true then ~~ (ha m) else ha m
     in policy ha == policy ha'}.

Definition strategy : Type :=
  forall n : nat, policy_of_one_person n.

Lemma ex_good_strategies :
  exists s : strategy, forall ha : hats_assignment, exists N : nat, forall n : nat, n >= N ->
    (projT1 (s n)) ha == ha n.
Proof.
Admitted.

If you want to solve it, you need to replace Admitted. with an actual proof.

[Ege Erdil]

This is great.

[Ege Erdil]

For clarification, the people can all see the color of other people’s hats, right? If so, then:

The people agree in advance (using the axiom of choice!) on a set of representatives for all equivalence classes in $2^N/\sim$, where two bit sequences are equivalent under $\sim$ iff they differ in only finitely many positions.

When they are guessing, they all know the equivalence class they are in and they guess the color for their hat that is implied by the agreed upon representative of that equivalence class. By construction, only finitely many of them can guess incorrectly.

[Yair Halberstadt]

Yes they can see each others hats.

[philip_b]

Do people have common knowledge of an ordering of all of them?

[Yair Halberstadt]

We can assume that they can each magically agree on the same strategy, and that as they are countably infinite they can find a common ordering of them.

[Yair Halberstadt]

Show that every countably infinite graph contains either a countably infinite complete subgraph, or a countably infinite edgeless subgraph.

[Ege Erdil]

Another nice one. I liked this one enough for a strong upvote. Here is my solution:

Say the graph is $G=G_0$. If $G$ has no vertices of infinite degree then it has a countably infinite edgeless subgraph: we just pick any vertex, throw away its neighbors, pick another vertex, throw away its neighbors, etc. Since we can always do this, we end up picking countably infinite vertices without any edges between them, so we’re done.

Now suppose $G$ has at least one vertex of infinite degree, say $v_1$. Let $G_1$ be the subgraph consisting of the neighbors of $v_1$ and all the edges between them. If this subgraph has no vertices of infinite degree then we’re again done as above, and if there is such a vertex $v_2$ then we look at the subgraph of all of its neighbors in $G_1$, say $G_2$. If we can continue this process indefinitely then we end up picking countably infinitely many vertices $v_i$ which form a complete subgraph, and if it stops then one of the $G_i$ and thus $G$ itself has a countably infinite edgeless subgraph.

[AprilSR]

This sounds obviously false to me? Why can’t you have a countably infinite graph where all vertices have degree 2?

[Algon]

Biject the graph to $z$, drop all odd edges and you get a countably infinite subgraph. The key point is that you’re looking for any subgraph that is complete or edgeless.

[AprilSR]

Ah! I see.

[Ege Erdil]

There are $n$ paratroopers that simultaneously land on the plane $R^2$ at independently and identically distributed positions, drawn from a distribution with density $p$. After landing, each paratrooper sleeps for independent and identically distributed times drawn from a distribution with density $q$ on the positive real numbers. Before they wake up they are unable to take any action other than standing at the position they’ve landed on.

All paratroopers have two devices with them: an infinite precision radar and a detonation button, both of which can only be used once.

Using the radar tells them the exact positions of all other paratroopers relative to the current position of the radar user. (This is important—the paratroopers don’t have a compass to fix global directions such as north and south, and the radar only gives them information about relative positions.) This is the only way the paratroopers have of getting information about each other’s locations: aside from all of them being able to use the radar once, they have no other way of getting information about the location of other paratroopers even if they are standing on the same spot at the same time. The radar also doesn’t tell the user which paratroopers are at which locations, it only displays every location (possibly with multiplicity in the case of coincidence) at which there is a paratrooper.

The mission of the paratroopers is to press their detonation buttons all at the same location on the plane, though not necessarily at the same time. In other words, they all need to coordinate to go to the same point and press the detonation button once they are there, after which they are once again free to move as they please until the mission is either a success or a failure.

As a final technical detail, both density functions $p$ and $q$ are nonzero on their whole domain: this is $R^2$ for $p$ and $R^{\ge 0}$ for $q$.

Assuming that the paratroopers can agree on a strategy before the mission begins, show that there is a strategy with which they can win almost surely (with probability equal to 1).

[DaemonicSigil]

Cool problem, I think I may have (at least a sketch of) a solution. The way the paratroopers are allowed to move wasn’t specified in the problem, but it would be too easy if they were allowed to just teleport around to arbitrary locations, so I’ll assume that their movement has to be described by continuous functions.

Everyone will head towards a point chosen by the first paratrooper to wake up. Thus the first paratrooper to wake up must somehow “mark” himself. Further, he must mark himself instantly, right after waking up. This seems impossible, since the only available information he can mark himself with is his position relative to the others. Moving anywhere takes time doesn’t it? It’s not obvious how you can mark yourself instantly if you’re constrained to move in a continuous manner. In any case, all the troopers will use their infinite precision radar as soon as they wake up, so that they can find out instantly whether or not they are the first trooper, and mark themselves instantly if it turns out they are. (You can check if you’re the first trooper by checking the map your radar gives you to see if anyone else is marked already. If no one is, you’re first.)

My general solution works only for $n\ge 3$, so as a warmup, let’s solve $n=2$. In this case, there is a line between the troopers. My chosen strategy will never have the troopers move off that line, so this reduces to a problem in $R$. With probability 1, the troopers will be an irrational distance apart. The first trooper to wake up will instantly mark himself by moving to be a rational distance from the other trooper. How to accomplish this is kind of tricky. He can pick a particular nearby rational point to move to, but it will take him finite time to get there by moving continuously, and the other trooper might wake up during that time.

The trick is a construction very similar to how the Minkowski Question Mark Function is constructed. I recommend taking a look at that Wikipedia article; there’s a good picture of the function, and it will help with understanding the following. The first trooper to wake up will move to the position of the second trooper, taking 1 second to do so, and then stay there. At a random time $t$ (for any probability density function on $t$), $?\left(t\right)$ is rational. We’ll describe this by saying that $?$ is “rational almost everywhere”. Similarly, we’d like to construct a continuous function $f\left(t\right):[0,1]\to R$ that is a rational distance from the position of the second trooper almost everywhere. We’d also like $f\left(0\right)$ to equal the starting position of the first trooper, and $f\left(1\right)$ to equal the starting position of the second trooper.

Just as when constructing the Minkowski Question Mark Function, we proceed by recursively defining $f$ on middle thirds. WLOG suppose $f\left(0\right)<f\left(1\right)$. Pick a point $a$ to be a rational distance from $f\left(1\right)$ such that $f\left(0\right)<a<f\left(1\right)$, and set $f\left(\right[1/3,2/3\left]\right)=a$. Pick $a_{+}$ and $a_{-}$ to be a rational distance from $f\left(1\right)$ such that $f\left(0\right)<a_{-}<a<a_{+}<f\left(1\right)$. Set $f\left(\right[1/9,2/9\left]\right)=a_{-}$ and $f\left(\right[7/9,8/9\left]\right)=a_{+}$. Proceed in this way, until $f$ is defined everywhere on $[0,1]$ except for the middle-thirds Cantor set. The values of $f$ on those remaining Cantor set points are determined by the constraint that $f$ must be continuous. Also, $f\left(t\right)$ is a rational distance from $f\left(1\right)$ whenever $t$ is not in that Cantor set, that is to say, almost everywhere.

So now we have that the first trooper can instantly mark himself, by being a rational distance from the second trooper. So even if the second trooper wakes up while the first trooper is still moving, the first trooper manages to be a rational distance away with probability 1.

For this $n=2$ case, the rendezvous point will be the location of the second trooper to wake up. So overall, the first trooper wakes up, notices he is an irrational distance from the second trooper, and concludes he is the first to wake up. He makes a Minkowski-style movement to the location of the second trooper, and presses his detonation button once he gets there. The second trooper wakes up, notices that the first trooper is a rational distance away (this has probability 1, even if the first trooper is still in the process of moving), and concludes that his current location is the final destination. He presses his detonation button without moving anywhere.

Handling $n\ge 3$ is similar. The only tricky thing is that the first trooper must now mark not only himself, but the destination. He’ll mark the destination by choosing another trooper at random to be the destination, and moving to that trooper over the course of 1 second, always staying a rational distance away. Upon reaching the destination, he’ll press his detonation button, but continue moving without pausing, still always staying a rational distance away. He’ll stop moving at a position 1 unit north of the destination, after a total elapsed time of 2 seconds. He’ll mark himself, and distinguish himself from the destination by also staying at a distance of $\pi$ times a rational number from some randomly chosen third paratrooper (we’ll call this third trooper the “tail”). (In 2 dimensions, this kind of Minkowski movement where you stay a rational and $\pi$ times rational distance from 2 points is possible, details left as an exercise.) Anyone waking up and using their radar after the first trooper starts moving can tell (with probability 1) who is the first trooper, who is the destination, and who is the tail. The destination and tail have special instructions, everyone else will move towards the destination in a straight line at constant speed, press their detonation buttons as they pass over, and keep going in that direction at that speed afterwards. As for special instructions, the destination will press their button right away, and will never move. The tail will wait 2 seconds before moving, so he can be absolutely sure that the first trooper is 1 unit north of the destination. Then he will first move to the destination, making sure to stay $\pi$ times a rational distance from the first trooper. He passes through and presses his detonation button, and ends at a position $\pi +1$ units north of the destination.

[Ege Erdil]

I think this solution works and it uses a lot of the same ideas as the solution I had in mind.

Here is a way you can try to improve the solution: what if the motion of the paratroopers has to be smooth and their maximum speed is bounded by an absolute constant $K>0$?

[Throwaway2367]

Isn’t moving after reaching the destination superfluous? Everyone can see where to go as the radar gives position with multiplicity and with probability 1 there won’t be another pair on the same point.

[Ege Erdil]

For some solutions it is. I wanted to allow it anyway in case someone found a solution which requires it.

[Throwaway2367]

I get that, I am talking specifically about DaemonicSigil’s solution. I understand that you need to move to know who is the tail and the first trooper, but knowing who those are is not necessary to know the destination, so I’m wondering why they keep moving.

[Ege Erdil]

Ah, then yes, I think it’s superfluous.

[paulfchristiano]

Here is a kind of long solution that I think works (ETA: for the case $n=3$)

This was posted on our house puzzle slack before, it was one of the few problems that wasn’t solved though it didn’t get as much love as some of the harder problems.

I’d expect that a fairly large fraction of working mathematicians wouldn’t get it in 2 hours (and similarly for most of the hard Putnam problems) though I may be underestimating their ability to solve contest-like problems or it may have a simpler solution than this one.

Every paratrooper will use their radar as soon as they wake.

Suppose I see the points A, B, C. If ABC are collinear, then I’ll walk to the median paratrooper, detonate, and then stay in place. In particular, if two paratroopers are at the same location, then I walk towards that location and detonate.

Otherwise, we’ll assume that ABC has distinct edge lengths. (We’ll revisit this assumption and see if we can ensure it at the end.)

So suppose WLOG that the edge lengths are AB < BC < AC. We are going to try to end up at paratrooper A. I’m going to hold fixed the names A, B, C at this point, from my perspective.

Note that other paratroopers may assign the labels A, B, C differently. But we’ll guarantee that they don’t, by ensuring everyone takes paths that preserve the ordering AB < AC < BC until everyone is on the same line. (And that once everyone is on the same line, A is in between B and C, and everyone who has already used their radar is already trying to get to A. There are some more technicalities but I think this is fine.)

I’ll assign coordinates so that A is at (0, 0) and B is at (0, 1), and I’m at a location (x, y) with y > 0. Note that different paratroopers my assign coordinates differently depending on when they wake up.

If I am paratrooper A, I simply detonate and stay still.

If I am paratrooper C, I am going to first walk north 1 unit, then west 1 unit, then south until I reach the x-axis, then east to paratrooper A. Then I detonate and stand still. I’ll maintain a constant speed of 1 unit per hour over that whole path.

If I’m paratrooper B, I am going to move very quickly to paratrooper A’s position while preserving AB < AC < AC. Then I’ll detonate and stand still.

If C is at (x, y) with x < 0, then I just walk straight to A. It’s easy to see this maintains our invariant no matter how C moves. So assume that C is at (x, y) with x > 0.

Then I pick a path which is strictly outside of circle CA and strictly inside of AC (i.e. never touches the boundaries except at the endpoint of A). I think it’s easy to see that such a path exists but I don’t like geometry.

I then walk along this path extremely quickly. That is, I have an upper bound for the speed at which paratrooper C will ever walk (in 1 hour they will cover the max distance between me and paratrooper A), and I know that paratrooper A will never move at all as long as the rest of the scheme goes according to plan. That means there is a maximum speed at which the circles AC and CA can shift. Since my path was strictly in the interior, if I walk fast enough I can ensure that I remain in the safe region until possibly at the very end of my path.

To make the end of my path fine I just need to be careful about how I approach A. Fortunately, I know that if C is moving, it will either be north or west (since once it’s done moving west we’ll have x < 0). That means if I approach A while moving northwest, the last part of my trajectory will also be safe. This leads to a slightly more constrained geometry problem: I need a path from (1, 0) to (0, 0) that approaches (0, 0) from the southeast quadrant, while staying inside of AC and outside of CA. But this is still pretty easy.

Now we can check that everything works out, assuming my claims about geometry are OK:

• The initial configuration ABC is scalene with probability 1.

• We’ll maintain the invariant that either (i) AB < AC < BC, (ii) ABC are collinear with A in between B and C (with perhaps A and B coincident).

• Therefore paratrooper A will never move.

• Paratrooper C’s trajectory maintains this property until B wakes up.

• If paratrooper B wakes up while the points aren’t collinear, then they are able to walk a path that preserves the property no matter who C is moving, until A and B are on top of one another. After that point, we’ve won.

• If B wakes up while the points are collinear, they they just start walking towards A, which preserves the invariant.

This is kind of fiddly so I likely overlooked some things, but I’d be surprised if the basic idea didn’t work. It seems like we only need either (i) the waking times aren’t equal, or (ii) the paratroopers can randomize the timing of their radar use, (iii) the paratroopers can walk a short distance in a random direction before using their radar, (iv) the initial configuration isn’t an isosceles triangle. I’m very unclear on whether it’s possible to handle the case of equilateral triangles where multiple people can wake up simultaneously and we don’t have access to randomization, but I don’t see an impossibility proof.

[paulfchristiano]

Note on this solution (potential bug in the solution /​ problem statement, depending on exactly what you meant, this would also break the other proposed solution):

• I need to assume that either the points are in generic position or the wakeup times are unequal, which follows from them being continuous w.r.t. lebesgue measure, but it sounds like you are assuming a lower-bound on the probabilities rather than an upper bound. But I don’t see how “nonzero density everywhere” can possibly be useful: if there is a distribution of locations/​times for which the problem is impossible, then I could just take an equal mixture of that distribution and the uniform distribution, which would also guarantee a non-zero probability of failure (since it has a $1/2^6$ probability of drawing all quantities from the failure distribution) and also has non-zero density everywhere.

• My solution works if the paratroopers can randomly choose when to use their radar such that they have 0 probability of using it at the same time. In that case if I use my radar and see an isosceles triangle, I can immediately start moving to make it scalene (e.g. by walking very slowly for 1 second in an appropriate direction). No matter how close after me someone else wakes, they won’t see an isosceles triangle. So with this assumption we didn’t need any further restriction on the density of the paratroopers, in fact it seems like their locations can just be chosen adversarially. Not sure if you intended to allow this.

Small bug in solution that is easy to patch:

When charting paratrooper B’s path, I said that paratrooper C could only be walking north or west. This was needed for analyzing whether paratrooper B would potentially end up inside the circle AC no matter how fast they walk, which might cause paratrooper A to choose the wrong Schelling point if they wake up during that short interval. But if paratroooper C wakes up in the middle of paratrooper B’s path, they could end up walking at a different angle in the northeast quadrant. This is a flaw in the proof but very easy to fix, here are two options:

• Paratrooper B can ensure they always complete their path in <1 hour. And paratrooper C can stay still for 1 hour after using their radar. That ensures that if paratrooper C starts moving during paratrooper B’s path, they will be using stale information about paratrooper B’s location and will always start moving north.

• If paratrooper B stays strictly in the southeast quadrant, then paratrooper C will only ever be moving northeast, due north, northwest, or due west. So we could just have paratrooper B chart a path that approaches A along a circular arc tangent to the y-axis.

Overall this entire part of the proof is annoying but seems incredibly loose.

I would currently guess that the problem is solvable with adversarially chosen points /​ wakeup times, and with no access to randomization. But it’s very unclear and it involves a much more annoying argument.

[Ege Erdil]

Responding to the points in your note:

• The assumption that the densities are nonzero everywhere is supposed to rule out some kinds of solutions. The assumption of absolute continuity with respect to the Lebesgue measure is to make sure any event like “all three points forming an equilateral triangle” will be of null probability, while the nonzero density assumption is to make sure that the positions/​arrival times aren’t compactly supported.

  Without this assumption (and with the requirement of a maximum speed) there are alternative ways to solve the problem. For example, if the arrival times are compactly supported then in some solutions a “pivot player” around which everyone coordinates can determine some finite amount of time to wait before starting to move to ensure everyone else already used the radar and got his original position. There’s something similar with the original positions if we assume a speed limit on how fast people can move.

  In short, this is an assumption that’s meant to make the problem harder, not easier. I mention it explicitly so people don’t give solutions which work in the special case of when some distributions are compactly supported.

• The exact assumptions I mentioned in the problem are far from tight, and there are a variety of different solutions that work against adversaries of different capabilities. Any solution you end up finding will probably still work under more restrictive assumptions than the ones I outlined in the OP.

[Ege Erdil]

I didn’t sanity check this solution yet but it’s a very different idea from what I had in mind. Does it only work in the case $n=3$?

[paulfchristiano]

This solution only works for $n=3$. I think it’s probably possible to adapt it to $n>3$, but it’s clearly much more complicated and I suspect a different approach is easier.

Compared to DaemomicSigil’s solution, I think the main advantages in the $n=3$ case are:

My approach works for almost all configurations of initial points even if two people wake up simultaneously. It also works for adversarially chosen configurations of points as long as no two people wake up at the same time. So in that way it only uses one of the two assumptions instead of both of them.

It also works for noisy radars and constant movement speeds (I stated a version where people move arbitrarily fast, but it’s easy to just have paratrooper C move slowly enough that paratrooper B never needs to move at a speed >1 unit/​time), with the error probability dropping continuously to 0 as radar error goes to 0, instead of leaning hard on the infinite-precision assumption.

(ETA: actually this version checks whether ABC are exactly collinear so doesn’t quite work, but this is very nonessential and you could have an analogous solution where the paratroopers’ movements are continuous functions of their observations.)

[PatrikN]

For n = 3 you can exploit that the soldiers land on a circle for a neat solutions (meet at the soldier opposite to the longest circle segment walking along the arcs).

[paulfchristiano]

Oh man, that’s a way better solution. Seems like the same basic idea as mine (and converges to the same point), it just uses a super natural/​clean set of trajectories instead of a handwaving argument that they must exist. It seems like you can probably also generalize that to $n>3$.

[Ege Erdil]

What’s your idea for generalizing this to $n>3$? Seems nontrivial to me.

I would be interested if something like this ended up working for large $n$ because my solution leans very hard into the fact that the radar has infinite precision. I’ll post it in spoiler tags as a direct comment to the question so people can examine it, maybe it helps inspire some ideas.

[paulfchristiano]

Definitely doesn’t seem trivial to generalize, and I’m not sure if this is actually easier or harder than my solution.

It seems pretty interesting to find something that works for imprecise radar (in the sense that the error probability goes to 0 as radar error approaches 0).

Idea for $n=4$:

• Let AB be the closest together pair of points. Let AC be the second-shortest distance involving either A or B. Then we all decide to approach point A.

• If I’m not one of ABC, then I start by moving very far away from everyone else so that I won’t disrupt anything. Then I circle around until I get on the other side of A, and finally I approach A in such a way that I’m always closer to A than either B or C. This guarantees that A will remain the target point.

• Hopefully it’s also possible to define approaches for B and C that preserve the fact that A is the target:

• Point B would need to ensure that it’s always further than AC away from any non-A point, and that it’s always closer to A than the next-closest distance between a pair of points. So the valid region for B to walk in is a circle centered at A minus a bunch of circles centered at other points, and the question is whether those other circles can disconnect A and B

• Point C needs to ensure that it never gets within AB of any non-B point, so its valid region is the complement of a union of circles, and the question is whether it can be disconnected from A.

• I think I can use the same tricks from my original solution to avoid worrying about the possibility of multiple points moving at once. You still have to deal with the final instant of the trajectory just as before, which is another annoying geometry problem.

• I’m maybe 50-50 that this exact approach would work, but it feels like something will.

If I wanted to solve in general I’d probably just keep trying larger and larger $n$ and see if any general solution became clear.

Designating “one of the two points in the closest pair” breaks down immediately for $n=5$ since the target point could be surrounded from all sides by 3 other points, making it impossible for the 5th point to approach without messing up the target. My inclination would be to instead designate one of the vertices of the triangle with smallest max side length. (I.e. the one that is opposite the longest side fo that triangle). Then I think you are probably OK for $n=5$ but not larger $n$.

[PatrikN]

For n = 4 the following trick works, but does not really have the same flavor as the n = 3 case:

If the soldiers land in a convex position (they are the corners of a convex quadrilateral) then meet at the intersection of the straight lines connecting the opposite soldiers. If they land in a triangle with one soldier in the interior, meet at the soldier in the middle.

Here the soldiers are forced to walk in straight lines.

It would not surprise me if there are tricks like these for some more n, but I don’t see a general strategy. I think there is something you can do for odd n that is quite different from the other solutions so far, but I have not checked it fully yet and worked out what it requires from the radar.

[paulfchristiano]

Wait, can we just

move on a straight line to the geometric median of the n points, i.e. the point that minimizes the sum of the distances to all the paratroopers?

Suppose that X was previously the geometric median, with a total distance of k, and I walk 1 unit towards X. Then the total distance from all points to X is now (k-1). Suppose for a contradiction that some other point X’ is now the median, i.e. it has a total distance k’ < (k-1). But by the triangle inequality, the total distance from X’ to the old set of points is at most k’ + 1 < k, contradicting the fact that X was the old median.

This suggests that moving on a straight line to the median never changes the median. So everyone will always see the same median and end up there.

We have trouble if there are multiple medians, but for n > 2 that seems like it should happen with probability 0. (And indeed, for n = 2 I think it’s easy to prove that there is no continuous strategy that works with probability 1.)

ETA: for n = 3 this corresponds to moving to the Fermat point. For n = 4 it corresponds exactly to your solution though I didn’t know this until looking at the wikipedia page for geometric median. For n=3 on a circle it corresponds to your solution. I think this was a situation where examining small cases led very directly to the general answer.

[PatrikN]

That’s pretty cool, I wonder why I did not remember this concept.

[Ege Erdil]

I thought of this idea before but I believed there was a problem with it which I can’t immediately see now—probably having to do with something that happens when multiple people are moving at once. If I can figure out what the problem was I’ll let you know.

EDIT: Yeah, I can’t see what the problem with it is. I think I convinced myself for some reason that this invariance would break if multiple people were moving at once but it doesn’t, so I think this works.

[paulfchristiano]

Yeah, to make this explicit we can just apply the same argument over and over again to show that moving any set of points any distance towards the median preserves the median.

[paulfchristiano]

Now I feel silly again for having such an ugly solution.

I do feel like we can probably generalize the super ugly solutions: it seems like we have plenty of degrees of freedom and so the challenge is about how to compactly describe a strategy rather than coping with any fundamental difficulty.

(But of course there may be some fundamental obstruction that just isn’t obvious yet.)

[Ege Erdil]

By the way, as a bit of trivia about the problem: I don’t know who came up with it but the person who gave the problem to me said that there is a nice solution which works for all $n\ge 3$ and only fails when $n$ is even and everyone’s starting positions are collinear. I haven’t made much headway into finding such a solution yet.

I’m wondering how helpful it is to try cases with small $n$ and hope a general pattern is going to emerge instead of trying to find a solution from scratch that at least works for all sufficiently large $n$. It’s difficult to decide which you want to spend your time doing.

[paulfchristiano]

Oh, I think I just found that solution in parallel (or at least I found a solution with exactly the same failure condition). It was directly inspired by PatrikN’s solution. (Although I didn’t realize until after writing it that it is literally a generalization of PatrikN’s solution.)

[ESRogs]

Does the radar tell the paratroopers which other paratrooper is where, or just that there is some unknown paratrooper at each spot? In other words, are the paratroopers labeled on the radar?

[Ege Erdil]

They aren’t, otherwise the problem would be trivial since everyone could just agree on a person to be the target beforehand. I’ve edited the question to clear this up.

[ESRogs]

Gotcha, in that case:

Pick the paratrooper nearest to centroid of all paratroopers and go directly towards their location in a straight line.

As you move, the location of the centroid will change, but which paratrooper is nearest won’t change. This is because your contribution to the average distance to that paratrooper will decrease by at least as much as your contribution to the average distance to any other paratrooper (because you’re moving in a straight line towards them).

(For n equals two, you have to pick one of you to move and one to stay fixed ahead of time. For n is three or more, except for in measure zero cases, there will be exactly one paratrooper who is nearest to the centroid, with no ties.)

EDIT: Actually I think there’s a flaw in this, but I don’t see which part is wrong. The reason I think there’s a flaw is that 1) I think the centroid moves away from you as you move towards it, but 2) it seems like my argument about the delta in your contribution to the average distance to a point applies to the location of the centroid itself, in which case the location of the centroid shouldn’t move as you move towards it. So there’s a contradiction...

EDIT2: Oh, I see the flaw. The centroid moves away from you in your direction of travel. The magnitude of the decrease in average distance to the centroid is maximized along the line connecting you and the centroid, but it’s negative for points in between you two. So, if you move towards a point that point’s distance from the center of mass is actually increasing the most, not the least.

EDIT3: Wait, actually, I think we can rescue this. What if we ignore the centroid altogether, and just choose the paratrooper that has the lowest average distance to each of the other paratroopers. Then I think maybe my original line of reasoning works?

EDIT4: I figured out what I was missing here — when you move towards a point, it’s true that the average distance of that point to all other points is shrinking at least as much as for any other point, as I was saying above, except for yourself. You might be moving closer to multiple points, meaning that you might become the point with the least average distance to other points!

[Ege Erdil]

So a general bit of advice for this problem is that the solution I have in mind is not trivial at all—it involves plenty of cleverness to come up with and some careful accounting of all of the edge cases to prove that it works. My solution is most likely not the simplest possible but my suspicion is that no solution is going to be as simple as the ones people have proposed thus far.

If you think you have a simple solution, your solution is probably wrong.

[Ege Erdil]

Here is my solution:

For $n=2$ the solution is easy, as others have pointed out.

For $n\ge 3$, everyone executes the following algorithm (which works even if everyone has to move at a constant speed):

when you wake up:
    if (there exists a rational angle):
        let angle = ABC
        if you're B:
            press the button, then stand still
        else:
            walk towards B in a straight line
            press button at the point B
    else:
        let {B, C} be the pair of points with the shortest distance
        let B be the one with the larger distance from the center of mass of points outside {B, C}
        if you're B:
            press the button, then stand still
        if you're C:
            walk towards B in a straight line
            press button at the point B
            walk back an infinitesimal distance
        if neither:
            say you're A
            walk an infinitesimal distance to make angle ABC rational
            then walk towards B in a straight line
            press button at the point B
            walk back an infinitesimal distance

The idea is similar to DaemonicSigil’s, except I use rational angles to communicate information instead of rational distances. Since my motion trajectories are more regular (piecewise linear), I face the additional problem that someone can wake up and use their radar while the first person to wake up is moving some fixed distance $\epsilon$ to make some angle rational. To fix this, I have everyone coordinate on a point which with probability 1 won’t be affected by small perturbations of the configuration of points.

The rest is just working out the technical details to ensure that this solution always works. To implement it as a proper algorithm I also have to say how to calculate these infinitesimal distances depending on the configuration of points displayed by the radar, and essentially you need to pick $\epsilon$ small enough such that even if everyone moves by that distance, the following two are left invariant almost surely:

• The rank order relation of distances to the center of mass

• The pair of points with the smallest distance between them

There’s going to be such a valid choice of $\epsilon$ almost surely, so this solution works.

[Richard_Kennaway]

I’m not seeing what the time delays have to do with it, nor the probability distributions. Cannot they win with certainty (not just almost surely) by going to the average of all their positions?

[Ege Erdil]

If one person wakes up and starts to go to the center of mass, his movement will change the location of the center of mass. If another person wakes up afterwards and uses the radar, he’ll see the center of mass at a different location and this will break the coordination.

[Richard_Kennaway]

I see, that’s where the times come into it. They have no way of knowing when everyone has woken and used their radar.

[PatrikN]

Everyone uses the radar once they wake up. The two closest soldiers go towards each other on a straight line. Once they meet up and possibly wait for the other one to wake up they are free to visit all other soldiers in any order, when they are all together they can detonate. The important property is that the initial shortest distance is unique almost surely.

[Ege Erdil]

This doesn’t work (among other reasons) because the only way you have of finding out the position of the other paratroopers is to use the radar.

Suppose one of the two closest soldiers wakes up, uses his radar and heads towards the other paratrooper in the pair in a straight line. In the midst of this motion, suppose the other member of this pair also wakes up, uses his radar and executes the same strategy. Then they will fail to meet because the first paratrooper will be heading to the original position of the second, while the second will be heading towards some random point on the straight line joining them.

They won’t be able to tell if they’ve “met up” along the line because as I said the only way of getting any information about the position of the other paratroopers is by using the radar. Without it, you can’t even tell if you’re coincident (on the same point) with another paratrooper or not.

[PatrikN]

I see I should have read the instructions more carefully. I don’t quite understand all of your complaints though, if they can notice if they are on the same spot at the same time (they can’t I missed that) the strategy would work: the two soldiers would meet as they will not leave the line connecting them (walking towards some random point on it sure but still in the right direction)?

[oh54321]

Prove or disprove the existence of random variables X_n so that the expected value of X_n goes to infinity as n goes to infinity but X_n goes to 0 almost surely (maybe not as much of a problem, but a pretty useful thing to think about for people who use EV calculations to make decisions).

Find the number of ways to tile a 1000 by 1000 grid with white and black tiles so each tile is adjacent to exactly two tiles of the same color.

First is much easier than 2nd.

[Ege Erdil]

About the second problem:

I’ve determined computationally that for an $n\times n$ grid the number of tilings is $2^{n/2}$ if $n$ is even and $0$ if $n$ is odd, but I don’t have a proof of this fact yet. I’ll be looking for one—the answer looks quite nice so there ought to be a neat argument for seeing why it’s like this.

More precisely, it looks like the possible tilings correspond to the ways of tiling the first row of the grid with 2x1 white or black dominoes. It’s easy to see that the first row has to be of this form and that any such first row can’t correspond to more than one tiling of the grid, but showing that there is always a valid extension of the coloring to the whole grid seems to be the hard part.

[Measure]

Find the number of ways to tile a 1000 by 1000 grid with white and black tiles so each tile is adjacent to exactly two tiles of the same color.

The adjacency condition means that colored regions will form simple closed loops since ends and splits are disallowed. The smallest allowed region is a 2x2 tiles. The basic “textures” will be checkerboards of 2x2 regions and longer alternating stripes or concentric rings.

There are two ways to choose the color of the first corner tile at (1,1) position. The two tiles adjacent to the corner, (2,1) and (1,2) must match the corner. This covers the first two diagonals.

This gives another choice for the color of the (3,1) tile—it can either match the corner or not. Choosing this tile’s color constrains other tiles, specifically any tile (x,y) with x+y ⇐ 5 (the next two diagonals). The (4,1) tile must match the (3,1) tile, the (3,2) tile must be different from the corner, the (2,2) tile must be different from the (3,1) tile, etc. All colors will be symmetrical about the x=y diagonal.

Each additional choice constrains another two diagonals until the corner is reached, at which point the entire rest of the grid is constrained (it symmetrically matches the first half). For a 2Nx2N grid, this results in N choices before the entire grid is constrained or 2^n tilings (this extends even to the single degenerate tiling of the 0x0 grid).

For a 1000x1000 grid, there are 2^500 tilings satisfying the condition.

[Yair Halberstadt]

I can only find 4 tilings of the 6 by 6 grid:

110011
110011
001100
001100
110011
110011

And

111111
100001
101101
101101
100001
111111

As well as their inverses.

What am I missing?

[Measure]

111100  
100100  
100111  
111001  
001001  
001111  

This one, its rotation, and their inverses.

[Yair Halberstadt]

For the 2nd, does adjacent include diagonals?

[Measure]

If it does, I don’t think there are any valid tilings.

[deleted]

[oh54321]

My University has a problem sheet question that presents the first problem in a nice way that feels more real-worldy

[deleted]

[interstice]

Find the maximum cardinality of a set of disjoint figure-eights in the plane, and prove that it is the maximum.

Let a = 1/​n be the reciprocal of a positive integer n. Let A and B be two points of the plane such that the segment AB has length 1. Prove that every continuous curve joining A to B has a chord parallel to AB and of length a. Show that if a is not the reciprocal of an integer, then there is a continuous curve joining A to B which has no such chord of length a. [Source: Challenging Mathematical Problems with Elementary Solutions vol.2]

[Ege Erdil]

I forgot about this one. For the first problem:

You can get an injection from any collection of disjoint figure-eights on the plane to $Q^4$ by picking any rational point in the interior of each of the two circles making up the figure, so there can only be countably many such disjoint figures. This is an injection because if another figure-eight had the same rational points as its representative, then it’s easy to show that the two figures must intersect somewhere.

[Ege Erdil]

I don’t understand your first question. Can you clarify?

[interstice]

By a figure-eight I mean a curve consisting of two topological circles that meet at a single point, e.g. Then you want to find the maximal cardinality of a set of these, such that no two intersect. Obviously there can be at least countably many; the question is whether there can be more.

[Ege Erdil]

Ah, I understand. Thanks.

[Algon]

Let $\alpha$ be an ordinal s.t. $Card\left(\alpha \right)>Card\left(R\right)$. Let ${\alpha }^{\omega }$ be the cardinality of functions from $\omega$ to $\alpha$ . Is $Card\left(\alpha \right)={\alpha }^{\omega }$ ? If so, prove it.

[Ege Erdil]

Nice question. I’m providing my solution below, spoiler protected so people can attempt to solve the problem on their own.

By König’s theorem

$${\aleph }_{\omega }=\sum _{n\in \omega }{\aleph }_n<\prod _{n\in \omega }{\aleph }_{\omega }={\aleph }_{\omega }^{\omega }$$

so the answer is no. This is also the smallest counterexample that ZFC should be able to decide, since GCH is undecided in ZFC and if GCH is true then ${\aleph }_{\alpha }$ will have a base two logarithm for any successor ordinal $\alpha$ and any infinite $\kappa$ that has a base two logarithm will satisfy ${\kappa }^{\omega }=\kappa$.

[interstice]

Define a ribbon rile of length $n$ to be a 2D configuration of $n$ squares, constructed from a starting square by repeatedly adjoining a square above or to the right of the most recently added square. Prove that the number of tilings of a $n\times n$ square by length-$n$ ribbon tiles is $n!$

[Ege Erdil]

What do the following problems all have in common?

1. What’s the number of permutations in the symmetric group on $n$ letters $S_n$ without fixed points? What happens to the ratio of this number to the size of the group $|S_n|=n!$ as $n\to \infty$?

2. Suppose you draw $n$ samples with replacement from the set $S=\{1,2,3,\dots ,n-1,n\}$ uniformly at random. Say the set of all elements you get is $A$, where we don’t distinguish between two draws of the same element. What’s $E[|S-A|]$, i.e. the expected value of the cardinality of the set difference $S-A$? What happens to $E[|S-A|]/n$ as $n\to \infty$?

3. Two players A and B play the following zero-sum game: they take turns sampling from a probability distribution on the real numbers $R$ with a continuous probability density function. The first player to draw a value that’s smaller than the maximum of all previous values drawn by both players loses. If A goes first, what’s the probability that B wins the game?

   Shoutout to Jane Street for this problem!

4. The secretary problem: there’s a totally ordered finite set $S$ with distinct elements. You know the cardinality $n$ of $S$. You play the following single-player game: you get to sample one element at a time from $S$ without replacement and uniformly at random. At any point you may choose to stop sampling and keep the last element you’ve sampled. You win if you halt on the maximum element of $S$ and lose otherwise.

   For $n$ large, what’s the strategy that maximizes the chance of victory in this game? What’s the probability of victory achieved by the optimal strategy?

[acgt]

The answer to all of them is 1/​e?

[Ege Erdil]

That’s right :)

There’s a type of problem that is recognizably a “1/​e problem”, in the sense that you expect the answer will somehow involve 1/​e, but I haven’t been able to make this intuition precise. What properties about a problem make it likely that 1/​e shows up?

Some of the above problems involve use of the inclusion-exclusion principle, which is a typical way 1/​e can show up in these problems, but e.g. the secretary problem does not.

[deleted]

[Ege Erdil]

Consider the following game: there are $N$ players standing in a row, each with a tower of countably infinitely many red or blue hats on top of their heads. The probability of any hat being red is $1/2$ and likewise for any hat being blue, and the colors of the hats are jointly independent. Each player can see all of the hats on the heads of everyone other than themselves but they can’t see any of their own hats.

To win the game, the players must all simultaneously guess a natural number (the number can be different for different players) and ensure that all of the hats on their own heads in the position they named from the bottom of the tower are red. For example, if three players are in the game and their guesses are $1,5,13$, then they win if the first hat from the bottom on player 1′s head, the fifth hat from the bottom on player 2′s head and the thirteenth hat from the bottom on player 3′s head are all red. If even one of them is blue, then they lose.

The players can all agree on a strategy to execute as a group beforehand, but can’t communicate with each other once the game begins.

Prove that there is a strategy with which the players can win with probability $\Theta \left(1/\log N\right)$.

[Ege Erdil]

Let $S$ be the set of integers $n\ge 2$ such that all groups with a proper subgroup of index $n$ also have a proper subgroup of index strictly less than $n$.

Give an explicit description of $S$.

[Yair Halberstadt]

Show there are no integer solution to $a^n+b^n=c^n$ for $n\ge 3.$

An excellent solution should take slightly more space than this comment ( ͡° ͜ʖ ͡°).

[Pattern]

A good mathematician who hasn’t seen the problem before should take anywhere from 30 minutes to 2 hours to solve it.

I wouldn’t have necessarily characterized that as

the best elementary math problems you know?

[Ege Erdil]

That’s fair, though I’m not sure what else to put in the title in this case. It’s necessarily going to be a compressed version of what I’m actually asking for.

[Pattern]

• A good mathematician who hasn’t seen the problem before should take anywhere from 30 minutes to 2 hours to solve it.

• The solution should only involve undergraduate level maths. Difficult Putnam problems are a good benchmark for what kind of maths background should be required to solve the problems. The background required can be much less than this, but it shouldn’t be more.

• For whatever reason you think the problem should be more widely known. The reason is completely up to you: the solution might include some insight which you find useful, it might be particularly elegant, it might involve some surprising elements that you wouldn’t expect to appear in the context of the problem, et cetera.

• It’s fine if the problem is well known, your examples don’t have to be original or obscure.

‘Good 0.5-2 hour undergraduate problems you think should be more widely known.’

Overall, the tricky thing about it is finding a problem that meets all those requirements.

https://​​www.lesswrong.com/​​posts/​​R82zuc4MZXvG2dJXY/​​if-your-solution-doesn-t-work-make-it-work

This has a good problem, that might take awhile if you’re not familiar with linear algebra. It might or might not be useful to spreading basic understanding of linear algebra, or what (some of) that is about.

Is this good mathematician an undergrad?

The background required can be much less than this, but it shouldn’t be more.

I didn’t read this the first time through, and I think it suggests me posting the above link here, even if it doesn’t take long enough.

[Yair Halberstadt]

This has a good problem, that might take awhile if you’re not familiar with linear algebra

The problem is very simple without linear algebra—just notice that relative parities are preserved (i.e. if there are an even number of reds and an odd number of blacks, then after any sequence of moves they will always have opposite parities).

The given solution is to highlight a strategy, not the easiest way to solve the problem.