2

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.

Rohcana
  • 4,010
  • 21
  • 49
  • 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. – GentlePurpleRain Sep 01 '15 at 15:28
  • 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. – Kingrames Sep 01 '15 at 15:33
  • Sorry for the ambiguities, hope it's clear now. – Rohcana Sep 01 '15 at 15:47
  • "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? – Kingrames Sep 01 '15 at 16:01
  • I think it may be more ambiguous now. How can he give the crew a number before he even opens the chests and is able to count the gold, let alone divvy up half of it? Or is this based on word-play. In the sentence, 'He wants to give the crew as many treasure chests as possible', treasure chests is bold. Is the answer that the crew can have all the chests, because after the gold is removed they have no value? – quirky purple Sep 01 '15 at 16:02
  • I think it's supposed to be: declare how many chests he gives to the crew, then open the chests, then take note of the gold values in each chest, then give them chests of various values such that he gets most of the gold. – Kingrames Sep 01 '15 at 16:20
  • Unless I am just dumb/missing something I can't see how without knowing the distribution of the gold/silver you can say a specific number of chests will guarantee he gets half and gives the most possible chests. That is because he decides after EACH chest, if at the end he could decide to keep or give a specific chest (while still respecting the initial quantities he selected at the beginning) it would be a different scenario. Does he know the sum of the amounts before opening them? – IfTrue Sep 01 '15 at 16:26
  • 1
    @IfTrue Nothing in the question specifies, that he must give away a chest before he knows what the other chests contain. – Sleafar Sep 01 '15 at 16:35
  • @Sleafar I may be reading too much into Anachor's use of the word "each" instead of "all"/"every" in the OP when he states "After that he opens up each chest and decides which chests to keep and which to give away". In fact I think I am, I will keep trying to figure it out. – IfTrue Sep 01 '15 at 16:36
  • @IfTrue I think you could rephrase the riddle as this (Jacks point of view): "There are X chests. How many do I have to take at least to make sure I get half of the gold and silver." – Sleafar Sep 01 '15 at 16:42
  • Also given the information in the comments now, if Slefar is right in that Jack doesn't have to give away or keep each chest before opening the next I think that the note: "Without opening a chest there is no way to tell how many gold or silver it contains." is misleading as I can't see a point of why it would matter if he can open up every single chest before having to make a decision on whether to keep or give a specific individual chest. – IfTrue Sep 01 '15 at 16:49
  • @iftrue It was there to prevent answers like "weight each box and do stuff" – Rohcana Sep 01 '15 at 16:52
  • When you say "opens up each chest" door you mean "opens up all the chests" (which makes it the same as the 99 Bags of Apples and Oranges), or "opens up the chests one by one" (deciding as he goes, and before he knows what's in the remaining chests). – Dr Xorile Sep 01 '15 at 20:13

3 Answers3

5

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.

Samthere
  • 2,844
  • 13
  • 29
  • Currently the only answer I can think that makes sense. – IfTrue Sep 01 '15 at 16:42
  • You are on the right track is all I can say. – Rohcana Sep 01 '15 at 16:53
  • 2
    http://puzzling.stackexchange.com/questions/15412/ – f'' Sep 01 '15 at 17:42
  • 2
    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 :-) – SylvainD Sep 01 '15 at 18:00
  • 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. – Spacemonkey Sep 01 '15 at 18:40
  • So it has to be at least half. The article that @f'' linked to proves that you can do it with half, if you know how the coins are distributed before you make the decision. My read of the puzzle is that Jack has to decide as he's going, without knowing what's coming. Is this the difference between the puzzles? – Dr Xorile Sep 01 '15 at 18:50
3

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.

Samthere
  • 2,844
  • 13
  • 29
0

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.

quirky purple
  • 354
  • 1
  • 8
  • 2
    I think the question wants a number that Jack can distribute regardless of the distribution of gold and silver in the chests. – Ross Millikan Sep 01 '15 at 16:28