Wednesday, 22 July 2015

mathematics - How to choose at least half of everything




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?




No comments:

Post a Comment

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...