Coin Flips and Dice Rolls

Trivial Cases
We want to simulate an $n$-sided die by flipping a biased coin. Our goal is to simultaneously minimize the number of coins and flips. If $n=1$ we don't need any flips. If $n=2^k$ we only need to flip a fair coin $\log n$ times.


Using 1 Coin
Interestingly, you can simulate an $n$-sided die using only 1 coin and $\,3 \log n\,$ flips. The only caveat is that I can't give you the bias of the coin explicitly. Suppose we have a coin with bias $b$. We have $n$ numbered bins and we want to map each individual sequence of $f$ flips to a bin such that each bin has probability $1/n$. There are ${f \choose k}$ sequences that have $k$ heads. For each $k$, we map $\left\lfloor {f \choose k}(n-1)^{-1} \right\rfloor$ of these to the first $n-1$ bins, and put the remainder in the last bin. By construction, the first $n-1$ bins have the same probability, so it remains to show that the last bin is filled to $1/n$. Let $R(b)$ be the probability of the last bin. Then
$$
\begin{align}
R(b) &= \sum_{k=0}^f r_k \; b^k \; (1-b)^{f-k} \\ & \\
r_k &= \small{{f \choose k} \;\; (\text{mod } n-1)}
\end{align}
$$
We have $\,R(0) = 1\,$ and if we take $f$ large enough such that $\,R(1/2)<1/n$, then by continuity and the intermediate value theorem there must be a $b'$ such that $\,R(b') = 1/n$. Noting the bound $\,R(1/2) < 2^{-f} f n\,$ we find that $\,f-\log f > 2 \log n\,$ implies $\,R(1/2) < 1/n$. Choosing $\,f = 3\log n\,$ satisfies the inequality and we are done.

We can make this prettier if we don't care about minimizing $f$. Suppose $n$ is one more than an odd prime and let $f=n-1$. Then there are no remainders since $n-1 \choose k$ is always a multiple of $n-1$. Thus $R(b) = b^{n-1} + (1-b)^{n-1}$ which clearly has a solution $R(b) = 1/n$. For cases where $n$ is not one more than an odd prime, use Dirichlet's Theorem to get a multiple of $n$ that is.



Using 2 Coins
The best I can do with two coins is $\sim 2\log n$ flips. Let one coin be fair and one coin have bias $1/n$. Let $f$ be such that $2^f \geq (n-1)^2$. Flip the fair coin $f$ times and the $1/n$ coin once. There are $2^{f+1}$ total outcomes, half of which have probability $\tfrac{1}{ 2^fn}$ and the other half have probability $\tfrac{n-1}{2^f n}$. Label the former $L$ and the latter $H$. We want to group these outcomes into bins of probability $\tfrac{2^f}{2^fn}$.

Add as many $H$ outcomes as possible to the first bin and denote the number $h_1 \geq n-1$. Fill the remainder with $t_1 < n-1 $ of the $T$ outcomes. Repeat for the next bin, and then the next, and so on. Because $h_i>t_i$, we run out of $H$ outcomes first and can fill the remaining bins with $L$ outcomes.



Remarks
A few more interesting observations. Let $F(n)$ be the minimum number of flips needed using a mutable coin (you can change the bias every flip). If $n=ab$, then we can "roll" an $a$ and $b$-sided die and take the result $b (r_a -1) + r_b$. Also, if $n = a+b$, then we flip an $a/n$-biased coin and then roll either an $a$ or $b$-sided die depending on whether the coin flip came up heads or tails. So we get the recurrence relations

$$ \begin{align}
F(ab) &\leq F(a) + F(b) \\ \; \\
F(a+b) &\leq 1 + \text{max}\{F(a), F(b)\} \\
\end{align}
$$

The second relation let's us simulate an $n=2^k + 2^{\ell}_{(k > \ell)}$-sided die using 2 coins and $k+1$ flips.


_________________________________________________________________________________

Counting Trees with Subtrees

Suppose we want to count the number of binary trees that contain exactly $k$ distinct subtrees. A recent Stack Exchange thread asked this question and with the help of two other users I wrote a post describing a few methods of enumeration (see link). We submitted the sequence to OEIS and it was just recently approved.


_________________________________________________________________________________

The Four Color Theorem

The four color theorem states that no more than four colors are required to color the countries of a map so that no two adjacent countries share the same color. To gain an intuition for why this is true, lets try to construct a counterexample

                              

In the left picture we have four countries Red, Blue, Yellow, and Black. We must add the fifth country Green such that all countries touch all other countries. However, we notice that if Green is adjacent to Red, Blue and Yellow, then no matter how we draw it, it encloses a country thereby disconnecting it from Black. An example is shown in the picture on the right where Yellow becomes disconnected from Black (and so you can color them the same color). This seems like it would be an easy theorem to prove using some sort of topological argument, however the only known proofs rely on the aid of a computer. The Supreme Fascist remains unforthcoming.


If you construct a graph by turning each face into a vertex you can rephrase the four color theorem as a statement of vertex colorings of planar graphs. For a graph to be 4-colorable, it is certainly necessary that it not contain a $K_5$ subgraph. But is this condition sufficient? The answer is no, and here is a counterexample

This graph has a chromatic number of 5 but it does not have a $K_5$ subgraph. It also does not contain a subdivision of $K_5$, so it also serves as a counterexample to Hajós' conjecture (first disproved by Catlin in 1979). On the other hand, by contracting both red--pink edges we find that $K_5$ is a minor of this graph, so Hadwiger's conjecture still stands.

_________________________________________________________________________________

Real Root Isolation of Polynomials

Let's first list a few properties about polynomials. Given a polynomial \[    f(x) = \alpha_0 + \alpha_1 x + ... + \alpha_n x^n    \]

the Fundamental Theorem of Algebra tells us that there are $n$ complex roots (counted with multiplicity). A root $r$ has multiplicity $k$ if $f(r) = f'(r) = ... = f^{(k)}(r) = 0 \neq f^{(k+1)}(r)$. A root is simple if it has multiplicity one and a polynomial is square-free if all of its roots are simple. The complex roots must come in conjugate pairs and any rational roots must be of the form (factor of $a_0$) / (factor of $a_n$). Also, the ratio $(-1)^k \alpha_{n-k}/\alpha_n$ gives the sum of the products of all $k$-combinations of roots. Lastly, a result of Cauchy is that the magnitude of any root is bounded by $M = 1 +\max \left| a_i/a_n \right|$.

These properties as well as Descartes' rule of signs (stated below) and synthetic division can all be used to find the roots of a polynomial. Other methods include Newton's, Bisection, Secant, Regula Falsi, etc. Below describes two subdivision methods for isolating all the real roots of a square-free polynomial with real coefficients. They work by determining whether an interval contains zero roots, one root, or multiple roots, and then respectively discarding, storing, or subdividing the interval. The methods can be generalized but not without some effort.

Box Method and code

Descartes' Method


_________________________________________________________________________________

Pólya Enumeration

Pólya Counting enables you to count the equivalence classes of group acting on a set. For example, you might want to find the number of ways to color the corners of a square red or blue, respective of symmetry. The permutation group of symmetries is the dihedral group $D_4$. Pólya Counting gives the generating function $$P_{D_4}(r+b,r^2+b^2,r^3+b^3,r^4+b^4) =  r^4 +r^3b + 2r^2b^2 + rb^3 + b^4$$ where the coefficient in front of $r^pb^q$ tells you the number of nonequivalent colorings given that $p$ corners are colored red and $q$ are colored blue. Thus, the total number is of colorings is 6.

This method can be easily applied to PE 281: Pizza Toppings. It can also be used to count the number of non-isomorphic graphs. [code]

I've Tex'd up some notes for my own reference that are accessible in the link below. The proof is only outlined so it is a bit terse but the example problems should be enough to show how the method is used. Polya Counting Notes


_________________________________________________________________________________

Puzzler - Egg Drop

You are given two identical eggs and access to a 100-story building. You want to determine the highest floor from which an egg will not break when dropped. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.

If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.

The question is: What strategy should you adopt to minimize the number egg drops it takes to find the solution? (And what is the worst case for the number of drops it will take?)

Solution: Suppose we start by dropping the first egg from floor 50 and it breaks. The only way to determine the correct floor is to then start with floor 1, then 2, 3, ... until our second egg breaks. If the highest floor is 49 then we get 50 total egg drops -- far from optimal. Generalizing, if our first drop is from floor n and the egg breaks, then in the worst case we require n total egg drops. We know that the solution is between 1 and n-1 inclusive. On the other hand, if the egg does not break, we know the solution is between n+1 and 100. Within this range we can use the same technique but instead drop from n-1 floors above floor n. If the egg then breaks, then in the worst case we still total n egg drops. If it doesn't break we continue by taking our third drop to be n-2 floors above the second drop, and so on.. So assuming the first egg does not break, our successive drops are n, 2n-1, 3n-3, 4n-6, ..., n(n+1)/2. -- given by n, n+(n-1), n+(n-1)+(n-2), ..., n+...+1. When the egg finally does break on the kth drop, we drop the second egg incrementally from the floor of the (k-1)th drop up to the floor of the kth drop and in the worst case we get n total drops. Now we simply need to minimize n, which is done by taking the smallest integer n such that n(n+1)/2 > 99. Our solution is thus 14 total drops.

_________________________________________________________________________________

Puzzler - Prisoners and Lightbulbs

There are 100 prisoners in solitary confinement. There's a central living room with one light bulb that is  initially off. No prisoner can see the light bulb from his or her own cell. Everyday, the warden picks a prisoner at random to visit the living room. While there, the prisoner can toggle the bulb if he or she wishes. The prisoner also has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is false, all 100 prisoners are shot. However, if it is indeed true, all prisoners are set free. So the assertion should only be made if the prisoner is 100% certain of its validity. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?

Solution: Here is one sub-optimal solution: Suppose each of the prisoners are assigned a different number from 0-99. Each day is taken modulo 100 and if the prisoner is assigned the same number as the day he turns the light on (or keeps it on) and otherwise he turns the light off (or keeps it off). Whenever a prisoner is called to the room and sees that the light is on, he makes note that the previous days' prisoner has been to the room. Once any of the prisoners has tallied every other prisoner being in the room, he can declare so and they will be set free. For example, say prisoner 50 is called to the room on day 134=34 (mod 100) and sees that the light is on. He concludes that prisoner 33 was in the room the previous day and then proceeds to turn the light off.

There is a simple way to alter this solution to make it way better -- the expected wait goes from ~10,000 to ~1,500 days. Can you think of it?

_________________________________________________________________________________