Problème d'arrangement de paires d'élèves
Bonjour j'ai un petit problème rigolo et sans doute très classique mais tout cela n'est pas trop mon domaine :
J'ai une classe de n élèves (n est pair) et je veux organiser n-1 séquences de travail et pour chaque séquence je veux que les élèves soient répartis en n/2 groupes de 2 tels qu'à la fin des n-1 séquence tout élève ait travaillé avec tous ses camarades (une fois et une une seule fois évidement !).
J'ai trouvé la solution pour n=4,6,8,10,12 mais j'ai une classe de 18 élèves (oui je veux vraiment utiliser la solution).
Si vous le souhaitez je peux vous exposer mes solutions (pour 4 et 6 c'est très facile, pour 8 çà demande quelques minutes et 10/12 çà m'a pris plus de temps, mais j'ai sans doute raté une méthode évidente !!).
Ma question est double :
(i) y a-t-il un algo simple pour résoudre ce problème (parce que je vais finir par faire un algo de recherche exhaustive sur mon ordi sinon
...) ?
(ii) y a-t-il toujours une solution ?
Je suis certain qu'il y a un algo tout simple qui m'échappe ou bien un truc scioux de théorie des groupes avec des groupes quotients ou des trucs de Galois que je ne connais pas..
Merci d'avance !!
Robin
J'ai une classe de n élèves (n est pair) et je veux organiser n-1 séquences de travail et pour chaque séquence je veux que les élèves soient répartis en n/2 groupes de 2 tels qu'à la fin des n-1 séquence tout élève ait travaillé avec tous ses camarades (une fois et une une seule fois évidement !).
J'ai trouvé la solution pour n=4,6,8,10,12 mais j'ai une classe de 18 élèves (oui je veux vraiment utiliser la solution).
Si vous le souhaitez je peux vous exposer mes solutions (pour 4 et 6 c'est très facile, pour 8 çà demande quelques minutes et 10/12 çà m'a pris plus de temps, mais j'ai sans doute raté une méthode évidente !!).
Ma question est double :
(i) y a-t-il un algo simple pour résoudre ce problème (parce que je vais finir par faire un algo de recherche exhaustive sur mon ordi sinon
...) ?(ii) y a-t-il toujours une solution ?
Je suis certain qu'il y a un algo tout simple qui m'échappe ou bien un truc scioux de théorie des groupes avec des groupes quotients ou des trucs de Galois que je ne connais pas..
Merci d'avance !!
Robin
Réponses
-
En cherchant un peu j'ai trouvé çà https://pdfs.semanticscholar.org/9d06/210bb12aaafc4d22bcc723f9258cfb658ae5.pdf je vais regarder. Ce serait bien si il y avait un petit logiciel (ou un package R/python) pour donner les factorisations pour n suffisamment petit
-
Bonjour,
A la main, illustration pour $n=4$ élèves : $A,B,C,D.$ Tu fais $n/2=2$ groupes de $2$, et tu organises $n-1=3$ séquences de travail.
Tu listes les élèves et tu décales d'une unité pour la première séquence :
$A-B-C-D$
$D-A-B-C$
Les groupes sont donc, dans l'ordre, $(A,D)$, $(B,A)$, $(C,B)$, $(D,C)$. Tu élimines $(B,A)$ puisque $A$ est déjà dans le premier groupe, tu élimines $(C,B)$ puisque $B$ est déjà dans le deuxième groupe. Il reste $(A,D)$ et $(C,B).$
Tu décales d'une autre unité :
$A-B-C-D$
$C-D-A-B$
Les groupes sont donc, dans l'ordre, $(A,C)$, $(B,D)$, $(C,A)$, $(D,B).$ Tu élimines les deux derniers et il reste $(A,C)$, $(B,D).$
Tu décales d'une autre unité :
$A-B-C-D$
$B-C-D-A$
Les groupes sont donc, dans l'ordre, $(A,B)$, $(B,C)$, $(C,D)$, $(D,A).$ Tu élimines $(B,C)$ et $(D,A)$ et il reste $(A,B)$ et $(C,D).$
Tu vérifies que chaque élève rencontre une seule fois chacun des autres.
Pour $n=6$, tu trouves d'abord $(A,F)$, $(C,B)$ et $(E,D).$
Puis quand tu décales $(A,E)$ et $(B,F)$ : donc ça ne marche pas. Il suffit de continuer à décaler.
Tu trouves $(A,E)$ et $(B,F)$ : donc ça ne marche pas. Il suffit de continuer à décaler.
Tu trouves : $(A,D)$, $(B,E)$, $(C,F).$
En gros l'algorithme c'est d'écrire la liste, puis de décaler d'une unité, puis de former les couples et si ça marche on continue, si ça ne marche pas, on décale d'une unité supplémentaire.
A programmer pour $n=18.$ -
Ai-je bien compris ?
1) on désire la liste des combinaison de $2$ éléments pris parmi $n$
2) on souhaite ordonner cette liste en $n-1$ ensembles (distincts) de $\dfrac{n}{2}$ couples dont chacun des $n$ élèves apparaît une et une seule fois
Pour $n=6$
(1,2)-(3,4)-(5,6)
(1,3)-(2,5)-(4,6)
(1,4)-(2,6)-(3,5)
(1,5)-(2,4)-(3,6)
(1,6)-(2,3)-(4,5)
J'ai utilisé une méthode similaire à celle de @YvesM, en éliminant les cas où l'on a un couple qui s'est déjà rencontré.
J'ai pris les élèves dans l'ordre croissant au lieu de décaler d'un cran.
En effet, l'algorithme est "facile à imaginer". -
Cet algorithme fournit quelque chose lorsque le décalage $k$ vérifie $v_2(k) \leq v_2(n)$, avec $v_2$ la valuation $2$-adique.
Le problème est équivalent à celui de trouver un carré latin symétrique avec des $0$ sur la diagonale. Le symbole $0$ ne correspond à rien et chaque autre symbole donne les couplages d'un jour. (Par cette interprétation, si un symbole n'apparaît pas sur la diagonale, alors la taille du carré doit être paire.)
On trouve des exemples pour toute taille qui est une puissance de $2$ grâce aux groupes $(\Z/2\Z)^k$. Ça correspond en fait exactement aux cas résolus par l'algorithme de YvesM, dommage. -
Nommons $P_0,P_1, \cdots, P_{n-1}$ les personnes.
En fait, il suffit de construire un $n-1$-gone régulier aux sommets duquel, on place $P_1,\cdots, P_{n-1}$.
On fixe $i$ dans $\{1,\cdots, n-1\}$.
Comme $n-1$ est impair, il est facile de vérifier qu'en utilisant des parallèles au côté $[P_iP_{i+1}]$ (avec $P_n=P_1$) du polygone, on peut répartir tous les autres sommets sauf un (celui sur la médiatrice de $[P_iP_{i+1}]$) par paires. On apparie ce sommet isolé avec $P_0$. Cela fournit une séquence de travail.
Et on fait ça successivement pour chaque côté du $(n-1)$-gone. Comme deux côtés ne sont jamais parallèles, on ne retombe jamais sur des paires déjà considérées, et le sommet isolé n'est jamais le même non plus.
Pierre. -
@PierreB
Merci Pierre c'est exactement le genre de solution que je voulais, c'est très astucieux
Robin
[Inutile de reproduire le message précédent. AD] -
Bonjour à tous,
Une récente discussion sur ce forum a suscité chez moi la question suivante:
Est -il possible d'organiser un tournoi opposant $2n$ équipes, se déroulant en $2n-1$ journées pendant lesquelles chaque équipe affronte une de ses adversaires, et à l'issue duquel chaque équipe a rencontré une et une seule fois chacune de ses rivales?
Ce problème équivaut à celui-ci:
Démontrer que le nombre chromatique du graphe $T(2n)$ est $2n-1$ où $T(n)$ désigne, pour $n\in \N,\: n>1$, le graphe ainsi défini:
L'ensemble des sommets de $T(n)$ est l'ensemble des paires de $\{1,2,\ldots,n\}$ et deux paires sont adjacentes si et seulement si leur intersection est un singleton.
Par sa naïveté, cette question fera bien entendu ricaner les rugbymen qui savent depuis longtemps que $\chi (6) =5$ et les footeux, plus subtils, qui n'ignorent pas que $\chi (20) =19$ , tout ce monde pensant à juste titre (je l'ai lu sur internet), que:
$$\boxed { \forall n\in \N, n>1\:\: \:\:\chi(n) =\left\{ \begin{array} {cl} n-1& \text{si }n\text{ est pair}\\ n &\text{sinon}\\ \end{array} \right.}$$
Quelqu'un aurait-il une référence pour une preuve de cette affirmation?
Amicalement,
[Discussions fusionnées. AD] -
Merci beaucoup,
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 8
+5 Invités