79
$\begingroup$

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.

$\endgroup$
  • 14
    $\begingroup$ @Cryol, I think that the question basically is: Divide the bar in some number of pieces so you can distribute the pieces in 7, 8 or 9 equal volumes $\endgroup$ – Ivo Beckers Aug 11 '15 at 9:56
  • 16
    $\begingroup$ One obvious solution is to divide it in 7x8x9=504 equal pieces. But this can probably be improved by using pieces of different sizes $\endgroup$ – Ivo Beckers Aug 11 '15 at 9:58
  • 13
    $\begingroup$ I assume we're not allowing the answer of "1 piece. You're a gangster, after all! Take it and run!" $\endgroup$ – Kingrames Aug 11 '15 at 12:41
  • 10
    $\begingroup$ @Kingrames, two of them already tried to do that, and this ended as a quite sophisticated puzzle. $\endgroup$ – Glinka Aug 11 '15 at 12:54
  • 3
    $\begingroup$ @IvoBeckers, a friend of mine solved this with less number of pieces (I don't know how many, but I assume it's not less then 17) and he refused to tell me his solution. He even pretended (or not) that he proved the minimality. So we bet that I'll come up with the solution before the end of the month. It started as a much more general and complicated mathematical problem, but this particular case with the gangster backstory seemed to me as a good puzzle. $\endgroup$ – Glinka Aug 11 '15 at 13:03

18 Answers 18

70
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great answer! You know if 17 pieces is possible? $\endgroup$ – Ivo Beckers Aug 11 '15 at 15:33
  • $\begingroup$ @IvoBeckers I don't think it is, but I can't prove that. $\endgroup$ – f'' Aug 11 '15 at 15:39
  • $\begingroup$ Ok. I was thinking that if you start with more pieces that also is divisible by 504, like 1008 for example it would expend the options you have which could lead to a better solution. But of course a larger number would make it even harder $\endgroup$ – Ivo Beckers Aug 11 '15 at 15:43
  • 3
    $\begingroup$ @Anachor - could you write out your proof that less than 17 is impossible? (I've tried and failed - hence very interested in it, and I think it would form a part of the answer to the OP's question. I'd suggest making it a separate answer to your attempt giving 22 pieces.) $\endgroup$ – AndyT Aug 12 '15 at 8:26
  • 4
    $\begingroup$ We can easily prove that 15 isn't possible -- pigeonhole principle would mean that for an 8-way split one person would have a single piece of weight 63, which would preclude any 9-way split. $\endgroup$ – user295691 Aug 12 '15 at 19:31
23
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think we have the winner ! $\endgroup$ – The random guy Aug 11 '15 at 11:12
  • $\begingroup$ That is correct with 23 pieces and it's the best answer yet! But there still is a better way :) $\endgroup$ – Glinka Aug 11 '15 at 11:16
  • $\begingroup$ I think my answer is correct and it's 22 pieces. I think It's basically the same oas you except that D is 1 piece of weight 2. You don't need two pieces $\endgroup$ – Ivo Beckers Aug 11 '15 at 11:17
  • 1
    $\begingroup$ Yeah I just noticed that, There is no need to have 2 pieces of one, just have one piece of 2. Thnks. I did some editing, so you won the race. You might want to explain your answer better, right now it seems hard to understand. $\endgroup$ – Rohcana Aug 11 '15 at 11:21
  • 10
    $\begingroup$ Just a note, there's a very simple way to get 22 pieces without counting in 504ths. Treat the gold as a line segment. Cut it into equal 7ths. Then cut it into equal 8ths (ignoring the previous cuts). Then cut it into equal 9ths (still ignoring the previous cuts). This uses 21 cuts, so it produces 22 pieces, and it's obvious that it works. $\endgroup$ – f'' Aug 11 '15 at 14:56
21
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Excellent work! I hope we will find a proof to decide between 17 and 18.... Do you think there is a proof that you never need parts which are not an integer multiple of 1/504 ? If we could somehow show that we don't need smaller/different fractions, we could brute force all combinations of 17 parts for 1/504ths... $\endgroup$ – Falco Aug 13 '15 at 9:12
  • 1
    $\begingroup$ I was working on a Matlab script to brute force the 16 and 17 solutions (16 wasn't ruled out until this post), but it is not a trivial task. I ultimately gave up and am now waiting for someone smarter than me to find whether or not it is possible. It is 2 (or 4) NP problems in series. first it's finding all the combinations of 17 numbers that sum to 504 (stackoverflow.com/questions/4632322/…), and then 3 k-partitionings (en.wikipedia.org/wiki/Partition_problem#The_k-partition_problem) on each combination. $\endgroup$ – dberm22 Aug 13 '15 at 19:18
  • $\begingroup$ @Falco - 504 has been selected precisely because it means you only need to consider integers. Brute forcing it is horrendously complicated - I can't follow dberm22's explanation as it's too complicated for me, but the number of possible combinations is huge. $\endgroup$ – AndyT Aug 14 '15 at 9:12
  • 1
    $\begingroup$ Brute forcing the 17-piece scenario could also be helped by realizing that there must be at least one piece of size 56, and there can be at most 2 pieces smaller than 7, and at most 6 pieces smaller than 16. $\endgroup$ – Arkku Aug 19 '15 at 23:52
  • 2
    $\begingroup$ @Falco, I've brute-forced all the combinations and shown that a 17-part solution requires at least four parts which are not an integer multiple of 1/504. $\endgroup$ – Peter Taylor Aug 22 '15 at 16:07
16
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Which algorithm or technique did you use to identify those selections - trial and error, or something more powerful? $\endgroup$ – Philip Oakley Aug 11 '15 at 14:01
  • 1
    $\begingroup$ @PhilipOakley, see picture oi60.tinypic.com/2jfek5v.jpg. First I divided the bar into 9 pieces (black lines), then into 8 pieces with the shift (red lines). Using obtained pieces I tried to assemble pieces of the size 72 (wich is one 7th). I managed to assemble 4 such pieces (16+56, 2+19+51, 9+23+40, 30+5+37), and I had to do 2 more cuts to get 3 remained pieces. 16 cuts on the picture plus 2 additional cuts gives us 19 total pieces. $\endgroup$ – Glinka Aug 11 '15 at 14:19
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Try telling them that, you might get your head blown off. $\endgroup$ – Rohcana Aug 11 '15 at 15:37
  • $\begingroup$ Gangsters have such a bad reputation... $\endgroup$ – Bobby Aug 11 '15 at 15:38
  • $\begingroup$ Also, If only one of them survives, I don't think he would be too keen to the idea. $\endgroup$ – Rohcana Aug 11 '15 at 15:52
  • 1
    $\begingroup$ If anything he should feel more guilty for taking away the bread winner of the family! $\endgroup$ – Bobby Aug 11 '15 at 15:54
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ After writing up my answer, I realized you had written a much better one (especially for the single 56 impossibility proof). Cheers! I think I did prove that three 56s are also impossible (even with fractional parts), maybe that would help closing up the entire proof for a 17-piece solution? Also, I am not sure either of our single 56 proofs work if fractional gold pieces exist... $\endgroup$ – Hackiisan Oct 23 '15 at 16:59
  • $\begingroup$ @Hackiisan, my single 56 proof does not rely directly on the pieces being integral (although the lemma does prove that they must be; I could have stopped the proof there by reference to the brute-force calculation which shows that there must be some fractional pieces, but I'd like to prove as much as possible without that brute-force calculation). I think the graph technique I used for the single 56 proof can be extended to two 56s, but there are a few cases to consider. I may revisit my work on that at some point and try to simplify it. I'll try to work through your 56³ proof later. $\endgroup$ – Peter Taylor Oct 23 '15 at 17:24
  • $\begingroup$ I agree, the graph technique is more powerful and flexible. (I attempted to do the same with a odd/even parity argument, but could not justify satisfactorily the (mod 7) requirement.) The 56$^n (n \geq 3)$ proof I have is based on repeated applications of the pigeonhole principle, which fails for $n \leq 3$. I'm confused what you mean by "the lemma does prove that they must be [integer pieces]", because right now I don't see how your single 56 proof eliminates fractional pieces (since modulo arithmetic is meaningless for fractional sizes?). $\endgroup$ – Hackiisan Oct 24 '15 at 0:18
  • $\begingroup$ @Hackiisan, I think the argument following "Now consider rational values of a" is straightforward. Modulo arithmetic is actually perfectly meaningful for fractional sizes: $a = b\pmod n$ is a convenient notation for $\exists k : a = b + kn$, and doesn't require the variables to be integers. In fact $a\bmod 1$ is a conventional way of describing the fractional part of $a$. $\endgroup$ – Peter Taylor Oct 24 '15 at 8:35
9
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Your proof about 16 pieces is not correct: If no piece except 56 can be greater than 49, we can only colnclude that no piece except 7 can be less than 14. $\endgroup$ – Hagen von Eitzen Aug 12 '15 at 14:02
  • 1
    $\begingroup$ For 16, there must be pieces that are not divisible by 7 (otherwise making 72 would be impossible). Consider the smallest piece that is not divisible by 7. $\endgroup$ – f'' Aug 12 '15 at 14:24
  • $\begingroup$ I thought that, but that doesn't exactly work. The reason is there might be 3 or 4 pieces that add to 56. Maybe, I'm missing something. $\endgroup$ – Rohcana Aug 12 '15 at 14:34
  • 1
    $\begingroup$ @Dennis Any chance of sharing that proof with us? =) $\endgroup$ – Arkku Aug 13 '15 at 13:27
  • 1
    $\begingroup$ @Dennis - Yes please for the 17 blocks impossible proof! I've been working on it and failing. $\endgroup$ – AndyT Aug 13 '15 at 14:54
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can explain again, how do you distribute it to 7 guys? $\endgroup$ – Glinka Aug 11 '15 at 11:18
  • $\begingroup$ Everyone gets a X piece and a Y piece. 6 get the (X+Y)/7 piece and the last one another Y piece and the ((X+Y)/7 - Y) piece $\endgroup$ – Ivo Beckers Aug 11 '15 at 11:26
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Okay Didnt Thought about making 3 differnt Kind of pieces...Good Job! $\endgroup$ – Cryol Aug 11 '15 at 11:05
  • $\begingroup$ Correct with 28, but it is not the minimum. There is a better way :) $\endgroup$ – Glinka Aug 11 '15 at 11:05
3
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ If shared 7 ways, it would be 72. It seemed you did it right, but typed it wrong. $\endgroup$ – Rohcana Aug 11 '15 at 11:24
  • $\begingroup$ Yeah, and 22 is not the minimum $\endgroup$ – Glinka Aug 11 '15 at 11:25
3
$\begingroup$

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! :)

$\endgroup$
  • $\begingroup$ That's funny, but that is not what question is about :) @f'' gave a brilliant answer, I need to verify that it's the right one, and then I think the problem is closed. $\endgroup$ – Glinka Aug 11 '15 at 14:39
  • 5
    $\begingroup$ These are gangsters. Dumping a body in the river isn't very expensive. $\endgroup$ – Lampost42 Aug 11 '15 at 14:40
  • 1
    $\begingroup$ @Lampost42 - have these gangsters no respect for the dead!? =) $\endgroup$ – user15576 Aug 11 '15 at 14:41
  • $\begingroup$ Damn I read your answer after posting mine! $\endgroup$ – Bobby Aug 11 '15 at 15:37
  • 2
    $\begingroup$ @user15576 They are more rational than you think. They care more about the hungry sharks than two dead guys. After all, catering to the living is more important than catering to the dead. $\endgroup$ – Rohcana Aug 11 '15 at 16:05
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In Scenario 3 only seven gangsters lives. You give each of them one big piece and 2 little pieces, right? We have 14 little pieces distributed, but 2 little pieces remains undistributed. $\endgroup$ – Glinka Aug 11 '15 at 10:25
  • $\begingroup$ @Dennis I edited my Post. Now everything SHOULD be alright^^ $\endgroup$ – Cryol Aug 11 '15 at 10:54
  • $\begingroup$ There are still some mistakes to edit, but I got your idea. Unfortunately, 112 parts is to many $\endgroup$ – Glinka Aug 11 '15 at 11:00
2
$\begingroup$

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:

$\endgroup$
2
$\begingroup$

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:

9 Gangsters and a Gold Bar

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.

$\endgroup$
  • $\begingroup$ Hmm... I just realized I didn't take care of fractional solutions... =( $\endgroup$ – Hackiisan Oct 23 '15 at 0:30
1
$\begingroup$
  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.
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Eh, what if you use the 7's as a fourteen, you might not need 2 49's $\endgroup$ – Going hamateur Aug 13 '15 at 16:07
  • $\begingroup$ Those 7's have to be broken away from other 56 pieces, forming two 49's. Either that or those two 7's came from the same piece, which is now broken in three and looks like this: 7 + 7 + 42. Checking the numbers, that would lead to: 7, 7, 7, 14, 21, 21. 28, 28, 35, 35, 42, 42, 49, 56, 56, 56. These are, again, 16 numbers that are all a multiple of 7, leading to the same result as before. I hope I'm not forgetting something fundamental here. $\endgroup$ – Daniel Sigurdsson Aug 13 '15 at 16:38
  • 2
    $\begingroup$ Informally I'm inclined to believe the conclusion based on my own attempts at proving the case of 17 pieces always leading to similar situations, but I don't think this is conclusive proof since it is not clear that there aren't other ways to make the splits (the 8-way split allows up to two pieces smaller than 7 so we are not forced to match every piece of size s with 63 - s). $\endgroup$ – Arkku Aug 13 '15 at 16:41
  • $\begingroup$ @Arkku Damn it, you're right! $\endgroup$ – Daniel Sigurdsson Aug 13 '15 at 17:57
-1
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ If one gangster shoots the other one, there will be 8 gangsters to split the bar between. These two are not the only ones armed, they are just the unstable ones. $\endgroup$ – Glinka Aug 11 '15 at 13:59
  • 2
    $\begingroup$ I don't think he misread the question, I just think this is a lateral thinking answer. Of course, for his theory, you only need 8 parts (6 of equal size, 2 of half that size). $\endgroup$ – Joel Rondeau Aug 11 '15 at 14:21
  • 1
    $\begingroup$ if one one armed gangster is left alive, why should he share with the non-armed? However, Joel's 8 parts are enough $\endgroup$ – corvairjo Aug 12 '15 at 12:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.