On a un groupe de 31 personnes et on veut les faire asseoir sur une table ronde indiscernable de 31 places. Pendant combien de jours peut on les faire asseoir de telles sortes que chacun n'est jamais les deux mêmes voisins (voisin de gauche et de droite)?
Bonjour, svp Comment commencer ce problème ? J’ai un peu du mal à débuter mon raisonnement
Je suggère de commencer avec un plus petit nombre de convives. Avec 3 et 4, c'est 1 jour (il y a toujours un voisin identique le deuxième jour). Avec 5 ce serait 2 jours si je n'ai pas fait d'erreur. La logique à suivre ne me semble toutefois pas évidente.
un majorant du nombre de jours est (n-1)!/2 (pour n convives). Mais il est très très mauvais...
Quand une personne aura vu les 30 autres personnes, il ne sera plus possible de lui trouver des voisins, soit 15 jours au mieux ou (n-1)/2Envoyé par MissJenny
Ah, si n était pair, on pourrait opérer des rotations.
plutôt (n-1)(n-2)/2 puisqu'il faut éviter les "2 mêmes voisins", il me semble.
J'ai encore mal lu l'énoncé. Avoir un même voisin plusieurs fois est autorisé, un même couple de voisins n'est pas permis.
Nombre de couples de voisins = C(30,2) = 435 couples possibles (30 * 29 / 2) ou (n-1)(n-2)/2 comme le note MissJenny.
Bonjour
Ce problème ne peut pas être résolut analytiquement, il faut voir du coté numérique.
Il faut imaginer, concevoir et écrire mathématiquement un algorithme
Et au lieu d’un groupe de 31, écrire, un groupe de N personnes
puis résoudre pour N= 31
ton algorithme sera surement NP et non P
Dernière modification par amineyasmine ; 28/11/2023 à 22h19.
Avec quelques lignes de programme je trouve le nombre de jours pour les petites valeurs de N
par exemple pour les premières valeurs, et nommant les convives avec des lettres et en imposant de commencer par le convive A, ce qui ne restreint pas la généralité:Code:N=3 ==> 1 N=4 ==> 3 N=5 ==> 6 N=6 ==> 9 N=7 ==> 11 N=8 ==> 15 N=9 ==> 21 N=10 ==> 28 N=11 ==> 35 N=12 ==> 43
Mauvaise nouvelle, aucune suite de l'OEIS ne commence par 1,3,6,9,11,15,21, etc...Code:configuration n = 3 : ABC configuration n = 4 : ABCD configuration n = 4 : ACBD configuration n = 4 : ACDB configuration n = 5 : ABCDE configuration n = 5 : ACDBE configuration n = 5 : ADBCE configuration n = 5 : ADCEB configuration n = 5 : ABDEC configuration n = 5 : ADEBC configuration n = 6 : ABCDEF configuration n = 6 : ADCEBF configuration n = 6 : ADECFB configuration n = 6 : ADBEFC configuration n = 6 : ACBEDF configuration n = 6 : AEDBCF configuration n = 6 : ACEFDB configuration n = 6 : AECBFD configuration n = 6 : AEFBDC configuration n = 7 : ABCDEFG configuration n = 7 : ADCEFBG configuration n = 7 : ADECFGB configuration n = 7 : AEBDFCG configuration n = 7 : ABEDFGC configuration n = 7 : ACBEFDG configuration n = 7 : ACEBFGD configuration n = 7 : AFCBDEG configuration n = 7 : AFEGCDB configuration n = 7 : ACFBDGE configuration n = 7 : AFBCGDE
There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.
Il faudrait peut-être travailler sur l’ensemble des entiers compris entre 1 et 31 et commencer par calculer le nombre d’ensembles obtenus par permutation des 2 entiers qui encadrent celui du milieu pour chaque élément .
Puis sélectionner un d’entre eux au départ par exemple le premier, celui contenant tous les entiers compris entre 1 et 31. On peut aussi choisir les 31 premières lettres de l'alphabet. On peut rajouter des lettres grecques.
Et calculer -je sais pas comment- le nombre de permutations possibles en s’arrêtant au moment où il y a forcément un ensemble contenant au moins un triplet identique à un autre parmi les autres ensembles. Jusque là c’est votre énoncé.
Ça a l’air assez compliqué et il faut trouver d’abord le formalisme adéquat: travailler sur un nombre en base 31 ?
Ou écrire un programme qui réalise ce comptage avec toutes les permutations possibles et les mettre dans un tableau, ce qui représente quelque chose de pas évident au départ.
Ensuite faire un autre tableau contenant lui tous les triplets possibles depuis l’ensemble initial des nombre compris entre 1 et 31. Ou des lettres comprises entre a et la 31ème de l'alphabet.
Ensuite il y a une heuristique à trouver pour répondre à votre question.
Dernière modification par oualos ; 02/12/2023 à 08h26.
L'adverbe s'applique aux trois verbes ?
Affirmation gratuite et non prouvée.
Not only is it not right, it's not even wrong!
Salut,
En raisonnant sur des triplets (a, b, c) représentant trois personnes côte à côte à une tablée et en construisant une tablée comme ceci :
(a, b, c) + (c, d, e) + (e, f, g) + ... , en tournant dans le sens anti horaire.
Rappel : on n convives et n places à une seule table
On a Arrangement(n, 3) triplets de convives différents possibles (Arr(31, 3) = 27970)
(on garde les symétriques, pour ... le programme)
On compte n triplets différents par tablée qu'il faut multiplier par 2 pour inclure les triplets inverses ((a,b,c) et (b, c, a)), on "consomme" donc 2 * n triplets par tablée. Un majorant de la solution vaut la partie entière de Arr(n, 3)/(2 * n)
Si on émet l'hypothèse qu'il est toujours possible de constituer une tablée avec les triplets non encore utilisés, pour autant qu'ils soient en nombre suffisant, alors on la solution simplissime = partie entière de int(Arr(n, 3)/(2 * n))
Résultats pour n de 3 à 50 sous spoiler (je confirme n=5 solution = 6)
Cliquez pour afficher
Me suis-encore affreusement trompé ?
Biname
Dernière modification par Biname ; 03/12/2023 à 08h43.
Ou
pourquoi répéter ce qui est connu dès le message #5 ?Ou
et que vient faire ici "la somme des entiers" ?
Dernière modification par jacknicklaus ; 03/12/2023 à 20h20.
There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.
Pourquoi dans ta solution informatique t'es tu arrêté à n = 13 ?
P(31) = 8.2e33 et A(31, 3) = 26970
Les majorants que donne le msg #11et que vient faire ici "la somme des entiers" ?
Au msg 11, je n'avais pas vu la simplification, le msg 12 l'ajoute.
Dernière modification par Biname ; 04/12/2023 à 06h48.
