11
$\begingroup$

Question: Ali-Baba is a prisoner of the $42$ thieves who have just stolen $41$ identical magic incense sticks. The thieves want share this loot in such a way that everyone has exactly the same pieces as the others. Ali-Baba offers his know-how in exchange for his freedom. Ali arranges the $41$ sticks side by side, moves some pieces, then, after a few cuts carried out using a sword, between which he moves the pieces again, he gives each of the $42$ thieves exactly the same share made up of the same pieces.

Attribution: 16th international championship of mathematical games, day 1, question 16, available in the original French PDF.

What is the minimum number of cuts made by Ali-Baba? How many pieces will each of the thieves then have? Note: A cut can slice through a very large number of pieces of incense.

I literally have no idea how to approach this problem, tips and solutions would be appreciated.

Improve this question
$\endgroup$
7
  • $\begingroup$ the question is simply; ax+by+c*z=42*k where a+b+c=41 and a,b,c,x,y,z,k are positive integers. $\endgroup$
    – Oray
    Aug 4, 2022 at 11:27
  • 2
    $\begingroup$ determine the least popular thief and cast him out of the guild. Who wants their magical incense sticks cut up? $\endgroup$
    – Robin Clower
    Aug 4, 2022 at 14:12
  • $\begingroup$ @Oray, that's not right, the incense don't have to all be cut to the same number of pieces, as the accepted answer shows $\endgroup$
    – justhalf
    Aug 5, 2022 at 8:54
  • $\begingroup$ Why not cut the 42 thieves into pieces to reassemble 41 thieves, all composed of identically sized pieces? $\endgroup$
    – Florian F
    Aug 6, 2022 at 15:55
  • $\begingroup$ @Oray I don’t see how that is true at all. How does the solution $a=1$, $b=40$, $c=0$, $x=2$, $y=1$, $z=17$ $k=1$ correspond to a solution to the puzzle? $\endgroup$
    – Daniel S
    Aug 6, 2022 at 17:52

2 Answers 2

Reset to default
15
$\begingroup$

I don't yet have a proof of minimality, but my initial thought is

Create a group of 21 sticks, a group of 14 sticks and a group of 6 sticks

Divide the 21 sticks in half; the 14 sticks into thirds and the 6 sticks into sevenths. This can be achieved with six cuts.

Actually, on rethinking

This can be done with three cuts, as $\lceil(\log n)/(\log 2)\rceil$ cuts are needed to divide a stick into $n$ pieces.

Each thief can then have three pieces: a half stick, a third of a stick and a seventh of a stick.

Somewhat disappointingly

We can use this to construct an infinite family of solutions: we can cut the collections of half sticks and third sticks up arbitrarily with the freedom to make two and one additional cuts respectively. This means that the second half of the problem does not have a unique solution as stated.

For first steps towards showing minimality, note that

If at most two cuts are used, then each stick is divided into at most four pieces. There are therefore at most 164 pieces, but because the pieces can be divided into identical groups of 42 there can only be 42, 84 or 126 pieces. It's easy to dispense with the 42 and 84 cases, but I've not yet shown that one cannot use two cuts to create 3 groups of 42 identical pieces.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Yup now I get it all! $\endgroup$
    – David G.
    Aug 4, 2022 at 0:43
  • $\begingroup$ Indeed, the answer is 3! $\endgroup$
    – David G.
    Aug 4, 2022 at 0:52
  • 1
    $\begingroup$ This is likely to be the intended answer, but one thing keeps nagging me: how do you cut off one-seventh (or for that matter, one-half) of a piece (let alone multiple pieces at once) if all you have is a sword, and no ruler nor a right angle? $\endgroup$
    – Abigail
    Aug 4, 2022 at 10:12
  • 2
    $\begingroup$ @Abigail it doesn't say he doesn't have a ruler. But maybe one of the "magic" properties of the incense is allowing you to make accurate cuts as desired :-) $\endgroup$
    – armb
    Aug 4, 2022 at 17:34
5
$\begingroup$

Note that this is a wrong solution (but definitely minimal).

I missed the part about everyone getting the same number and size of pieces.
I'll leave it here for now as an example of how not to do it.

Don't up-vote this answer.

I've no idea why (no comments given), but in the last 12 hours this wrong answer has just received 5 upvotes. Even if you do consider it a good answer, it is still a bad answer to this question.

To save typing, I'll do this with 5 sticks and 6 people:

Consider 5 sticks:
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |

Make one cut:
| | | | |
\ | | | |
| \ | | |
| | \ | |
| | | \ |
| | | | \
| | | | |

Shift the upper set to the right:
  | | | | |
    | | | |
|     | | |
| |     | |
| | |     |
| | | | 
| | | | |

And move it down:
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |

Improve this answer
$\endgroup$
4
  • $\begingroup$ rot13(Va guvf fbyhgvba gjb crbcyr trg n svir ybat cvrpr, gjb crbcyr trg n sbhe ybat cvrpr naq n bar ybat cvrpr naq gjb crbcyr trg n guerr ybat cvrpr naq n gjb ybat cvrpr. Guvf zrnaf gung fbzr crbcyr trg qvssrerag ahzoref bs cvrprf naq nyfb cvrprf bs qvssrerag fvmr.) $\endgroup$
    – Daniel S
    Aug 4, 2022 at 0:45
  • $\begingroup$ All parts they recieve have to be exactly the same and in the same number. By one cut, you get 10 sticks which means at least 2 people get 1 stick and the rest get more than one. $\endgroup$
    – David G.
    Aug 4, 2022 at 0:45
  • $\begingroup$ @DavidG., Ah, I missed that aspect of it. Is it more appropriate to delete this answer, or to leave it as an example of how not to do it? (I'm okay with either.) $\endgroup$
    – Ray Butterworth
    Aug 4, 2022 at 0:48
  • $\begingroup$ It's up to you, I'm still not sure what the real solution is anyways so it might still be useful. $\endgroup$
    – David G.
    Aug 4, 2022 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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