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

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.

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

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

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. 

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]

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.

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

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?

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

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