What are the best elementary math problems you know?

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.

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.

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.

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.

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 [LW · GW]'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.

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?

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.

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.

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.

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.

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