All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Numbers and Dots (Posted on 2003-12-24) Difficulty: 4 of 5
This is a famous problem from 1882, to which a prize of $1000 was awarded for the best solution.

The task is to arrange the seven numbers 4, 5, 6, 7, 8, 9, and 0, and eight dots, in such a way that an addition of two or more numbers approximates 82 as closely as possible.
Each of the numbers can be used only once.
The dots can be used in two ways: as decimal point and as symbol for a recurring decimal.

For example, the fraction 1/3 can be written as:
  . 
. 3
The dot on top of the three denotes that this digit is repeated infinitely. If a group of numbers needs to be repeated, two dots are used: one to denote the beginning of the recurring part and one to denote the end of it. For example, the fraction 1/7 can be written as:
  .         . 
. 1 4 2 8 5 7
(Note that '0.5' is written as '.5'.)

How close can you get to the number 82?

See The Solution Submitted by DJ    
Rating: 4.2857 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution re(2): even closer... | Comment 10 of 12 |
(In reply to re: even closer... by Charlie)

Well, by avoiding going through all those permutations, I got a program written, anticlimactically after the solution was found manually.

The program doesn't count the dots, but there are not that many solutions that add to 82, so the ones with 8 dots can be picked out manually. The output shows the ordinary decimal points, plus a dot before a repetition, and after a repetition of more than one digit. The total is shown, and sometimes due to internal rounding, it does not seem to be exactly 82, but it is:


80.4.6 ..5 .9.7 82
80..46. ..5 ..97. 82
80.6.4 ..5 .7.9 82
80..64. ..5 ..79. 82
80.4.7 ..5 .9.6 82.00000000000001
80..47. ..5 ..96. 82
80.7.4 ..5 .6.9 82.00000000000001
80..74. ..5 ..69. 82.00000000000001
80..5 .4.6 .9.7 82
80..5 ..46. ..97. 82
80..5 .6.4 .7.9 82
80..5 ..64. ..79. 82
80..5 .4.7 .9.6 82
80..5 ..47. ..96. 82
80..5 .7.4 .6.9 82
80..5 ..74. ..69. 82.00000000000001
80.6.9 .7.4 ..5 81.99999999999999
80..69. ..74. ..5 82.00000000000001
80.9.6 .4.7 ..5 82
80..96. ..47. ..5 82
80.7.9 .6.4 ..5 82
80..79. ..64. ..5 82
80.9.7 .4.6 ..5 82.00000000000001
80..97. ..46. ..5 82
80 .4.6 ..5 .9.7 82
80 ..46. ..5 ..97. 82
80 .6.4 ..5 .7.9 82
80 ..64. ..5 ..79. 82
80 .4.7 ..5 .9.6 82
80 ..47. ..5 ..96. 82
80 .7.4 ..5 .6.9 82
80 ..74. ..5 ..69. 82.00000000000001

-------

These are the same results Tristan got manually, with the fractions shuffled among the three addends. The ones with only 6 dots in fact merely have a single digit after the decimal and a single repeated digit after that.


The program:
DECLARE SUB groupEm (avail$)
DECLARE SUB buildOn (avail$)
DECLARE SUB examine (g#)
DECLARE SUB permute (a$)
DEFDBL A-Z

CLEAR , , 4000
dig$ = "0456789"
DIM SHARED grps AS INTEGER
DIM SHARED grp$(10), hist$(10), valHist(10), perm(10)
DIM SHARED minDots, maxDots, totValue

OPEN "dots.txt" FOR OUTPUT AS #2
perm(1) = 1
FOR i = 2 TO 10
  perm(i) = i * perm(i - 1)
NEXT

grps = 0: totValue = 0
groupEm dig$
CLOSE

END

SUB buildOn (avail$)
 STATIC ct
  IF avail$ = "" THEN
    ct = ct + 1
    PRINT ct; " ";
    FOR i = 1 TO grps
      PRINT grp$(i); " ";
    NEXT
    PRINT
    minDots = 0: maxDots = 0: totValue = 0
    examine 1
' IF ct / 40 = INT(ct / 40) THEN DO: LOOP UNTIL INKEY$ > ""
  ELSE
    groupEm avail$
    IF LEN(avail$) > 3 - grps THEN
      FOR i = 1 TO LEN(avail$)
       ch$ = MID$(avail$, i, 1)
       IF ch$ > RIGHT$(grp$(grps), 1) THEN
        grp$(grps) = grp$(grps) + ch$
        av2$ = LEFT$(avail$, i - 1) + MID$(avail$, i + 1)
        buildOn av2$
        grp$(grps) = LEFT$(grp$(grps), LEN(grp$(grps)) - 1)
       END IF
      NEXT
    END IF
  END IF
END SUB

SUB examine (g)
 gr$ = grp$(g)
 l = LEN(gr$)
 FOR p = 1 TO perm(l)
   FOR decimal = 0 TO l
    FOR begrept = 0 TO decimal
     iPart$ = LEFT$(gr$, l - decimal)
     valHist(g) = VAL(iPart$)
     n1$ = ""
     n2$ = ""
     IF decimal > 0 THEN
       n1$ = MID$(gr$, l - decimal + 1, decimal - begrept)
       num1 = VAL(n1$)
       den1 = VAL(LEFT$("100000000", decimal - begrept + 1))
       valHist(g) = valHist(g) + num1 / den1
       IF begrept > 0 THEN
         n2$ = MID$(gr$, l - begrept + 1)
         num2 = VAL(n2$)
         den2 = VAL(LEFT$("999999999", begrept))
         valHist(g) = valHist(g) + num2 / (den2 * den1)
       END IF
     END IF
     hist$(g) = iPart$
     IF n1$ > "" OR n2$ > "" THEN hist$(g) = hist$(g) + "." + n1$
     IF n2$ > "" THEN hist$(g) = hist$(g) + "." + n2$
     IF LEN(n2$) > 1 THEN hist$(g) = hist$(g) + ". "
     tValSave = totValue
     totValue = totValue + valHist(g)
     IF g < grps THEN
      IF totValue < 83 THEN
       examine g + 1
      END IF
     ELSE
       IF ABS(totValue - 82) < .001 THEN
         FOR i = 1 TO grps
          PRINT hist$(i); \" \";
          PRINT #2, hist$(i); \" \";
         NEXT
         PRINT \" \"; totValue
         PRINT #2, \" \"; totValue
       END IF
     END IF
     totValue = tValSave
    NEXT begrept
   NEXT decimal
   permute gr$
 NEXT p
END SUB

SUB groupEm (avail$)
  grps = grps + 1
  grp$(grps) = LEFT$(avail$, 1)
  av2$ = MID$(avail$, 2)
  buildOn av2$
  grps = grps - 1
END SUB

DEFSNG A-Z
SUB permute (a$)
DEFINT A-Z
 x$ = \"\"
 FOR i = LEN(a$) TO 1 STEP -1
  l$ = x$
  x$ = MID$(a$, i, 1)
  IF x$ < l$ THEN EXIT FOR
 NEXT

 IF i = 0 THEN
  FOR j = 1 TO LEN(a$) \ 2
   x$ = MID$(a$, j, 1)
   MID$(a$, j, 1) = MID$(a$, LEN(a$) - j + 1, 1)
   MID$(a$, LEN(a$) - j + 1, 1) = x$
  NEXT
 ELSE
  FOR j = LEN(a$) TO i + 1 STEP -1
   IF MID$(a$, j, 1) > x$ THEN EXIT FOR
  NEXT
  MID$(a$, i, 1) = MID$(a$, j, 1)
  MID$(a$, j, 1) = x$
  FOR j = 1 TO (LEN(a$) - i) \ 2
   x$ = MID$(a$, i + j, 1)
   MID$(a$, i + j, 1) = MID$(a$, LEN(a$) - j + 1, 1)
   MID$(a$, LEN(a$) - j + 1, 1) = x$
  NEXT
 END IF

END SUB


  Posted by Charlie on 2003-12-25 01:37:02
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information