A copy machine features 7 buttons for making copies, ranging from 10% to 625% in size. The buttons are: 10%, 80%, 100%, 125%, 128%, 512%, 625%.

If the 100% button breaks down, how can you make a 100% copy in a minimum number of steps using:

(i) Each of the buttons 10%, 80% and 625% at least once?

(ii) Each of the buttons 10%, 512% and 625% at least once?

(iii) Each of the buttons 10%, 80%, 512% and 625% at least once?

(iv) Each of the buttons 10%, 80%, 128%, 512% and 625% at least once?

(v) Each of the buttons 10%, 80%, 125%, 128%, 512% and 625% at least once?

Note: In each of the five cases only the specified buttons must be used. Utilization of any button(s) not included in a given case is not permissible.

10% = 1/10 = 1/(2*5)
80% = 4/5 = 2*2/5
125% = 5/4 = 5/(2*2)
128% = 2^7/10^2 = 2^5/(5*5)
512% = 2^9/10^2 = 2^7/(5*5)
625% = 5^4/10^2 = 5*5/2*2

which leads to needing to find sums of powers of 2 and of 5 that lead to a net of zero for each, for which the following program searches, starting with the lowest total number of copies.

DEFDBL A-Z

CLS

found = 0
FOR tot = 1 TO 100
  FOR n1 = 1 TO tot - 2
  FOR n2 = 1 TO tot - n1 - 1
  FOR n6 = 1 TO tot - n1 - n2
    p2 = 2 * n2 - 2 * n6 - n1
    p5 = -n2 + 2 * n6 - n1
    IF p2 = 0 AND p5 = 0 THEN found = 1: PRINT "(i) "; n1; n2; n6; TAB(25); tot
  NEXT
  NEXT
  NEXT
  IF found THEN EXIT FOR
NEXT
found1:

found = 0
FOR tot = 1 TO 100
  FOR n1 = 1 TO tot - 2
  FOR n5 = 1 TO tot - n1 - 1
  FOR n6 = 1 TO tot - n1 - n5
    p2 = 7 * n5 - 2 * n6 - n1
    p5 = -2 * n5 + 2 * n6 - n1
    IF p2 = 0 AND p5 = 0 THEN found = 1: PRINT "(ii) "; n1; n5; n6; TAB(25); tot
  NEXT
  NEXT
  NEXT
  IF found THEN EXIT FOR
NEXT

found = 0
FOR tot = 1 TO 100
  FOR n1 = 1 TO tot - 3
  FOR n2 = 1 TO tot - n1 - 2
  FOR n5 = 1 TO tot - n1 - n2 - n4 - 1
  FOR n6 = 1 TO tot - n1 - n2 - n4 - n5
    p2 = 2 * n2 + 7 * n5 - 2 * n6 - n1
    p5 = -n2 - 2 * n5 + 2 * n6 - n1
    IF p2 = 0 AND p5 = 0 THEN found = 1:   PRINT "(iii) "; n1; n2; n5; n6; TAB(25); tot
  NEXT
  NEXT
  NEXT
  NEXT
  IF found THEN EXIT FOR
NEXT

found = 0
FOR tot = 1 TO 100
  FOR n1 = 1 TO tot - 4
  FOR n2 = 1 TO tot - n1 - 3
  FOR n4 = 1 TO tot - n1 - n2 - 2
  FOR n5 = 1 TO tot - n1 - n2 - n4 - 1
  FOR n6 = 1 TO tot - n1 - n2 - n4 - n5
    p2 = 2 * n2 + 5 * n4 + 7 * n5 - 2 * n6 - n1
    p5 = -n2 - 2 * n4 - 2 * n5 + 2 * n6 - n1
    IF p2 = 0 AND p5 = 0 THEN found = 1:   PRINT "(iv) "; n1; n2; n4; n5; n6; TAB(25); tot
  NEXT
  NEXT
  NEXT
  NEXT
  NEXT
  IF found THEN EXIT FOR
NEXT

found = 0
FOR tot = 1 TO 100
  FOR n1 = 1 TO tot - 5
  FOR n2 = 1 TO tot - n1 - 4
  FOR n3 = 1 TO tot - n1 - n2 - 3
  FOR n4 = 1 TO tot - n1 - n2 - 2
  FOR n5 = 1 TO tot - n1 - n2 - n4 - 1
  FOR n6 = 1 TO tot - n1 - n2 - n4 - n5
    p2 = 2 * n2 - 2 * n3 + 5 * n4 + 7 * n5 - 2 * n6 - n1
    p5 = -n2 + n3 - 2 * n4 - 2 * n5 + 2 * n6 - n1
    IF p2 = 0 AND p5 = 0 THEN found = 1:   PRINT "(v) "; n1; n2; n3; n4; n5; n6; TAB(25); tot
  NEXT
  NEXT
  NEXT
  NEXT
  NEXT
  NEXT
  IF found THEN EXIT FOR
NEXT

finds

(i)  2  4  3             9
(ii)  10  4  9           23
(iii)  3  1  1  3        8
(iv)  7  1  1  2  7      18
(v)  2  1  5  1  1  1    11
(v)  4  1  1  1  1  4    11 **

where each line lists, in order of the buttons as mentioned in the particular part of the puzzle, the number of times that button is to be used. At the end is the total generations of copy made for that part. Note there are two solutions for part (v). **

So:
(i) .10^2 * .80^4 * 6.25^3 = 1
(ii)  .10^10 * 5.12^4 * 6.25^9 = 1      
(iii)  .10^3 * .80^1 * 5.12^1 * 6.25^3 = 1   
(iv)  .10^7 * .80^1 * 1.28^1 * 5.12^2 * 6.25^7 = 1  
(v)  .10^2 * .80^1 * 1.25^5 * 1.28^1 * 5.12^1 * 6.25^1 = 1
(v)  .10^4 * .80^1 * 1.25^1 * 1.28^1 * 5.12^1 * 6.25^4 = 1 **

so there are actually two solutions for the minimum number of generations (11) of copies for part (v). **

** See a later post as to why the second "solution" to part (v) is not in fact a solution as the total actually adds to 12, not 11.

Edited on July 22, 2012, 10:48 am

Posted by Charlie on 2012-07-21 16:47:49