Nine gangsters and a gold bar

Question

One night nine gangsters stole a gold bar. When the time came for dividing the bar, they faced a problem: two of the criminals put guns to each other's faces. Now it's up to fate whether one of them lives, they both live or both die.

While these two are dealing with each other, the others decide to continue dividing the gold bar. What is the minimal amount of pieces they should divide the bar into, so that no matter how things pan out, everyone can be given an equal share?

Scenario 1: Both gangsters blow each other's brains out. The gold must be divided evenly among the seven remaining gangsters.

Scenario 2: One gangster is quicker on the draw, and manages to take out his opponent. The gold must be divided evenly among the eight remaining gangsters.

Scenario 3: The duelling gangsters discuss their differences, come to a mutually beneficial agreement, and put away their guns. The gold must be divided evenly among all nine gangsters.

Answer 1

18 pieces:

3,7,9,14,16,18,23,24,25,30,31,32,38,40,42,47,49,56

In 9 parts:

{3,23,30} {7,49} {9,47} {14,42} {16,40} {18,38} {24,32} {25,31} {56}

In 8 parts:

{3,18,42} {7,56} {9,24,30} {14,49} {16,47} {23,40} {25,38} {31,32}

In 7 parts:

{3,7,24,38} {9,14,18,31} {16,56} {23,49} {25,47} {30,42} {32,40}

---

We need to be able to split it into 9 parts of 56, so it can't hurt to make 9 pieces of 56 and then split those further. Since we need to do better than 19 pieces, we can have at most 18 pieces. This means that most of our 56s are split into exactly two parts (we can have an extra piece for every 56 we don't split).

Now, what will our pieces be mod 9? We must be able to group them into 7 or 8 groups that sum to 0, or make 9 pairs (mostly) that sum to 2. If we have a 2, we can group it with a 7 to make 0. Then we pair the 7 with a 4, and repeat with a 5 and 6. If we do this 3 times, we can use the 6s to make another 0.

To make 63s and 72s, we should repeat at an interval of 9, so that we can swap the pairs to add 9 (e.g. {7,56} {16,47} {25,38} -> {16,56} {25,47}). The other two numbers that are swapped out need an extra 27.

Suppose we start with a 56 (freeing up one cut) and see what numbers we need.

    56-> 7->49->14->42
 9->47->16->40->23->33
18->38->25->31->32->24

So far, this makes 6 63s with 9 18 24 33 42 left over. We also need to make a 27 and a 72 out of 24 33 42. If we split 33 into 3 and 30, both of these are resolved. This results in the final answer with 18 pieces.

Answer 2

22 pieces

Suppose the weight of the bar is 504. I chose 504 since 7*8*9=504, so, the numbers would be easy to work with.

• 7 pieces of weight 56 (A)
• 8 pieces of weight 7 (B)
• 6 pieces of weight 9 (C)
• 1 pieces of weight 2 (D)

Scenario 1: The two gangsters decide to settle in a peaceful manner

Each gets a share of weight 504/9=56.

Give 7 A pieces to 7 people. 8th gets all the B pieces. The rest goes to 9th.

Scenario 2: One blows the head of the other and manages to survive

Each gets a share of weight 504/8=63.

Each of first 7 gets one A & one B piece. The rest goes to 8th.

Scenario 3: Both heads are blown

Each gets a share of weight 504/7=72.

Each of the first six get one A, one B & one C piece. The rest goes to 7th.

Answer 3

It has been shown that fewer than 16 pieces is not possible (due to the 8-way split then requiring someone to have a single piece larger than a single portion of the 9-way split). I'll show by contradiction than a split into exactly 16 pieces is not possible: for that purpose let's assume that there exists a solution for 16 pieces.

We'll use units of 1/504th (1/(7×8×9)) of the whole bar to discuss the sizes of the pieces (this does not affect the solution).

For the 9-way split at least two people must have only one piece (by the pigeonhole principle). Therefore there must be at least two pieces of size 56 (one ninth) - this also the largest size possible, otherwise whoever got a larger piece in the 9-way split would have more than their share.

For the 8-way split everyone must have exactly two pieces: otherwise someone would have to have only one piece, and that one piece would have to be of size 63 (one eighth), which is too large for the 9-way split. Therefore there must be at least two pieces of size 63 - 56 = 7, and since 56 is the largest size, 7 must also be the smallest size (or the 8-way split would require pairing it with a piece too large). The rest of the proof is basically showing that the existence of a piece of size 56 would inevitably lead to a piece smaller than size 7.

In the 7-way split a single portion of pieces must add up to size 72 (one seventh). Thus the pieces of size 56 each need to be paired with a total size of 72 - 56 = 16, and since 7 is the smallest possible size, this total can be obtained by using at most two pieces (floor(16 / 7)).

In a two-piece combination, the larger piece must be larger than 7 and at most 16 - 7 = 9. But in the 8-way split it would then be paired with a size less than 56 but at most 54, all of which would have to be paired with a piece smaller than 7 in the 9-way split to add up to 56. (In fact, 7 is the only size smaller than 63 - (56 - 7) = 14 which does not lead to this problem.) Therefore only a single piece of size 16 can be paired with a 56 in the 7-way split.

Since everyone has exactly two pieces in the 8-way split, pieces of size 63 - 16 = 47 are also required. For the 9-way split these pieces are paired with size 56 - 47 = 9 as other pairings would require pieces smaller than 7. But in the 8-way split the pieces of size 9 are then paired with size 63 - 9 = 54, which would lead to a piece of size at most 56 - 54 = 2 in the 9-way split. This contradicts the fact that 7 is the smallest piece, therefore there exists no solution for 16 pieces.

Since it has now been shown that there are no solutions with fewer than 17 pieces, the correct answer must be either 17 or 18 (which has been shown possible).

I'm fairly certain that there exists no solution for 17 pieces, but I have not been able to prove it – the problem is that unlike this solution, there are no immediate forced pairings in the 8-way split (up to two pieces may be smaller than 7), so it becomes very complex to consider all possible cases in the same manner as I've done here.

Answer 4

I've managed to solve it using 19 pieces like this:

Nineteen pieces in 504th portions:
2,5,9,12,13,16,18,19,20,23,26,26,30,37,40,47,51,54,56

In 7 shares, by 72:
{16, 56}, {2, 19, 51}, {9, 23, 40}, {5, 30, 37}, {18, 54}, {20, 26, 26}, {12, 13, 47}

In 8 shares, by 63:
{26, 37}, {13, 20, 30}, {23, 40}, {16, 47}, {9, 54}, {2, 5, 56}, {12, 51}, {18, 19, 26}

In 9 shares, by 56:
{26, 30}, {13, 20, 23}, {16, 40}, {9, 47}, {2, 54}, {56}, {5, 51}, {12, 18, 26}, {19, 37}

But there's a better solution with less number of pieces.

Answer 5

They should divide the bar into 9 pieces.

If the 2 gangsters kill each other their 2 pieces should go to their families. Respect is important in the mob world.

Answer 6

This is only a partial answer, but it does rule out some broad classes of 17-part solutions.

As has been observed by others, it's convenient to work in units of 1/504 of the loot.

Executive summary (TL;DR)

The three key contributions of this partial answer are that if there is a solution in 17 parts then:

• There are seven pairs which each add up to 63 and one triplet which adds up to 63.
• There are at least four parts which are not integral multiples of 1/504 of the loot.
• There are at least two and at most three parts equal to 56.

Important notes on notation

$\fbox{a}$ means an indivisible part equal to $a$.

I'm using superscript as frequency notation, not as exponentiation. E.g. $56^4$ means four 56s, and $\fbox{56}^4$ means four indivisible parts each equal to 56.

$\textrm{parts} = \textrm{vals}$ means that the parts on the left can be grouped to form the values on the right. E.g. $\fbox{7}^2 + \fbox{a} = 7 + 9$ would require $a = 2$. (I did consider using $\vdash$, but it turns out not to be very readable).

Basic observations

These two are mentioned in other answers, and included here for completeness since I rely on them below.

1. No part can be greater than 56.
2. By the pigeonhole principle, the nine-way division of seventeen parts requires at least one singleton; so there is at least one part of $\fbox{56}$.

There are other applications of the pigeonhole principle and its generalisations which I haven't seen explicitly in other answers:

• There are no more than seven parts greater than 36, for if there were then one of the partitions of 72 would have to contain more than one of them, giving a contradiction. (Similarly there are no more than 9 parts greater than 28).
• Since no part is greater than 56, each of the 63s in the eight-way division requires at least two parts, so in particular seven of them have exactly two parts and the eighth has three parts. This means that
  • There are nine degrees of freedom.
  • There are at least seven parts which are greater than 31.
  • There are at most two parts smaller than 7 (and if there are exactly two then they must sum to at least 7).

Brute-forcing partitions into "integral" parts

Let us define an "integral" part to be a part which is an integer multiple of 1/504 of the loot. Then we can use the observation that the 63s are made up of seven pairs and a triplet to brute-force. There are 25 partitions of 63 into two parts no greater than 56, and 322 partitions of 63 into three parts no greater than 56, so there are only $\binom{25+6}{7} \cdot 322= 846723150$ "integral" cases to brute-force.

In fact, applying the requirement for a part of $\fbox{56}$, there are only $\binom{25+5}{6} \cdot 322 + \binom{25+6}{7} \cdot 3 = 199084275$ "integral" cases to brute-force. I've written a computer program to test them, and none of them works.

Fractional parts

However, I haven't seen a proof that the parts must be "integral". Suppose that one of them, $\fbox{a}$ is "fractional". Then in every share in which it occurs there must be at least one other "fractional" part in order to give an "integral" total. Wlog the share of 56 which contains $\fbox{a}$ contains another fractional part $\fbox{b}$. If $\fbox{b}$ is also in the same share of 63 as $\fbox{a}$ and the same share of 72 as $\fbox{a}$ then we could merge them into one part of $\fbox{a+b}$ getting a 16-part solution, which is impossible. Therefore there must be one "integral" share which contains $\fbox{a}$ but not $\fbox{b}$, and one which contains $\fbox{b}$ but not $\fbox{a}$. So we require at least four "fractional" parts.

I think this bound is tight, because if we have four "half-integral" parts $\fbox{a}, \fbox{b}, \fbox{c}, \fbox{d}$ then we can pair them as $(\fbox{a} + \fbox{b}, \fbox{c} + \fbox{d}); (\fbox{a} + \fbox{c}, \fbox{b}+\fbox{d}); (\fbox{a} + d, \fbox{b}+\fbox{c})$ in the three divisions. This doesn't allow grouping them into fewer parts or rounding two up and two down.

Upper bound on parts equal to 56.

There are at most three parts equal to $\fbox{56}$. Proof is by contradiction.

Suppose that we have $\fbox{56}^4$. Then at least three of them come from pairs which add up to 63, so there are at least three parts equal to $\fbox{7}$. And looking at the seven-way division into 72s, there are thirteen non-56 parts to make four 16s and three 72s; each 72 takes at least two of those parts, leaving seven to make four 16s, so there must be a $\fbox{16}$.

So far our known parts are $\fbox{7}^3 + \fbox{16} + \fbox{56}^4$, and there are nine unknown parts $\fbox{a} \ldots \fbox{i}$. If we take $$\begin{eqnarray} \fbox{7}^3 + \fbox{16} + \fbox{56}^4 + \fbox{a} + \fbox{b} + \fbox{c} + \fbox{d} + \fbox{e} + \fbox{f} + \fbox{g} + \fbox{h} + \fbox{i} & = 56^9 \\ \fbox{7}^3 + \fbox{16} + \fbox{56}^4 + \fbox{a} + \fbox{b} + \fbox{c} + \fbox{d} + \fbox{e} + \fbox{f} + \fbox{g} + \fbox{h} + \fbox{i} & = 63^8 \\ \fbox{7}^3 + \fbox{16} + \fbox{56}^4 + \fbox{a} + \fbox{b} + \fbox{c} + \fbox{d} + \fbox{e} + \fbox{f} + \fbox{g} + \fbox{h} + \fbox{i} & = 72^7 \\ \end{eqnarray}$$ and remove known parts from the equations where there's only one value on the RHS which they fit or where they exactly match a value on the RHS, we get $$\begin{eqnarray} \fbox{7}^3 + & \fbox{a} + \fbox{b} + \fbox{c} + \fbox{d} + \fbox{e} + \fbox{f} + \fbox{g} + \fbox{h} + \fbox{i} & = 40 + 56^4 \\ & \fbox{a} + \fbox{b} + \fbox{c} + \fbox{d} + \fbox{e} + \fbox{f} + \fbox{g} + \fbox{h} + \fbox{i} & = 7 + 47 + 63^3 \\ \fbox{7}^3 + & \fbox{a} + \fbox{b} + \fbox{c} + \fbox{d} + \fbox{e} + \fbox{f} + \fbox{g} + \fbox{h} + \fbox{i} & = 16^3 + 72^3 \\ \end{eqnarray}$$

If we look at the seven-way division into 72s, each 16 on the RHS requires at least one of the unknown parts (since 16 is not a multiple of 7), and each of the 72s requires at least two of the unknown parts unless it has all three of the $\fbox{7}$s (since $72 - 7 - 7 = 58 > 56$).

Case split:

• Case 1: one of the 72s has only one of the unknown parts (wlog $\fbox{7}^3 + \fbox{i} = 72$, $i = 51$). Let's look at the three divisions of the loot, removing known parts as before: $$\begin{eqnarray} \fbox{7}^3 + & \fbox{a} + \fbox{b} + \fbox{c} + \fbox{d} + \fbox{e} + \fbox{f} + \fbox{g} + \fbox{h} & = 5 + 40 + 56^3 \\ & \fbox{a} + \fbox{b} + \fbox{c} + \fbox{d} + \fbox{e} + \fbox{f} + \fbox{g} + \fbox{h} & = 7 + 12 + 47 + 63 \\ & \fbox{a} + \fbox{b} + \fbox{c} + \fbox{d} + \fbox{e} + \fbox{f} + \fbox{g} + \fbox{h} & = 16^3 + 72^2 \end{eqnarray}$$

  The 5 and 7 (from, respectively, the nine-way and the eight-way divisions) take at least two unknown parts between them. $5 + 7 < 16$, so each of the 16s in the seven-way division takes at least one additional unknown part; $72 - 5 - 7 = 60 > 56$, so each of the 72s takes at least two additional unknown parts. That requires 2 + 3 + 4 = 9 unknown parts, and there are only eight left. This case is impossible.

• Case 2: each of the 72s has two of the unknown parts. Wlog each of $\fbox{a}, \fbox{b}, \fbox{c}$ goes towards a different 16, and each of $(\fbox{d} + \fbox{e}), (\fbox{f} + \fbox{g}), (\fbox{h} + \fbox{i})$ goes towards a different 72. (There are also the $\fbox{7}^3$ to assign).

  Observe that $a \equiv b \equiv c \equiv d + e \equiv f + g \equiv h + i \equiv 2 \pmod 7$.

  Observe also that the eight-way division is still requiring us to produce a 7 from the unknown parts. If we produce it as a $\fbox{7}$ then it can't come from a 16 (since $7 \not\equiv 2 \pmod 7$), so it must come from a 72; but then in order that the other unknown part which contributes towards that 72 be $\le 56$ we must contribute two of the previously known $\fbox{7}$ towards that 72, and this is equivalent to case 1.

  Therefore the 7 must come from two parts. (See "Basic observations": there are at most two parts smaller than 7). If both of those two parts contribute towards 72s (wlog $d + f = 7$) then even putting all three known $\fbox{7}$s towards them as well we require $e + g = 116$, which requires a part greater than 56.

  So one of the two parts must contribute towards a 16, and since the only positive number smaller than 7 which is equal to 2 (mod 7) is 2, we have wlog $a = 2$ and $d = 5$. But then $\fbox{a}$ must be grouped with two $\fbox{7}$s to make 16, leaving $\fbox{7} + \fbox{5} + \fbox{e} = 72$, so we need a part equal to 60, which is impossible. Both cases are now eliminated.

Lower bound on parts equal to 56

Lemma: if the parts (mod 7) are $a^x + (-a)^x + 0^{17-2x}$ (where obviously $x \le 8$) then wlog a = 2 and x = 6.

Proof: mod 7, the seven-way division is $2^7$. We can ignore the $0^{17-2x}$ for the purposes of forming those $2^7$.

Consider first the integral values of a.

• a = 0: useless.
• a = 1: $a^2 = (-a)^5 = 2$. We require $x = 10$ to make $2^7$ as $(a^2)^5 + ((-a)^5)^2$. That's too high.
• a = 2: $a = (-a)^6 = 2$. We require $x = 6$ to make $2^7$ as $a^6 + ((-a)^6)^1$. That's possible.
• a = 3: $a^3 = (-a)^4 = 2$. We require $x = 12$ to make $2^7$ as $(a^3)^4 + ((-a)^4)^3$. That's too high.

Now consider rational values of a. Let $a = p/q$ with $\gcd(p, q) = 1$. Then the minimum value of x can be found by taking the value which corresponds to $a = p$ and multiplying by $q$. But only $p=2$ works even with $q$ as low as 1, and any integral multiple of 6 greater than 6 is also greater than 8.

Corollary: there is no 17-part solution where the parts (mod 7) are $a^x + (-a)^x + 0^{17-2x}$.

Proof: Since one of the shares of 72 would have to include all six parts equal to -2 (mod 7), that would leave at most eleven parts for the remaining six shares, so we would require a part $\fbox{72}$, which is impossible.

Theorem: there is no 17-part solution with only one part of $\fbox{56}$.

Proof: suppose the contrary: that we have a 17-part solution with only one part of $\fbox{56}$. Then that leaves sixteen parts to make eight 56s, so they must pair up.

Consider a graph whose vertices are the parts and which has edges connecting the vertices in each pair of the nine-way division $56^9$, and in each pair of the eight-way division $63^8$. No vertex has more than two edges (one for a pair summing to 56, and one for a pair summing to 63). There are no cycles (because they would have to have alternating edges, but then we have $2x$ vertices which sum to both $56x$ and $63x$, so $x$ must be 0). The $\fbox{56}$ is the only vertex with no edge to pair it in a sum of 56; the three vertices of the triple which sums to 63 are the only vertices not to have an edge to pair them in a sum of 63. Therefore we have two chains: one from $\fbox{56}$ to one vertex of the triple; the other from the second vertex of the triple to the third vertex of the triple.

Observe that since $56 = 63 = 0 \pmod 7$, the vertices in a chain alternate in sign (mod 7). So the chain which contains $\fbox{56}$ contains only multiples of 7, and the other chain must have equal numbers of $a \pmod 7$ and $-a \pmod 7$. By the corollary above, there is no solution.

Answer 7

While my quick upper bound of 22 isn't new (multiple people have reached this), I reached it through a logical division rather than figuring it out mathematically. Here's the method:

We might have 9 people. We divide the bar into 9 A-pieces (size 1). Everyone gets one.

We might have 8 people. Everyone gets one A, then we divide the remaining piece into 8 smaller B-pieces and everyone gets one of those. We have 16 pieces so far.

We might have 7 people. Everyone gets one A and one B. We now have a spare A and B to divide. Divide the A into 6 C1-pieces and a C2 piece (C1s are equal, C2 is a B-piece smaller than a C1). 6 people get a C1, 1 person gets a C2 and the spare B. We have 22 pieces.

Answer 8

This is a proof that this problem is not solvable in less than 16 pieces. (Thanks to AndyT for the suggestion).

Suppose the weight of the bar is 504. Again, 504 is just for brevity and has no effect on the proof. We need to partition 504 into parts which can be rearranged to form blocks of

• 9 X 56,
• 8 X 63
• 7 X 72.

Note that the largest piece size can be 56.

Less than 16 pieces

Since we have to partition less than 16 pieces in 8 blocks of 63, one of those blocks must be a singleton (ie. contains a single element), hence must be the set {63}. But no piece can be larger than 56

Answer 9

Not sure it is the best solution but this is one way:

First divide the bar in 9 equal parts and call it size X. Divide one of those parts in 8 equal parts of size Y. So now if one dies you can distribute the 9th part easily among the 8 others.

Now you divide another part of X in 7 parts with 6 of those parts being of size (X+Y)/7. the seventh part will be together with an Y part the same size.

So you now have in total 7 parts of X, 8 parts of Y, 6 parts of (X+Y)/7 and one part of ((X+Y)/7 - Y) = 22 parts.

Answer 10

I think its 9 pieces!

scenario 1 = all 9 live, each gangster gets a piece
scenario 2 = 8 live, 8 get a piece, the last piece pays for the funeral of the dead guy
scenario 3 = 7 live, 7 get a piece, the remaining two pieces pays for the dead guys funerals

simple! :)

Answer 11

Okay first divide it into 9 Pieces.

Now we take the 8th and 9th Piece and divide them into 112 Equal Part.

We have now 7 + 112 = 119 Pieces.

56 Little Parts = 1 Big Piece

Scenario 1:

Everyone Lives. You have the Seven Pieces and the other 2 get 56 Little Parts each.

Scenario 2:

Only 1 Dies. You give everyone one big Piece and the 8th get 56 Little Pieces (Which is Equal to 1 Big Piece) and everyone get 7 Extra Little Piece

Scenario 3:

Both Die. You give everyone one big Piece and 16 Little Pieces.

Answer 12

The minimal number of pieces in which the gold can be divided is 28.

First, divide the entire bar into 9 equal pieces of volume $V$. Set aside 7 of those pieces and divide one of the other two into 7 pieces of volume $V_1$ = $V/7$.

Cut the last piece into 8 pieces of volume $V_2$ = $V/8$. Set aside 7 pieces of volume $V_2$, and divide the last piece of $V_2$ into 7 pieces of volume $V_3$ = $V_2$/7.

The total number of pieces is 28. (7 of volume V, 7 of volume $V_1$, 7 of volume $V_2$, 7 of volume $V_3$.)

Scenario 1: Both survive the shootout.
First seven gangsters get a piece of volume $V$ and the eighth gets the seven pieces of volume $V_1$. The ninth gets the 7 pieces of volume $V_2$ and the 7 pieces of volume $V_3$. So each one ends up with a volume $V$.

Scenario 2: One perishes in the shootout.
First seven gangsters get a piece of volume $V$ first. The survivor gets the 7 pieces of volume $V_1$. After that, the gangsters divide the last piece, such that seven of them get a piece of volume $V_2$, while one of them takes the 7 pieces of volume $V_3$. Thus, each ends up with a volume $9V/8$.

Scenario 3: Both die in the shootout.
First seven gangsters get a piece of volume $V$ first. Then they split up the eighth piece, each taking a piece of volume $V_1$. Then they each take a piece of volume $V_2$. Lastly, they each take a piece of volume $V_3$. This, each ends up with a volume $9V/7$.

Answer 13

I can do it with:

22 Pieces

The lowest common multiple of 7, 8 and 9 is 504. If this is shared 7 ways, then each gangster gets 72 504ths. If this is shared 8 ways, each gets 63 504ths. If this is shared 9 ways, each gets 56 504ths

Cut the bar into 9 equal pieces, each containing 56no 504ths. Take two of these pieces and cut each into (3 pieces that are 16no 504ths and one of 8no 504ths). Take another large piece and cut it into 7 smaller pieces, each containing 8no 504ths.

If you need to share 9 ways:

(6 * 56); (2 * 16+16+16+8); (1 * 7+7+7+7+7+7+7+7);

8 ways:

(6 * 56+7); (2 * 16+16+16+8+7);

7 ways:

(6 * 56+16); (1 * 7+7+7+7+7+7+7+7+8+8)

Answer 14

You need to divide your gold bar into 9 equals pieces (big parts). Take 2 big parts and divide each of them into 14 small parts. You have 7 big parts and 14 small parts (21 parts)
1 big part = 7 small parts

If both live (9 equals shares)
Everyone have 1 big part OR 7 small parts

If one live and one die (8 equals shares)
Everyone have 1 big part and 1 small part OR 8 small part

If both die (7 equals shares)
Everyone have 1 big part and 2 small part

Lateral thinking answer

when the time had come for dividing the bar they faced a problem

They don't divided the golden bar yet. The solution is to divide the gold bar AFTER the two gangster shoot themselves or not.

---

EDIT

i'm bat at maths, the 2nd case doesn't work D:

Answer 15

Let's ask ourselves the question: How many pieces of 56 grams can we possibly have if we want a 17-piece solution? This will help us limit the groupings in the 9-way split.

Let's assume we have three pieces of 56 grams. Then in the 8-way split scenario, one of the 56-gram pieces must be in a 2-piece group to get 63 grams, and thus there must exist (at least) two pieces of 7 grams. We also know that there is either a third piece $K$ of 7 grams, or exactly two pieces $K_1, K_2$ which add up to 7 grams.

In the 7-way split scenario, each 63-gram group needs to have at least two pieces of gold (otherwise, there will be a single piece of 72 grams > 56 grams). This means that we have 3 extra pieces of gold to assign to groups in the 7-way split. The known two pieces that weigh 7 grams cannot be in a group with only two pieces (otherwise the other piece in the group would be heavier than 56 grams). So the following three possibilities exist:

One group only with more than 2 pieces:

[56] + [ 7] + [ 7] + [A?] + [B?]

We know this cannot be true, since $K$ or both $K_1, K_2$ must be in this group, making the total larger than 72 grams.

Two groups with more than 2 pieces, a 3-piece group and a 4-piece group:

[56] + [ 7] + [A?] + [C1?]

[56] + [B?] + [C2?]

[56] + [16]

Because of the pigeonhole principle, we cannot have $K = 7$ be in one of the these groups (which would make at least one group unequal to 72 grams total), nor A = $K_1$, B = $K_2$ (for the same reason). Thus we have C1 = $K_1$, C2 = $K_2$. The last 7-gram piece also needs to be in one of these groups, so either:

B = 7 $\Rightarrow$ $K_2$ = 9 (contradiction)

or

A = 7 $\Rightarrow$ $K_1$ = 2 $\Rightarrow$ $K_2$ = 5 $\Rightarrow$ B = 11

We will now do some Sudoku-like deductions and reach a contradiction. The 11-gram piece will occupy a 2-piece group in the 8-way split, and thus generate a 52-gram piece, which will generate a 4-gram piece in the 9-way split, and this 4-gram piece must be part of a 2-piece group in the 8-way or 7-way split, and generate a piece that is larger than 56 grams.

Three groups with more than 2 pieces, 3 pieces each:

[56] + [ 7] + [B1?]

[56] + [ 7] + [B2?]

[56] + [A?] + [B3?]

We also know this cannot be true, because either $K_1, K_2$ must be in this group (which by the pigeonhole principle would make at least one group unequal to 72 grams total), or A = $K$, and $B_i = 9, \forall i$.

In this latter case, the pigeonhole principle again requires at least one $B_i$ to be in a two-piece group in the 8-way split and generate a 54-gram piece, and at least one 7-gram and one 9-gram piece to be in a two-piece group in the 9-way split and generate a 49-gram and a 47-gram piece, respectively. The 54-gram, 49-gram and 47-gram pieces must then generate 18-gram, 23-gram and 25-gram pieces in the 7-way split, leaving two free pieces that must add up to 72. But since the 54-piece must either create two pieces of 1 grams or one piece of 2 grams in the 9-way split, we reach a contradiction.

---

From the above, it is clear that there can be at most two 56-gram pieces in a 17-piece solution. This implies that the 9-way split has at least six 2-piece groups, plus either a 56-gram single-piece group + one 3-piece group (two 56-gram pieces case), or two 2-piece groups (single 56-gram piece case).

We will now show that the single 56-gram piece case admits no solutions with 17 pieces. To do this, we will consider the even/odd parity required for each of the groups in the 8-way split. There are 7 2-piece groups and one 3-piece groups in the 8-way split. Since each group must sum to 63 grams (odd), each 2-piece group must have one odd-weighted piece and one even-weighted piece. (The 3-piece group is either one odd or all odd pieces.)

Correspondingly, the 9-way split has 8 groups of 2 pieces, and one group of a single 56-gram piece. These 2-piece groups must be either all odd-weighted or all even weighted. Therefore, any pairing in the 8-way split cannot appear in the 9-way split. Moreover, this means that if we fix the location and the weight of any two pieces in the 8-way split not in the same group, the weights of all the other pieces can be determined, relative to the fixed weights.

For example, consider the scenario in which the 56-gram piece is in the 2-piece group, which generates a piece of 7 grams in the same group, which, when put in a (2-piece) group in the 9-way split, generates a piece of 49 grams, which can then be put back in the 8-way split again, so on and so forth.

I did this for all the possible scenarios with a single 56-gram piece in the 8-way split:

1. 56-gram piece in 2-piece group $\Rightarrow$ 7-gram weight $\Rightarrow$ 49-gram in 9-way split $\Rightarrow$ 49-gram put into 2-piece group in 8-way split ...
2. 56-gram piece in 2-piece group $\Rightarrow$ 7-gram weight $\Rightarrow$ 49-gram in 9-way split $\Rightarrow$ 49-gram put into 3-piece group (all odd / one odd only) in 8-way split ...
3. 56-gram piece in 3-piece group $\Rightarrow$ $K_1 = 7 - K_2, K_2$ $\Rightarrow$ $7-K_2$ put into 9-way split ...

In all these scenarios, a full, self-consistent set of weights will be generated, all dependent on a single variable, in the form of $n_i-X$ or $n_i+X$, where $X$ is the independent variable. One example is as follows:

This is for scenario 3 above, with independent variable $X = K_2$. It is easy to see that no two pieces with the same weight parity can sum to 72 grams if they have opposing signs (such that the independent variable $X$ is cancelled out). This is because for all scenarios, $n_i$ must be a multiple of 7 between 0 and 56, and even and odd pairs can never share $n_i$ by construction. (I know "by construction" is not rigorous at all, but I don't know of a clever way to prove this more elegantly.)

The only possibility is if the signs are the same, in which case the value of X will be forced to one value. However, this means that only a maximum of 1 same-parity pair can sum to 72 grams. By the pigeonhole principle, there are at least 4 2-piece groups in the 7-way split scenario, one of which is guaranteed to be both odd in weight parity, and the other guaranteed to be both even in weight parity. Therefore, the 7-way split has at least one 2-piece group that can never sum to 72 grams, and our proof for the single 56-gram case is done.

---

We are now left with the case where exactly two 56-gram pieces (and one 7-gram piece) exist in the 17-piece solution. If we can prove this case hsa no valid solutions, we are done. However, I was lazy, so I just brute-forced all possible combinations. I found no valid solutions in this case, and so the proof is done.

Answer 16

1. Split the bar into 9 equal pieces.

2. Split two of the pieces into 28 (7x8/2) equal smaller pieces, for a total of 7 big pieces and 56 small pieces.

   • If 9 gangsters survive, 7 of them each get 1 big piece, and 2 each get 28 small pieces.
   • If 8 gangsters survive, 7 of them each get 1 big piece and 7 small pieces, and the other gets 35 (28+7) small pieces.
   • If 7 gangsters survive, they each get 1 big piece and 8 small pieces.

Answer 17

I think f'' gives a clue on how to prove it can't be done in 17 pieces. We start with his original split into 17 pieces:

56->7->49->14->42->9->47->16->40->23->33->18->38->25->31->32->24

We need at least one 56 piece because otherwise we'd have split the original 9 into (at least) 2 pieces each, making 18 pieces. This split however is not complete (as shown in his method). We need to split some of the other pieces further, and to compensate (to still have 17 pieces), we need two 56 pieces.

What I'm mainly getting at is that we'll need two whole 56 pieces. To form 63 pieces out of those we need two 7's, which would need two 49's, which need two 14, etc. forcing the pieces to be

7, 7, 14, 14, 21, 21, 28, 28, 35, 35, 42, 42, 49, 49, 56, 56

before we split them further. These are sixteen all in all. But notice that they are all a multiple of 7 and their sum can never form a 72 = 8*9. Splitting one of them would possibly fix the situation for two of the pieces, but that is not enough, we're still left with 13 pieces, none of which can be summed up to 72.

Answer 18

I would go with 1x2x7 = 14 parts. Reason is:

• If one gangster shoots the other one, he will take all 14 parts
• If the two armed gangsters agree, they take equal parts - 7 parts each
• If the two armed gangsters shoot each other, the remaining 7 split the gold equally - 2 parts each