23
$\begingroup$

Some number of gold, silver, and copper coins are scattered in $N$ chests. You may look into each chest and count each type of coin in them, and then select $M$ of the chests. Your goal is to have at least 50% of all the gold coins, at least 50% of all the silver coins, and at least 50% of all the copper coins. What is the minimum number $M$ that will allow you to do this, no matter how many coins there are or how they are scattered between the chests?

In other words, you need to find the minimum number $M_{min} = f(N)$, that allows you to choose at least half of each type of coins.

Example: If $N=3$, then $M_{min}=3$, because you need to take every chest in the case that one chest contains all gold coins, one chest contains all silver coins, and one chest contains all copper coins.

Example: If $N=100$, then $M_{min}<100$. Indeed, suppose that you cannot do it with $M=99$. Then whichever 99 chests you select the other 100th chest must have at least $50\%$ of some type of coins. That means that you must have at least $50\%$ of some type of coins in each chest. That would give you more than (50*100/3)% coins in total, which is impossible.

This is mathematical puzzle, not a riddle. Do not try to cheat or to find workarounds. If some rules are unclear - please ask in the comments.


Note, the formulation was reworked (leaving the mathematical part of the puzzle exactly the same). And, since a lot of answers were already posted, just to avoid confusion I site previous formulation here:

There are $N$ chests with gold, silver and copper coins in a dragon's cave. You see how many chests there are, but you have no idea how coins are distributed, and the clever dragon proposes you a hard game:

  1. You must to chose and say a number (let's call it $M$).
  2. Then you go and check out all chests, their content and select any $M$ of them.
  3. If your $M$ selected chests have less than 50% of all gold coins in the chests, or less than 50% of all silver coins, or less than 50% of copper - the dragon kills you.
  4. Then you have to prove that you selected the smallest $M$ possible. You are allowed to distribute all the coins between $N$ chests as you wish, so now dragon won't know how they are distributed.
  5. Then the dragon goes and tries to selects $M−1$ chests that have at least 50% of each type of coins in total. If he succeeds, you are dead.
  6. If you survive you get 50% of all coins and are free to go. What number you must say to survive for sure?
$\endgroup$
  • $\begingroup$ is there a condition that $M$ has to be less than $N$ and in that case will we be told the value of $N$ $\endgroup$ – skv Oct 29 '14 at 9:32
  • 1
    $\begingroup$ @skv, you know N. No conditions on M, except that it is integer and you must survive. $\endgroup$ – klm123 Oct 29 '14 at 9:33
  • 1
    $\begingroup$ Are we to assume that there are equal number of coins of each metal? $\endgroup$ – skv Oct 29 '14 at 11:39
  • 1
    $\begingroup$ But then the dragon might be smart enough to anticipate that strategy from you. $\endgroup$ – EagleV_Attnam Oct 29 '14 at 12:06
  • 1
    $\begingroup$ @supercat There might be a typo in your last sentence, but I was thinking the same thing: In the first case, you would lose if you pick M smaller than 4 (because you cannot choose less than 4 chests to have 50% of each). In the latter case you would lose if you pick M greater than 3 (because S = M-1 would be at least 3 and so the dragon could chose correctly, no matter how you redistribute the 3 coins). Maybe, klm123 can state where we went wrong. If there is nothing wrong with this thinking, the puzzle is not well defined, because there is no safe M that depends only on N. $\endgroup$ – Oguk Oct 29 '14 at 17:57
15
$\begingroup$

Easily Divisible Treasure

Lets assume that the treasure can be divided into any portions we want. This could be done with coins of different values, or with a sufficient number of coins the problem goes away on its own (see below).

If $N$ is odd, then there exists 3 numbers, $g,s,c$ such that $g+s+c=N$ and $g,s,c$ are all odd.

Then, you can split all the gold evenly amongst the $g$ gold chests, and all the silver evenly amongst the $s$ silver chests, and all the copper evenly amongst the $c$ copper chests.

Since they are all odd, you need an extra one of each, so $$M=\frac{g+1}{2} + \frac{s+1}{2}+\frac{c+1}{2}=\frac{g+s+c+3}{2}=\frac{N+1}{2}+1$$

If $N$ is even, then you can only get two odd numbered groups out of it. Thus: $$M=\frac{g}{2} + \frac{s+1}{2} + \frac{c+1}{2}=\frac{g+s+c+2}{2}=\frac{N}{2} + 1$$

So, if we select our $M$ based on these values, we should be able to guarantee that we get half of all the coins. Then we can distribute in this way to ensure the dragon cannot get half of all of them with $S=M-1$.

Discrete Coins

If the number of coins is not divisible by the size of the group, and the number of coins is small, there can be problems. For example, if there are $5$ chests and $7$ coins, then two of the chests would have $2$ coins. Instead of forcing the dragon to pick $3$ of these chests, he could get away with only those $2$ since they contain $4$ coins - over half of $7$.

If we do not know the amount of coins, it is possible that we are in either situation, in which case our $M$ would be too high if we used the method described above, or too low if we assumed the number of coins was low as in this example.

Also, if we have only a few coins and large number of chests, we are in trouble. For example, 1 coin of each means that for any $N$, we'd need to set $M=3$. If we don't know the number of coins ahead of time, we'd be eaten for sure.

Thus, this kind of thing needs to be either known ahead of time (i.e. we are told the amounts of each denomination of coin), or avoided by saying the number of coins is much greater than the number of chests. How much higher before this problem goes away? Well, if the number of coins is greater than $N(\frac{N+1}{2})$, it seems to do the trick. Why? Take a look at the following:

   Chests
1 2 3 4 5 6 7
o o o o o o o
o o o o o o o
o o o o o o o
o o o

In this example, we have 24 coins split over 7 chest as evenly as we can make it. But picking the first 3 chests gets you 12 coins, and we needed to make the dragon pick 4 chests.

By going to 31 coins, the problem goes away:

   Chests
1 2 3 4 5 6 7
o o o o o o o
o o o o o o o
o o o o o o o
o o o o o o o
o o o

Now, those first 3 chests only gets you 15 coins.

If you draw a line between these two groups you will notice we have two rectangles - a 3x5 rectangle and a 4x4 rectangle. In the 24 coin example, we had a 3x4 rectangle and a 3x4 rectangle. In order to ensure the extra chest is needed, we need to maximize the rectangle on the right. This is accomplished when it is a square. After that, additional rows will make the right rectangle always bigger than the left. For arbitrary $N$, we achieve this square when we have $N+1$ rows of coins.

However...

Is there a way to avoid the problem even if we don't have sufficient coin and we don't know that? Perhaps we can select our groups better to avoid it? For example, if we have 7 of each coin and 15 chests, the construction method above could result in: $$G:=\{2,2,1,1,1\}$$ $$S:=\{2,2,1,1,1\}$$ $$C:=\{2,2,1,1,1\}$$ Thus we'd have $M=9$ chests, but the dragon can clearly win with $S=6$.

However, if we set $\left|G\right|=\left|S\right|=7$ and $\left|C\right|=1$, we'd have: $$G:=\{1,1,1,1,1,1,1\}$$ $$S:=\{1,1,1,1,1,1,1\}$$ $$C:=\{7\}$$

We'd still have $M=9$, but any $S<M$ would fail for the dragon.

So, there will be some numbers of coins for which we can still achieve the optimal value, but we would still need to know ahead of time the number of coins of each denomination.

$\endgroup$
  • 1
    $\begingroup$ Em... I do not see any reason why "split all the gold evenly amongst the g gold chests, and all the silver evenly amongst the s silver chests, and all the copper evenly amongst the c copper chest" would be a worst case for me??? So you can deal with this case, but where is a prove that you can guaranty survival for any case?? $\endgroup$ – klm123 Oct 29 '14 at 15:05
  • $\begingroup$ @klm123 Working on that... So far is seems to be the worst case of all the examples in other answers, but is it the overall worst case? Perhaps... $\endgroup$ – Trenin Oct 29 '14 at 15:17
5
$\begingroup$

The answer

The trivial case $N=1$ has $f(1)=1$ and is kind of exceptional; this case will be ignored in all further discussion. The answer to the puzzle for $N\ge2$ depends on the parity of $N$:

If $N=2n-1$ is odd, then $f(2n-1)=n+1$.
If $N=2n$ is even, then $f(2n)=n+1$.


Proof of the lower bound

If $N=2n-1$ is odd (with $n\ge2$), we put one gold coin in the first chest, one silver coin in the second chest, and one copper coin in each of the remaining $2n-3$ chests. Then one must pick the first chest, the second chest, and at least $n-1$ of the remaining chests. This shows $f(2n-1)\ge1+1+(n-1)=n+1$.

If $N=2n$ is even (with $n\ge1$), we put one gold coin in the first chest, one silver coin in the second chest, and one copper coin in each of the remaining $2n-2$ chests. Then one must pick the first chest, the second chest, and $n-1$ of the remaining chests. This shows $f(2n)\ge1+1+(n-1)=n+1$.


An auxiliary result

We consider the special situation with an even number $2k$ of chests, where the $i$-th chest contains $g_i$ gold coins and $s_i$ silver coins. We assume without loss of generality that $g_1\le g_2\le\cdots\le g_{2k}$. We denote $g_{\max}=\max g_i=g_{2k}$ and $s_{\max}=\max s_i$. Then the following holds:

Auxiliary result: There exist a partition of the $2k$ chests into two groups with $k$ chests, such that the total amounts $G_1$ and $G_2$ of gold in the two groups and the total amounts $S_1$ and $S_2$ of silver in the two groups satisfy $|G_1-G_2|\le g_{\max}$ and $|S_1-S_2|\le s_{\max}$.

In the proof, we consider a "special" balanced partition into two groups, so that from every pair $g_{2i-1}$ and $g_{2i}$ one chest goes into one group and the other chest goes into the other group. The most unbalanced (and for us worst) way of doing this for the gold coins is to put all values $g_{2i-1}$ into the first group, and all the values $g_{2i}$ into the second group. Then $G_1\le G_2$, and furthermore $$ g_2\le g_3;~~~~~~~ g_4\le g_5;~~~~~~~ \ldots~~\ldots~~~~~~~ g_{2k-2}\le g_{2k-1};~~~~~~~ g_{2k}\le g_{\max}$$ implies $G_2\le G_1+g_{\max}$. Hence any such balanced partition satisfies the desired property $|G_1-G_2|\le g_{\max}$, and we only need to take care of the balance of the silver coins.

For the silver coins, we construct such a special balanced partition into two groups by working through the pairs $s_{2i-1}$ and $s_{2i}$ by increasing $i=1,\ldots,k$. The first step assigns $s_1$ to the first group and $s_2$ to the second group. In all further steps, we look at the current total silver amounts in both groups and assign the larger of $s_{2i-1}$ and $s_{2i}$ to the group with smaller silver value and the smaller of $s_{2i-1}$ and $s_{2i}$ to the group with larger silver value.

Then the difference between the two silver values always remains below $s_{\max}$: This is true at the very beginning, and is easy to check that each step maintains this property. Hence, in the end we will have the desired $|S_1-S_2|\le s_{\max}$. This completes the proof of the auxiliary result.


Proof of the upper bound

(The even case). If $N=2n$ is even (with $n\ge1$), we pick two chests that contain $g_{\max}$ gold coins and $s_{\max}$ silver coins. The remaining $2n-2$ chests are partitioned into two specially balanced groups with $n-1$ chests according to our auxiliary result. We pick the group that has higher copper value for us.

  • The total gold value that we did not pick is the gold value $G_1$ in the unpicked group. Since $G_1\le G_2+g_{\max}$ by the auxiliary result, we have picked at least half of the total gold.
  • The total silver value that we did not pick is the silver value $S_1$ in the unpicked group. Since $S_1\le S_2+s_{\max}$ by the auxiliary result, we have picked at least half of the total silver.
  • The total copper value that we did not pick is the copper value $C_1$ in the unpicked group. Since the picked group has copper value $C_2\ge C_1$, we have picked at least half of the total copper.

Since altogether we have picked $n+1$ chests, this shows $f(2n)\le n+1$ and completes the analysis of the even case.

(The odd case). If $N=2n-1$ is odd (with $n\ge2$), we first pick an arbitrary chest and then pick $n$ from the remaining $2n-2$ chests according to the solution of the even case. This altogether yields $n+1$ chests and shows $f(2n-1)\le n+1$ and completes the analysis of the odd case.

$\endgroup$
  • 1
    $\begingroup$ +1 I had to read through it a bit, but I understand it all and can vouch for its correctness. Nice work! $\endgroup$ – Trenin Feb 23 '15 at 17:57
3
$\begingroup$

Let's say we have only gold and N = 3, we know that M would have to equal 2, since the dragon could evenly divide the gold between the chests. If we add 2 more metals and bump N to 9, M would have to be 6, by the same principle.

So, a basic method would be to take Ceil(N/6) * 3. Divide by 6 since we have 3 groups and need at least half. Multiply by 3 because we have the three metals.

Edit: After a counter point, I have a new thought: Ceil(N/2) + 1. For 5 chests, the dragon could go Gold, Silver, 1/3 Cop, 1/3 Cop, 1/3 Cop for 4 chests. For 9 chests, 1 gold, 1 silver, 7 copper = 6 chests, the same as we've established for equal distribution w/o mixing.

$\endgroup$
  • $\begingroup$ For N=6 the dragon would simply need to put all the gold in one chest, all the silver in another chest and then divide the other type into the remaining 4 chests and then you wouldn't be able to win. what if you choose FLOOR(n/2 + 1)? $\endgroup$ – Bozman Oct 29 '14 at 13:33
  • $\begingroup$ You pointed out a good counter point, but your idea wouldn't quite work either. If N = 9, the dragon could make it so you'd have to open 6 chests, whereas your formula would only give 5. $\endgroup$ – JonTheMon Oct 29 '14 at 13:37
  • $\begingroup$ so is S = FLOOR(n/2+1) or your equation and then M would be that plus 1? aren't you dead regardless if the number of coins is less than M? like one of each of a coin and then any number of chests greater than 6 and you are essentially dead regardless of the M you choose unless you somehow choose 3. $\endgroup$ – Bozman Oct 29 '14 at 13:50
  • $\begingroup$ My formula is for finding M, the minimum number of chests you need to open to make sure you get past step 3. After that, just use the correct method to make sure that M is the smallest number, so M-1 won't get you killed by the dragon $\endgroup$ – JonTheMon Oct 29 '14 at 13:55
  • 1
    $\begingroup$ Ceil of 3/2 is 2, and 2+1 = 3 $\endgroup$ – JonTheMon Oct 30 '14 at 12:41
3
$\begingroup$

I think you have alluded to the most challenging distribution. The chests are divided into $G$ chests containing one (or the same number) of gold coins, $S$ containing one silver coin, and $C$ containing one copper coin, with $G+S+C=N$ I need to choose $\lceil \frac G2 \rceil +\lceil \frac S2 \rceil +\lceil \frac C2 \rceil $ of them. If $N$ is odd, all three numbers may be odd, so $M=\frac {N+3}2$ as all of them may need to round up. If $M$ is even, only two can be odd, so $M=\frac {N+2}2$

This is not a full answer, as if the coins do not distribute evenly you may be able to do better. Let there be $9$ chests and $4$ of each kind of coin. The above would say $M=6$, but if you make three chests of each type there will be one of each type with two coins and you can just take those three. We can show that $M=5$ by putting all the gold coins in one chest and each other coin in its own chest in that case.

$\endgroup$
  • $\begingroup$ So how do you guaranty survival with this M for any possible coins distributions? $\endgroup$ – klm123 Oct 29 '14 at 15:08
  • 1
    $\begingroup$ Intuitively, it seems mixing coins should just make it easier. I can't see a nice way to make that precise. It would be nice to say that if you have a solution with mixed coins, you can move the coins to sort them into chests containing just one type of coin and the same set of chests will solve the second problem. But it isn't obvious. $\endgroup$ – Ross Millikan Oct 29 '14 at 15:41
1
$\begingroup$

The dragon made the rules and the dragon wants to kill you. Since you get to look in the chests before choosing them, the dragon must spread the coins evenly.

Imagine the dragon put all the gold in one chest, all the silver in another, and all the copper in a third. You've chosen M to be 50 out of 100 - just make sure you include those 3 in your 50. If any chest has more than its share of the coins, you can include it in your list of M chests. The only way the dragon wins here is if you choose a number smaller than 50, but the coins are spread evenly among all the chests.

So if all the coins are spread evenly you need to choose N/2. (Unless it's a very small number of chests. Here the dragon could put a different type in each of 3 chests and you need to choose 3 to be sure you won't get killed on the first try. You can't guess less than 3 to protect against this strategy. ) You don't even need to rearrange anything if the dragon did the right thing, there will be less than half in the dragon's M-1 chests. If the dragon did the wrong thing, go ahead and rearrange the coins to be evenly shared among all the chests. You will always win.

$\endgroup$
  • $\begingroup$ No, you don't get to look before announcing $M$. $\endgroup$ – Trenin Oct 29 '14 at 13:25
  • $\begingroup$ Say you have 21 chests (not a small number) so by your theory, $M=11$ should suffice right? But if I split them into 3 groups of 7 and put $\frac{1}{7}$th of the copper in each of the first 7, and $\frac{1}{7}$th of the silver in each of the second group of 7, and also for the gold, then you would need to pick 4 chests from each group to get half of each - i.e. 12 chests. Thus, you'd die. $\endgroup$ – Trenin Oct 29 '14 at 13:39
  • $\begingroup$ ok, so the dragon has to spread each coin evenly - if one chest has more than its share of gold you'll choose it - but must separate the types. So M must be a multiple of 3. Figure N/2 and then bump up to the next multiple of 3. $\endgroup$ – Kate Gregory Oct 29 '14 at 13:44
  • $\begingroup$ Check out my answer - the goal in redistribution should be to make an odd number of each group. $\endgroup$ – Trenin Oct 29 '14 at 13:58
  • $\begingroup$ yes @Trenin I think you've got it. Just rounding up to next 3 might make M too high and give the dragon room to slide in at M-1 for some Ns. $\endgroup$ – Kate Gregory Oct 29 '14 at 13:59
0
$\begingroup$

If you end up with $M = 2$, and you've got at least $3$ (and uneven) coins of two different metals, you are safe. Then you can distribute those coins such that there is $>50\%$ of one metal in one chest, and $>50\%$ of the other metal in the other chest. In that way, the dragon cannot pick $S$ (=1) chests that have $>50\%$ of all coins in total.

(note that this isn't put here as full answer, because you have no way to control $M=2$, more as a sort of hint/thinking idea for others, or partial answer (in case there is the opportunity that the initial chests are so distributed that my initial requirements are met.)

$\endgroup$
0
$\begingroup$

First it's easy to see that if $N\le3$ then $M = N$

For $M\gt3$ Let's divide the question based on whether $N \equiv 0 \mod 3$ or not.

If $N$ is divisible by three, then you would distribute the chests into three parts, and put even amount of coins into each of the chests. If we normalize the amount of coins to $1$ then this means you have $1/(N/3) = \frac{3}{N}$ coins in each chest. You need to open up at least $\lceil 1/\frac{3}{N}/2 \rceil = \lceil \frac{N}{6} \rceil $ chests for each coin type, so a total of $M = 3 \lceil\frac{N}{6}\rceil$.

If you chose one less than this value, then by the algorithm above you can distribute the coins in a way that you will not get enough coins for one of the coin types.

If N is not divisible by three, then decrease the number of chests for one type of coin by one or two, and distribute the coins the same way as before (but one of the coins will have less chests, so the amounts will be different) This results in $M_{G,S} = \lceil \frac{N}{6} \rceil$ but $M_C = \lceil \frac{N-N\%3}{6}\rceil$.

This gives an end result of

$M = M_G + M_S + M_C = \lceil \frac{N}{6} \rceil + \lceil \frac{N}{6} \rceil + \lceil \frac{N-N\%3}{6}\rceil$

Some values for small Ns:

N  M
1  1
2  2
3  3
4  3
5  3
6  3
7  5
8  5
9  6
10 6
11 6
12 6
13 8

For example for $N=7$ you would distribute the coins as follows:

1: 1/3 G
2: 1/3 G
3: 1/3 G
4: 1/3 S
5: 1/3 S
6: 1/3 S
7: 1   C

you'll need to open up 1,2,4,5,7 (5) to get the necessary amount of coins. In case of $N=8$ it is similar, but the coppers are distributed evenly into to 7th and 8th chest. The end result remains the same.

$\endgroup$
  • $\begingroup$ By this method, if $N=7$, you'd have $\frac{1}{3}$ of the copper coins in the first three chests, $\frac{1}{2}$ of the silver in the next $2$, and $\frac{1}{2}$ of the gold in the last $2$. By picking $M=4$, I could get half of everything - 2 copper chests, and one each of gold and silver. $\endgroup$ – Trenin Oct 29 '14 at 13:34
  • $\begingroup$ At $N=7$ you would distribute G:$1/3$,$1/3$,$1/3$ S:$1/3$,$1/3$,$1/3$ C:$1$. You'd need to open up 5 chests to get half of each (2 chests for gold, 2 chests for silver and all of the copper from as the 5th), 4 would not be enough for this scenario $\endgroup$ – SztupY Oct 29 '14 at 13:38
  • $\begingroup$ What about for $N=11$ if I did the following: Gold: 5 groups of $\frac{1}{5}$, Copper and Silver: 3 groups of $\frac{1}{3}$. By your calculation, you'd need 6, but in this scenario, you'd need 3 gold and 2 each of copper and silver for a total of 7. $\endgroup$ – Trenin Oct 29 '14 at 13:43
  • $\begingroup$ @Trenin: that's true though. I have to add a scenario where it's better to use differnet values for both silver and copper not just for one of them. $\endgroup$ – SztupY Oct 29 '14 at 13:48
  • $\begingroup$ actually for $N=12$ M is also 7 and not 6. I have to add provisions to try to prefer odd number of chests whenever possible (as an odd amount of chests will increase the required number of chests by one) $\endgroup$ – SztupY Oct 29 '14 at 13:54
-3
$\begingroup$

Number 1.

  1. If the dragon can say a number $S<M$ and then go and selects $S$ chests that have at least $50\%$ of each type of coins in total, then you are dead too.

In that sense, the dragon have to say a number smaller than my number (in this case, $1$). So the only logical whole number smaller than 1 has to be 0. Therefore, he picks 0 chests, which means 0 coins.

$\endgroup$
  • 2
    $\begingroup$ good answer but if there are three chests containing each metal you would end up being dead even before the second part that you have solved begins $\endgroup$ – skv Oct 29 '14 at 9:33
  • $\begingroup$ Ahhh yes. I knew it couldn't be that easy. $\endgroup$ – FortMauris Oct 29 '14 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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