| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 14.1 | | HARE::STAN | | Mon Jan 23 1984 06:01 | 216 |
| N= 2
1 2
3
2 1
3
2 solutions found. Maximum= 3
N= 3
2 1 4
3 5
8
4 1 2
5 3
8
2 solutions found. Maximum= 8
N= 4
2 3 1 6
5 4 7
9 11
20
4 1 2 7
5 3 9
8 12
20
4 2 1 7
6 3 8
9 11
20
6 1 3 2
7 4 5
11 9
20
7 1 2 4
8 3 6
11 9
20
7 2 1 4
9 3 5
12 8
20
6 solutions found. Maximum= 20
N= 5
6 4 1 2 7
10 5 3 9
15 8 12
23 20
43
7 2 1 4 6
9 3 5 10
12 8 15
20 23
43
2 solutions found. Maximum= 43
N= 6
8 6 1 3 2 10
14 7 4 5 12
21 11 9 17
32 20 26
52 46
98
10 2 3 1 6 8
12 5 4 7 14
17 9 11 21
26 20 32
46 52
98
2 solutions found. Maximum= 98
N= 7
11 7 2 1 4 6 13
18 9 3 5 10 19
27 12 8 15 29
39 20 23 44
59 43 67
102 110
212
13 6 4 1 2 7 11
19 10 5 3 9 18
29 15 8 12 27
44 23 20 39
67 43 59
110 102
212
2 solutions found. Maximum= 212
N= 8
15 10 2 3 1 6 8 16
25 12 5 4 7 14 24
37 17 9 11 21 38
54 26 20 32 59
80 46 52 91
126 98 143
224 241
465
16 8 6 1 3 2 10 15
24 14 7 4 5 12 25
38 21 11 9 17 37
59 32 20 26 54
91 52 46 80
143 98 126
241 224
465
2 solutions found. Maximum= 465
N= 9
17 11 7 2 1 4 6 13 21
28 18 9 3 5 10 19 34
46 27 12 8 15 29 53
73 39 20 23 44 82
112 59 43 67 126
171 102 110 193
273 212 303
485 515
1000
17 13 6 4 1 2 7 11 21
30 19 10 5 3 9 18 32
49 29 15 8 12 27 50
78 44 23 20 39 77
122 67 43 59 116
189 110 102 175
299 212 277
511 489
1000
21 11 7 2 1 4 6 13 17
32 18 9 3 5 10 19 30
50 27 12 8 15 29 49
77 39 20 23 44 78
116 59 43 67 122
175 102 110 189
277 212 299
489 511
1000
21 13 6 4 1 2 7 11 17
34 19 10 5 3 9 18 28
53 29 15 8 12 27 46
82 44 23 20 39 73
126 67 43 59 112
193 110 102 171
303 212 273
515 485
1000
|
| 14.2 | | AURORA::HALLYB | | Sat Jan 28 1984 23:26 | 15 |
| From the description of the problem I deduce that a triangle of the form
10 2 5 3
12 7 2
19 5
24
is illegal not only because of the duplications but also because the second
column is not strictly increasing, which perhaps implies the 2 in the third
column should be -2. Right? This implies that each (n+1)-sequence must
contain an n-sequence as the first set of differences. Intuition tells me
then that the mimimum entry in these triangles must be more than twice the
minimum value of the 1-smaller triangle, which is supported for n=1 to 9.
This also implies that 2148 is close to a minimum, if not the minimum itself.
But you already knew that...
|
| 14.3 | | HARE::STAN | | Sun Jan 29 1984 21:40 | 4 |
| Correct. The differences ( a - a ) must be positive.
n+1 n
In your example, the 2 in the third column should be a -2.
|
| 14.4 | | LAMBDA::VOSBURY | | Wed Feb 15 1984 18:39 | 94 |
| The following two pages are the essential contents of two messages I MAILed
to Stan a few weeks ago concerning this problem. He suggested I post them
here and I've just gotten around to it.
Mike.
I played around a little with what you called Distinct Difference Triangles.
At the risk of belaboring the obvious, a few things struck me.
The first was that your solutions come in symmetric pairs. This is basically
because your problem is isomorphic to the following one:
Write down in a row N positive integers.
Form a triangle where each number is the sum of the two numbers above it.
Require that each number in the triangle be distinct.
Find the triangle with the smallest number at the apex.
For example (using one of your triangles):
6 4 1 2 7
10 5 3 9
15 8 11
23 29
43
It may be more profitable to take this viewpoint. For example, the number at
the apex (call it S) is a simple function of the N numbers in the top row
(call them A(i) for 0 <= i <= N-1):
N-1
----
\ N-1
S = > ( ) * A(i)
/ i
----
i=0
Your search algorithm could be:
Pick N distinct integers to form the top row.
Calculate S.
If it is greater than that of the best solution so far, abandon this try.
Otherwise, generate the triangle checking for duplicate entries.
The form of S suggests that the middle of the top row should contain the small
numbers with the larger ones on the ends. Given a good initial solution and
some care in choosing the numbers in the top row you should be able to quickly
run through all of the possible top rows.
The other thing that I noticed in the examples you gave was that the solution
for N-2 was to be found embedded in the solution for N (for N>4). I don't
immediately see that this MUST be so, but it suggests the following method for
generating a trial solution before using the search algorithm described above:
Take a solution for N-2.
Pick two numbers not found in the N-2 triangle and place them to the left
and right of the top row of the N-2 solution.
Generate the missing outsides of the order N triangle, checking for
duplicate entries.
Repeat as necessary, until you get a solution and then search as above
for a better one.
Having a good initial solution should help you prune the hell out of the
search tree.
I produced the following in a few minutes via DIGICALC:
18 15 10 2 3 1 6 8 16 23
33 25 12 5 4 7 14 24 39
58 37 17 9 11 21 38 63
95 54 26 20 32 59 101
149 80 46 52 91 160
229 126 98 143 251
355 224 241 394
579 465 635
1044 1100
2144
I just eye-balled it for duplicate entries so I may have missed one but I
think it's OK. The numbers 13, 19 and 22 don't work in either of the upper
corners and 23 doesn't work in the upper right, so I expect it's unique
(except for its mirror image, of course.)
I also expect it's minimum. Because of the weights associated with the middle
eight entries in the top row, increasing one of them by 1 would mean an
increase in the apex number of at least 9, hence the numbers on the upper
corners would have to drop by a total of 10 or more and they can't; the
numbers less than 18 and 23 are mostly all used up. (This is not a proof,
of course.)
Because of essentially this argument, my intuition expects that an order N
solution will always contain an order N-2 solution embedded in it.
|
| 14.5 | | HARE::STAN | | Fri Feb 24 1984 16:15 | 1 |
| See note 42 for a related problem.
|
| 14.6 | | HARE::STAN | | Mon Jul 23 1984 21:04 | 11 |
| George's problem now appears in print as
George Berzsenyi, Complete Difference Triangles. The New James
Cook Mathematical Notes. 4(June 1984)4054-4055.
------------------
In a private communication I received from Basil Rennie (the editor
of the JCMN), he conjectures that for n=11, the smallest maximum
number is 4562, as generated by
<14, 35, 69, 122, 204, 330, 523, 826, 1341, 2341, 4562>.
|
| 14.7 | | CFSCTC::GILBERT | | Fri Jul 30 1993 03:22 | 22 |
| Basil Rennie's conjecture produces an apex that's too large.
Using Mike Vosbury's approach and notation (.14), the minimum apex (of 4497)
for n=11 is produced by:
30 19 12 2 5 1 3 8 9 18 20
(Mike's solution is best for n=10.)
I have solutions for the minimal apexes (apexii?) for n <= 28.
(For n=28, the apex is 972,479,046).
FWIW, for n=4 and n=9, the triangle with minimal apex is not unique
(even after accounting for reflective symmetry), viz:
7 2 1 4 4 2 1 7 2 3 1 6
9 3 5 6 3 8 5 4 7
12 8 9 11 9 11
20 20 20
21 13 6 4 1 2 7 11 17
and 17 13 6 4 1 2 7 11 21, obviously produce the same apex.
|