I attach a list that I made in 98 with 37 solutions but I have found a mention in a note of mine that is much older that there are 38 solutions. Saludos Robert Reid --------------------------------- Hi, Ed, On 21 October 2002 you posted a puzzle from Robert Reid. As I understand it, it is the n=4 case of finding a perfect collection of n Golomb rulers with 0,1,...,n-1 marks, measuring every distance from 1 to BinomialCoefficent(n+2,3). I wrote a program that indicates the number of such ruler collections (up to reversal of the rulers) is 1,1,2,5,47,136,1 for n=0,1,2,...,6. Here are the ruler collections for n=4,5,6. I list each ruler as the sequence of intervals measured between adjacent marks. 1,2,10,5; 4,7,9; 6,8; 19 1,2,11,6; 4,5,7; 8,10; 15 1,3,8,6; 5,2,13; 9,10; 16 1,3,11,5; 7,2,8; 6,12; 13 1,4,8,3; 2,7,10; 6,14; 18 1,4,11,2; 7,3,9; 6,8; 20 1,4,11,2; 7,3,9; 6,14; 8 1,5,7,3; 2,9,8; 4,14; 20 1,6,2,10; 4,11,5; 3,14; 13 1,6,9,4; 3,2,12; 8,10; 11 1,7,10,2; 4,5,6; 3,13; 14 1,8,6,5; 4,3,10; 2,16; 12 1,9,2,6; 4,3,13; 5,14; 15 1,9,3,4; 5,6,8; 2,18; 15 1,9,4,2; 3,5,12; 7,11; 19 1,10,6,3; 2,5,8; 4,14; 12 1,11,2,4; 3,7,9; 5,15; 8 1,11,3,5; 4,6,7; 2,16; 9 1,11,5,3; 2,7,6; 4,10; 18 1,11,5,3; 2,7,6; 4,14; 10 1,11,6,2; 3,4,9; 5,10; 14 1,12,4,2; 5,3,7; 9,11; 14 1,13,2,3; 6,4,7; 8,12; 9 1,13,2,4; 5,3,9; 7,11; 10 1,13,2,4; 7,3,8; 5,12; 9 2,1,10,6; 5,7,8; 4,14; 9 2,1,12,4; 6,5,9; 8,10; 7 2,3,11,4; 6,1,12; 8,9; 10 2,3,11,4; 7,1,9; 6,13; 12 2,4,11,3; 1,7,5; 9,10; 16 2,6,1,11; 4,10,5; 3,13; 17 2,6,3,7; 1,14,5; 4,13; 12 2,7,8,3; 5,1,13; 4,12; 10 2,8,4,3; 1,5,13; 9,11; 16 2,11,1,5; 3,7,8; 4,16; 9 2,13,1,4; 6,3,8; 7,12; 10 2,13,1,4; 7,3,9; 6,11; 8 3,2,9,4; 1,6,10; 8,12; 19 3,2,9,4; 1,7,12; 6,10; 17 3,8,2,7; 4,1,14; 6,12; 16 3,11,2,4; 1,8,10; 5,7; 15 4,5,2,8; 1,13,3; 6,12; 20 4,6,2,5; 1,15,3; 9,11; 14 4,9,1,6; 2,3,12; 8,11; 18 5,3,4,6; 1,14,2; 9,11; 19 5,6,1,8; 3,10,4; 2,16; 19 7,2,3,8; 1,14,4; 6,10; 17 1,2,10,11,6; 4,15,7,9; 5,20,8; 14,18; 34 1,2,15,8,6; 4,9,11,10; 7,12,16; 5,22; 33 1,3,8,13,6; 2,16,10,7; 5,15,14; 9,23; 22 1,3,18,7,2; 10,5,8,11; 6,14,12; 16,17; 35 1,4,16,7,6; 3,14,8,10; 2,9,15; 12,19; 30 1,5,4,17,3; 2,12,11,8; 7,15,13; 16,18; 32 1,5,14,12,3; 2,11,10,7; 8,16,9; 4,18; 27 1,5,19,3,7; 9,8,4,11; 2,18,13; 14,16; 26 1,6,17,5,4; 8,2,11,14; 3,16,15; 12,18; 20 1,6,18,4,5; 8,11,2,10; 3,17,15; 14,16; 26 1,7,12,3,10; 4,17,9,5; 2,16,11; 6,28; 24 1,7,14,2,10; 3,15,13,4; 5,6,19; 9,20; 27 1,7,14,9,3; 6,13,5,11; 2,15,10; 4,28; 20 1,7,18,4,2; 5,9,3,16; 11,10,13; 15,20; 27 1,8,2,14,5; 3,15,13,4; 6,20,7; 12,22; 23 1,8,5,17,2; 6,10,11,7; 12,3,20; 4,25; 26 1,8,12,4,6; 2,13,14,5; 7,11,17; 3,23; 33 1,8,18,2,4; 5,7,10,13; 3,16,15; 11,14; 21 1,9,6,17,2; 3,8,13,7; 4,14,12; 5,22; 29 1,9,11,7,6; 4,12,14,5; 2,15,8; 3,29; 22 1,9,13,7,5; 6,15,3,8; 14,2,17; 4,27; 28 1,9,17,2,3; 8,7,6,12; 4,16,14; 11,24; 23 1,10,5,17,2; 3,9,14,4; 7,13,8; 6,25; 29 1,10,7,12,4; 3,2,20,6; 8,13,14; 9,15; 32 1,10,7,14,2; 5,4,20,6; 3,12,13; 8,19; 22 1,10,14,5,2; 8,15,3,9; 13,4,16; 6,22; 34 1,10,14,5,2; 8,15,3,9; 13,4,16; 6,28; 22 1,11,8,5,9; 2,4,23,3; 7,10,18; 15,16; 21 1,11,10,8,5; 2,4,20,7; 3,16,9; 15,17; 14 1,12,6,11,4; 3,5,20,7; 2,14,10; 9,22; 23 1,12,7,11,4; 3,2,21,6; 8,9,16; 10,14; 28 1,12,16,2,4; 5,3,17,7; 10,9,14; 11,15; 21 1,14,4,7,9; 3,2,22,6; 8,13,10; 12,17; 32 1,14,9,4,3; 6,11,8,10; 2,20,12; 5,21; 33 1,15,6,4,8; 5,2,17,11; 3,20,9; 13,14; 31 1,15,7,2,10; 5,13,8,6; 3,17,11; 4,29; 30 1,15,8,4,6; 2,5,14,11; 3,17,9; 13,22; 31 1,18,2,9,4; 5,3,14,10; 7,16,12; 6,25; 26 1,18,5,4,7; 3,10,12,8; 2,15,14; 6,26; 21 2,1,15,7,10; 5,9,12,8; 6,13,11; 4,27; 28 2,3,16,8,4; 1,14,11,9; 7,6,17; 10,22; 18 2,3,18,4,6; 9,7,8,11; 1,12,17; 14,20; 32 2,3,18,8,4; 7,6,9,10; 1,16,11; 14,20; 24 2,3,19,6,4; 8,1,14,12; 11,7,13; 16,17; 21 2,4,12,14,3; 10,5,8,11; 1,20,7; 9,22; 25 2,4,17,1,9; 3,12,13,7; 11,5,14; 8,26; 29 2,4,20,1,7; 10,9,3,11; 5,13,17; 15,16; 29 2,5,9,13,6; 3,20,1,10; 4,8,18; 15,17; 25 2,5,18,6,4; 12,8,1,13; 3,16,11; 15,17; 26 2,5,19,3,6; 8,12,1,10; 4,14,16; 15,17; 25 2,6,18,4,3; 1,11,9,14; 5,10,17; 13,16; 19 2,6,18,4,3; 11,9,1,13; 5,12,15; 16,19; 29 2,7,6,14,3; 1,21,4,8; 11,5,19; 10,18; 31 2,7,14,8,3; 1,12,5,10; 4,20,6; 16,19; 33 2,7,15,3,8; 1,16,4,10; 5,23,6; 13,19; 12 2,8,6,11,7; 4,19,3,9; 5,15,13; 1,29; 21 2,8,12,4,7; 3,14,13,5; 9,6,19; 1,28; 21 2,9,8,10,5; 3,21,1,6; 4,12,14; 13,20; 35 2,9,17,1,4; 3,7,13,12; 6,8,16; 15,19; 21 2,9,17,1,5; 3,10,12,8; 4,15,16; 7,14; 24 2,10,6,8,9; 4,3,22,5; 1,20,11; 13,15; 19 2,10,17,1,3; 8,6,5,15; 7,16,9; 13,22; 24 2,11,1,16,5; 7,8,10,9; 3,23,6; 4,20; 31 2,11,17,1,3; 8,6,10,9; 5,15,7; 12,23; 26 2,12,7,6,3; 1,17,5,10; 4,20,11; 8,26; 29 2,12,8,10,3; 1,16,7,4; 9,6,19; 5,26; 29 2,12,8,10,3; 5,4,19,6; 1,15,11; 7,17; 31 2,12,8,10,3; 5,4,19,6; 1,15,11; 7,24; 17 2,12,10,5,6; 4,3,16,9; 1,17,13; 8,26; 20 2,13,1,8,10; 3,4,21,5; 6,17,12; 11,20; 27 2,14,3,9,6; 1,10,13,7; 4,21,8; 5,22; 35 2,14,4,8,7; 3,10,11,6; 1,22,9; 5,29; 25 2,14,4,9,6; 1,21,3,7; 5,12,11; 8,26; 30 2,14,11,1,7; 5,15,3,6; 4,17,13; 10,22; 31 2,15,11,1,6; 4,16,5,9; 10,3,19; 8,23; 24 2,16,6,1,10; 5,9,12,8; 4,15,13; 3,27; 31 2,18,1,9,5; 3,8,16,7; 4,13,12; 6,26; 22 3,1,15,8,6; 2,11,9,12; 7,10,18; 5,26; 25 3,1,15,8,6; 2,11,9,12; 7,18,10; 5,26; 17 3,1,15,8,6; 2,11,9,12; 10,7,18; 5,26; 28 3,4,11,12,5; 2,6,16,9; 13,1,20; 10,19; 26 3,4,15,8,5; 2,12,6,11; 1,24,9; 10,16; 21 3,4,17,6,5; 8,1,13,12; 2,16,15; 10,19; 20 3,5,14,6,7; 1,17,12,4; 2,9,15; 10,21; 23 3,5,16,1,9; 2,13,14,6; 7,11,12; 4,28; 19 3,5,16,1,9; 2,13,14,6; 7,12,11; 4,28; 18 3,5,16,1,9; 2,13,14,6; 11,7,12; 4,28; 23 3,5,19,1,6; 4,11,2,16; 12,9,14; 10,22; 30 3,5,20,1,6; 10,9,4,11; 2,14,17; 12,18; 22 3,6,16,2,8; 1,13,15,5; 7,12,11; 4,17; 31 3,6,19,1,4; 12,2,8,13; 7,11,16; 15,17; 31 3,6,19,2,5; 4,13,1,15; 8,12,11; 10,24; 22 3,7,4,13,5; 6,19,1,8; 2,21,12; 15,16; 30 3,7,13,8,4; 2,16,6,5; 1,14,19; 9,17; 30 3,7,18,1,5; 9,8,4,11; 2,20,13; 14,16; 27 3,8,2,18,4; 1,14,12,7; 5,16,9; 6,17; 29 3,8,2,18,4; 1,14,12,7; 5,16,9; 6,23; 17 3,8,12,2,7; 6,13,5,10; 1,26,4; 16,17; 35 3,8,15,2,7; 1,19,10,4; 5,16,6; 13,18; 12 3,9,6,10,4; 5,17,2,11; 1,26,7; 8,23; 21 3,10,5,12,4; 6,20,2,7; 8,11,14; 1,23; 32 3,11,4,12,5; 1,6,13,9; 2,23,8; 10,24; 26 3,11,4,12,5; 6,19,1,8; 2,22,7; 10,13; 33 3,11,4,12,5; 6,19,1,8; 2,22,7; 10,23; 13 3,11,8,2,7; 4,12,13,5; 1,26,6; 15,20; 23 3,12,7,2,11; 1,16,10,4; 5,23,6; 8,25; 18 3,13,5,10,4; 1,24,2,7; 6,11,12; 8,22; 20 3,14,5,7,6; 1,8,15,10; 4,16,11; 2,28; 21 3,17,1,6,5; 2,14,9,10; 4,22,8; 13,15; 31 3,17,7,1,5; 4,12,10,9; 2,21,11; 14,15; 18 4,1,15,6,7; 3,14,10,8; 9,2,23; 12,19; 30 4,1,20,3,7; 6,9,2,16; 8,14,12; 13,19; 29 4,2,8,16,5; 7,15,3,9; 1,19,13; 11,17; 23 4,2,12,10,7; 1,20,5,8; 3,16,11; 9,23; 15 4,2,20,1,7; 10,9,5,11; 3,12,17; 13,18; 33 4,5,15,3,7; 2,11,8,14; 1,16,12; 6,26; 31 4,6,16,2,5; 1,19,12,3; 9,8,13; 11,14; 27 4,8,10,7,6; 3,2,19,9; 1,15,11; 14,20; 32 4,9,15,1,5; 2,8,12,11; 3,14,18; 7,19; 27 4,11,7,2,10; 1,5,23,3; 8,13,14; 16,17; 25 4,14,2,10,5; 1,24,3,6; 11,8,13; 7,22; 23 5,1,16,3,9; 4,10,13,8; 7,11,15; 2,30; 24 5,2,15,3,6; 1,10,19,4; 8,13,14; 12,16; 32 5,4,6,13,7; 1,21,3,8; 2,12,17; 16,18; 27 5,10,8,1,11; 2,4,22,3; 7,14,13; 16,17; 32 5,12,7,3,8; 2,14,9,6; 1,20,13; 4,28; 26 5,15,4,2,8; 3,9,16,7; 1,17,13; 11,22; 27 6,2,15,1,11; 3,4,21,5; 10,9,13; 14,20; 31 6,3,15,1,10; 2,5,23,4; 12,8,13; 14,17; 22 6,8,2,11,7; 4,19,3,9; 1,24,5; 15,17; 33 6,9,7,4,8; 3,14,13,5; 2,21,10; 1,24; 29 7,1,14,3,9; 5,11,13,6; 2,21,10; 4,28; 20 7,2,12,3,8; 1,18,10,6; 4,22,5; 13,20; 30 7,3,13,4,8; 1,21,9,2; 5,14,15; 6,18; 26 7,5,10,4,9; 2,6,21,3; 1,17,16; 11,20; 25 7,6,12,2,8; 3,21,5,4; 1,16,15; 11,23; 19 1,4,25,6,14,3; 8,10,16,12,9; 2,22,19,13; 7,33,11; 15,27; 39 My program ran for a few minutes for n=5 and several days for n=6, so I doubt I can get results for n>6. I would be surprised if there were any solutions, though. I think the constraints increase much faster than the possibilities. Dan Hoey ---------------------------------------------------------------- Leslie E Shader If you insist the distances be on the edges of the quadrilateral, try: side A=20 with points 1,8,10. Side B=16 with point 3. Side C=15 with points 4 and 9. Side D= 14 Now all 20 distances are obtained in exactly one way. Somewhat akin to a perfect Golumb Ruler. I still an earlier rectangular solution even it it is not perfect! A (0,0) B(19,0) C(0,12) D(19,12) E(2,0) F(10,0) G(16,0) H(19,4) I(7,12) J(18,12). All the points are on the vertices or sides of the parallelogram. Now for the lengths of the segments: DJ=1, AE=2, BG=3, BH=4, GH=5 (GBH is a 3-4-5 rt triangle) GF=6 CI=7, DH=8,BF=9, AF=10 IJ=11, AC=12, IE=13 (IEand (2,12) is a 5-12-13 rt triangle, The point (2,12) is not in my set but not used for other distances) GE=14, DF=15(BDF is a 9-12-15 rt triangle), AG=16, BE=17, CJ=18,AB=19,andGC=20 (ACG is a 12-16-20 rt triangle) ----------------------------------------------------------------- The solution of the measuring puzzle: The side which has 3 marks will have length 1, 9, 2, 6 and in this order. The side which has 2 marks will have length 4, 3, 13 and in this order. The side which has 1 marks will have length 5 and 14 and the fourth side should have length 15, so that we could measure all length from 1 to 20 -subhankar --------------------------------------------------------------- Hi Ed, Here is a list of the sub-lengths of the edges of the quadrilaterals that can measure lengths from one to twenty. There are 47 quadrilaterals in the list. I constrained my results by forcing the first sub-length to smaller than the last sub-length on the three sides that have at least one mark. Because each of these edges can be optionally flipped, there are a total of 47*8=376 quadrilaterals. If the edges may be rearranged relative to each other around the circumference, this multiplies the new total by a factor of three, for a total of 1128. You can double that to 2256 if the top and bottom of the slate are distinct. For some quadrilaterals, however, two of the edges have a total length equal to the other two edges. Only when "partner" edges are opposite do the resulting quadrilaterals have any area. 9 of the 47 listed below have this property, and in only 3 of those are the sides in the correct order. Therefore, only 41 of the 47 are constructable. As are only 41*8=328 of the 376 after edges are flipped. The 1128 number includes 24 variations for each of the nine "suspect" quadrilaterals, only one-third of which are "legal". This means we have 144 zero-area quadrilaterals, so the correct number is 984. Or 1968 if the top and bottom of the slate are distinct. -Matthew Bjorge ( 7) ( 8,10) ( 6, 5, 9) ( 2, 1,12, 4) ( 8) ( 5,15) ( 3, 7, 9) ( 1,11, 2, 4) ( 8) ( 6,11) ( 7, 3, 9) ( 2,13, 1, 4) ( 8) ( 6,14) ( 7, 3, 9) ( 1, 4,11, 2) ( 9) ( 2,16) ( 4, 6, 7) ( 1,11, 3, 5) ( 9) ( 4,14) ( 5, 7, 8) ( 2, 1,10, 6) ( 9) ( 4,16) ( 3, 7, 8) ( 2,11, 1, 5) ( 9) ( 5,12) ( 7, 3, 8) ( 1,13, 2, 4) ( 9) ( 8,12) ( 6, 4, 7) ( 1,13, 2, 3) (10) ( 4,12) ( 5, 1,13) ( 2, 7, 8, 3) (10) ( 4,14) ( 2, 7, 6) ( 1,11, 5, 3) (10) ( 7,11) ( 5, 3, 9) ( 1,13, 2, 4) (10) ( 7,12) ( 6, 3, 8) ( 2,13, 1, 4) (10) ( 8, 9) ( 6, 1,12) ( 2, 3,11, 4) (11) ( 8,10) ( 3, 2,12) ( 1, 6, 9, 4) (12) ( 2,16) ( 4, 3,10) ( 1, 8, 6, 5) (12) ( 4,13) ( 1,14, 5) ( 2, 6, 3, 7) (12) ( 4,14) ( 2, 5, 8) ( 1,10, 6, 3) (12) ( 6,13) ( 7, 1, 9) ( 2, 3,11, 4) (13) ( 3,14) ( 4,11, 5) ( 1, 6, 2,10) (13) ( 6,12) ( 7, 2, 8) ( 1, 3,11, 5) (14) ( 3,13) ( 4, 5, 6) ( 1, 7,10, 2) (14) ( 5,10) ( 3, 4, 9) ( 1,11, 6, 2) (14) ( 9,11) ( 1,15, 3) ( 4, 6, 2, 5) (14) ( 9,11) ( 5, 3, 7) ( 1,12, 4, 2) (15) ( 2,18) ( 5, 6, 8) ( 1, 9, 3, 4) (15) ( 5, 7) ( 1, 8,10) ( 3,11, 2, 4) (15) ( 5,14) ( 4, 3,13) ( 1, 9, 2, 6) (15) ( 8,10) ( 4, 5, 7) ( 1, 2,11, 6) (16) ( 6,12) ( 4, 1,14) ( 3, 8, 2, 7) (16) ( 9,10) ( 1, 7, 5) ( 2, 4,11, 3) (16) ( 9,10) ( 5, 2,13) ( 1, 3, 8, 6) (16) ( 9,11) ( 1, 5,13) ( 2, 8, 4, 3) (17) ( 3,13) ( 4,10, 5) ( 2, 6, 1,11) (17) ( 6,10) ( 1, 7,12) ( 3, 2, 9, 4) (17) ( 6,10) ( 1,14, 4) ( 7, 2, 3, 8) (18) ( 4,10) ( 2, 7, 6) ( 1,11, 5, 3) (18) ( 6,14) ( 2, 7,10) ( 1, 4, 8, 3) (18) ( 8,11) ( 2, 3,12) ( 4, 9, 1, 6) (19) ( 2,16) ( 3,10, 4) ( 5, 6, 1, 8) (19) ( 6, 8) ( 4, 7, 9) ( 1, 2,10, 5) (19) ( 7,11) ( 3, 5,12) ( 1, 9, 4, 2) (19) ( 8,12) ( 1, 6,10) ( 3, 2, 9, 4) (19) ( 9,11) ( 1,14, 2) ( 5, 3, 4, 6) (20) ( 4,14) ( 2, 9, 8) ( 1, 5, 7, 3) (20) ( 6, 8) ( 7, 3, 9) ( 1, 4,11, 2) (20) ( 6,12) ( 1,13, 3) ( 4, 5, 2, 8) --------------------------------------------------------------- The answer to the question he meant is that the slates must have sides 16,18,19,20. The slates must be marked 6 units from either corner on the 18-length side, 4 and 5 units from either corner on the 19-length side and 3,11,13 units from either corner on the 20-length side. This assumes however that the only way of measuring distances is between two points on the same side of the slate. If in fact you are able to compare any of the 10 pairs of points, there are presumably many other ways to do it. L.T. Pebody -----------------------------------------------------------------