12
$\begingroup$

Your package from Orinoco has finally arrived!

It's the Master Chef's Environmentally-Friendly Measuring Cup Set. It comes with 64 measuring cups having a volume of 1 cup, 1/2 cup, 1/3 cup, 1/4 cup, ..., all the way down to 1/64 cup.

Because these are master chef's cups, they have master features:

  • when in the presence of sufficient ingredient to fill themselves completely, they instantly fill to capacity with the ingredient at the command "riempire!"
  • when not in the presence of sufficient ingredient to fill themselves completely, the command "riempire!" does nothing
  • when full, they instantly and completely empty themselves at the command "vuotare!"

Because these are also environmentally-friendly cups, each cup instantly dissolves into fresh mountain air after one use (that is, upon being emptied). No waste, no pollution.

You have a giant 25 US gallon tub of nutmeg and an empty 1 gallon soup pot. As a master chef, you know that the best soups must have some nutmeg in them, but ideally as little as possible, making for perfectly nuanced flavour.

Using only your set of 64 single-use cups to transfer nutmeg between your nutmeg tub and soup bowl, both to and from, what is the smallest nonzero amount of nutmeg you can leave in your soup bowl?

For example, you could transfer 1/2 cup, then 1/3 cup, then 1/4 cup of nutmeg to the soup bowl, then 1 cup back to the tub to be left with 1/12 cup in the soup bowl.

There is, of course, an optimal solution to the puzzle, but it's extremely hard to intuit (in my opinion), hence everyone's best attempts are welcome. The lower, the better!

(Disclaimer: This problem is, at its core, mathematical. It isn't a lateral thinking puzzle, there are no tricks, and you can disregard any realistic physical limitations such as errors in measurement or being left with an unreasonably tiny quantity of nutmeg.)

$\endgroup$
  • $\begingroup$ I feel like you an I would get along splendidly. May we infer computery people may do computery things? (also you might want to add the optimization tag) $\endgroup$ – Dark Thunder Jun 27 at 20:09
  • $\begingroup$ My intuition is that it's base64(MS9sY20oMSwyLC4uLjY0KQ==) but I can't explain that $\endgroup$ – RShields Jun 27 at 20:11
  • 1
    $\begingroup$ It would be a heavy brute force for a computer. Each cup may be used for -1, 0 or +1 operations so there are $3^{64}$ permutations of their capacities. $\endgroup$ – Weather Vane Jun 27 at 20:11
  • 3
    $\begingroup$ @RShields "each cup instantly dissolves into fresh mountain air after one use." $\endgroup$ – Weather Vane Jun 27 at 20:15
  • 1
    $\begingroup$ @WeatherVane: Thanks for the heads-up. I've added the 'optimization' tag, as suggested in the meta thread and by Dark Thunder earlier. It is a true puzzle in the sense of having only one correct solution. Many of my favourite puzzles on this site are optimization questions. The "blanket for baby snake" puzzle, for instance. $\endgroup$ – COTO Jun 28 at 19:23
6
$\begingroup$

Edit: as @DarkThunder pointed out, this is incorrect.

My most perfect soup contains

$1.483936579 \times 10^{-15}$, or $\frac{3}{2021649740510400}$ cups of nutmeg.

The lowest common multiple of the divisors of the cup sizes is $2021649740510400$.
Each cup can be expressed as a number of units of that, so I can work in integers.
Ideally I wanted the smallest amount of nutmeg to be one unit, $\frac{1}{2021649740510400}$ cups.

The obvious brute force method is ruled out as impractical so I first prepared an array of permutations of the smallest cups. I then examined permutations of the larger cups, ruling out any that are impossible, for example if my best result is 2, the sum of the cups used is 10 and the sum of the cups remaining is 5 then it is not worth proceeding through the rest of the cups. When the recursion reaches the smallest cups I make a binary search of the sorted array I made earlier.

The result uses the following cups (their fractions):

-1 -2 -3 -4 +6 +7 +8 +9 +10 +11 +12 +13 +14 +15 +16 +18 +19 +20 +22 +23 +24 +25 +26 +27 +28 +29 +30 +31 +32 +33 +35 +36 +37 +38 +39 +40 -41 +42 +43 +46 +48 +49 +51 +52 +53 -55 +56 -57 +58 +59 +60 +62 +63 +64.

Not all the cups are used.
However, I did not complete the search and I think the optimal solution will be one unit, that is

$4.9464552 \times 10^{-16}$ cups of nutmeg, or $\frac{1}{2021649740510400}$ cups.

But I can't prove it.

$\endgroup$
  • $\begingroup$ Very nicely done. $\endgroup$ – COTO Jun 28 at 10:19
  • 1
    $\begingroup$ Looking good! Because of your formulation, I'm fairly sure that this nutmeg problem reduces to the (NP-complete) subset sum problem, so there may not be any efficient way of searching for a better answer, nor indeed any way to verify whether your proposed optimum is achievable. en.wikipedia.org/wiki/Subset_sum_problem $\endgroup$ – ymbirtt Jun 28 at 12:46
  • $\begingroup$ @ymbirtt despite the efficiencies I tried to make the recursion is still running, probably won't end any time soon, and I was lucky to have hit on this answer. I think this is essentially a "scales" problem to find the minimal imbalance between the two sides. So where I might go from here is to take this solution and try a swapping exercise between the sides, and the unused cups. $\endgroup$ – Weather Vane Jun 28 at 12:53
  • $\begingroup$ I hate to ask, because I'm sure I'm just missing something, but why do I get a different number when I find the least common denominator? Using your number I don't get an integer for the 1/37 cup, for example. $\endgroup$ – Dark Thunder Jun 28 at 14:48
  • $\begingroup$ @DarkThunder good spot: you are quite right - nor 41, 43, 47, 53, 59 or 61. Stupidly, I only considered the primes up to half of 64 when computing the LCM, I don't know why. That means the LCM will no longer fit a 64-bit integer, so I'll have to delete this answer. It also means the potential answer can be a lot smaller. Please let me know when you've seen this comment. $\endgroup$ – Weather Vane Jun 28 at 15:04
5
$\begingroup$

An upper bound

Consider just the cups with prime-power sizes: the reciprocals of 1,2,3,4,7,8,9,11,13,16,17,19,23,25,27,29,31,32,37,41,43,47,49,53,59,61,64. No two sums of subsets of these are equal. (Proof: easy exercise.) There are $2^{27}$ such subsets and their sums all lie between 0 and $\frac11+\cdots+\frac1{61}+\frac1{64}=:S\simeq3.207$, so the closest two must be less than $2^{-27}S<2.4\times10^{-8}$ apart.

This can surely be improved substantially because

there are surely larger subsets with the property that no two sums-of-subsets are equal. Note that this isn't true for the whole set, because e.g. $\frac13=\frac16+\frac1{10}+\frac1{15}$.

Another (smaller) upper-bound

Applying a bit of brute force,

let's begin by making some smallish numbers by taking $a-b-c+d$ where a,b,c,d are the reciprocals of 1,2,3,4; 5,6,7,8; ...; 61,62,63,64. This gives us 16 numbers. That's few enough that we can now find all the sums of subsets of these, sort them, and look for the smallest difference. That turns out to be about $3.966\times10^{-9}$. Writing $S(1),S(5),\dots$ for the sums above, it turns out that $S(33)+S(37)-S(41)-S(45)-S(49)-S(53)-S(57)\simeq3.966\times10^{-9}$.

A smaller upper bound still

Same idea again; now let's take a different set of 16 smallish numbers: $\frac1{33}-\frac1{34},\dots,\frac1{63}-\frac1{64}$. Again, it's pretty quick to find all the sums of subsets, etc. This time, if we call those differences $D(33)$ etc., we find that $-D(35)+D(39)-D(47)-D(51)+D(53)+D(55)+D(59)+D(61)-D(63)\simeq2.316\times10^{-10}$.

And smaller still

There's no particular reason to consider $2^{16}$ an upper limit on how much tedium to endure :-). Repeating the previous calculation but starting at $\frac1{25}-\frac1{26}$, so that now there are $2^{20}$ possible subset-sums, we find that (with a hopefully-obvious abuse of notation to reduce the length of this unwieldy formula) $D((25+27-29+31-33-37-39-45+47-49-53+55-57+59+61-63))\simeq7.616\times10^{-13}$.

$\endgroup$
  • $\begingroup$ This kind of divide-and-conquer approach is very similar to the best that I was able to come up with. $\endgroup$ – COTO Jun 28 at 1:39
  • $\begingroup$ It seems clear that the same approach can be pushed further, at the cost of increasing brute force. $\endgroup$ – Gareth McCaughan Jun 28 at 1:40
  • $\begingroup$ My gut feel is that the optimal solution can be proved without brute force. ...But my gut also told me that I'd have an answer: "Oh, this is just the famous XYZ problem with n = 64. Gauss proved during a 2-minute bathroom break that the lower limit is ABC." within 30 minutes of posting the question, since I can count on one hand the number of times this hasn't happened to me. Hence my gut may not be all that reliable a witness here. ;) $\endgroup$ – COTO Jun 28 at 1:53
2
$\begingroup$

0k I'll start with my intuition which probably is not the best one, but you can outdo me now ;) .

Idea:

You start with cup $1$, then you substract from it $1/2$, then $1/3$, then $1/4$. Now your value is negative so you add $1/5$.
Basically if your currrent value is negative, you add the next cup and if it's positive you substract.

Java code:

res = 1;
for(int i = 2; i < 63; i++){
if(res > 0) {
res -= 1.0 / i;
} else {
res += 1.0 / i;
}
} System.out.print(res);

Result:

$2.3499E-6$

Note:

It is not bad that the stand in the soup bowl is sometimes negative, the master chef can first perform all positive operations and then all negative.

Other idea:

I agree @Weather Vane in his assumption, that the smallest amount could be $1/2021649740510400$. To proof that maybe you can start with amounts of $1/1$ and $1/2$, the smallest common multiple is $2$, so the smallest amount is $2/2 - 1/2 = 1/2$. Then you take amounts of $1/1, 1/2, 1/3, 1/4$. The smallest common multiple is $12$. So you have to look if you can make 1 with numbers: $12,6,4,3 --> 6 + 4 + 3 - 12 = 1$. So the smallest amount you can make is $1/12.$ Then with $2^3$ amounts. $1/1, 1/2, 1/3, ..., 1/8$. The smallest common multiple is $840$. So you have to make $1$ with $840,420,280,210,168,140,120,105$. And so on... Maybe you can prove it that way...

$\endgroup$
  • $\begingroup$ Did you notice that using cups down to 1/8 cannot make a 1? Most of them are multiples of 10 so that's not hard to prove. Luckily we use base 10 or that may not have been as obvious. I was playing around with that set by hand and best I can get down to is 7. $\endgroup$ – Dark Thunder Jun 28 at 15:28
  • $\begingroup$ Oh ok, you are right. I think my best was 2, but with only 2 numbers 16!8! and 10!5! wich aren't multiples of 10 it is clear that you can't reach 1. $\endgroup$ – Matti Jun 28 at 15:41
1
$\begingroup$

An initial lower Bound

Let $L$ be the least common multiple of the numbers 1 through 64 then $L = 1182266884102822267511361600$. We can express the amount in the $i$th cup as an integer $n_i$ divided by $L$ where $n_i = L/i$ and we can express whether or not we subtracted, didn't use or added that cup as $c_i \in \{-1,0,1\}$, then the total fraction after all the cups uses will be $\sum_{i=0}^{64} c_i\frac{n_i}{L} = \frac{\sum_{i=0}^{64} c_i × n_i}{L}$ thus since the numerator is an integer and must be greater than 0 our first lower bound is $1/L \approx 8.46 × 10^{-27}$

Finding a better lower bound

Lets call the numerator from above $N = \sum_{i=0}^{64} c_i × n_i$. Now lets consider the value of $N \pmod{p}$ for some prime $p$. Any of the initial cups which did not have $p$ as a factor of their denominator will have their $n_i$ divisible by $p$ and always contribute $0$ to $N\pmod{p}$ so only cups where $i$ divides $p$ matter for this calculation. For example if $p=61$ we have $n_{61} \pmod{p} = 32$ and $-n_{61} \pmod{p} = 29$ therefore $N \pmod{61} \in \{0,29,32\}$ and we have a new lower bound of $29/L \approx 2.45 × 10^{-26}$

Doing a bit better with some brute force

Now lets consider $N \pmod{q}$ where $q$ is the product of multiple primes. By the same logic as above, any $n_i$ which for which $i$ is relatively prime to $q$ will contribute 0 so we only have to consider the numbers which share at least one factor with $q$. I wrote a little java program to check all possible values for $N \pmod{q}$ with $q=17×19×23×29×31×37×41×43×47×53×59×61$ and got a new lower bound of $27322970884/L \approx 2.45 × 10^{-17}$

The code used : https://pastebin.com/8nQ9UgBP

Notes about the code:

I got the same lower bound with or without multiples of 17 included, so I commented them out of the pasted version so the run time would under about 2 minutes instead of around 40 (I'd estimate that including 13 would take me 50+ hours to run). Also there is room for about a 10x optimization by considering situations like $n_{p}, n_{2p}, n_{3p}$ as $b × n_{3p}$ with $b \in \{-6,-5,...,5,6\}$, this would avoid double counting values that can be made in multiple ways with those numbers.

$\endgroup$
-3
$\begingroup$

since they are 1/64th increments, you can be left with a minimum of 1/64th of a cup. Add 1 cup, remove 1/2 cup, remove 1/4 cup, remove 1/8 cup, remove 1/16 cup, remove 1/32 cup, remove 1/64 cup, there is 1/64th of a cup left.

$\endgroup$
  • 2
    $\begingroup$ What if you start with 1/63 cup and remove 1/64 cup? $\endgroup$ – Jay Jun 28 at 5:50
  • 1
    $\begingroup$ @Jay: true, I was caught up with halving it $\endgroup$ – Adrian Howard Jun 28 at 5:55

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.