Lynsey is a biology student. Her project for this term is measuring the effect of an increase in vitamin C in the diet of twenty-five laboratory mice. Each mouse will have a different diet supplement of between 1 to 50 units. Fractions of a unit are not possible.

Although the university pays for the mice's food, Lynsey has to buy the vitamin C supplement herself. This first consideration in designing this experiment was therefore to minimize the total number of supplements. The second consideration was that no mouse should have an exact multiple of another mouse's supplement. Thus, if one mouse was on a supplement of 14 units, then this would preclude supplements of 1, 2, 7, 28, and 42 units.

What supplements should Lynsey use?

DECLARE SUB addon (n#)
DEFDBL A-Z
CLEAR , , 25000
DIM SHARED h(25), tot, mintot, hmin(25)

mintot = 999999
CLS
OPEN "mice supplements.txt" FOR OUTPUT AS #2

FOR a = 1 TO 25
    h(1) = a
    addon 2
NEXT
FOR j = 1 TO 25
    PRINT hmin(j);
NEXT
PRINT
PRINT mintot
CLOSE 2

SUB addon (n)
STATIC good, j
FOR i = h(n - 1) TO n + 25
    good = 1
    FOR j = 1 TO n - 1
        IF i MOD h(j) = 0 THEN good = 0: EXIT FOR
    NEXT
    IF good THEN
        h(n) = i
        IF n = 25 THEN
            tot = 0
            FOR j = 1 TO 25
                PRINT h(j);
                PRINT #2, h(j);
                tot = tot + h(j)
            NEXT: PRINT: PRINT #2, "= "; tot
            IF tot < mintot THEN
                mintot = tot
                FOR j = 1 TO 25
                    hmin(j) = h(j)
                NEXT: PRINT
            END IF
        ELSE
            addon n + 1
        END IF
    END IF
NEXT
END SUB

finds that the least total is provided by:

8 + 12 + 14 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 25 + 26 + 27 + 29 + 30 + 31 + 33 + 35 + 37 + 39 + 41 + 43 + 45 + 47 + 49 =  711

No addend is a multiple of any other and the total of 711 is the minimum to have that property.

Posted by Charlie on 2013-05-22 17:32:03