Pyramide des différences

Olympiades mathématiques, énigmes et défis
pecheur2savon
Membre Naturel
Messages: 10
Enregistré le: 26 Mai 2008, 13:06

pyramide des différences

par pecheur2savon » 26 Mai 2008, 13:55

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:

a b
c impose c=|a-b|;

Voici quelques exemples pour bien se fixer les idées(pour n=2,3,4,5):
Ces résultats sont trouvables à la main bien que de plus en plus difficiles si n grandit.


Pour n=2:

3 1
2

3 2
1


Pour n=3:

4 6 1
2 5
3

5 6 2
1 4
3

6 1 4
5 3
2

6 2 5
4 3
1


Pour n=4:

8 1 10 6
7 9 4
2 5
3

8 10 1 6
2 9 5
7 4
3

9 3 10 8
6 7 2
1 5
4

9 10 3 8
1 7 5
6 2
4


Pour n=5:

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? :mur:

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



mehack
Membre Naturel
Messages: 16
Enregistré le: 30 Jan 2008, 21:08

par mehack » 26 Mai 2008, 14:10

ca me rapelle le triangle de pascal.
use wikipedia :id:

pecheur2savon
Membre Naturel
Messages: 10
Enregistré le: 26 Mai 2008, 13:06

par pecheur2savon » 26 Mai 2008, 14:30

C'est une pyramide de différences et pas d'addition:

c'est à dire que pour

a b
c

c=|a-b| ce qui signifit que c="valeur absolue de"(a-b) c'est plus problèmatique.


De plus il ne s'agit pas de simplement construire ligne après ligne mais il faut qu'à la fin chaque entier de 1 à z apparaisse une et une seule fois dans la pyramide.

Mais l'idée générale de la construction mis à part cette dernière condition s'apparente effectivement un peu au triangle de Pascal.

Merci d'y réfléchir Mehack, ça me prend la tête depuis une semaine. :mur:

bombastus
Membre Complexe
Messages: 2295
Enregistré le: 29 Nov 2007, 23:35

par bombastus » 26 Mai 2008, 22:31

Bonjour pecheur2savon,

J'ai légèrement réfléchi à ton cas de figure.
Le problème, c'est que lorsque tu as z valeurs, il y a z! matrices possibles (permutation de z éléments), donc pour le moment, j'ai testé avec une méthode bourrin, c'est à dire le test de chaque matrice pour voir si elle vérifie la pyramide des différences, et pour le moment j'obtiens les mêmes résultats que toi jusqu'à n=4. Après il faut que je modifie certaines choses car je stocke trop de données.

Tu as trouvé des contraintes qui permettent d'éliminer directement certains cas?

pecheur2savon
Membre Naturel
Messages: 10
Enregistré le: 26 Mai 2008, 13:06

par pecheur2savon » 27 Mai 2008, 00:25

Salut bombastus

En fait au début je faisais défiler le compteur du haut(la première ligne) je construisait la pyramide tout en vérifiant à chaque élément que ça allait.
(je suppose que c'est ce que tu fais)

la technique de mon dernier prog consiste à partir d'un coin supérieur:
pour un z fixé, je construit une petite pyramide(deux lignes) qui convient puis je la complète (je rajoute un élément à la premiere ligne) je regarde si ca marche etc
dès que ça marche pas j'incrémente la roue qu'il faut...(je repart en arrière)
Je sais c'est pas très clair dit comme ça mais ce programme est vachement plus efficace.

Je l'ai tapé en C, il est disponible à:
http://www.developpez.net/forums/forumdisplay.php?f=520
où j'ai ouvert un sujet similaire(même titre).

pseudocode m'y a donné des informations intéressantes pour ce sujet (taper "(absolute) difference triangles" dans google.

si tu veux je te détaille un peu plus ma deuxième technique...
C'est un problème qui devient beaucoup plus compliqué si n augmente un peu.
Pour me le figurer j'imagine dans la première technique qu'il s'agit de faire tourner un compteur à n roues ayant chacune presque z chiffres.
Au rang suivant cela devient n+1 roues à chacune presque z+(n+1)

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 7 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite