Suppose you throw the 1/*n* coin once and then the fair coin *k*
times. This action divides the probability space to 2^{k} pieces
of probability 1/2^{k}*n* and 2^{k} pieces of
probability (*n*-1)/2^{k}*n*. Let us refer to the
former as *A*-type pieces and the latter as *B*-type pieces.
The question is: can these pieces be joined together in order to form *n*
pieces of total probability 1/*n* each?

We can, for example, take *a* of the *A*-type pieces
and *b* of the *B*-type pieces to form the first slice. For this
to work, we need to have *a*+(*n*-1)*b*=2^{k}.
For example, we can have *b*=2^{k} div (*n*-1) and
*a*=2^{k} mod (*n*-1). Let's call that the
*canonical* (*a*,*b*) combination. There are no solutions that
use a smaller *a* value than the canonical combination, but decreasing
*b* is always possible, given a large-enough supply of *A*-type
pieces: to reduce *b* by one, we compensate by increasing *a* by
*n*-1.

Suppose, now, that we try to map as many of the *n* target pieces as
possible with the canonical (*a*,*b*) combination.
If nothing stops us then we are done, but if something does stop us, it will
be that we've run out of either enough *A*-types or enough *B*-types.
As we have seen, running out of *B*-types is not a problem, as we can
always tile the probability space with less of them (including with
*none* of them) by replacing them with the appropriate number of
*A*-types. Running out of *A*s, however, is something we'd like to
avoid.

The solution is to make sure that *a*≤*b*. As we have started with
an equal number of *A*-types and *B*-types, choosing an
(*a*,*b*) combination that uses at least as many of the *B*-types
as of the *A*-types
guarantees us that *A*-types will not run out first.

If we are able to find an (*a*,*b*) combination with
*a*≤*b*, the problem is solved:
we begin by creating slices with our chosen
combination until *B*-types run out. From that point on, we make up
the missing *B*-types by replacing them with the appropriate number of
*A*-types. Because all our pieces have probabilities that sum up to 1,
the number of *A*-types will clearly be exactly enough to complete the
last piece.

We are now left with the question of how to ensure *a*≤*b*.
Recall that in the canonical combination we have chosen *a* to be
2^{k} mod (*n*-1).
For this reason we are guaranteed *a*<*n*-1. By choosing a large
enough *k* -- such as a *k* value for which
2^{k}≥(*n*-1)^{2} -- we have that our *b* value,
namely 2^{k} div (*n*-1), satisfies
*b*≥*n*-1. Therefore, *b*≥*a* as required, and we
are done.

Q.E.D.