Mfcttrf

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

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.

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+frac161+frac164=:Ssimeq3.207$, so the closest two must be less than $2^-27S<2.4times10^-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+frac110+frac115$.

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.966times10^-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.966times10^-9$.

A smaller upper bound still

Same idea again; now let's take a different set of 16 smallish numbers: $frac133-frac134,dots,frac163-frac164$. 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.316times10^-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 $frac125-frac126$, 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.616times10^-13$.