Du recuit simulé
Toujours trouvé que cette expression était magnifique ! Et voilà qu'elle devient (un peu) mienne grâce au triangle ci-dessous (grâce aussi à Jean-Charles M. et Mark K.)
Tout a commencé par un message (raté) sur Math-Fun et sa correction :
Hello Math-Fun,
no cell of the hereunder triangle shares any of its digits with another cell of the same rank or column:
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 22 | 11 | 777 | 666 | 888 | 333 | 444 | 9 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| 33 | 8 | 555 | 111 | 222 | 47 | 69 |
+-----+-----+-----+-----+-----+-----+-----+
| 44 | 3 | 1 | 59 | 67 | 28 |
+-----+-----+-----+-----+-----+-----+
| 55 | 4 | 68 | 27 | 13 |
+-----+-----+-----+-----+-----+
| 66 | 5 | 2 | 38 |
+-----+-----+-----+-----+
| 77 | 6 | 49 |
+-----+-----+-----+
| 88 | 7 |
+-----+-----+
| 99 |
+-----+
The cell with 68, for instance, doesn't share a 6 or a 8 with a cell above it, below it, on its right or left. Can you beat this triangle -- in terms of "sum of its 45 integers"? (I have 5451 here, I guess)
On m'a vite fait comprendre que la première rangée du triangle (la plus haute) alignait les zéros en totale contradiction avec la règle... J'ai rectifié quelques instants plus tard :
...1 ...3 ...6 ..22 ..44 ..77 .555 .800 .999
...2 ...5 ...9 ..33 .777 ..14 .808 .666
...4 ...8 ..11 ..66 ..23 ..50 ..97
...7 .111 ..88 ..49 ..56 ..32
.333 .222 ..40 ..17 ..89
..55 .444 ..37 ..80
..99 ..67 ..25
.888 ..90
..60
Tom K. m'a corrigé encore : You should be able to change 97 to 79. I think you can also change 17 to 15.
Il avait raison... Je suis retourné au boulot... Je reproduis mon record actuel (il tient toujours au 26 juin à 19:45, Brussels time) :
Impossible de faire moins que 6400...
J'ai alors appelé à l'aide le fidèle Jean-Charles Meyrignac – qui a pensé à construire des triangles de plus en plus grands.
Il a mobilisé les talents de son ami Mark M. pour vérifier tout ça... à l'aide d'un programme de « simulated annealing », donc. Je vous tiens au courant car ça cuit et recuit à mort pour l'instant ! (est-ce la bonne technique ? On verra !-)
Voici à 00:00 pile le record en cours (pour le triangle "9" ; on verra plus tard pour les autres, les triangles "8", "7", "6",... plus faciles à calculer).
La somme des 45 entiers du triangle est actuellement de 6240 (pour rappel, aucun nombre de ce triangle ne partage de chiffres avec un autre nombre de sa colonne ou de sa rangée ; et les 45 nombres présents doivent être distincts) :
55 666 9 333 77 4 222 80 11
888 99 44 6 111 5 70 23
66 7 88 2 50 39 14
33 555 10 48 69 27
1 8 22 57 34
20 3 56 19
444 12 37
777 40
999
____________________
Mise à jour du samedi 27 juin 2020
Saturday, June 27th 2020 update
Reçu ceci de Walter Trump, lequel a vu passer le problème sur Math-Fun (il y en a au moins un qui suit ;-)
I like your triangular puzzle and wrote a program that improves existing solutions by swapping digits.
A good approach is to put the digits "1" in the longest diagonal and digits "2" in the next one.
A lower bound of the sum is exactly 6000. My best solution so far has a sum of 6073.
It is not possible to replace one of the numbers 111, 222, 333, ..., 999.
555, 666, 888, 444, 999, 70, 333, 222, 111
44, 777, 66, 8, 55, 39, 20, 1
77, 9, 3, 6, 40, 25, 18
99, 5, 7, 30, 26, 14
88, 4, 50, 27, 13
60, 38, 24, 15
33, 2, 19
22, 10
11
Sum = 6073
Maybe this solution can be improved if the integers 50, 60 and 70 are replaced by smaller integers.
The latest MFH solution can be improved to the sum 6212 by swapping digits:
55, 999, 6, 888, 33, 4, 222, 70, 11
777, 66, 44, 9, 111, 5, 30, 28
99, 3, 77, 2, 50, 68, 14
88, 555, 10, 47, 69, 23
1, 7, 22, 35, 48
20, 8, 59, 16
444, 12, 38
333, 40
666
Maybe it helps to use the trick with the digits “1” and “2” when searching for an optimal solution.
But I have not proof that an optimal solution has to have such an arrangement.
The problem can also be considered in a numeral system with other base than 10.
My best solution for base 7 has the sum 445:
55, 6, 40, 3, 22, 1
66, 44, 33, 25, 10
30, 5, 26, 14
4, 20, 15
2, 13
11
Walter
P.-S.
If the problem is handled like this, there is no need to stop at base 10.
You can define an infinite sequence for OEIS.
But it will be very difficult to find the minimum sum for a hexadecimal system.
The future (finite) sequence that might enter the OEIS is:
S = 1, 6, 21, 55, 133, 299, 568, 1020, 6073.
+---+
| 1 | sum = 1
+---+
+---+---+
| 1 | 2 | sum = 6
+---+---+
| 3 |
+---+
+---+---+---+
| 1 | 2 | 3 | sum = 21
+---+---+---+
| 4 | 5 |
+---+---+
| 6 |
+---+
+---+---+---+---+
| 2 | 1 | 3 | 4 | sum = 55
+---+---+---+---+
| 5 | 6 | 7 |
+---+---+---+
| 8 | 9 |
+---+---+
| 10|
+---+
+---+---+---+---+---+
| 4 | 5 | 2 | 3 | 10| sum = 133
+---+---+---+---+---+
| 6 | 7 | 9 | 12|
+---+---+---+---+
| 8 | 22| 1 |
+---+---+---+
| 20| 11|
+---+---+
| 13|
+---+
+---+---+---+---+---+---+
| 7 | 8 | 9 | 34| 25| 11| sum = 299 (Mark Mammel)
+---+---+---+---+---+---+
| 5 | 4 | 3 | 20| 16|
+---+---+---+---+---+
| 6 | 33| 2 | 15|
+---+---+---+---+
| 30| 22| 14|
+---+---+---+
| 24| 10|
+---+---+
| 1 |
+---+
+---+---+---+---+---+---+---+
| 7 | 8 | 50| 4 | 36| 22| 1 | sum = 568 (Mark M.)
+---+---+---+---+---+---+---+
| 5 | 6 | 44| 37| 20| 18|
+---+---+---+---+---+---+
| 9 | 40| 3 | 26| 15|
+---+---+---+---+---+
| 46| 33| 27| 10|
+---+---+---+---+
| 30| 25| 16|
+---+---+---+
| 2 | 17|
+---+---+
| 11|
+---+
+---+---+---+---+---+---+---+---+
| 88| 55| 66| 77| 40| 19| 2 | 33| sum = 1020 (Mark M.)
+---+---+---+---+---+---+---+---+ (see below for an improvement)
| 9 | 8 | 4 | 5 | 27| 36| 10|
+---+---+---+---+---+---+---+
| 44| 7 | 50| 16| 38| 22|
+---+---+---+---+---+---+
| 6 | 49| 37| 28| 15|
+---+---+---+---+---+
| 57| 26| 18| 34|
+---+---+---+---+
| 1 | 30| 29|
+---+---+---+
| 3 | 11|
+---+---+
| 20|
+---+
____________________
Update, June 28th 2020
Walter T. had another brilliant idea today – I quote him:
> with decimal numbers I would prefer to allow only the digits from 0 to n.
The problem is more fascinating with less available digits.
Look at your solution for n=3:
+---+---+---+
| 1 | 2 | 3 | sum = 21
+---+---+---+
| 4 | 5 |
+---+---+
| 6 |
+---+
> This is trivial. You can arrange the numbers arbitrarily.
It is more interesting if only the digits from 0 to 3 are allowed:
+---+---+---+
| 3 | 2 | 10| sum = 47
+---+---+---+
| 20| 1 |
+---+---+
| 11|
+---+
> Of course this also can be considered as a further problem (...)
> For (this) second problem, I can provide the following solutions which may not be optimal.
n=4, sum= 117
4 3 20 1
30 2 14
22 10
11
n=5, sum=239
5 4 3 2 1
44 33 20 15
30 25 14
22 10
11
n=6, sum=445
55 66 30 44 22 11
6 3 4 25 10
40 5 26 13
33 20 15
2 14
1
n=7, sum=999
55 77 44 30 66 222 111
6 5 3 47 20 1
7 4 50 26 13
40 36 27 15
33 2 16
22 10
11
Walter
____________________
In the meantime, I got this message by Mark, with two improvements of his personal bests:
+---+---+---+---+---+---+---+---+
| 6 | 9 | 7 | 44| 58| 33| 22| 10| sum = 999 (Mark M.)
+---+---+---+---+---+---+---+---+ (better than the former 1020)
| 8 | 5 | 3 | 60| 47| 29| 1 |
+---+---+---+---+---+---+---+
| 77| 66| 49| 28| 30| 15|
+---+---+---+---+---+---+
| 4 | 2 | 50| 37| 16|
+---+---+---+---+---+
| 55| 38| 26| 19|
+---+---+---+---+
| 39| 40| 18|
+---+---+---+
| 20| 17|
+---+---+
| 11|
+---+
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 7 | 66 | 8 | 9 | 444 | 55 | 111 | 20 | 333 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 999 | 5 | 3 | 777 | 88 | 40 | 26 | 11 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| 555 | 99 | 666 | 222 | 70 | 18 | 34 |
+-----+-----+-----+-----+-----+-----+-----+
| 6 | 77 | 50 | 48 | 13 | 29 |
+-----+-----+-----+-----+-----+-----+
| 888 | 44 | 17 | 36 | 25 |
+-----+-----+-----+-----+-----+
| 2 | 30 | 49 | 15 |
+-----+-----+-----+-----+
| 4 | 1 | 22 |
+-----+-----+-----+
| 10 | 28 |
+-----+-----+
| 33 | sum = 6093
+-----+
____________________
Message to which Walter replied (in private to me):
> The solution of Mark can be improved with my program to the sum 6074 (the record holder is Walter with 6073 – one unit less!)
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 6 | 88 | 7 | 9 | 333 | 55 | 111 | 20 | 444 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 999 | 5 | 4 | 666 | 77 | 30 | 28 | 11 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| 555 | 99 | 888 | 222 | 60 | 17 | 34 |
+-----+-----+-----+-----+-----+-----+-----+
| 8 | 66 | 50 | 37 | 14 | 29 |
+-----+-----+-----+-----+-----+-----+
| 777 | 33 | 16 | 48 | 25 |
+-----+-----+-----+-----+-----+
| 2 | 40 | 39 | 15 |
+-----+-----+-----+-----+
| 3 | 1 | 22 |
+-----+-----+-----+
| 10 | 27 |
+-----+-----+
| 77 | sum = 6074
+-----+
Why doesn’t Mark fix the digits “1” in the long diagonal?
This is the only way to achieve digit “1” nine times.
His new solution has the advantage that the number 70 is not used.
It should be possible to reach 6050.
The inferior limit is in fact a little greater than 6000. Now I found it is at least 6002.
That’s difficult to explain.
It can be shown that 27 numbers which are made of only one digit are necessary.
Therefore you need 1, 2, ... 9, 11, 22, ... 99, 111, 222, ... 999. Then the sum is already 5535.
Then it can be shown that 6 numbers with digit “0” are needed, namely 10, 20, ..., 60.
Inspecting the next available numbers leads to 6002.
With further investigations it should be possible to find an even greater inferior limit.
Best regards,
Walter
____________________
So, many thanks to all of you, Jean-Charles, Mark, Walter and Maximilian – I guess we are approaching a limit here!
(and the OEIS will wait, I guess, for the definitive record-sequences – including the brilliant variant from Walter!)
____________________
Updates and more records on June 29th, 2020
From Mark, triangles « 8 » and « 9 »:
9 6 55 8 44 30 2 17
4 7 66 50 33 29 18
88 5 49 37 20 16
57 40 38 26 19
60 39 27 14 triangle « 8 » with sum 988 (by Mark)
3 28 10
22 11
1
8 99 7 6 55 44 3 20 11
777 666 9 40 88 33 25 111
5 77 222 888 39 60 14
999 555 444 37 26 18
66 48 50 29 17
4 22 38 15
2 30 16 triangle « 9 » with sum 6067 (by Mark)
333 1
10
From Walter, triangle« 9 » (new record):
> I like that good solutions can be achieved by hand.
> My program could only subtract 3 from the constructed solution.
> Sum = 6047
777 444 999 666 888 50 333 222 111
99 8 66 55 7 34 20 1
555 9 77 40 3 26 18
60 5 4 38 29 17
88 6 30 27 14
44 37 28 19
33 2 15 triangle « 9 » with sum 6047 (current record by Walter)
22 10
11
Best regards,
Walter
Again, bravo to all — I guess the optimal solution is close...
____________________
Update Tuesday 13:00, June 30 2020
Indeed, we are close!
Got this mail this morning from Walter:
> Today I wrote a small backtracking program in order to find the optimal digit distribution.
So, if my construction considerations are correct, then the minimum sum for n=9 is 6041.
444 777 999 888 50 666 333 222 111
88 9 555 66 44 37 20 1
99 8 6 40 3 25 17
60 5 7 39 28 14
55 4 30 27 16
77 36 24 15
33 2 18
22 10 triangle « 9 » with sum 6041 (current record by Walter)
11
Walter
____________________
Update Wednesday 17:00, July 1st 2020
[Mark]:
> OK, here are my final results, with the correct triangles! I repeated the 974 for N=8 and was able to bring down the N=9 to 6045.
A very interesting problem. Both have the 1s, 2s, 3s along the first three diagonals.
9 8 6 44 50 33 22 17
66 4 7 58 39 20 1
77 55 49 30 26 18
5 60 38 27 14
40 37 25 16
3 2 10
28 19 triangle « 8 » with sum 974 (by Mark)
11
6 7 9 555 44 88 333 22 10
99 8 777 66 50 3 222 14
888 666 5 40 37 2 19
77 4 60 39 28 15
444 999 38 27 16
55 30 24 18 triangle « 9 » with sum 6045 (by Mark)
33 25 11
20 1
111
[Walter]:
> For N=9 Mark’s new solution can be improved from 6045 to 6044 by interchanging all digits “7” and “8”.
(Then you obtain 17 instead of 18 in the longest diagonal.)
As Mark’s best solution also has the 1s, 2s and 3s in the diagonals I am rather sure that the sum 6041 is the minimum.
The distribution of the integers in the triangle is very intriguing.
Walter
6 8 9 555 44 77 333 22 10
99 7 888 66 50 3 222 14
777 666 5 40 38 2 19
88 4 60 39 27 15
444 999 37 28 16
55 30 24 17
33 25 11 triangle « 9 » with sum 6044 (by Walter & Mark)
20 1
111
Tout a commencé par un message (raté) sur Math-Fun et sa correction :
Hello Math-Fun,
no cell of the hereunder triangle shares any of its digits with another cell of the same rank or column:
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 22 | 11 | 777 | 666 | 888 | 333 | 444 | 9 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| 33 | 8 | 555 | 111 | 222 | 47 | 69 |
+-----+-----+-----+-----+-----+-----+-----+
| 44 | 3 | 1 | 59 | 67 | 28 |
+-----+-----+-----+-----+-----+-----+
| 55 | 4 | 68 | 27 | 13 |
+-----+-----+-----+-----+-----+
| 66 | 5 | 2 | 38 |
+-----+-----+-----+-----+
| 77 | 6 | 49 |
+-----+-----+-----+
| 88 | 7 |
+-----+-----+
| 99 |
+-----+
The cell with 68, for instance, doesn't share a 6 or a 8 with a cell above it, below it, on its right or left. Can you beat this triangle -- in terms of "sum of its 45 integers"? (I have 5451 here, I guess)
On m'a vite fait comprendre que la première rangée du triangle (la plus haute) alignait les zéros en totale contradiction avec la règle... J'ai rectifié quelques instants plus tard :
...1 ...3 ...6 ..22 ..44 ..77 .555 .800 .999
...2 ...5 ...9 ..33 .777 ..14 .808 .666
...4 ...8 ..11 ..66 ..23 ..50 ..97
...7 .111 ..88 ..49 ..56 ..32
.333 .222 ..40 ..17 ..89
..55 .444 ..37 ..80
..99 ..67 ..25
.888 ..90
..60
Tom K. m'a corrigé encore : You should be able to change 97 to 79. I think you can also change 17 to 15.
Il avait raison... Je suis retourné au boulot... Je reproduis mon record actuel (il tient toujours au 26 juin à 19:45, Brussels time) :
J'ai alors appelé à l'aide le fidèle Jean-Charles Meyrignac – qui a pensé à construire des triangles de plus en plus grands.
Il a mobilisé les talents de son ami Mark M. pour vérifier tout ça... à l'aide d'un programme de « simulated annealing », donc. Je vous tiens au courant car ça cuit et recuit à mort pour l'instant ! (est-ce la bonne technique ? On verra !-)
Voici à 00:00 pile le record en cours (pour le triangle "9" ; on verra plus tard pour les autres, les triangles "8", "7", "6",... plus faciles à calculer).
La somme des 45 entiers du triangle est actuellement de 6240 (pour rappel, aucun nombre de ce triangle ne partage de chiffres avec un autre nombre de sa colonne ou de sa rangée ; et les 45 nombres présents doivent être distincts) :
55 666 9 333 77 4 222 80 11
888 99 44 6 111 5 70 23
66 7 88 2 50 39 14
33 555 10 48 69 27
1 8 22 57 34
20 3 56 19
444 12 37
777 40
999
Mise à jour du samedi 27 juin 2020
Saturday, June 27th 2020 update
Reçu ceci de Walter Trump, lequel a vu passer le problème sur Math-Fun (il y en a au moins un qui suit ;-)
I like your triangular puzzle and wrote a program that improves existing solutions by swapping digits.
A good approach is to put the digits "1" in the longest diagonal and digits "2" in the next one.
A lower bound of the sum is exactly 6000. My best solution so far has a sum of 6073.
It is not possible to replace one of the numbers 111, 222, 333, ..., 999.
555, 666, 888, 444, 999, 70, 333, 222, 111
44, 777, 66, 8, 55, 39, 20, 1
77, 9, 3, 6, 40, 25, 18
99, 5, 7, 30, 26, 14
88, 4, 50, 27, 13
60, 38, 24, 15
33, 2, 19
22, 10
11
Sum = 6073
Maybe this solution can be improved if the integers 50, 60 and 70 are replaced by smaller integers.
The latest MFH solution can be improved to the sum 6212 by swapping digits:
55, 999, 6, 888, 33, 4, 222, 70, 11
777, 66, 44, 9, 111, 5, 30, 28
99, 3, 77, 2, 50, 68, 14
88, 555, 10, 47, 69, 23
1, 7, 22, 35, 48
20, 8, 59, 16
444, 12, 38
333, 40
666
Maybe it helps to use the trick with the digits “1” and “2” when searching for an optimal solution.
But I have not proof that an optimal solution has to have such an arrangement.
The problem can also be considered in a numeral system with other base than 10.
My best solution for base 7 has the sum 445:
55, 6, 40, 3, 22, 1
66, 44, 33, 25, 10
30, 5, 26, 14
4, 20, 15
2, 13
11
Walter
P.-S.
There is one problem you should think about when using other numeral systems.
I sent you a solution for base 7 and said the sum is 445.If the problem is handled like this, there is no need to stop at base 10.
You can define an infinite sequence for OEIS.
But it will be very difficult to find the minimum sum for a hexadecimal system.
This is not quite correct because the integers first have to be transformed to the decimal system before adding them.
For example (25)7 = (2*7 + 5)10 = 19
The correct sum of the triangle should be (652)7 = (331)10 = 331
The future (finite) sequence that might enter the OEIS is:
S = 1, 6, 21, 55, 133, 299, 568, 1020, 6073.
+---+
| 1 | sum = 1
+---+
+---+---+
| 1 | 2 | sum = 6
+---+---+
| 3 |
+---+
+---+---+---+
| 1 | 2 | 3 | sum = 21
+---+---+---+
| 4 | 5 |
+---+---+
| 6 |
+---+
+---+---+---+---+
| 2 | 1 | 3 | 4 | sum = 55
+---+---+---+---+
| 5 | 6 | 7 |
+---+---+---+
| 8 | 9 |
+---+---+
| 10|
+---+
+---+---+---+---+---+
| 4 | 5 | 2 | 3 | 10| sum = 133
+---+---+---+---+---+
| 6 | 7 | 9 | 12|
+---+---+---+---+
| 8 | 22| 1 |
+---+---+---+
| 20| 11|
+---+---+
| 13|
+---+
+---+---+---+---+---+---+
| 7 | 8 | 9 | 34| 25| 11| sum = 299 (Mark Mammel)
+---+---+---+---+---+---+
| 5 | 4 | 3 | 20| 16|
+---+---+---+---+---+
| 6 | 33| 2 | 15|
+---+---+---+---+
| 30| 22| 14|
+---+---+---+
| 24| 10|
+---+---+
| 1 |
+---+
+---+---+---+---+---+---+---+
| 7 | 8 | 50| 4 | 36| 22| 1 | sum = 568 (Mark M.)
+---+---+---+---+---+---+---+
| 5 | 6 | 44| 37| 20| 18|
+---+---+---+---+---+---+
| 9 | 40| 3 | 26| 15|
+---+---+---+---+---+
| 46| 33| 27| 10|
+---+---+---+---+
| 30| 25| 16|
+---+---+---+
| 2 | 17|
+---+---+
| 11|
+---+
+---+---+---+---+---+---+---+---+
| 88| 55| 66| 77| 40| 19| 2 | 33| sum = 1020 (Mark M.)
+---+---+---+---+---+---+---+---+ (see below for an improvement)
| 9 | 8 | 4 | 5 | 27| 36| 10|
+---+---+---+---+---+---+---+
| 44| 7 | 50| 16| 38| 22|
+---+---+---+---+---+---+
| 6 | 49| 37| 28| 15|
+---+---+---+---+---+
| 57| 26| 18| 34|
+---+---+---+---+
| 1 | 30| 29|
+---+---+---+
| 3 | 11|
+---+---+
| 20|
+---+
____________________
Update, June 28th 2020
Walter T. had another brilliant idea today – I quote him:
> with decimal numbers I would prefer to allow only the digits from 0 to n.
The problem is more fascinating with less available digits.
Look at your solution for n=3:
+---+---+---+
| 1 | 2 | 3 | sum = 21
+---+---+---+
| 4 | 5 |
+---+---+
| 6 |
+---+
> This is trivial. You can arrange the numbers arbitrarily.
It is more interesting if only the digits from 0 to 3 are allowed:
+---+---+---+
| 3 | 2 | 10| sum = 47
+---+---+---+
| 20| 1 |
+---+---+
| 11|
+---+
> Of course this also can be considered as a further problem (...)
> For (this) second problem, I can provide the following solutions which may not be optimal.
n=4, sum= 117
4 3 20 1
30 2 14
22 10
11
n=5, sum=239
5 4 3 2 1
44 33 20 15
30 25 14
22 10
11
n=6, sum=445
55 66 30 44 22 11
6 3 4 25 10
40 5 26 13
33 20 15
2 14
1
n=7, sum=999
55 77 44 30 66 222 111
6 5 3 47 20 1
7 4 50 26 13
40 36 27 15
33 2 16
22 10
11
Walter
____________________
In the meantime, I got this message by Mark, with two improvements of his personal bests:
+---+---+---+---+---+---+---+---+
| 6 | 9 | 7 | 44| 58| 33| 22| 10| sum = 999 (Mark M.)
+---+---+---+---+---+---+---+---+ (better than the former 1020)
| 8 | 5 | 3 | 60| 47| 29| 1 |
+---+---+---+---+---+---+---+
| 77| 66| 49| 28| 30| 15|
+---+---+---+---+---+---+
| 4 | 2 | 50| 37| 16|
+---+---+---+---+---+
| 55| 38| 26| 19|
+---+---+---+---+
| 39| 40| 18|
+---+---+---+
| 20| 17|
+---+---+
| 11|
+---+
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 7 | 66 | 8 | 9 | 444 | 55 | 111 | 20 | 333 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 999 | 5 | 3 | 777 | 88 | 40 | 26 | 11 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| 555 | 99 | 666 | 222 | 70 | 18 | 34 |
+-----+-----+-----+-----+-----+-----+-----+
| 6 | 77 | 50 | 48 | 13 | 29 |
+-----+-----+-----+-----+-----+-----+
| 888 | 44 | 17 | 36 | 25 |
+-----+-----+-----+-----+-----+
| 2 | 30 | 49 | 15 |
+-----+-----+-----+-----+
| 4 | 1 | 22 |
+-----+-----+-----+
| 10 | 28 |
+-----+-----+
| 33 | sum = 6093
+-----+
____________________
Message to which Walter replied (in private to me):
> The solution of Mark can be improved with my program to the sum 6074 (the record holder is Walter with 6073 – one unit less!)
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 6 | 88 | 7 | 9 | 333 | 55 | 111 | 20 | 444 |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
| 999 | 5 | 4 | 666 | 77 | 30 | 28 | 11 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| 555 | 99 | 888 | 222 | 60 | 17 | 34 |
+-----+-----+-----+-----+-----+-----+-----+
| 8 | 66 | 50 | 37 | 14 | 29 |
+-----+-----+-----+-----+-----+-----+
| 777 | 33 | 16 | 48 | 25 |
+-----+-----+-----+-----+-----+
| 2 | 40 | 39 | 15 |
+-----+-----+-----+-----+
| 3 | 1 | 22 |
+-----+-----+-----+
| 10 | 27 |
+-----+-----+
| 77 | sum = 6074
+-----+
Why doesn’t Mark fix the digits “1” in the long diagonal?
This is the only way to achieve digit “1” nine times.
His new solution has the advantage that the number 70 is not used.
It should be possible to reach 6050.
The inferior limit is in fact a little greater than 6000. Now I found it is at least 6002.
That’s difficult to explain.
It can be shown that 27 numbers which are made of only one digit are necessary.
Therefore you need 1, 2, ... 9, 11, 22, ... 99, 111, 222, ... 999. Then the sum is already 5535.
Then it can be shown that 6 numbers with digit “0” are needed, namely 10, 20, ..., 60.
Inspecting the next available numbers leads to 6002.
With further investigations it should be possible to find an even greater inferior limit.
Best regards,
Walter
____________________
So, many thanks to all of you, Jean-Charles, Mark, Walter and Maximilian – I guess we are approaching a limit here!
(and the OEIS will wait, I guess, for the definitive record-sequences – including the brilliant variant from Walter!)
____________________
Updates and more records on June 29th, 2020
From Mark, triangles « 8 » and « 9 »:
9 6 55 8 44 30 2 17
4 7 66 50 33 29 18
88 5 49 37 20 16
57 40 38 26 19
60 39 27 14 triangle « 8 » with sum 988 (by Mark)
3 28 10
22 11
1
8 99 7 6 55 44 3 20 11
777 666 9 40 88 33 25 111
5 77 222 888 39 60 14
999 555 444 37 26 18
66 48 50 29 17
4 22 38 15
2 30 16 triangle « 9 » with sum 6067 (by Mark)
333 1
10
From Walter, triangle« 9 » (new record):
> I like that good solutions can be achieved by hand.
> My program could only subtract 3 from the constructed solution.
> Sum = 6047
777 444 999 666 888 50 333 222 111
99 8 66 55 7 34 20 1
555 9 77 40 3 26 18
60 5 4 38 29 17
88 6 30 27 14
44 37 28 19
33 2 15 triangle « 9 » with sum 6047 (current record by Walter)
22 10
11
Best regards,
Walter
Again, bravo to all — I guess the optimal solution is close...
____________________
Update Tuesday 13:00, June 30 2020
Indeed, we are close!
Got this mail this morning from Walter:
> Today I wrote a small backtracking program in order to find the optimal digit distribution.
So, if my construction considerations are correct, then the minimum sum for n=9 is 6041.
444 777 999 888 50 666 333 222 111
88 9 555 66 44 37 20 1
99 8 6 40 3 25 17
60 5 7 39 28 14
55 4 30 27 16
77 36 24 15
33 2 18
22 10 triangle « 9 » with sum 6041 (current record by Walter)
11
Walter
____________________
Update Wednesday 17:00, July 1st 2020
[Mark]:
> OK, here are my final results, with the correct triangles! I repeated the 974 for N=8 and was able to bring down the N=9 to 6045.
A very interesting problem. Both have the 1s, 2s, 3s along the first three diagonals.
9 8 6 44 50 33 22 17
66 4 7 58 39 20 1
77 55 49 30 26 18
5 60 38 27 14
40 37 25 16
3 2 10
28 19 triangle « 8 » with sum 974 (by Mark)
11
6 7 9 555 44 88 333 22 10
99 8 777 66 50 3 222 14
888 666 5 40 37 2 19
77 4 60 39 28 15
444 999 38 27 16
55 30 24 18 triangle « 9 » with sum 6045 (by Mark)
33 25 11
20 1
111
[Walter]:
> For N=9 Mark’s new solution can be improved from 6045 to 6044 by interchanging all digits “7” and “8”.
(Then you obtain 17 instead of 18 in the longest diagonal.)
As Mark’s best solution also has the 1s, 2s and 3s in the diagonals I am rather sure that the sum 6041 is the minimum.
The distribution of the integers in the triangle is very intriguing.
Walter
6 8 9 555 44 77 333 22 10
99 7 888 66 50 3 222 14
777 666 5 40 38 2 19
88 4 60 39 27 15
444 999 37 28 16
55 30 24 17
33 25 11 triangle « 9 » with sum 6044 (by Walter & Mark)
20 1
111
The record of 6041 by Walter still holds. I guess this is the end!
Je mettrai 20 au lieu de 22 ...
RépondreSupprimerCe commentaire a été supprimé par l'auteur.
RépondreSupprimerIl y a déjà un 20 !
RépondreSupprimerIt seems that if you swap 3s & 4s you win a few points (resulting sum: 6400)
RépondreSupprimerThis variation (also swap 5<->7) gives sum 6382:
RépondreSupprimer1 4 6 22 333 555 777 80 999
2 7 9 444 55 38 10 666
3 8 111 66 20 79 54
5 11 888 39 47 26
44 222 30 57 16
77 33 45 100
99 50 27
88 69
60
Sorry, the page was not updated with the new solution when I wrote my last post.
RépondreSupprimerIt seems the new solution can be improved to sum=6231 as follows:
55 888 9 777 33 4 222 60 11
666 99 44 8 111 5 30 27
88 3 66 2 50 79 14
77 555 10 46 89 23
1 6 22 35 47
20 7 58 19
444 12 37
333 40
999
Ce commentaire a été supprimé par l'auteur.
RépondreSupprimerCe commentaire a été supprimé par l'auteur.
RépondreSupprimerHello, almost 2 years later, I randomly ran into this. Back then (a little later) I had submitted a few OEIS sequences concerning this. In particular, https://oeis.org/A332080 lists the lexicographic earliest solution with minimum sum, with Walter's constraint to use only digit 0 to n for a triangle of width n. (Each "row" of that sequence is the list of all elements of a full triangle, read by diagonals in the layout used here.) Sequence https://oeis.org/A332081 corresponds to the sum of the elements, when read in base n+1 (as in Walter's example with sum 445).
RépondreSupprimer