9
$\begingroup$

Bob meets a magician with two bags and a chest on a bridge. The magician challenges him with the following enigma:

  • Here is a bag A, holding 5080 pebbles.

  • Here is another bag B.

  • Most of the pebbles are unique, or very little alike, regarding the following features: size, color, origin, weight, value. You may examine each pebble as much as you like, but you can't know the pebble's value by merely looking at it. Some pebbles are tremendously much more valuable than others.

  • You are allowed to pick as many pebbles as you want from bag A and put them into the bag B. You could do that as many times as you want, but each time I will weight the bag on a magic scale. This magic scale performs an unknown, deterministic computation for around 5 seconds, based on the cumulative value of the pebbles. Afterwards, it either answers "OK" or "No it's too much.", with regard to a secret threshold only known by the magic scale.

  • When it answers "No it's too much", you have to try again. You would do that by putting back as many pebbles as you like in the bag A. You're free the examine the bag and choose carefully which pebble you want to put back. If it answers "OK", you may choose to leave and earn as many gold coins as there are pebbles in the bag B.

  • The pebbles in the bags would be of no use to anyone because no one is able to estimate their value (except for the magic scale of course), whereas gold coins are the country's currency.

  • When the sun sets and finally reaches the same height as it currently occupies, I will, if you're still here, weight the bag B one last time. If the magic scale answers "OK", I will give you as many gold coins as there are pebbles in the bag B. Then, I will depart from here.

Hearing this, Bob doesn't take very long to understand how to proceed and leave with as many coins as possible.

Note: the magician is prone to pity and may wait just a little bit if you're late, yet close to getting an "OK" from the magic scale (but only a little bit).

Edit: Fix according to remark of @dr-xorile. Also both bags can be ordered.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ How long is it until the sun sets? I don't quite understand 'reaches the same height as it currently occupies'. Also, what exactly are you asking: is it 'how much money does Bob get?' or 'what strategy should Bob use?' or what? $\endgroup$
    – ZanyG
    Feb 15, 2019 at 9:42
  • $\begingroup$ To clarify, the bit about the sun's travel is a contrived way of saying that Bob only has 24 hours, more or less. The question is "how can Bob maximize his gains", or "what strategy does Bob use to leave with as many coins as possible". $\endgroup$
    – plowsec
    Feb 15, 2019 at 10:02
  • $\begingroup$ Is the value based on the other 4 features? $\endgroup$
    – Nautilus
    Feb 15, 2019 at 12:28
  • $\begingroup$ Sometimes it is, yes, especially when the combinations of the features is very similar to another high value pebble. Also, both bags can be ordered, something that I failed to explicitly state. $\endgroup$
    – plowsec
    Feb 15, 2019 at 13:54
  • $\begingroup$ Is it possible to take pebbles out of both bags, so as to control your sample size? $\endgroup$
    – Bewilderer
    Feb 16, 2019 at 2:56

1 Answer 1

Reset to default
2
$\begingroup$

I am assuming he can partition the stones in the bag A into two or more parts by using his hands and nearby materials (his clothes and anything he can get).

First he should start by dividing the pebbles in two halves (2540), then measuring each halves to check if it's OK or not .

If none are okay

he can rearrange the pebbles for 3 or 5 times (time limit, he can change the number of times he can rearrange depending on time) and if it doesn't work then he should divide the pebbles into three parts and check for validity. He should follow similar steps as when it is in twoparts.

If one of them is ok

he should subdivide another one so as to get the maximum pebbles from the 2nd part and use it along with first half one to maximize his earning( rearrangement )

If both of the halves are okay

he can subdivide one of them, add it to the another one and again go on checking in same way until he can get maximum pebbles and hence most coin possible.

If it doesn't work

he can subdivide to four or more parts and follow similar steps. Eventually he will get the maximum number of gold coins.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nice you got it :-) Divide-and-conquer is the way to, especially because a query takes 5 seconds, independently from the number of pebbles in the bag (from your answer, I think you didn't take into account that last fact.). I have trouble seeing the advantages of splitting into three parts? Splitting in two recursively doesn't achieve what you want? $\endgroup$
    – plowsec
    Feb 17, 2019 at 9:32
  • $\begingroup$ I just wanted Bob to go to 3 parts or more if he was unable to get the 'ok' from the magic scale by using half of the pebbles (like he spent too much time rearranging them but he is not getting the result and if he felt like time is running out he can do it with less number of pebbles). (1700,1700,1680 for 3 parts and again checking it because the stones were too precious) Sorry for my bad English $\endgroup$
    – Bijay
    Feb 17, 2019 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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