I'm thinking of four positive integers A, B, C, and D. A>B>C>D is true.

I have written down another inequality that is also true, but I'm not showing it to you. This inequality puts the following values in order from greatest to smallest:
A, A+C, B, A+D, C, B+C, D, B+D, A+B, C+D
(this is obviously not the order, as A+C can't be less than A or less than C)

I showed the two inequalities to my friend, and he was able to minimize A, B, C, and D all at once. I told him that he had just guessed correctly which numbers were on my mind.

Based only on this information, what is the highest possible sum of the four numbers on my mind?

If we label the possible orders with numbers as follows:

 1 a+b > a+c > a+d > a > b+c > b+d > b > c+d > c > d
 2 a+b > a+c > a+d > a > b+c > b+d > c+d > b > c > d
 3 a+b > a+c > a+d > b+c > a > b+d > b > c+d > c > d
 4 a+b > a+c > a+d > b+c > a > b+d > c+d > b > c > d
 5 a+b > a+c > a+d > b+c > b+d > a > b > c+d > c > d
 6 a+b > a+c > a+d > b+c > b+d > a > c+d > b > c > d
 7 a+b > a+c > a+d > b+c > b+d > c+d > a > b > c > d
 8 a+b > a+c > b+c > a+d > a > b+d > b > c+d > c > d
 9 a+b > a+c > b+c > a+d > a > b+d > c+d > b > c > d
10 a+b > a+c > b+c > a+d > b+d > a > b > c+d > c > d
11 a+b > a+c > b+c > a+d > b+d > a > c+d > b > c > d
12 a+b > a+c > b+c > a+d > b+d > c+d > a > b > c > d

Then, the following program will, for increasing totals of a+b+c+d, try all values for those variables that add up to that sum, consistent with a>b>c>d, and categorize the inequality as 1 through 12 as above.  The first one in each category is counted, so that it is the minimum total for that category.  This is the program:

DIM needs(4), type$(15), minTot(15), aVal(15), bVal(15), cVal(15), dVal(15), numbers(10)

numTypes = 0
needs(4) = 6: needs(3) = 3: needs(2) = 1: needs(1) = 0
FOR total = 10 TO 100
   FOR d = 1 TO (total - needs(4)) / 4
    FOR c = d + 1 TO (total - d - needs(3)) / 3
     FOR b = c + 1 TO (total - d - c - needs(2)) / 2
      FOR a = b + 1 TO (total - d - c - b)
         numbers(1) = a + b
         numbers(2) = a + c
         numbers(3) = a + d
         numbers(4) = b + c
         numbers(5) = b + d
         numbers(6) = c + d
         numbers(7) = a
         numbers(8) = b
         numbers(9) = c
         numbers(10) = d
         DO
           fl = 0
           FOR i = 1 TO 9
            IF numbers(i) < numbers(i + 1) THEN SWAP numbers(i), numbers(i + 1): fl = 1
           NEXT
         LOOP UNTIL fl = 0
         good = 1
         IF numbers(1) = numbers(2) OR numbers(2) = numbers(3) OR numbers(3) = numbers(4) THEN
           good = 0
         END IF
         IF numbers(4) = numbers(5) OR numbers(5) = numbers(6) OR numbers(6) = numbers(7) THEN
           good = 0
         END IF
         IF numbers(7) = numbers(8) OR numbers(8) = numbers(9) OR numbers(9) = numbers(10) THEN
           good = 0
         END IF
         IF good THEN
          IF numbers(4) = a THEN
           IF numbers(7) = b THEN
            t$ = "1"
           ELSE
            t$ = "2"
           END IF
          ELSEIF numbers(5) = a THEN
           IF numbers(3) = a + d THEN
            IF numbers(7) = b THEN
             t$ = "3"
            ELSE
             t$ = "4"
            END IF
           ELSE
            IF numbers(7) = b THEN
             t$ = "8"
            ELSE
             t$ = "9"
            END IF
           END IF
          ELSEIF numbers(6) = a THEN
           IF numbers(3) = a + d THEN
            IF numbers(7) = b THEN
             t$ = "5"
            ELSE
             t$ = "6"
            END IF
           ELSE
            IF numbers(7) = b THEN
             t$ = "10"
            ELSE
             t$ = "11"
            END IF
           END IF
          ELSEIF numbers(7) = a THEN
           IF numbers(3) = a + d THEN
            t$ = "7"
           ELSE
            t$ = "12"
           END IF
          END IF
          FOR i = 1 TO numTypes
           IF type$(i) = t$ THEN good = 0: EXIT FOR
          NEXT
          IF good THEN
            numTypes = numTypes + 1
            type$(numTypes) = t$
            minTot(numTypes) = total
            aVal(numTypes) = a
            bVal(numTypes) = b
            cVal(numTypes) = c
            dVal(numTypes) = d
            IF numTypes = 12 THEN GOTO outtaHere
          END IF
         END IF
      NEXT a
     NEXT b
    NEXT c
   NEXT d
NEXT

outtaHere:
FOR i = 1 TO numTypes
  PRINT type$(i), minTot(i), aVal(i); bVal(i); cVal(i); dVal(i)
NEXT

The program finds

Ineq. type    a+b+c+d        a  b  c  d
1              14            7  4  2  1
2              17            8  4  3  2
8              19            8  6  4  1
4              19            8  5  4  2
10             21            8  7  4  2
6              21            8  6  4  3
12             21            7  6  5  3
3              23           10  7  4  2
7              23            8  6  5  4
9              25           10  7  6  2
5              25           10  8  4  3
11             27           10  8  6  3

The middle column is the total a+b+c+d and the left column is the inequality type.  The minimum total for type 11 is 27, having the numbers a=10, b=8, c=6 and d=3 as shown in the right column.

So when the friend sees

a+b > a+c > b+c > a+d > b+d > a > c+d > b > c > d

he finds the minimum total as 27 being obtained with the values shown, and this is the maximum possible consistent with what we've been told.  The highest possible sum is 27.

Posted by Charlie on 2005-01-14 06:32:56