2
$\begingroup$

This question already has an answer here:

Captain Jack and his crew have uncovered another treasure full of glistening golds and shiny silvers. There are 2015 chest and each of them contains some amount of gold and silver coins. Different chests may contain different amounts of gold or silver.

Captain Jack, being greedy as ever, wants to keep at least half of the gold and half of the silver. However, he is aware of dissatisfaction among the crew and wants to avoid a mutiny at all costs. So, he wants to give the crew as many treasure chests as possible.

Captain Jack must tell the crews how many chests he is going to give them before he opens up the chests. After that he opens up each chest and decides which chests to keep and which to give away.

What number should Jack tell the crews to ensure that he keeps at least half of the gold and half of the silver while keeping the crew as satisfied as possible? In other words, Find the maximum $N$ such that Jack can always distribute the chests in such a way that he gets to keep half the gold and half the silver and give away $N$ chests.

Notes

  • The captain may count how many silver and gold is in each chest, but cannot remove any gold or silver from its chest, since doing so will result in a irreversible curse for the entire crew and the captain.

  • Without opening a chest there is no way to tell how many gold or silver it contains.

$\endgroup$

marked as duplicate by JonTheMon, Ross Millikan, TroyAndAbed, Kingrames, Engineer Toast Sep 1 '15 at 20:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I feel like we need more information. For example, if there happens to be one chest that contains $\frac34$ of the gold and $\frac34$ of the silver, then he can give away 2014 chests. If the gold and silver are evenly distributed, then he can only give away 1007 chests. $\endgroup$ – GentlePurpleRain Sep 1 '15 at 15:28
  • $\begingroup$ Yeah, if each chest has one gold and one silver except the big one that has infinity gold and silver, then he'll pick that one and give away 2014 chests. This is actually quite nice of him because that's a very heavy chest, and the smaller chests are probably worth something on their own anyway. $\endgroup$ – Kingrames Sep 1 '15 at 15:33
  • $\begingroup$ Sorry for the ambiguities, hope it's clear now. $\endgroup$ – Rohcana Sep 1 '15 at 15:47
  • $\begingroup$ "as satisfied as possible" is still pretty ambiguous. We don't know what the mutiny level is, and the only way to guarantee that he gets half is if he takes every chest, because any given chest has no upper limit. So what happens if he takes every chest? $\endgroup$ – Kingrames Sep 1 '15 at 16:01
  • 1
    $\begingroup$ @IfTrue Nothing in the question specifies, that he must give away a chest before he knows what the other chests contain. $\endgroup$ – Sleafar Sep 1 '15 at 16:35
5
$\begingroup$

Given the changes, my other answer is no longer valid (but I'll leave it up). My new answer is:

1007, which covers the worst-case scenario. He takes 1008.

I've got an explanation but not a mathematical proof:

The worst-case scenario is the one in which an equal amount of gold and silver is in every chest. Because it's an odd number of chests, he has to take half (rounded up) to get half the total. This answer is the same if each chest contains the same total amount of gold and silver but in a linearly changing ratio (e.g. 5 4 3 2 1 gold and 1 2 3 4 5 silver). Any non-uniform chests are either higher-value on average, making them worth taking, or lower value on average, making all the other chests more worth taking; both of these cases make the case better than worst-case.

$\endgroup$
  • $\begingroup$ Currently the only answer I can think that makes sense. $\endgroup$ – IfTrue Sep 1 '15 at 16:42
  • $\begingroup$ You are on the right track is all I can say. $\endgroup$ – Rohcana Sep 1 '15 at 16:53
  • 2
    $\begingroup$ puzzling.stackexchange.com/questions/15412 $\endgroup$ – f'' Sep 1 '15 at 17:42
  • 2
    $\begingroup$ Interesting question and possible answer. I'm not quite sure the situation you are describing corresponds to the worst case. It does correspond to the worst case if we were to handle only silver OR gold but it might be a bit trickier with both constraints. Maybe a situation where half the chests have a bit more gold than the average and a bit less silver is actually worse. I'll need to give this a try with pen and paper :-) $\endgroup$ – Josay Sep 1 '15 at 18:00
  • $\begingroup$ I still see this as being the ONLY possible answer because you can not know the amount or ratio of coins in each chest before giving the crew a number. $\endgroup$ – Spacemonkey Sep 1 '15 at 18:40
3
$\begingroup$

2015.

Because:

He can't transfer gold or silver between chests, but he can still remove gold and silver from chests. He removes gold and silver until he has at least half, then gives all the chests away.

$\endgroup$
  • 2
    $\begingroup$ Nice! A rather clever way to get around the ambiguities. $\endgroup$ – Kingrames Sep 1 '15 at 15:35
  • 1
    $\begingroup$ Loopholes... You can't get rid of them. $\endgroup$ – Rohcana Sep 1 '15 at 15:46
  • $\begingroup$ Note that this still works, because he can still say he's going to give them all of the chests and then skim a few gold off each one. $\endgroup$ – Kingrames Sep 1 '15 at 15:47
  • $\begingroup$ @kingrames I got rid of that loop hole as well $\endgroup$ – Rohcana Sep 1 '15 at 15:51
  • $\begingroup$ Nope! He'll have THEM remove the gold or silver from the chest. No curse for the captain! Jack Sparrow wins again. $\endgroup$ – Kingrames Sep 1 '15 at 15:53
0
$\begingroup$

Post-edit

Captain Jack must tell the crews how many chests he is going to give them before he opens up the chests.

Captain Jack doesn't want chests, he wants coin. The crew can have all 2015 chests after the gold and silver has been removed.

Pre-edit

Assuming he can't remove any gold or silver in addition to not being able to transfer, the maximum number of chests he could give is

2014.

Example,

chest 1 has 2014 gold and 2014 silver, and the remaining chests have 1g and 1 silver each.

$\endgroup$
  • 2
    $\begingroup$ I think the question wants a number that Jack can distribute regardless of the distribution of gold and silver in the chests. $\endgroup$ – Ross Millikan Sep 1 '15 at 16:28

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