How to choose at least half of everything

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.)

Answer 7

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.

Answer 8

Number 1.

5. 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.