induction - Book Proofs

How many times can you add up the digits?

This week’s Fiddler is a puzzle about adding digits over and over again.

For any positive, base-10 integer $n$, define $f(n)$ as the number of times you have to add up its digits until you get a one-digit number. For example, $f(23) = 1$ because $2+3 = 5$, a one-digit number. Meanwhile, $f(888) = 2$, since $8+8+8 = 24$, a two-digit number, and then adding up those digits gives you $2+4 = 6$, a one-digit number. Find the smallest whole number $n$ such that $f(n) = 4$.

Extra Credit: For how many whole numbers $n$ between $1$ and $10,000$ does $f(n) = 3$?

My solution:
[Show Solution]

Let $a_n$ be the smallest integer $n$ such that $f(a_n) = n$. We can calculate the first few values manually.

$a_1 = 10$. This must be the case since every one-digit number has $f(n)=0$, and $10$ is the smallest two-digit number and $f(10)=1$.
$a_2 = 19$. We seek the smallest number such that the sum of its digits needs to be summed once more to get to a one-digit number. In other words, we want the smallest number whose digits sum to $10$. This requires at least two digits and can be done in two ways ($19$ and $91$). Using more than two digits leads to larger numbers so we can exclude these possibilities.
$a_3 = 199$. Now, we seek the smallest number whose digits sum to $19$. This is impossible with two digits (smallest sum is $9+9=18$), so we try with three. This can be done with a $1$ as the first digit ($1+9+9$), so this must be the answer.

The pattern is now clear. For all $n\geq 1$, $a_{n+1}$ is the smallest integer whose digits sum to $a_n$. Based on the pattern, let’s suppose that
\[
a_n = 1\,\underbrace{9\,9\,\cdots\,9}_{k_n\text{ times}}
\qquad\text{for }n=2,3,\dots
\]where $k_2=1$ and $k_3=2$. Now $a_{n+1}$ is the smallest number whose digits sum to $a_n$. How many digits must $a_n$ have? Rewrite $a_n$ in a particular way:
\begin{align}
a_n &= 1\,\underbrace{9\,9\,\cdots\,9}_{k_n\text{ times}}\\
&= 2\cdot 10^{k_n}-1 \\
&= 2\left( 10^{k_n}-1\right)+1 \\
&= 2\cdot 9\cdot \left( \frac{10^{k_n}-1}{10-1}\right)+1\\
&= 2\cdot 9\cdot \left( 1+10+10^2+\cdots+10^{k_n-1}\right) +1 \\
&= 9 \cdot \bigl(\, \underbrace{2\,2\,\cdots\,2}_{k_n\text{ times}}\,\bigr) + 1
\end{align}where we used the formula for a finite geometric series in the third step. Based on this representation, it is clear that $a_{n+1}$ requires more than $\underbrace{2\,2\,\cdots\,2}_{k_n\text{ times}}$ digits, since even if we made all the digits $9$ it would not be enough. W should add the extra $+1$ digit at the front of the number to get the smallest number possible. This leads to:
\[
a_{n+1} = 1\underbrace{9\,9\,\cdots\,9}_{\underbrace{2\,2\,\cdots\,2}_{k_n\text{ times}}\text{ times}}
\]So $a_{n+1}$ is of the same form as $a_n$, and we find:
\[
k_{n+1} = \underbrace{2\,2\,\cdots\,2}_{k_n\text{ times}}\qquad\text{for }k=2,3,\dots.
\]So although the sequence $f(n)$ seemed to grow at a moderate pace, for $n=0,1,2,3$, we find that
\[
f(4) = 19,\!999,\!999,\!999,\!999,\!999,\!999,\!999
\]That escalated quickly!

In general, we can write the full recursion as:
\begin{align}
a_1 &= 10,\\
a_2 &= 19,\\
a_{n+1} &= 2\cdot 10^{(a_n-1)/9}-1\qquad\text{for }n=2,3,\dots
\end{align}

Extra credit

The most straightforward way to count how many $n$ between $1$ and $10,\!000$ satisfy $f(n)=3$ is to write a short script. Here is a two-line script in Julia that does the job:

f(n) = n < 10 ? 0 : 1 + f(sum(digits(n)))
length( [n for n in 1:10000 if f(n) == 3] )

and the answer is 945.

Sniff out the spies

This interesting problem appeared on the Riddler blog. Here it goes:

There are N agents and K of them are spies. Your job is to identify all the spies. You can send a given number of agents to a “retreat” on a remote island. If all K spies are present at the retreat, they will meet to strategize. If even one spy is missing, this spy meeting will not take place. The only information you get from a retreat is whether or not the spy meeting happened. You can send as many agents as you like to the retreat, and the retreat can happen as many times as needed. You know the values of N and K.

What’s the minimum number of retreats needed to guarantee you can identify all K spies? If each retreat costs \$1,000 per person, what is the total cost to identify all K spies?

To begin with, let’s assume you know that N = 1,024 and K = 17.

Here is my solution for $K=1$:
[Show Solution]

The case $k=1$

Let’s warm up with the simple case $k=1$. We’ll call $r_1(n)$ the minimum number of retreats needed to identify a single spy in a group of $n$ agents. If we choose to send $m$ of the $n$ agents on a retreat, then either a meeting took place, which means the spy is among those $m$, or no meeting took place, so the spy must be among the $n-m$ that didn’t go on the retreat. Depending on the result, we’ll either need $r_1(m)$ or $r_1(n-m)$ more retreats. We can therefore write this little (dynamic programming) recursion:
\begin{align}
r_1(1) &= 0 \\
r_1(n) &= \underset{m\in\{1,\dots,n-1\}}{\text{minimize}}\,\, 1+\text{max}\{ r_1(m), r_1(n-m) \}
\qquad\text{for }n=2,3,\dots
\end{align}The reason for the “max” is that we want a guarantee that this number of retreats will always find the spy. Therefore, we assume the spy is wherever they need to be so that it takes as long as possible to find them. From here, it’s clear that we should always split in half. Therefore,
\begin{align}
r_1(1) = 0\quad\text{and}\quad r_1(n) = 1 + r_1\bigl(\lceil \tfrac{n}{2} \rceil\bigr)
\quad\text{for }n=2,3,\dots
\end{align}Where $\lceil x \rceil$ means that we round $x$ up to the nearest integer. By inspection, we can solve this recursion and we find that:

$\displaystyle
\text{number of retreats} = r_1(n) = \lceil \log_2(n) \rceil
$

What about the cost? We can simply count the total number of retreat attendees, which we’ll call $a_1(n)$. When we split $n$ in half, we can choose to send either $\lceil \tfrac{n}{2} \rceil$ or $\lfloor \tfrac{n}{2} \rfloor$ (round up or round down) to the retreat. Both give us the same information, so we’ll choose to send fewer agents. The number of attendees therefore satisfies:
\begin{align}
a_1(1) = 0\quad\text{and}\quad a_1(n) = \lfloor \tfrac{n}{2} \rfloor + a_1\bigl(\lceil \tfrac{n}{2} \rceil\bigr)
\quad\text{for }n=2,3,\dots
\end{align}Again, by inspection, we find that the number of attendees is:

$\displaystyle
\text{number of attendees} = a_1(n) = n-1
$

Note that we could have achieved the same total cost by sending the agents one-by-one on individual retreats. By the time we’ve sent all but one agent, we must know who the spy is. However, we were asked to minimize the number of retreats, so it would be wasteful to have this many retreats.

And here is a partial solution for $K \gt 1$:
[Show Solution]

The case $k\gt 1$

The case $k=1$ was all about finding one spy. There were $n$ possibilities (each of the $n$ agents could be the spy) and each time we had a retreat, we received one bit of information (yes/no). The best we could do was use that bit to cut our possibilities by a factor of two, and this was achievable by sending half of the agents on the retreat each time.

If $k \gt 1$, we are tasked with finding $k$ spies, and there are now $\binom{n}{k}$ possibilities (choosing $k$ spies out of $n$ agents). Again, the logic is the same: the best we can hope for with one bit of information is to reduce the possibilities by a factor of two. If we call $r_k(n)$ the minimum number of retreats required to identify the spies with certainty, then this argument yields the bound:

$\displaystyle
\text{number of retreats} = r_k(n) \ge \left\lceil \log_2\binom{n}{k} \right\rceil
$

If $n=1024$ and $k=17$, this yields the bound $r_{17}(1024) \ge 122$. The question then becomes: how close can we actually come to reaching this bound? One possible approach is to be greedy: we keep track of all possible remaining subsets, then we consider all possible retreat arrangements and use the one that reduces the number of remaining subsets by as much as possible (which can never be more than than a factor of two). We continue in this fashion until we have reduced the number of possible subsets to one, and that must be our set of spies.

While this greedy approach would likely be optimal, it’s computationally intractable. There are $\binom{1024}{17} \approx 3.68\times 10^{34}$ possible subsets of spies and there are $2^{1024} \approx 1.8\times 10^{308}$ possible retreats we could arrange at every step. So there is no hope of computing the optimal greedy strategy and seeing how well it performs compared to our lower bound.

We can think of this as a game, where I’m trying to guess the spies and the adversary is trying to arrange the spies such that it’s as difficult as possible for me to guess. So this becomes a philosophical question: if I pick a split such that there is a slight advantage for my adversary to say “yes, there was a meeting”, then as long as they keep saying “yes”, the solution is recursive and easily computable. But if my adversary knows that the problem gets very hard whenever they say “no, there was no meeting”, they they might just do something “suboptimal” with the goal of running me out of memory.

Suboptimal heuristic

The greedy heuristic seems out of reach, so here is another heuristic, which was truly a team effort — discussions with my colleague Alberto Del Pia, comments on this post by Jim Crimmins, Adam, and Jason Weisman, as well as a little bit of effort on my end. The idea is to split the $n$ agents into $m$ groups of roughly equal size, where $k+1 \le m \le n$. Let’s number the groups $1,\dots,m$. Here is the plan:

Take
Group 1 stays home, all other groups go on a retreat.
- If there was a meeting, then Group 1 has no spies in it.
- If there was no meeting, then Group 1 has at least one spy in it.
Return to step 1, but this time, Group 2 stays home and all other groups go on a retreat.
Keep going in this fashion until we have identified all groups with at least one spy in them. There can be at most $k$ such groups. Merge these groups (this becomes our new $n$), discard all other groups, and repeat the entire process with the new smaller group: picking $m$, dividing into groups, etc.

Note that we do not need to try all $m$ possible retreats in each round! As soon as there are $k$ retreats with “no meeting”, then we can stop and immediately proceed to the next round, since we now know which $k$ groups contain spies. In the worst case, this won’t happen. We will always be forced to have as many retreats as possible. By the time we have done $m-1$ retreats, two things can happen:

We have identified $k$ spies, in which case we can carry over our $k$ spy-containing groups to the next round immediately.
We have identified $k-1$ spies, in which case we can just carry over the last group to the next round without testing it.

In either case, we only require $m-1$ retreats and we always send $k$ groups to the next round. So there is never any need to have all $m$ retreats in a given round. To see what happens at each round, note that if we divide $n$ into $m$ groups, then to figure out the group sizes, let $q$ and $r$ be the quotient and remainder, respectively, when we divide $n$ by $m$. So $n = qm + r$, with $0\le r\le m-1$. Then $n$ will be divided into $m$ groups as follows:
\[
n = \underbrace{q+\cdots+q}_{m-r} + \underbrace{(q+1) + \cdots + (q+1)}_{r}
\]But which groups carry over to the next round? Since we get to choose the order in which we schedule the retreats, and not all groups are of equal size, we can ensure that the last group (corresponding to the last retreat that never happens) is as small as possible. But it’s also possible that our $(m-1)^\text{th}$ group gets sent to the next round instead. So our best bet is to keep the two smallest groups for last. Ultimately, the worst case will see the $k-1$ largest groups and the $2^\text{nd}$ smallest group sent to the next round. Let’s call $g(n,m)$ this number. It’s somewhat annoying to compute $g(m,n)$, since it depends on the relative size of $k$ and $r$, but it’s approximately equal to $kn/m$. Here is what the recursion looks like:
\[
r_k(k) = 0\qquad\text{and}\qquad
r_k(n) = \underset{m\in\{k+1,\dots,n\}}{\text{minimize}}\,\, \left( m-1 + r_k( g(n,m) ) \right)
\]The recursion can be solved in a straightforward manner using recursion. Here is some Julia code along with the full computation of $g(n,m)$ that does the job:

nmax = 1024
k = 17

memo = -1 + zeros(Int,nmax)

# if n agents are divided into m groups, pick k-1 largest and 2nd smallest
function g(n,m,k)
    # n = q*(m-r) + (q+1)*r
    q,r = floor(Int,n/m), rem(n,m)
    if m == k+1  # we must pick the k largest in this case
        (r >= k ? k*(q+1) : r*(q+1) + (k-r)*q)
    else  # pick the k-1 largest and the 2nd smallest in this case
        (r >= k-1 ? (k-1)*(q+1) : r*(q+1) + (k-1-r)*q) + (m-r >= 2 ? q : q+1)
    end
end

function rk(n)
    if memo[n] != -1
        memo[n]
    else
        memo[n] = ( n == k ? 0 : minimum([m-1+rk(g(n,m)) for m=k+1:n]) )
    end
end
        
rk(1024)

In the first round, we have $n=1024$ suspects. The optimal thing to do is to choose $m=43$ groups, leaving us with $407$ suspects. Then we choose $51$ groups to get down to $136$ suspects. Then choose $46$ groups again to get down to $50$ suspects. Finally, we choose $50$ groups and we’re down to $17$ suspects, which must be our spies. So the total is $(43-1)+(51-1)+(46-1)+(50-1)=186$ total retreats. Interestingly, if we use the approximation $g(n,m) \approx \lceil \tfrac{kn}{m} \rceil$, we also get the result of $186$. Together with our previously derived lower bound, we obtain:

$\displaystyle
\text{number of retreats}:\quad 122 \leq r_{17}(1024) \leq 186
$

The lower bound means that it’s impossible for any strategy to do better than this, but there may not be any strategies that are this good. The upper bound says it’s definitely possible to do this well using a particular strategy, but other strategies might do better. In this case, the ratio between our upper and lower bounds is about 1.52. This sort of ratio is used in approximation theory to quantify the quality of a proposed solution when the problem is hard to solve exactly.

How about the cost? We will approximate. For each round, in the worst case, we have $m$ retreats, where $k$ of them have meetings and $m-k$ do not. Whenever there is a meeting, the group that stayed home can be excluded forever after (since we know it contains no spies), so we don’t need to send that group on subsequent retreats. The most expensive thing that can happen is that our $k$ retreats with meetings come last. So the total number of attendees will be approximately:
\begin{align}
a(n,m) &\approx (m-1-k)\left(n-\tfrac{n}{m}\right) + \sum_{j=1}^k \left(n-j\tfrac{n}{m}\right)\\
&\approx \frac{n \left(k-k^2+2 (m-1)^2\right)}{2 m}
\end{align}So if we end up choosing $m$ groups when there are $n$ attendees, we should add $a(n,m)$ to our running count of attendees. Incorporating this using the solution found above, we obtain the result that the strategy will require sending about $65484$ attendees to retreats. At a cost of \$1,000 per attendee, this means it will cost at most \$65.48 million to find all the spies.

For the curious, here is a plot showing the maximum number of retreats required to sniff out 17 spies, as a function of the total number of agents:

As we can see, the upper and lower bounds start close together but end up spreading apart as $n$ increases.

Minimizing cost instead?

The problem statement asked us to minimize the number of retreats, which led us to 186 retreats at a cost of \$65.48 million. If instead we attempted to minimize dollars using a similar strategy of dividing into groups and keeping one group home, we can formulate a similar recursion to the one above, except this time we perform the minimization over cost rather than retreats. The result in this case is 220 retreats at a cost of \$54.46 million. This makes sense. We can lower the cost if we want, but only at the expense of adding more retreats.

Even better!

It turns out the upper bound can be reduced to $131$ by instead singling out one spy at a time! This turns out to have a much better worst-case performance than splitting the remaining agents into equally-sized groups as I described in my solution. As one might expect, the worst-case cost in dollars goes up dramatically. The solution, due to Tim Black, can be found here. It still remains to be seen whether there exists a simple strategy that can further close the gap between the lower bound of 122 and the new upper bound of 131.

The blue-eyed islanders

Today’s Riddler problem is another classic. The current incarnation of the puzzle is about error-prone mathematicians, while the classic version is about blue-eyed islanders.

A university has 10 mathematicians, each one so proud that, if she learns that she made a mistake in a paper, no matter how long ago the mistake was made, she resigns the next Friday. To avoid resignations, when one of them detects a mistake in the work of another, she tells everyone else but doesn’t inform the mistake-maker. All of them have made mistakes, so each one thinks only she is perfect. One Wednesday, a super-mathematician, whom all respect and believe, comes to visit. She looks at all the papers and says: “Someone here has made a mistake.”

What happens then? Why?

Here is the solution:
[Show Solution]

On the tenth Friday, all mathematicians will resign. To understand why this happens, we’ll use a recursive approach similar to what we did for the puzzle of the pirate booty.

For simplicity, we’ll say a mathematician is flawed if they made a mistake, and perfect otherwise. Let’s look at the world through the eyes of Alice, one of the ten mathematicians. Alice doesn’t know whether she is flawed or not. She does, however, know how many of her colleagues are flawed.

According to the problem statement, all the mathematicians are flawed. So Alice sees that all nine of her colleagues are flawed. Let’s solve a simpler version of the problem first. What if none of Alice’s colleagues were flawed? In this case, the news that “someone here has made a mistake” can only mean one thing: that “someone” must be Alice! So Alice will resign on Friday.

What if exactly one of Alice’s colleagues is flawed? Two possibilities:

If Alice is perfect, then the flawed mathematician will see that everyone else is perfect and resign on Friday, just as Alice would have done in the previous case when she saw her colleagues were all perfect.
If Alice is flawed, then nothing happens on Friday. Alice then deduces that she must be flawed and resigns on the next Friday.

What if exactly two of Alice’s colleagues are flawed? Two possibilities:

If Alice is perfect, then each flawed mathematician sees one other flawed mathematician. As in the previous case, we expect them to both resign on the second Friday.
If Alice is flawed, then nothing happens on the second Friday. In that case, Alice will know of her flaw and resign on the third Friday.

The pattern is clear: if Alice has $k$ flawed colleagues but Alice is perfect, then the flawed mathematicians all resign on the $k^\text{th}$ Friday. If Alice is flawed, then nothing happens on the $k^\text{th}$ Friday, and Alice resigns on the $(k+1)^\text{st}$ Friday (along with all the other flawed mathematicians). In particular, if all ten mathematicians are flawed as in the problem statement, they all resign on the tenth Friday.

But but but…

It seems that we have a paradox — we aren’t telling the mathematicians anything they don’t already know! Each mathematician can clearly see that they have flawed colleagues, so why should explicitly announcing this fact make any difference? The answer lies in the distinction between mutual knowledge and common knowledge.

If everybody knows some proposition $P$ to be true, then $P$ is mutual knowledge. However, if everybody knows $P$, and everybody knows that everybody knows $P$, and everybody knows that everybody knows that everybody knows $P$, and so on, then $P$ is common knowledge. Although the fact that there is at least one flawed mathematician is mutual knowledge, it is not common knowledge. When the super-mathematician makes her announcement that there is at least one flawed mathematician, it becomes common knowledge, and this makes all the difference.

Rather than giving a detailed solution, I will defer to some other existing solutions online that are already well-explained. No need to reinvent the wheel! Here are some pointers.

The solution to the blue eyes puzzle featured on the xkcd website.
The wikipedia article on common knowledge, which uses the blue eyes puzzle as an illustrative example.
A post on the math stackexchange site that gives a detailed an formal proof of result.

The puzzle of the pirate booty

Today’s puzzle was posed on the Riddler blog, but it’s actually a classic among problem-solving enthusiasts, and is commonly known as the pirate game. Here is the formulation used in the Riddler:

Ten Perfectly Rational Pirate Logicians (PRPLs) find 10 (indivisible) gold pieces and wish to distribute the booty among themselves.

The pirates each have a unique rank, from the captain on down. The captain puts forth the first plan to divide up the gold, whereupon the pirates (including the captain) vote. If at least half the pirates vote for the plan, it is enacted, and the gold is distributed accordingly. If the plan gets fewer than half the votes, however, the captain is killed, the second-in-command is promoted, and the process starts over. (They’re mutinous, these PRPLs.)

Pirates always vote by the following rules, with the earliest rule taking precedence in a conflict:

Self-preservation: A pirate values his life above all else.

Greed: A pirate seeks as much gold as possible.

Bloodthirst: Failing a threat to his life or bounty, a pirate always votes to kill.

Under this system, how do the PRPLs divide up their gold?

Extra credit: Solve the generalized problem where there are P pirates and G gold pieces.

Here is the solution to the main problem:
[Show Solution]

This problem is a perfect example of when to use recursion. If there are $P$ pirates, when each pirate contemplates how to vote, they are comparing what would happen if they voted yes (and agreed to the current proposal) to what would happen if they voted no (and the current pirate died, reducing to the $P-1$ case).

Let’s start with two pirates and build up from there. For each case, here is a list of each pirates’ share of the gold. We ordered the pirates from lowest rank to highest rank (captain).

\begin{align}
&\quad\text{Gold distribution} &\text{Votes}&\text{ needed}\\ \hline
v_2 &: \begin{bmatrix} 0 & 10 \end{bmatrix} && 1\\
v_3 &: \begin{bmatrix} 1 & 0 & 9 \end{bmatrix} && 2\\
v_4 &: \begin{bmatrix} 0 & 1 & 0 & 9 \end{bmatrix} && 2\\
v_5 &: \begin{bmatrix} 1 & 0 & 1 & 0 & 8 \end{bmatrix} && 3\\
v_6 &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 8 \end{bmatrix} && 3\\
v_7 &: \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 7 \end{bmatrix} && 4\\
v_8 &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 7 \end{bmatrix} && 4\\
v_9 &: \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 6 \end{bmatrix} && 5 \\
v_{10} &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 6 \end{bmatrix} && 5
\end{align}

Let’s examine this table one row at a time. If there are two pirates ($v_2$), a majority is decided by a single vote. Since the captain gets to vote, they can safely propose to keep all the gold.

If there are three pirates ($v_3$), a majority is decided by two votes. So the captain needs to secure one extra vote. The first pirate (lowest rank) won’t win anything if the captain dies, because we would reduce to the $v_2$ case. The captain must give this pirate at least one gold piece to buy their vote and avoid death, but can keep the remaining $9$ pieces.

Similarly, if there are four pirates ($v_4$), a majority is decided by two votes. This time, the first pirate’s vote costs two gold pieces because they stand to win one gold piece if we reduce to $v_3$. However, the second pirate’s vote now costs one gold piece because they win nothing in the $v_3$ case. A similar argument applies as we continue to add pirates.

The final solution is that if we number the pirates $1,2,\dots,10$ in order from lowest rank to highest rank, then pirates $2,4,6,8$ each get one gold piece and the captain gets $6$ gold pieces.

And here is a solution to the general case:
[Show Solution]

As we saw in the previous solution, it makes sense to recurse on $P$, the number of pirates. If $G$ is the number of gold pieces, the pattern we observed in the simpler case still hold here, and we can continue it until the captain runs out of gold and is no longer able to bribe enough of his fellow pirates. So the table looks like:

\begin{align}
&\quad\text{Gold distribution} &\text{Votes}&\text{ needed}\\ \hline
v_2 &: \begin{bmatrix} 0 & G \end{bmatrix} && 1 \\
v_3 &: \begin{bmatrix} 1 & 0 & G-1 \end{bmatrix} && 2 \\
v_4 &: \begin{bmatrix} 0 & 1 & 0 & G-1 \end{bmatrix} && 2 \\
v_5 &: \begin{bmatrix} 1 & 0 & 1 & 0 & G-2 \end{bmatrix} && 3 \\
v_6 &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & G-2 \end{bmatrix} && 3 \\
&\vdots &&\vdots\\
v_{2G+1} &: \begin{bmatrix} 1 & 0 & \dots & 1 & 0 & 0 \end{bmatrix} && G+1\\
v_{2G+2} &: \begin{bmatrix} 0 & 1 & \dots & 0 & 1 & 0 & 0 \end{bmatrix} && G+1
\end{align}

In the last two rows of the table, there are $G$ 1’s. In the case with $2G+2$ pirates, a majority is decided by $G+1$ votes, so the captain wins nothing; they must forfeit all the gold in order to buy the votes necessary to survive. From this point forward, it may seem that if we add any additional pirates, they will be killed because there isn’t enough gold to buy enough votes. However, this isn’t quite the case. Here is what happens if we keep adding pirates:

\begin{align}
&\quad\text{Gold distribution} &\text{Votes}&\text{ needed}\\ \hline
v_{2G+2} &: \begin{bmatrix} 0 & 1 & \dots & 0 & 1 & 0 & 0 \end{bmatrix} && G+1 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}3}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & {\color{red}0} \end{bmatrix} && \color{red}G\color{red}+\color{red}2 \\
v_{2G+4} &: \begin{bmatrix} 1 & 0 & \dots & 1 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} && G+2 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}5}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & ? & ? & {\color{red}0} \end{bmatrix} && \color{red}G\color{red}+\color{red}3 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}6}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & ? & ? & {\color{red}0} & {\color{red}0} \end{bmatrix} && \color{red}G\color{red}+\color{red}3 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}7}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & ? & ? & {\color{red}0} & {\color{red}0} & {\color{red}0} \end{bmatrix}\hspace{-2cm} && \color{red}G\color{red}+\color{red}4 \\
v_{2G+8} &: \begin{bmatrix} 0 & 1 & \dots & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}\hspace{-2cm} && G+4
\end{align}

Once we get to $P = 2G+3$ pirates, the captain will always be killed (deaths are indicated in red) since there isn’t enough gold to buy the required votes. In the $2G+4$ case, however, the second in command is doomed to die if he votes to kill the captain, so he will vote yes even if offered nothing. This gives the captain a free vote, which is enough to secure the required $G+2$ votes. The captain must make an offer that compares favorably to the $2G+2$ case since the intermediate case $2G+3$ always leads to $2G+2$.

In the $2G+5$ case, none of the pirates have an incentive to keep the captain alive (since everybody will be safe with $P=2G+4$). The same happens with $2G+6$ and $2G+7$. Once we arrive at $2G+8$, three of the pirates are doomed if the captain dies, so they will vote yes even if offered nothing. Once again, this allows the captain to barely survive. This pattern continues, each time doubling the interval length between safe captains.

The solution to the general problem. Number the pirates $1,2,\dots,P$ in order from lowest rank to highest rank. If we have $G$ gold pieces to distribute, then we consider two cases:

If $P \le 2G+2$, then:

If $P$ is odd, pirates $1,3,5,\dots,P-2$ each get one gold piece, and the captain gets the remaining $G-\frac{P-1}{2}$ pieces.
If $P$ is even, pirates $2,4,6,\dots,P-2$ each get one gold piece, and the captain gets the remaining $G-\frac{P-2}{2}$ pieces.

If $P > 2G+2$, then the highest ranked captains will die until there are $P = 2G+2^k$ pirates remaining with $k$ as large as possible. Then:

If $k$ is even, pirates $1,3,5,\dots,2G-1$ each get one gold piece and nobody else gets anything.
If $k$ is odd, pirates $2,4,6,\dots,2G$ each get one gold piece and nobody else gets anything.

In the case where $P \ge 2G+2$, the solution is not unique in the sense that once we arrive at $P=2G+2^k$, there are other admissible ways of dividing up the gold besides the one shown above.

If this sort of problem interests you, I recommend taking a crack at the riddle of the blue-eyed islanders, or the unfaithful husbands. More information here as well.