Date: 10 Dec 1985 13:02:15 EST (Tue) From: Dan Hoey To: Alan Bawden Subject: Re: Attractive nuisances To continue (oops), I just wanted to mention the cutoffs I had found. I'll deal with them assuming that distances are chosen in order from the ends, because I've thought that way so far, but there may be a generalization worth working on here. What we have at some point is triangles filled in at the bottom and a parallelogram at the top, say after choosing 0, 55, 1, 53, 6, 10, and 41, we have 55 53 54 41 52 49 . 40 47 45 . . 35 43 . . . . 31 . . 10 J K L M N O 6 9 E F G H I 14 1 5 4 A B C D 12 2 Now all the remaining distances are bounded above by 45 (or 41), so we can put 46, 48, 50, and 51 off to the side. There are a fair amount of cutoffs from noticing that there aren't enough distances left to fill the triangle. There are also a fair amount of cutoffs from noticing there aren't enough possible marks to fill the left side. In the space from 11 to 40, we have eliminated all but 21, 23, 25, 26, 28, 30, 32, 33, 34, and 38 because of their distance to existing marks. Also, 21 is the midpoint of 1-41 and 28 is the midpoint of 1-55, so they are eliminated. Each new mark removes a large number of possibilities. The intense cutoff I found, though, is related from the proof that there are no perfect rulers. Fact one is that A+B+C+D=31, just dividing up the space from 10 to 41 in four jumps. If the four smallest remaining distances add up to more than 31, continuation is impossible. Fact two is that E+G+I=47, dividing the space from 6 to 53 in three double-jumps. So if the seven smallest remaining distances add up to more than 78, continuation is impossible. I also use F+H=31, J+M=40, K+N=47, and L+O=45. There might be some mileage gained from ordering the use of these, or trying them in different orders, but I didn't do it. Interesting corrolary to the ruler-nature criterion of my last message: given any path through the triangle, with alternate edges aligned with the left and right triangle edges, say B M H C L F, the sum of the odd vertices equals the sum of the even vertices. Also, the triangle is reflected in the row of zeroes at the base. Do you know if this kind of tableau has been studied before? News flash: There are no ten-space rulers exactly 73 units long, though there are two at 72 units and at least nine at 74. Oh, and my code took half an hour to find the two rulers at 72 units, and 45 minutes to check 73. So it's somewhat faster than yours, but not incredibly. The big win is its ability to run on these 68K boxes we have. Now you've got me interested. Amazing how contagious these time-sinks are. Dan