[Demande d'Aide] Course de voiture

par **Formule1** » 17 Juil 2010, 23:59

Salut,

je ne suis pas du tout dans le domaine des mathématiques mais plus dans le domaine des courses automobiles.

J'organise des courses automobiles dans le cadre d'un hobby entre passionné.

Pour un futur challenge sur trois mois,nous souhaitions organiser quelque d original mais je butte sur certains points et je pense que les mathématiques pourront m'y aider.

Problématique :

Nous sommes 20 concurrents ( C1 à C20 ) et nous faisons une course 2 par 2 à chaque fois sans que l'un ne rencontre le même adversaire.

Cela fait donc 190 courses.Jusque la le tableau des courses est simple.
(C1 vs C2 , C3 vs C4 ,ect

Il y a 20 modeles de voitures (V1 à V20),j 'aimerai que chaque participant roule une fois avec chaque modele tout en ne tombant pas contre une voiture et un membre qu il es deja couru.

C1 utilise V1 Vs C2 utilise V2
C1 utilise V2 Vs C3 utilise C3

il ne faut que je me retrouve a un moment avec
C1 utilise V1 Vs C2 utilise V2
C1 utilise V1 Vs C7 utilise V2

Est ce possible mathematiquement?
J ai essaye plusieurs fois et plusieurs facons sur des tableaux excel,je me retrouve avec des doublons de voitures a chaque fois

J ai un faible niveau (bep) dans ce domaine,j'espère que vous pourrez m'aider,merci

par **Ben314** » 18 Juil 2010, 00:08

Salut,
En ce qui me concerne, j'ai l'impression que ce n'est pas "façile-façile" comme type de problème.

De plus, il y a un détail qui m'échappe : chaque participant fait exactement 19 courses (une contre chacun des autres) alors qu'il y a 20 modèles de voitures différentes : il ne pourra donc pas utiliser une fois chaque modèle.
Soit on diminue le nombre de modèles à 19, soit on demande uniquement à ce qu'il n'utilise pas 2 fois la même voiture (mais dans ce cas, s'il y a un modèle "mieux" que les autres et un participant qui ne pilote jamais ce modèle, c'est un peu "tristouille" pour lui)

par **Formule1** » 18 Juil 2010, 00:15

Ah c est bien ce que je me disais , en reduisant le nombre de modeles de voiture ,cela est il possible?

Je tiens a votre disposition la programmation des courses du challenge.

par **Ben314** » 18 Juil 2010, 00:28

Ben... j'en sais rien.
Je vais y réfléchir, mais ç'est pas sûr que ce soit concluant (ni rapide...)

Bon on part donc sur 20 coureurs, 19 modèles de voitures, chaque coureur doit courir exactement une fois avec chacun des modèles et les voitures contre lesquelles il tombe doivent aussi être exactement une fois de chaque modèle.

Dernière question : les rencontre "monotype", c'est à dire où les deux courreurs ont le même modèle de voiture sont acceptées ou pas ? (je pense que non, mais je préfèrerais être sûr...)

par **Formule1** » 18 Juil 2010, 00:43

Pas de rencontre monotype non.

Merci pour votre aide.

par **Ben314** » 18 Juil 2010, 00:47

Je vais y réfléchir (en allant me coucher... :dodo: )

par **Formule1** » 18 Juil 2010, 00:51

:) , bonne nuit,a bientot

par **Formule1** » 18 Juil 2010, 09:58

(erreur de post)

par **Ben314** » 18 Juil 2010, 11:04

Bon, dans le cas ou le nombre de pilotes est impair, il y a une solution 'théorique' simple. Par contre, pour le cas pair, j'ai pas trouvé de soluce "théorique" mais en faisant un petit programme, j'ai des tonnes de solutions pour 20 pilotes.
Par exemple :

Code: Tout sélectionner: | C01 C02 C03 C04 C05 C06 C07 C08 C09 C10 C11 C12 C13 C14 C15 C16 C17 C18 C19 C20 ----+-------------------------------------------------------------------------------- C01| --- V01 V02 V03 V04 V05 V06 V07 V08 V09 V10 V11 V12 V13 V14 V15 V16 V17 V18 V19 C02| V02 --- V19 V01 V03 V04 V05 V06 V07 V08 V09 V10 V11 V12 V13 V14 V15 V16 V17 V18 C03| V03 V02 --- V18 [B][COLOR=Red]V19[/COLOR][/B] V01 V04 V05 V06 V07 V08 V09 V10 V11 V12 V13 V14 V15 V16 V17 C04| V04 V17 V01 --- V16 V18 V19 V02 V03 V05 V06 V07 V08 V09 V10 V11 V12 V13 V14 V15 C05| V05 V04 [B][COLOR=Red]V15[/COLOR][/B] V02 --- V16 V17 V18 V01 V19 V03 V06 V07 V08 V09 V10 V11 V12 V13 V14 C06| V06 V14 V11 V15 V12 --- V13 V16 V17 V01 V18 V19 V02 V03 V04 V05 V07 V08 V09 V10 C07| V07 V03 V05 V11 V09 V14 --- V13 V15 V16 V17 V18 V19 V10 V01 V12 V08 V02 V04 V06 C08| V08 V05 V10 V12 V01 V11 V14 --- V16 V17 V15 V02 V13 V18 V19 V06 V09 V07 V03 V04 C09| V09 V06 V18 V14 V13 V02 V01 V12 --- V11 V16 V17 V03 V19 V15 V04 V05 V10 V07 V08 C10| V10 V07 V16 V04 V14 V17 V02 V09 V05 --- V01 V12 V15 V06 V08 V19 V03 V18 V11 V13 C11| V11 V08 V09 V13 V07 V12 V15 V01 V19 V18 --- V03 V16 V14 V06 V02 V17 V04 V10 V05 C12| V12 V09 V08 V16 V11 V06 V03 V14 V13 V10 V19 --- V04 V15 V17 V07 V18 V05 V02 V01 C13| V13 V10 V12 V06 V02 V07 V18 V15 V14 V03 V11 V05 --- V04 V16 V17 V01 V19 V08 V09 C14| V14 V19 V07 V10 V15 V13 V11 V17 V18 V02 V04 V01 V09 --- V05 V08 V06 V03 V12 V16 C15| V15 V11 V14 V08 V18 V19 V12 V03 V09 V13 V05 V04 V17 V07 --- V16 V10 V06 V01 V02 C16| V16 V13 V17 V09 V08 V15 V07 V11 V10 V04 V12 V14 V18 V05 V02 --- V19 V01 V06 V03 C17| V17 V16 V06 V19 V05 V08 V10 V04 V02 V12 V07 V13 V14 V01 V18 V03 --- V09 V15 V11 C18| V18 V12 V13 V05 V17 V03 V08 V10 V04 V06 V14 V15 V01 V16 V11 V09 V02 --- V19 V07 C19| V19 V18 V04 V07 V06 V10 V09 V08 V11 V15 V02 V16 V05 V17 V03 V01 V13 V14 --- V12 C20| V01 V15 V03 V17 V10 V09 V16 V19 V12 V14 V13 V08 V06 V02 V07 V18 V04 V11 V05 ---

Le tableau est à comprendre sous la forme :
La case (i,j) (ligne i, colonne j) donne la voiture qu'emploira le pilote i lorsqu'il va rencontrer le pilote j.
Par exemple (en rouge) lors de la rencontre entre les pilotes 3 et 5, le pilote 3 prend la voiture 19 et le pilote 5 prend la voiture 15.

Evidement, à titre de "casse tête", s'il y en a que ça tente de trouver une solution dans le cas n (=nb de pilotes) pair, ça doit sans doute être trouvable... (il n'y a pas de soluce pour n=2 et n=4 mais il semblerait qu'il y en a pour tout n pair >=6)

par **Formule1** » 18 Juil 2010, 19:02

Super ton tableau, j'ai bien fait de faire appel à vous.

Merci beaucoup pour le temps passé sur mon problème.

J'essaie de retranscrire tout ça sur mon planning.Je laisse le post ouvert pour mes tests,merci encore Ben.

par **Formule1** » 18 Juil 2010, 21:47

Je pense que j'ai du oublier de parler d'une chose, il ne faut pas que deux modeles de voiture se soient non plus disputes

Exemple de ce qu'il ne faut pas

C1 conduit V1 VS C2 conduit V2
et dans une autre course
C3 conduit V1 Vs C4 conduit V2

Car là en fait dans ton tableau tout le monde joue tout le monde avec une voiture différente mais il arrive que 2 voitures se soient déjà disputées.

Je pense que le casse tête est encore plus dur avec cet option que j'avais oublié ou mal mentionné

Merci

par **Ben314** » 18 Juil 2010, 22:03

Oui, mais là, de nouveau, ça coince direct du fait que
20 pilotes => 20*19/2=190 "couples" de pilotes possibles (donc normalement 190 courses si tout le monde rencontre tout le monde)
19 voitures => 19*18/2=171 "couples" de voitures possibles.
Donc forcément, il va y avoir certain couples de voitures qui apparaitront 2 fois.
Ou alors, on remonte à 20 voitures, mais dans ce cas, au mieux, chaque pilote ne conduira que 19 des 20 voitures différentes vu qu'il ne cours que 19 courses...

par **Formule1** » 18 Juil 2010, 22:27

Ok pour remonter à 20 voitures alors, chaque joueur aura un modèle exclu de sa liste, désolé pour le temps passé sur le 1er tableau

par **Anonyme** » 19 Juil 2010, 00:56

Pour un futur challenge sur trois mois,nous souhaitions organiser quelque
Nike TN|TN Requin|Tn requin|Nike TN|Nike Ninjad original mais je butte sur certains points et je pense que les mathématiques pourront m'y aider.

par **Formule1** » 21 Juil 2010, 02:20

T es toujours sur le coup pour m'arranger un tableau Ben?

C est juste un message pour savoir , rien de pressé.Merci

par **Dihtbscii** » 21 Juil 2010, 11:34

Bizarrement je vois directement ce qui me semble être une solution (quelle que soit la parité) :
Quand le coureur a rencontre le coureur b (aMe trompe-je? :hein:

par **Dihtbscii** » 21 Juil 2010, 11:37

Ah j'avais pas vu la 2ème page, du coup c'est sur que mon truc marche plus, mais sans la derniere condition, j'ai l'impresson que j'ai donné qqchose de bon.

par **Ben314** » 21 Juil 2010, 12:51

Salut Dihtbscii,
Un des premiers essai que j'ai fait (avec n pilotes et n voiture) et de dire que, lorsque le pilote i rencontre le pilote j, il utilise la voiture f(i,j)=ai+bj modulo n où a et b sont fixé.
Il est assez façile de montrer que, pour que ça marche, il faut (et il suffit) que a, b, a+b et a-b soient premiers avec n.
Or de tels a et b n'existent que si n n'est divisible ni par 2, ni par 3 donc il n'y a pas de solutions de cette forme pour n=20 (ou n=21) mais il y en a une pour n=19 : par exemple f(i,j)=2i-j (modulo 19).

Pour n quelconque, j'ai fait un petit programme, mais il commence à demander du temps de calcul lorsque n vaut une dixaine, donc pour n=20, j'ai peur qu'il ne donne le résultat que dans quelque millier d'années... (il faudrait que j'améliore l'algo)

EDIT :

Dihtbscii a écrit:Bizarrement je vois directement ce qui me semble être une solution (quelle que soit la parité) :
Quand le coureur a rencontre le coureur b (a<b), le coureur a prend la voiture numéro b-a et le coureur b prend la voiture numéro n+a-b.
Me trompe-je? :hein:

Si n est pair et que b-a=n/2 alors n+a-b est aussi égal à n/2 et on a une "course monotype" qui est interdite par le réglement (même sans "la condition de la page 2")

par **gnarfk** » 21 Juil 2010, 13:53

J'ai déjà organisé des tournois fermés d'echecs, avec comme système d'appariements un pivot et les autres qui se déplacent tjrs dans le même sens. ton problème ici revient à ajouter une contrainte.
je vais illustrer par un exemple.

imaginez un tournoi de 8 joueurs (pour faire simple , ça se généralise facilement pour plus).

on les dispose 2 par tables , comme suit (les tables sont verticales):

1 2 3 4
8 7 6 5

à la ronde 2 , tout le monde tourne d'un cran , sauf le joueur 1 , qui ne bouge jamais.

on se retrouve alors :
1 8 2 3
7 6 5 4

ce que je propose pour résoudre ton problème, ça serait de faire un appariement de ce genre pour les coureurs, et un du même genre pour les voitures, tournant dans l'autre sens et avec un pivot à un autre endroit.
on aurait alors pour les voitures :
4 3 2 1
5 6 7 8

qui donnerait à la ronde 2

3 2 8 1
4 5 6 7

en superposant les 2 , tu obtiens donc un tournoi dans lequel chaque course confronterait bien à chaque fois 2 coureurs n'ayant pas couru l'un contre l'autre , et 2 voitures n'ayant pas couru l'une contre l'autre.
de plus , comme les pivots ne sont pas au même endroit et que ça ne tourne pas dans le même sens , les coureurs auront à chaque fois une voiture différente. (edit : il faut vérifier ce point la cependant, je ne l'ai pas démontré et je ne suis pas sur qu'il soit tjrs valable)
(en cas de nombre de participants impair , le pivot est un joueur "imaginaire" contre qui devrait courir celui qui ne court pas, mais il faudra quand meme le placer à 2 endroits différents dans le truc selon que ça soit pour les coureurs ou les voitures)

par **Formule1** » 28 Juil 2010, 01:14

Merci,j'avoue avoir compris le sens de la méthode mais malgré de multiples tentatives,je me trouve face à des doublons.

Peut etre que le programme de Ben calcule tout ca en ce moment,enfin j'espere car je coince vraiment.

[Demande d'Aide] Course de voiture

[Demande d'Aide] Course de voiture

Qui est en ligne