Pyramide des différences

Version imprimable

Bonjour,
le probleme est peu-etre déja connu de vous. On en trouve des énoncés simplifiés sur le net(concours de logiques). D'une manière générale c'est le suivant:

Pour n entier positif fixé et z=1+2+3+...+n=(n*(n+1))/2;
Comment placer les entiers de 1 à z dans une pyramide à n lignes tq un tel schemat:

Code:

1
2
3
 
a b
 c  impose c=|a-b|;

Voici quelques exemples pour bien se fixer les idées(pour n=2,3,4,5):
Ils sont trouvables à la main (si n grandi ça devient de plus en plus difficile)

Pour n=2:

Code:

Pour n=3:

Code:

Pour n=4:

Code:

Pour n=5:

Code:

1
2
3
4
5
6
 
13 3 15 14 6 
 10 12 1 8 
   2 11 7 
    9 4 
     5

En fait ce sont tous les cas possibles à la symétrie axiale près, pour n=2,3,4,5, d'après un programme en C de ma fabrication (Dont je suis d'autant plus fier qu'il m'a fallut environ une semaine pour l'optimiser et qu'il mette moins de 1 heure pour n=9...)

Pour n>5 je n'en trouve plus (je n'ai pas essayé pour n>10(trop long)).

Les questions que je me pose(et à vous par la même occasion) sont:

Y a-t-il d'autres pyramide pour n>5?

Les contraintes sur une telle pyramide sont-elles si complexes qu'il est impossible de répondre à cette question?

voici mon program en c que j'aimerai bien améliorer:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
#include <stdlib.h>
#include <stdio.h>
int M[31][31],n,z,t,C[31],y;
int i,j,l;
FILE *a;
 
 
int evol(int r)
{ 
    for(i=1;i<r;i++) for(j=i;j<r;j++) if(M[1][r]==M[i][j]) return 0;
 
    for(l=2;l<=r;l++) 
    {
                      M[l][r]=abs(M[l-1][r-1]-M[l-1][r]);
 
                      if(M[l][r]>y)
                      {
                                   for(i=1;i<l-1;i++) if(M[i][r]==M[l][r]) return 0;
                                   for(i=1;i<r-1;i++) for(j=i;j<r;j++) if(M[l][r]==M[i][j]) return 0;
                                   }
                      else
                      {
                                  for(i=l-1;i>0;i--) if(M[i][r]==M[l][r]) return 0;
                                  for(i=r-1;i>0;i--) for(j=i;j<r;j++) if(M[l][r]==M[i][j]) return 0;
                                  }                
                      }
    return 1;
    }
 
 
 
 
 
 
 
 
 
 
 
 
 
int ecrirepyramide(void)                                                         
{
    for(i=1;i<=n;i++)
    {
                     fprintf(a,"\n");
                     for(l=1;l<=i;l++) fprintf(a,"   ");
                     for(j=i;j<=n;j++) fprintf(a,"%3d   ",M[i][j]);
                     }
    fprintf(a,"\n");
    return 0;
    } 
 
 
 
 
 
 
 
int main(void)
{
  int u,v,s,k;
  a=fopen("pyramide.txt","w");
  do
  { 
    printf("\n");
    printf("taper n (n=0,1ou2 pour arreter):");
    scanf("%d",&n);
   if((n>2)&&(n<31))
   {
 
    z=(n*(n+1))/2;
    y=(z/2);
    printf("Compter jusqu a %d:\n1",z);
    fprintf(a,"\n\n\nPour n=%d:",n);
    for(u=2;u<=z;u++) 
    {
    for(v=1;v<=z;v++)
    {
                M[1][1]=u;
                M[1][2]=v;
                M[2][2]=abs(u-v);
                if((u==v)||(M[2][2]==M[1][1])||(M[2][2]==M[1][2]));
                else
                {
 
 
 
                s=3;
                C[3]=1;
 
 
 
 
 
                while(C[s]<=z) 
                {
                         M[1][s]=C[s];
                         if(evol(s)==1) 
                         {
                                        s++;
                                        if(s>n) 
                                        {
                                                if(M[1][n]>M[1][1]) ecrirepyramide() ;
                                                s--;
                                                if(C[s]==z)
                                                {
                                                   j=0;
                                                   for(i=s-1;(j==0)&&(i>2);i--) if(M[1][i]!=z) j=i;
                                                   if(j>0)
                                                   {
                                                          s=j;
                                                          C[s]++;
                                                          }
                                                   else C[s]++;
                                                   }
                                                else C[s]++;
                                                }
                                        else C[s]=1;
 
                                        }
                         else 
                         {
                                        if((s==3)&&(C[s]==z)) C[s]++;    
                                        if(C[s]<z) C[s]++;
                                        else if(C[s]==z)
                                            {
                                                   j=0;
                                                   for(i=s-1;(j==0)&&(i>2);i--) if(M[1][i]!=z) j=i;
                                                   if(j>0)
                                                   {
                                                          s=j;
                                                          C[s]++;
                                                          }
                                                   else C[s]++;
                                                   }
                                        }                                         
                         }
                         }
 
 
 
 
                        }
                        printf(" %d",u);  
                        }        
                }
    }  while((n>2)&&(n<31));
 
   fclose(a);
  return 0;
}

26/05/2008, 14h37
pseudocode

Citation:

Les contraintes sur une telle pyramide sont-elles si complexes qu'il est impossible de répondre à cette question?

Le problème que tu décris s'appelle "(absolute) difference triangles". Une recherche de ce terme sur Google te montreras que tu n'es pas seul dans l'univers hostile des nombres entiers. :mrgreen:
26/05/2008, 15h43
pecheur2savon

Merci beaucoup ce que j'ai commencé à lire m'a éclairé un peu...
31/05/2008, 01h29
SpiceGuid
J'imagine que tu as déjà trouvé ma page:

http://pagesperso-orange.fr/alphablo...angles_fr.html

Ton code est plus simple que le mien :)

La commande pour 9 étages, à coller dans l'interpréteur de commandes:
Code:

1 2 3 4 Kheopful.exe 9 0 1
Chez moi ça termine en moins de 2mins.

Encore plus fort !

Ma page perso n'est plus valide mais ça ne fait rien allez consulter plutôt le Dictionnaire de mathématiques récréatives.

Et, à propos, j'avais oublié de mentionner ma dernière trouvaille :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
20
64 84 
83 19 103 
38 121 140 37
92 54 175 35 72 
45 137 191 16 51 123
131 176 39 230 214 163 40 
164 33 209 248 18 232 69 29
26 190 223 14 262 244 12 81 110
41 67 257 34 48 310 66 78 159 49
115 74 7 264 298 346 36 102 180 21 70
11 126 52 59 323 25 371 407 305 125 146 76
6 17 143 91 32 355 380 9 416 111 236 90 166
4 10 27 170 79 47 402 22 13 429 318 82 172 338
1 5 15 42 212 133 86 488 466 453 24 342 260 88 426
2 3 8 23 65 277 144 58 546 80 533 509 167 427 515 89

Peut mieux faire :question:

30/07/2016, 18h55
François DORIN

Bonjour,

Citation:

Envoyé par pecheur2savon

Y a-t-il d'autres pyramide pour n>5?

Les contraintes sur une telle pyramide sont-elles si complexes qu'il est impossible de répondre à cette question?

Les réponses a tes questions ont été apportés en 1977 par G. J. Chang, M. C. Hu, K. W. Lih et T. C. Shieh dans un article intitulé "Exact Difference Triangles" et paru dans le "Bulletin of the Institute of Mathematics, Academia Sinica, Taipei, Taiwan". Les auteurs ont apportés une preuve mathématique de la non existence de tels triangles pour n >= 6.

Pour les plus curieux, l'article est disponible à l'adresse suivante : http://w3.math.sinica.edu.tw/bulleti...d/d51/5120.pdf
30/07/2016, 20h16
SpiceGuid

:merci: dorinf pour cette référence :)

En consultant le Dictionnaire de mathématiques récréatives je me suis convaincu que la bonne généralisation du triangle des différences c'est le trapèze des différences soit (pour 6 cases à la base) la solution que j'avais déjà proposée :

http://www.recreomath.qc.ca/Imdi_absolu_tr4.gif

Changement culturel : on passe de la pyramide égyptienne à la pyramide amérindienne.
Ça n'est plus la hauteur qui compte c'est le nombre de cases à la base.

La question m'a intéressé, et j'ai recherché des pyramides triangulaires (comme le problème de base), mais en modifiant un peu la règle.
Dans la règle initiale, le point au dessus de a et b devait avoir pour valeur abs(a-b).
Dans cette variante, il peut avoir comme valeur, soit abs(a-b), soit a+b

Pour une base de longueur 5, on a 744 solutions.
Pour une base de longueur 7, on a également des solutions.
Exemple :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 23 1 22 21 20 2 27 6 14 12 3 24 18 4 16 8 11 13 5 9 7 25 17 28 15 10 19 26 26 19 7 10 9 16 15 5 4 12 28 13 18 14 2 17 11 24 6 20 22 25 8 3 27 21 1 23
En fait, ces 2 solutions sont identiques, à une symétrie près. Ces triangles restent des solutions valables quand on les fait tourner de 120°, ou par symétrie axiale.

Sur ce triangle, on peut extraire une partie :
Code:

1 2 3 4 5 6 7 8 26 x x 10 x 16 x x x x 28 x 18 x 2 x x x x x x 25 x 3 x 21 x 23
Et on constate que sur cet extrait, on a encore notre règle de somme/différence. Je pense que c'est une coïncidence et que sur d'autres triangles solutions,ce ne serait pas le cas.

Pour une base de 6 éléments, il n'y pas de solution, et ça peut se vérifier rapidement (64 combinaisons seulement à regarder) en analysant juste les parités.
Pour une base de 6 éléments, on cherche à placer les nombres entre 1 et 21 dans notre triangle. Il y a 10 nombres pairs et 11 nombres impairs. Et il n'y a aucune façon de disposer 10 nombres pairs et 11 nombres impairs dans un triangle en respectant la règle de somme/différence.
Mais pour n = 8, 9 ou 10, ce test sur les parités dit qu'il peut y avoir des solutions.

31/07/2016, 15h32
SpiceGuid

:bravo: c'est une variante intéressante.

Du coup je ne suis plus du tout d'avis que ma proposition est la seule généralisation qui soit bien fondée.

À débattre donc.
(plus d'exemples sur des pyramides plus grandes peuvent aider à déterminer quelle est la généralisation qui porte le plus de potentiel)