Given \(n\), find the largest possible size of a set \(A\) of integers such that any subset of \(n\) elements of \(A\) has sum not multiple of \(n\)

\(2n-2\), this is the ErdÃ¶s-Ginzburg-Ziv theorem

Find the polynomial in \(x\) for \(\sum_{k=1}^x k^n\).

$$\sum_{k=1}^{n+1} \frac{n!}{k!}B(n+1-k)x^k$$ where \(B\) has generating function \(\frac x {1-e^{-x}}\)

In how many ways can 2n+3 people play a round robin with everyone getting n matches of rest between the ones they participate?

1, plus permutations and inversion. You can only get n or n+1 matches of rest, and when you change that after a round it forces many decisions to avoid repeating matches, so much that there are very few matches where that can happen (or it would make someone play too much). Namely, only the first or the last player switches every time, and everyone else only switches after playing him

There's a circular pool, one person swimming inside and another that can't swim on the border trying to catch the swimmer. How fast must the swimmer be to barely escape?

Move to the border of the \(\frac 1 v\) radius inner circle while keeping the runner opposite, then follow a tangent to this inner circle

A blind tazmanian devil can reach any speed he wants. He knows there's a pig in a confined square, that can't move faster than a given speed. How can he capture the pig, if both are just points?

If the speed was 0, the solution would be a Hilbert Square or similar. Just define it recursively, and then introduce the pig's possibility of movement (just expands each square a bit). Cantor set may help with connecting intervals of time.

(Source: Gugu)

(Source: Gugu)

You have a biased coin, but you don't know how biased it is. The only thing you can do with it is to throw it and get heads or tails. What's the most efficient way of extracting one unbiased bit from that?

int unbiasedToss(Coin c) {
int heads=0, tails=0;
int toss;
do {
toss = c.toss();
heads += toss;
tails += 1 - toss;
} while (heads + tails == heads ^ tails);
return toss;
}

This is optimal because we must pair up runs with the same amounts of heads and tails (only different by order), which can be nicely modeled with the Pascal Triangle. Glancing at it mod 2 shows it's optimal, pairing all possibilities.
Mathematically solve this game: two players on a black and white finite grid, a move is to choose a rectangle with bottom right cell white and swap the color of all it's cells, the player that can't move loses (so the player who flips the last white cell wins)

Nim Product

Is there a biased coin that allows you to make a 3-way decision based on a finite amount of its flips?

Leaving HHHH and TTTT to one decision, HT, HHHT, and TTH to the second and HHT, TH and TTTH to the third allows a 0.242 - 0.758 coin to work.

Solve the following sokoban puzzle:

####### #. . .# # $$$ # #.$@$.# # $$$ # #. . .# #######

$ $ $ $$$ $ $ $ $ $ $ -> $ $ -> $$$ $ $ $ $ $ $ $

An observation wheel of N gondolas gets filled without queueing or exiting. The N clients arrive at completely random times, and pay N minus the number of occupied gondolas they had to wait. What's the average profit?

Mathematically solve this variation of Price is Right: both participants have the same range information (0,1), and choose the price simultaneously, and the price is completely random. The payoff is the chance you get the item. What probability distribution should you use to have a Nash Equilibrium? (So if you bid x and the opponent y with x < y you have payoff 2y-x-1)

If you have a uniformly random variable x from 0 to 1, play \(1-\frac 1{(2-x)^2}\), which gives a density of \(\frac{(1-x)^{-\frac 3 2}} 2\) for \(x < \frac 3 4\)

Mathematically solve any two player zero sum game without perfect information

Same linear programming as with perfect information, but instead of finding probabilities of strategies restricted to sum 1, find probabilities of choice sequences, ignoring the other player and chance. This needs more restrictions: considering the tree of your view (with that ignoring), if it's your node you sum all children, if it's not you're restricted to all children must have the same probability and so the node itself will have that one too, and finally the root must have probability 1

(Source: "Fast Algorithms for Finding Randomized Strategies in Game Trees", by Koller et al.)

(Source: "Fast Algorithms for Finding Randomized Strategies in Game Trees", by Koller et al.)

(>>=) = (.) (flip (.) flip) (.)

Continuation monad