Nombres entiers.

[invitea5ab8741]

Bonjour,

Je voudrais donner une condition nécessaire et suffisante portant sur n pour que ladouble série de 1 à n puisse être rangée dans un ordre tel qu'il y ait un nombre entre les deux "1", deux nombres entre les deux "2", ..., n nombres entre les deux "n".

Pour n = 3 : cela fonctionne : 3;1;2;1;3;2.
Pour n = 4 : cela fonctionne : 2;3;4;2;1;3;1;4.

Je soupçonne que la condition nécessaire et suffisante portant sur n est : n congru à 3 [4] ou n congru à 0 [4].

Mais pour n = 7 : je n'arrive pas à trouver ...

Pouvez-vous m'aider ?
-----

[KerLannais]

Salut

17125623475364

[KerLannais]

et puis

1712862357436854

[invitea5ab8741]

Merci de tes réponses.
De mon côté j'ai trouvé :
pour n=7 : 71316435724625
pour n=8 : 8131743568427526.

Avec ces réponses j'essaie de trouver une logique du fait que cela marche qu'avec les nombres congrue à 0 mod4 et 3 mod4; si quelqu'un pouvait m'en faire part...

[A voir en vidéo sur Futura]

[KerLannais]

Je ne vois vraiment pas pourquoi la condition pourrait-être aussi simple que d'être congru à 0 ou 3 modulo 4, mais il faut avouer que jusqu'à n=12 ça marche encore:

1, 2, 1, 11, 2, 3, 9, 10, 4, 3, 8, 5, 7, 4, 6, 11, 9, 5, 10, 8, 7, 6,
1, 2, 1, 3, 2, 12, 10, 3, 11, 4, 5, 9, 6, 8, 4, 7, 5, 10, 12, 6, 11, 9, 8, 7,

[invitea5ab8741]

Ca n'a peut être rien à voir mais peut être que...

La condition portant sur n pour que la somme des éléments de l'ensemble {1;2;...;n} soit égale à la somme des deux sommes des éléments de deux sous-ensembles, est n congru à 0 ou 3 mod 4.

Par exemple : pour n=3:1+2=3.
Pour n=4:1+4=2+3.
Pour n=7: 6+8+4=1+2+3+5+7.
...

[KerLannais]

La conjecture est encore confirmée jusqu'à et on a
1, 2, 1, 3, 2, 4, 14, 3, 15, 13, 4, 5, 12, 6, 7, 10, 11, 5, 8, 9, 6, 14, 7, 13, 15, 12, 10, 8, 11, 9,

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

mais après cela commence à faire long en temps de calcul (enfin avec mon petit programme naïf il y a peut-être moyen de trouver un algorithme de recherche de solution plus efficace que l'approche naïve).

Pour et il n'y a chaque fois que deux solutions qui sont symétriques l'une de l'autre, à partir de ce n'est plus le cas et il semble que ce soit de plus en plus facile de trouver des solutions (pour congru à ou modulo ) ce qui prends plus de temps à l'ordi c'est vérifier qu'il n'y a pas de solution pour une valeur de car il est obligé de tester un peu toutes les possibilités, mais pour il trouve une solution quasi instantanément et à partir de on peut toujours en trouver une qui commence par (voire ie les nombres placés dans l'ordre mais en respectant la règle du jeu). Je n'ai donc pas testé pour et mais pour on trouve
1, 2, 1, 3, 2, 4, 5, 3, 18, 19, 4, 6, 5, 17, 15, 16, 9, 7, 6, 8, 13, 14, 10, 11, 12, 7, 9, 18, 8, 19, 15, 17, 16, 10, 13, 11, 14, 12,
(le calcul commence à prendre un peu de temps mais cela reste raisonnable)
Tout se passe comme si il y avait soit aucune solution, soit beaucoup (quand n devient grand) il doit donc y avoir une raison simple qui fait qu'il ne peut pas avoir de solution si est congru à ou modulo mais laquelle

[invite7863222222222]

Bonjour,

Je voudrais donner une condition nécessaire et suffisante portant sur n pour que ladouble série de 1 à n puisse être rangée dans un ordre tel qu'il y ait un nombre entre les deux "1", deux nombres entre les deux "2", ..., n nombres entre les deux "n".

Pour n = 3 : cela fonctionne : 3;1;2;1;3;2.
Pour n = 4 : cela fonctionne : 2;3;4;2;1;3;1;4.

Je soupçonne que la condition nécessaire et suffisante portant sur n est : n congru à 3 [4] ou n congru à 0 [4].

Mais pour n = 7 : je n'arrive pas à trouver ...

Pouvez-vous m'aider ?

Je ne comprends pas la logique de la construction, peux tu la détailler exactement ?

[invitea5ab8741]

Justement mes exemples sont un peu hasardeux je n'ai pas encore trouvé la logique.
Mais il y a plusieurs listes pour un meme n qui respectent la condition, par exemple KerLannais et moi avons trouvé deux listes différents pour le 7.

@KerLannais : en effet, il vaudrait mieux d'abord cherché pourquoi cela ne marche pas avec les nombres congrus à 1 et 2 mod 4.

[invitea5ab8741]

(Rectification message 6 : au lieu de "n=7"; c'est : n=8).

[invitea5ab8741]

Peut etre bien que le message 6 n'est pas hors-sujet :

Pour n=7: {1;2;5;6} ; {3;4;7}.

D'après Kerlannais : 17125623475364.

Pour n=7; on a aussi : {1;3;4;6} ;{2;5;7}.

J'avais trouvé : 71316435724625.

On constate que les termes d'un sous-ensemble sont toujours côte à côte.
Pour n=8; j'ai vérifié, ça fonctionne également.

Cela semble nécessaire pour que la liste de nombres respecte les règles.
Par exemple: pour n=4: {1;4};{2;3}.
Si je ne veux pas mettre le 1 à côté du 4 et le 2 à côté du 3; j'écris en premier: 1243 -> faux car il devrait y avoir un 1 à la place du 4.
3421 -> faux car si je continue en respectant les règles : le deuxième 2 et le deuxième 1 auront la même place.

Ca ne fonctionne pas avec les nombres congrus à 1 ou 2 mod4 (voir message 6).

L'énoncé du message 6 est prouvé.

Si on continue sur ce raisonnement, prouvons qu'il est nécessaire que : les termes d'un sous-ensemble sont toujours côte à côte dans une liste de nombres qui respecte les règles.

[invite986312212]

La condition portant sur n pour que la somme des éléments de l'ensemble {1;2;...;n} soit égale à la somme des deux sommes des éléments de deux sous-ensembles, est n congru à 0 ou 3 mod 4.

je ne suis pas sûr de comprendre cette assertion: tu veux dire que si on partitionne l'ensemble {1,..,n} en deux de sorte que les sommes des éléments des deux parties soient égales, alors n=0 ou 3 modulo 4 ?

si c'est bien ça, ça découle du fait que la somme des nombres de 1 à n est n(n+1)/2 et qu'il faut alors qu'elle soit paire, donc que n(n+1) soit divisible par 4. Or n et n+1 sont toujours premiers entre eux et donc il faut que 4 divise n ou n+1, soit n=0 ou -1 modulo 4.

[KerLannais]

Pour Ambrosio l'assertion de Guigs est bien une équivalence, même si un sens est plus dur à montrer que l'autre. Il est facile de montrer que s'il y a une telle décomposition alors la somme des entiers de 1 à n est paire et alors n est congru à -1 ou 0 modulo 4. Mais on peut montrer qu'il suffit que n soit congru à -1 ou 0 modulo 4 pour qu'on puisse effectuer une telle décomposition. Le cas le plus facile est le cas où n est multiple de 4. On regroupe les entiers de 1 à n par goupe de deux entiers succesifs : (1,2), (3,4), ..., (n-1,n), puisque n est un multiple de 4 il y a un nombre paire de telles paires, on encore une fois les regrouper par groupe deux paires successives:
((1,2),(3,4)), ((5,6),(7,8)), ...
dans la paire de gauche on met le nombre de gauche à gauche du signe égal et le nombre de droite à droite, dans la paire de droite on fait le contraire de sorte que
1+4=2+3
5+8=6+7
...
etc
on en déduit la décomposition recherchée
par exemple pour n=16
1+4=2+3
5+8=6+7
9+12=10+11
13+16=14+15
et donc
1+4+5+8+9+12+13+16=2+3+6+7+10+ 11+14+15

le cas où n est congru à 3 modulo 4 est à peine plus difficile, on sais que dans ce cas n s'écrit comme somme de deux entiers successifs dont le premier est impair, le nombre de paires d'entiers successifs qu'il reste une fois que l'on a enlevé n et la paire dont le somme vaut n est paire (puisque on a enlevé trois éléments on tombe sur un multiple de 4 et les nombres restant se classent bien par paires d'entiers successifs). On peut alors procéder comme avant pour les nombres restant. Exemple n=15

on écrit
15=7+8
il reste
((1,2),(3,4)),((5,6),(9,10)),( (11,12),(13,14))
1+4=2+3
5+10=6+9
11+14=12+13
donc
15+1+4+5+10+11+14=7+8+2+3+6+9+ 12+13

[KerLannais]

Guigs tu as eu un éclair de génie tu as raison sur le fait que pour qu'il y ait une solution il faut que la somme des entiers de 1 à n soit paire et donc que n soit congru à -1 ou 0 modulo 4, grace au lemme suivant

Lemme:Soit un entier naturel supérieur ou égal à . Soit des entiers naturels deux à deux distincs compris entre et (ils s'agit donc de tous les entiers de à ). On suppose que pour tout compris entre et , . Alors

est paire

preuve:

 Cliquez pour afficher

Pour un ensemble de positions on va noter la somme associée. On procède par récurence sur . Pour , c'est trivial, . On peut supposer quitte à renuméroter que , on a donc que trois cas possibles (suivant la valeur de )
et
et
et
d'où le résultat. On suppose donc le résultat vrai pour et on cherche à le montrer pour . Quitte à renuméroter on peut supposer que (qu'il s'agit du plus grand). On note toujours . On note pour compris entre et

et

Autrement dit, est l'ensemble de positions obtenues en enlevant et . En particulier, par hypothèse de récurrence on a qui est paire. Par ailleurs on a


ainsi, est paire et on a montrer le lemme par récurrence.

Dans notre cas on a d'après la règle du jeu

et donc

est pair ce qui implique que si il y a une solution alors est congru à ou modulo

[KerLannais]

oups dans la preuve du lemme il faut lire

comme le suggère l'indication dans la parenthèse. Désolé pour cette erreur d'étourderie qui nuit à la compréhension

[invite986312212]

pas mal. Saurais-tu trouver une cns pour 3 copies des nombres de 1 à n ? (puis k copies)

autre problème: peut-on ranger deux copies de tous les entiers naturels en respectant cette règle? (puis k copies)

[KerLannais]

Le problème c'est que ce n'est pas une cns, il reste le plus difficile à mon avis, montrer que si est congru à -1 ou 0 modulo 4 alors il y a des solutions. Même si c'est vérifié jusqu'à et qu'il semble y avoir de plus en plus de solutions, il faut quand même le démontrer et à part trouver une méthode de construction systématique de solutions je ne vois pas trop comment faire (une démonstration non constructive me parait improbable mais peut-être que je me trompe). Des idées comme dans le fameux message 6 sont une piste mais il faudrait pouvoir préciser un peu. Le problème c'est que la décomposition de la somme des entiers n'est pas unique, il suffit d'inverser simultanément deux paires d'entiers successifs de chaque côté du signe égal pour obtenir une autre décomposition. De plus ce sont des nombres qui apparaissent côte à côte dans la solution mais quelque part en plein milieu. Pour moi il est aussi difficile de trouver une décomposition de la somme des entiers à partir d'une solution du problème de Guigs que de faire l'inverse. Mais pour autant je ne pense pas que la remarque de Guigs soit anodine. Il y a une autre question alors c'est : y a-t-il un lien entre le nombre de solutions et le nombre de façon de décomposer la somme des entiers de à ?

Pour ce qui est du rangement de tous les entiers il me semble que le problème est trivial, il suffit de les prendre dans l'ordre:
1,2,1,3,2,4,5,3,6,7,4,8,5,9,10 ,6,11,7,12,13,8,...
même si elle n'est pas facile à écrire puisque l'on place l'entier suivant dans "le premier trou disponible" il me semble que cette suite est parfaitement définie, cela fonctionne parce que les deuxièmes occurences de deux nombres distincts ne peuvent pas se retrouver au même endroit dans la suite puisque leurs premières occurrences sont rangées par ordre croissant, il n'y a donc pas de conflit et puisque l'on dispose d'une infinité de nombres on peut boucher tous les trous qui se présentent au fur et à mesure Par contre le problème commence à devenir intéressant à partir de 3 copies.

[Médiat]

Bonjour,

Il me semble (si je ne me suis pas trompé) qu'il y a une démonstration plus simple que est paire :

Toute permutation conforme aux contraintes s'obtient à partir de la solution triviale (), en appliquant un certain nombre de transpositions.
Pour la solution triviale S est paire ().
Si une transposition échange deux éléments de type "-", ou deux éléments de type "+" S est inchangé, si elle échange un élément de type "-" et un de type "+", par exemple et , alors , autrement dit la parité de S n'est pas modifiée par une transposition, cqfd.

[KerLannais]

Oui il me semble que c'est là une très jolie démonstration

Pour info je donne la liste des solutions pour n=3,4,7 et 8, elle est générée automatiquement pas un programme. Je me suit arreté à 8 non pas parce que le temps de calcul devient devient trop long (pour 11 le calcul est encore quasi instantanné) mais parce que le fichier eut été trop énorme avec la liste des solutions pour n=11 ( 2.4Mo contre 20ko jusqu'à n=8)

[Médiat]

Il faudrait aussi étudier la fonction qui à n fait correspondre le nombre de solutions

[KerLannais]

bah euh pour ceux que ça intéresse


je ne suis pas allé plus loin. Cela dit si quelqu'un veut bien confirmer à l'aide d'un autre programme histoire d'être sûr que j'en oublie pas

[invite986312212]

des infos ici : http://en.wikipedia.org/wiki/Langford_pairing

[KerLannais]

cool ça veut dire que je ne me suis pas trompé dans le nombre de solutions (dans la page wiki ils comptent à symétrie près et donc ils divisent par 2). Dommage cette page soit aussi elliptique sur les méthodes algébriques utilisées pour le dénombrement de solutions
du coup il n'est pas clairement dit dans la page si la conjecture de Guigs est vraie

Je savais bien qu'il y avait un problème de graphe la dessous mais je n'ai pas cherché plus que ça. Ils ne disent pas dans la page s'il le problème des suites de Langford est polynomialement équivalent au problème de couverture exacte et donc on ne sais pas à priori si notre problème est NP-complet. Quelqu'un a une idée sur la question?

[invite986312212]

j'ai cherché ta suite (2,2,52,300...) sur le site OEIS mais elle n'y est pas alors j'ai pensé à la diviser par 2... par contre j'ai hésité à poster, tant il est vrai que savoir qu'un problème est bien connu peut être démobilisateur.

[inviteea2fb8cf]

L'article de Wikipédia mène sur une page plus détaillée, qui laisse penser (même si ce n'est pas explicitement écrit) que la conjecture de Guigs est vraie :

In one paper, Roy O. Davies gives a pattern for constructing a single solution for any valid n.

Je suppose que l'article est le suivant :
On Langford's problem. II., Davies, Roy O., Math. Gaz., 1959, vol. 43, pp. 253-255.
Il y a peut-être des références antérieures qui montrent l'existence de solutions, sans expliquer comment en construire explicitement.

~~~~~

Sinon, j'ai une autre "preuve" pour le fait qu'il est nécessaire que vaille ou modulo pour qu'il existe une solution.

Le problème peut être vu comme suit : il faut placer dans exactement blocs, où les blocs sont de la forme suivante :
+ - + (c'est le bloc 1 - 1)
+ - - + (c'est le bloc 2 - - 2)
+ - - - + (...)
etc.
Il ne peut y avoir aucune superposition partielle de blocs.

On peut voir comme étant une suite de cases alternativement blanches et noires : la case est blanche si est pair, et noire sinon (NB : j'aurais pu tout simplement utiliser "pair" et "impair", mais vu que je vais beaucoup utiliser ces termes par la suite, il me semble qu'utiliser "noir" et "blanc" est un peu moins confus).

Si est pair, alors le bloc - ... - occupe une case blanche et une case noire. Si est impair, alors le bloc - ... - occupe deux cases de même couleur.
Comme il y a autant de cases blanches que de cases noires à occuper, nécessairement il y a autant de blocs impairs (i.e. correspondant à un impair) occupant des cases blanches que de blocs impairs occupant des cases noires. Par conséquent, il y a un nombre pair de blocs impairs, on en d'autres termes le nombre d'entiers impairs de à est pair. Il est facile de vérifier que cela est équivalent à ce que vaille ou modulo .

[Forhaia]

Bonjour,

oui l'article donne une solution explicite:

Cas n=4m


Cas n=4m-1


Voilà encore une variante de la preuve que n=4m ou 4m-1 (elle est donnée dans l'article):
On suppose qu'on a une solution pour un certain n. On note la position du premier r pour .
Le deuxième r est alors en position et on a . Donc est entier, donc n est congru à 0 ou -1 modulo 4.