QBasic - 40lb weight problem

Over the Christmas holidays some friends and I were sat in a pub. For some reason, probably because Patty is a maths lecturer, the topic of conversation turned to mathematical problems.

A problem was set that confounded me for some time - in the end I had to write a program to help me solve it - I'm sorry to say my brain isn't agile enough for me to solve it any other way. The best I've seen anyone do with this problem is around 3 hours using just a pencil and paper. In April 2004, I received an email from Shane Bailey saying that he'd completed the problem in around five minutes, obviously the people I know weren't even trying! Shane is a founder of Ye Olde Gamers. To see how he did it, take a look at the bottom of the page - but only when you've had a go at the problem yourself.

Someone has a single 40lb weight. They drop it and it splits into four pieces. Picking up the pieces this person realises that using one, some or all of the pieces they can find the weight of any object (provided it weighs a whole number of pounds) up to and including 40lbs.

The problem isn't necessarily to do with weights - it's the mathematics of the problem that is important. What is required is four numbers whose sum is 40. These four numbers when used singly or in any combination must be able to produce any other number between the numbers 1 and 40. The mathematical functions that can be used are just addition and subtraction.

Please do not proceed further down this page until you have given some thought to this problem.

'40lbs.bas Ray Thomas Dec 1999

'A program to solve the 40lb problem

OPTION BASE 1

DIM Cmmnd AS STRING   'user input
DIM A AS INTEGER      'first number
DIM B AS INTEGER      'second number
DIM C AS INTEGER      'third number
DIM D AS INTEGER      'fourth number
DIM Total AS INTEGER  'when checking this number needs to be every number between 1 and 40
DIM ItCount AS LONG   'Number of iterations
DIM Numarray(4) AS INTEGER 'Array to hold A,B,C & D - for ease of use
DIM Test AS INTEGER   'Checks the number created againt Total
DIM Count1 AS INTEGER 'loop counter
DIM Count2 AS INTEGER 'loop counter
DIM Count3 AS INTEGER 'loop counter
DIM Count4 AS INTEGER 'loop counter

CLS
PRINT
PRINT "Four weights, which in total must weigh 40lbs, can be used to weigh any"
PRINT "item (in whole lbs). The weights can be used in any combination."
PRINT "What are the size of the weights ?"
PRINT
PRINT
PRINT "This program will attempt to solve this problem by trying all combinations"
PRINT "of four numbers that total 40, and then trying different mathematical"
PRINT "formulae on them until a solution is reached."
PRINT "This may take some time as there are 9,139 possible combinations of numbers."
PRINT
PRINT
PRINT "This seems at first sight to be a simple problem but I've got the feeling"
PRINT "that for this an intuitive brain will probably be quicker than this program."
PRINT
PRINT
PRINT "Are you ready to run this program ?"

DO
     Cmmnd$ = UCASE$(INKEY$)
LOOP UNTIL Cmmnd$ <> ""

IF Cmmnd$ <> "Y" THEN END

'*** Three loops to get the first three numbers - the fourth is gotten by ***
'*** D = 40 - A - B - C ***

CLS
PRINT
PRINT "Working please wait"
OPEN "D:\qbasic\40lb.txt" FOR OUTPUT ACCESS WRITE LOCK READ WRITE AS #1

'*** No weight may be 0lbs, so 37 is the max for any of them

FOR A = 1 TO 37
    FOR B = 1 TO 37
         IF A + B > 40 THEN EXIT FOR
         FOR C = 1 TO 37
              IF A + B + C > 39 THEN EXIT FOR
              D = 40 - A - B - C
              IF D <= 0 THEN EXIT FOR
              ItCount = ItCount + 1

'*** Put the numbers into the array

              Numarray(1) = A
              Numarray(2) = B
              Numarray(3) = C
              Numarray(4) = D

'*** It is here that things get complicated - which numbers are added and which
'*** are subtracted ?

'*** The combinations are complicated, A + or - every other number
'*** and that is only the start.

              FOR Test = 1 TO 40
                   LOCATE 4, 1
                   PRINT "Numbers being tested :-"; A; B; C; D
                   PRINT
                   PRINT "Number to be tested against"; Test
                   GOSUB Number1     'check if one number can be the total
                   IF Total <> Test THEN GOSUB Number2
                   IF Total <> Test THEN GOSUB Number3
                   IF Total <> Test THEN GOSUB Number4
                   IF Total <> Test THEN
                        PRINT #1, A; ","; B; ","; C; ","; D; "failed on"; Test
                        EXIT FOR
                   END IF

                   IF Total = 40 AND Test = 40 THEN
                        LOCATE 21, 1
                        PRINT "Possible solution found, please press any key to continue"
                        DO
                        LOOP UNTIL INKEY$ <> ""
                        LOCATE 21, 1
                        PRINT " "
                    END IF
               NEXT Test
          NEXT C
     NEXT B
NEXT A

CLOSE
END

Number1: 'Can 1 number meet the Test?

FOR Count1 = 1 TO 4
     Total = Numarray(Count1)
     IF Total = Test THEN RETURN
NEXT Count1
LOCATE 13, 1
PRINT "One number cannot reach this number"; Test
RETURN

Number2: 'Can 2 numbers meet the Test?

FOR Count1 = 1 TO 4
     FOR Count2 = 1 TO 4
          IF Count2 <> Count1 THEN
               Total = Numarray(Count1) + Numarray(Count2)
               IF Total = Test THEN RETURN
               Total = Numarray(Count1) - Numarray(Count2)
               IF Total = Test THEN RETURN
               Total = -Numarray(Count1) + Numarray(Count2)
               IF Total = Test THEN RETURN
               Total = -Numarray(Count1) - Numarray(Count2)
               IF Total = Test THEN RETURN
          END IF
     NEXT Count2
NEXT Count1
LOCATE 15, 1
PRINT "Two numbers cannot reach this number"; Test
RETURN

Number3: 'Can 3 numbers meet the Test?

FOR Count1 = 1 TO 4
     FOR Count2 = 1 TO 4
          IF Count2 <> Count1 THEN
               FOR Count3 = 1 TO 4
                    IF Count3 <> Count2 AND Count3 <> Count1 THEN
                         Total = Numarray(Count1) + Numarray(Count2) + Numarray(Count3)
                         IF Total = Test THEN RETURN
                         Total = Numarray(Count1) + Numarray(Count2) - Numarray(Count3)
                         IF Total = Test THEN RETURN
                         Total = Numarray(Count1) - Numarray(Count2) - Numarray(Count3)
                         IF Total = Test THEN RETURN
                         Total = Numarray(Count1) - Numarray(Count2) + Numarray(Count3)
                         IF Total = Test THEN RETURN
                         Total = -Numarray(Count1) + Numarray(Count2) + Numarray(Count3)
                         IF Total = Test THEN RETURN
                         Total = -Numarray(Count1) + Numarray(Count2) - Numarray(Count3)
                         IF Total = Test THEN RETURN
                         Total = -Numarray(Count1) - Numarray(Count2) - Numarray(Count3)
                         IF Total = Test THEN RETURN
                         Total = -Numarray(Count1) - Numarray(Count2) + Numarray(Count3)
                         IF Total = Test THEN RETURN
                    END IF
               NEXT Count3
          END IF
     NEXT Count2
NEXT Count1
LOCATE 17, 1
PRINT "Three numbers cannot reach this number"; Test
RETURN

Number4: 'Can 4 numbers meet the Test?

FOR Count1 = 1 TO 4
   FOR Count2 = 1 TO 4
      IF Count2 <> Count1 THEN
         FOR Count3 = 1 TO 4
            IF Count3 <> Count2 AND Count3 <> Count1 THEN
               FOR Count4 = 1 TO 4
                  IF Count4 <> Count3 AND Count4 <> Count2 AND Count4 <> Count1 THEN
                     Total = Numarray(Count1) + Numarray(Count2) + Numarray(Count3) + Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = Numarray(Count1) + Numarray(Count2) - Numarray(Count3) + Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = Numarray(Count1) - Numarray(Count2) - Numarray(Count3) + Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = Numarray(Count1) - Numarray(Count2) + Numarray(Count3) + Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = -Numarray(Count1) + Numarray(Count2) + Numarray(Count3) + Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = -Numarray(Count1) + Numarray(Count2) - Numarray(Count3) + Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = -Numarray(Count1) - Numarray(Count2) - Numarray(Count3) + Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = -Numarray(Count1) - Numarray(Count2) + Numarray(Count3) + Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = Numarray(Count1) + Numarray(Count2) + Numarray(Count3) - Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = Numarray(Count1) + Numarray(Count2) - Numarray(Count3) - Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = Numarray(Count1) - Numarray(Count2) - Numarray(Count3) - Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = Numarray(Count1) - Numarray(Count2) + Numarray(Count3) - Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = -Numarray(Count1) + Numarray(Count2) + Numarray(Count3) - Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = -Numarray(Count1) + Numarray(Count2) - Numarray(Count3) - Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = -Numarray(Count1) - Numarray(Count2) - Numarray(Count3) - Numarray(Count4)
                     IF Total = Test THEN RETURN
                     Total = -Numarray(Count1) - Numarray(Count2) + Numarray(Count3) - Numarray(Count4)
                     IF Total = Test THEN RETURN
                  END IF
               NEXT Count4
            END IF
         NEXT Count3
      END IF
   NEXT Count2
NEXT Count1
LOCATE 19, 1
PRINT "Four numbers cannot reach this number"; Test
RETURN

Despite its length this is a very simple program - all it does is take each number (1 - 40) in turn and tests whether or not any combination of one or more of the possible solutions - starting at 1,1,1,37 can fit the mathematical criteria of the problem. As soon as a 'wrong' answer is found processing is stopped and the next numbers in the series tested. For example if 1,1,1,37 is found to be false then the next number tested will be 1,1,2,36 and then 1,1,3,35 and so on.

If you would like to know the answer to the problem then scroll to the bottom of this page.