7
$\begingroup$

Archie, the archaeologist, has discovered 50 valuable gold coins, which he needs to ship to Zurich. Using an insured courier is expensive, costing $50\%$ of the shipment value. On the other hand, Archie knows of smuggler, named Smullyan, who claims to only deduct one coin as fee from a shipment of any number of coins. However, Smullyan is not only perfectly rational, but also a scoundrel, and will steal an entire shipment if he feels this is profitable.

In order to entice Smullyan into being honest, Archie makes the following promise:

"I will divide my gold into packages of size $s_1,s_2,\dots, s_n$, and tell you this ordered list. I will send the first package of size $s_1$ with you, and as long as you don't take more than your standard fee for the first $k-1$ packages, then I will let you deliver the $k^\text{th}$ package. However, if you ever cheat me, then I will use the insured courier for the rest."

Archie realizes he is promising to act irrationally, since Smullyan will always steal the last package if they get that far. Unlike Smullyan, however, Archie is an honest man, and Smullyan knows this to be true.

Smullyan replies,

"Since you are being so kind (or stupid, Smullyan thought), I will do something I don't normally do. Every time I considering stealing from you, and would gain the same either way, then I won't steal."

Archie is touched by the gesture.

How should Archie choose the sizes $s_1,\dots,s_n$ in order to minimize the amount of money he loses to theft, smuggling fees, and courier fees combined? Was this a stupid proposition after all?

Clarifications: Coins are indivisible, so all $s_i$ must be positive integers (positive so that Smullyan can deduct his fee). The reason the courier can charge $50\%$ is because the courier fee is payed legal tender, not in ancient coins. Archie is indifferent between losing coins and losing their cash value (he plans to sell them anyway).

Source: The Puzzler's Elusion, Dennis E. Shasha

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

I'm probably misinterpreting the problem, but I'll give this a shot.

By "Every time I consider stealing from you, I won't steal if I'd gain the same either way", I assume it means that Smullyan won't steal a package containing $n > 1$ gold coins if it's exactly or earlier than the $n$th-last package. If it's later than $n$th-last, then Smullyan would gain a greater fee from just stealing the one package.

Evidently this means that Archie will have to send a number of packages with coin counts decreasing by 1 per bag, in order to minimize the number of packages he sends. For example, suppose Archie only had 45 coins total, then putting them in packages of $9, 8, 7, 6, 5, 4, 3, 2, 1$ would result in a total fee of only $9$ coins.

Archie has 50 coins, which means that if he puts the remaining five coins in a package before the one with nine coins, then the packages are $5, 9, 8, 7, 6, 5, 4, 3, 2, 1$, with a total fee of $10$ coins for ten packages.

Improve this answer
$\endgroup$
9
  • $\begingroup$ This is almost perfect! But Archie can do a little better. Consider what happens when the package sizes are 2,3,2,1. According to your first paragraph, Smullyan would steal the first package, since he felt like the delivering the others was too much work. Is this what maximizes the rational Smullyan's profit? $\endgroup$
    – Mike Earnest
    Apr 20, 2015 at 6:25
  • $\begingroup$ I guess not. So the condition is greater than only, not just inequal? $\endgroup$
    – user88
    Apr 20, 2015 at 6:26
  • $\begingroup$ @MikeEarnest Is my edit correct? $\endgroup$
    – user88
    Apr 20, 2015 at 6:29
  • 1
    $\begingroup$ This is optimal I think. Prop: For $n \geq 3$, you'll lose at least $n$ coins if you need to ship ${n+1 \choose 2}$ coins or more. If you intend to lose less than $n$ coins, then you can ship at most $n-1$ coins to start with, since otherwise Smullyan will steal them. But now you've lost one coin and still have at least ${n \choose 2}$ coins left to ship and we're done by induction. Note this prop isn't true for n = 1 or 2, but it seems to work for n = 3 and above. $\endgroup$
    – Tyler Seacrest
    Apr 20, 2015 at 7:26
  • 1
    $\begingroup$ I would send 9,8,8,7,6,5,4,3. That would result in the same amount of coins brought home, but you'd have to make less packages. Or 9,8,7,6,5,5,4,3,2,1 if I fear that he will break his word and only maximize his money. $\endgroup$
    – Timbo
    Apr 20, 2015 at 11:18
5
$\begingroup$

Indeed, Joe Z.’s much earlier solution, with 10 packages, allows Archie to lose the minimum, ...

...10 coins undelivered, of 50 packed...

...but the number of packages needed is only...

...8 packages:   10, 9, 8, 7, 6, 5, 2 and 3.   (Not unique.)

Smullyan will charge 1 coin for each of the first 7 shipments and steal the 3-coin final package. 


   1.  Pack 10 coins.  Theft would net 10 so Smullyan charges 1, for 1 so far.
   2.   "    9   "  .         "        10          "          1,  "  2   "   .
   3.        8                         10                     1,     3
   4.        7                         10                     1,     4
   5.        6                         10                     1,     5
   6.        5                         10                     1,     6
   7.        2                          8                     1,     7
   8.   "    3   "  .  Smullyan steals all 3 and ends up with 10 total.

This was derived in two stages and depends on Smullyan’s promise to only steal a package if it would increase the total take.

1. Assuming that Smullyan nets S coins, how many coins maximum may be packed?

No package before the last should exceed S - (Smullyan's share so far) coins, or else Smullyan will steal that entire package and wind up with more than S coins.


     1.  Pack  S  coins.  Theft would net S so Smullyan charges 1, for 1 so far.
     2.   "   S-1   "  .        "         S          "          1,  "  2   "   .
     3.       S-2                         S                     1,     3
     .         .                          .                     .      .
     .         .                          .                     .      .
     .         .                          .                     .      .
   S-2.        3                          S                     1,    S-2
   S-1.        2                          S                     1,    S-1
     S.   "    1  coin.   Smullyan charges or steals it and ends with S total.
           ----------
            S(S+1)/2  total coins could be packed.

Thus, for 50 coins, S = 10, which would allow up to 55 coins to be handled by Smullyan, whereas S = 9 would allow at most 45.   Trying to save 1 coin by shipping 45 or fewer coins through Smullyan would not be worthwhile, either, as the 50% courier would charge at least 21⁄2 coins for shipping the remaining 5 or more coins.

2. Can the number of packages be decreased from 10?

Yes. Any number of shipments could be omitted from the end of the scheme above, and Smullyan would still net the same S by stealing the last remaining shipment.   Omitting the last two shipments from the scheme’s 55-coin version still allows 52 coins to be packed, 2 more than necessary.

The surplus 2 coins may be removed from anywhere except the last remaining package, as that package’s count is Smullyan’s incentive to deliver all prior packages.

The present solution omits the last two shipments of the 55-coin scheme, leaving the 3-coin package as last, and removes 2 coins from the second-to-last remaining shipment, changing it from a 4-coin package to 2 coins.

Note: After writing this up I noticed that Timbo’s comment under Joe Z.’s solution foreshadowed this solution.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If Smullyan smuggles 10..5, why do we do 2-3 and not 2-2-1? He smuggles the 2 since stealing wouldn't be better. But if instead of 2-3 we do 2-2-1, he'll smuggle the first 2, then smuggle and then take the final coin. This would result in a cost of 1+1+1 instead of 1+3. This would also leave Smullyan at 9 coins, which means he would steal earlier (on 5) since he doesn't know Archie's strategy. This leaves Archie with 5 to courier at a cost of 2.5, making Archie lose (5-1)+2.5 coins. It is very possible that I'm misunderstanding something - I really like the approach so I hope I did. $\endgroup$
    – Jakob Pamp Bengtsson
    Oct 12, 2017 at 11:07
  • $\begingroup$ Alas, @Jakob Pamp Bengtsson, if Smullyan steals at 5 he would wind up with 10, as that would be the 6th shipment and the previous 5 shipments already took in 1 coin each. Too bad Archie also promises to keep going back to Smullyan as long as Smullyan has only charged 1 coin per delivery; I had another better solution in mind, too, before accounting for that condition. Hah, even though they're lawbreakers, Archie and Smullyan sure do expect each other to keep a couple of unprofitable promises. $\endgroup$
    – humn
    Oct 12, 2017 at 16: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.