Combinaisons sur un damier

[Utilisateur supprimé]
[Utilisateur supprimé]
dans Combinatoire et Graphes
Bonjour

J'aimerais vos lumières pour trouver la faille dans un raisonnement manifestement faux. Je connais le résultat qui est 9 obtenu par un raisonnement et par un programme informatique, mais j'aimerais y arriver par un autre raisonnement qui me semble logique mais qui donne 11 au lieu de 9.

Voici le problème.
Supposons un damier carré contenant 16 cases, sur la diagonale se trouvent des tours noires. Je dispose de 4 autres tours rouges indistinguables.

Je voudrais le nombre de cas où les 4 tours rouges sont sur le damier de sorte qu'aucune rouge ne soit alignée avec une autre rouge.
Tout d'abord le 1er raisonnement : je pose une tour sur la 1ère colonne, pour une des 3 autres colonnes (celle où la noire est alignée avec la rouge posée) avec j'ai aussi 3 possibilités, et pour les colonnes restantes je n'ai plus qu'une possibilité d'où le nombre de cas possibles = 3x3 = 9.

Voici maintenant mon raisonnement qui me semble correct mais me donne 11 au lieu de 9.
Pour la 1ère tour j'ai 12 possibilités de placements sur tout l'échiquier.
Pour la deuxième j'en ai 7 mais suivant où je la place, je n'ai pas le même nombre de possibilité pour la 3ème tour.
pour 2 positions de la 2ème tour, j'ai 4 possibilités pour la 3ème tour, 1 possibilité pour la 4ème tour
pour 4 positions de la 2ème tour, j'ai 3 possibilités pour la 3ème tour, 1 possibilité pour la 4ème tour
pour 1 positions de la 2ème tour, j'ai 2 possibilités pour la 3ème tour, 1 possibilité pour la 4ème tour
Et c'est toujours ce même principe quelque soit où j'ai posé la 1ère tour.
Ce qui me donne le nombre de solutions :
(12 x 2 * 4* 1) + (12 x 4 * 3* 1) + (12 x 1 * 2* 1) que je divise par 4! pour éliminer les "doublons", car chaque tour est indiscernable, et ça me donne 11 au lieu de 9.

Sauriez-vous voir où est l'erreur ?65738

Réponses

  • GaBuZoMeu
    GaBuZoMeu
    Les positions des tours rouges correspondent exactement aux matrices de permutations sans point fixe (aussi appelées dérangements) : il y a exactement une tour rouge par ligne et une tour rouge par colonne (permutation) et aucune tour rouge est sur la diagonale (sans point fixe).
    Le comptage des dérangements a été traité de nombreuses fois sur le forum.
    Ici :
    $$4! -4\times 3!+ 6\times 2! - 4\times 1! + 0!=24-4\times 6+6\times 2-4\times 1+1=9\;.$$
    En termes d'échiquier :
    On compte toutes les dispositions possibles de tours rouges sans la contrainte qu'il n'y en ait pas sur la diagonale, on enlève pour chacune des quatre cases de la diagonale le nombre de dispositions contenant cette case, on rajoute pour chacun des six ensembles de deux cases de la diagonale le nombre de dispositions contenant ces deux cases (elles ont été enlevées deux fois), on enlève pour chacun des quatre ensembles de trois cases de la diagonale le nombre de dispositions contenant ces trois cases, et finalement on rajoute un pour la disposition diagonale.

    Maintenant, tu peux passer à un échiquier $8\times 8$ et 8 tours de chaque couleur. Quel résultat dans ce cas ?
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    J'aimerai aussi et surtout déjà savoir où est l'erreur dans mon raisonnement précédent en fait.
    Pourriez vous passer un peu de temps dessus pour identifier ce qui cloche, pourquoi j'obtiens 11 au lieu de 9, alors que le raisonnement semble logique ?
  • GaBuZoMeu
    GaBuZoMeu
    pour 4 positions de la 2ème tour, j'ai 3 possibilités pour la 3ème tour, 1 possibilité pour la 4ème tour
    Peux-tu justifier ça ?
  • soland
    soland
    Chaque disposition des tours rouges est le graphe d'une permutation (une tour par colonne, pas deux tours à la même hauteur).
    Les tours noires interdisent que la permutation ait des points fixes. La permutation est donc un dérangement.
    La proportion des dérangements dans l'ensemble des permutations de $n$ objets est très proche de $1/e$.
    Donc $24/e\approx 9$.
  • GaBuZoMeu
    GaBuZoMeu
    @soland : c'est ce que j'ai déjà expliqué, et j'ai fait un calcul exact.
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    GaBuZoMeu écrivait : http://www.les-mathematiques.net/phorum/read.php?34,1502152,1502160#msg-1502160
    [Inutile de recopier l'avant dernier message. Un lien suffit. AD]

    Oui en PJ les 4 cas (la tour 3 possède 3 positions possibles) en question
    J'ai aussi mis :
    - les 2 cas où la tour 3 possède 4 positions possibles
    - le cas où la tour 3 a 2 positions possibles65754
    65756
    65752
  • GaBuZoMeu
    GaBuZoMeu
    Voici pourquoi tu as forcément fait une erreur à l'endroit que j'ai indiqué :
    Une fois les tours 1 et 2 disposées, les dispositions correctes des tours 3 et 4 vont par paires (deux positions sont dans la même paire si on passe de l'une à l'autre en échangeant les dossards 3 et 4). Donc ton $3\times 1$ est forcément une erreur. Comme tu n'expliques rien de ton $3\times 1$, je ne peux pas en dire plus. À toi de voir où tu t'es gourré.
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    GaBuZoMeu écrivait : http://www.les-mathematiques.net/phorum/read.php?34,1502152,1502186#msg-1502186

    Dans mon raisonnement, chaque tour est considérée comme unique, j'énumère tous les cas et à la fin je divise par 4! le nombre de fois où chaque configuration semblable apparaît.

    Une fois les tours 1, mon dénombrement donne le nombre de position de la tour 2 où j'ai 2, 3 ou 4 positions possibles pour la tour 3. Dans tous les cas, les tours 1, 2, 3 étant posé je n'ai plus qu'une possibilité où mettre la tour 4.
    Par exemple, j'ai 4 positions de la tour 2 où j'ai 3 positions pour la tour 3 ( la tour 3 choisie, j'en ai plus qu'une pour la tour 4), ça donne 4*3*1.
    De même, j'ai 2 positions de la tour 2 où j'ai 4 positions pour la tour 3 ( la tour 3 choisie, j'en ai plus qu'une pour la tour 4), ça donne 2 *3*1
    De même, j'ai 1 position de la tour 2 où j'ai 2 positions pour la tour 3 ( la tour 3 choisie, j'en ai plus qu'une pour la tour 4), ça donne 1 *2*1

    Et j'ai ainsi énuméré les 7 (= 4 + 2 + 1) cas possibles où je pouvais mettre la tour 2.

    Et comme au départ j'ai 12 positions pour la 1ère tour ça donne

    12 * (4*3*1) = 12 * 12
    +
    12 * (2*4*1) = 12 * 8
    +
    12 * (1*2*1) = 12 * 2
    = 11 * 4!
  • GaBuZoMeu
    GaBuZoMeu
    Tu demandes qu'on t'indique ton erreur, et quand on te montre où elle est, tu refuses de la voir. Je t'ai donné un argument qui prouve que tu t'es trompé à l'endroit que j'ai indiqué.
    Bon, je te donne une indication supplémentaire : une fois que tu as placé la tour 3, es-tu sûr que tu peux toujours placer la tour 4 ?
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Non je veux bien la voir, je suppose que je n'ai pas compris.
    Oui je peux toujours placer la tour 4. Lorsque j'ai placé les 3 tours convenablement, j'ai ensuite qu'un choix possible pour la tour 4.
  • GaBuZoMeu
    GaBuZoMeu
    Tu ne réfléchis pas sérieusement à ce que je te dis. As-tu vraiment essayé de placer la quatrième tour ?

    PS. Puisque tu es sûr, démontre moi que pour les trois positions de ta tour 3, tu peux placer ta tour 4.
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Oui, j'ai pu la placer, il n'y a aucun souci pour faire cela.
    Par exemple :65758
  • GaBuZoMeu
    GaBuZoMeu
    Ton dessin ne prouve rien. Moi, j'ai prouvé que $3\times 1$ était impossible, puisque $3$ est impair.
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Oui oui ok, tu as raison, je suis tombé sur un cas où c'était possible, mais pour les 2 autres c'est en effet impossible.

    Merci de m'avoir indiqué l'erreur, j'ai été obligé d'aller jusqu'au bout pour le voir.

    J'aimerais bien comprendre comment vous avez vu que ça clochait.65760
  • remark
    remark
    .
  • GaBuZoMeu
    GaBuZoMeu
    J'aimerai bien comprendre comment vous avez vu que ca cochait.
    Je t'ai déjà expliqué pourquoi (le fait que 3 est impair).
    Oui oui ok, tu as raison, je suis tombé sur un cas où c'était possible, mais pour les 2 autres c'est en effet impossible.
    Tu es encore dans l'erreur ! Ce que tu racontes est tout aussi impossible pour raison de parité.

    Tu as l'air allergique aux raisonnements mathématiques. En plus tu es approximatif dans tes bricolages. La combinaison des deux est fatale.
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    > Tu es encore dans l'erreur ! Ce que tu racontes
    > est tout aussi impossible pour raison de parité.


    Tu ne m'as pas compris, dans les 3 dessins du haut en PJ, il n'y a qu'un seul cas où j'ai pu poser une rouge, les deux autres non, c'est tout.
  • GaBuZoMeu
    GaBuZoMeu
    Je t'ai très bien compris. Et je t'ai expliqué pourquoi " il n'y a qu'un seul cas où j'ai pu poser une rouge, les deux autres non. " est forcément faux. D'ailleurs, quand on regarde les dessins, on voit bien que ton affirmation est fausse, surtout en pensant à l'argument que j'ai donné et que je rappelle :
    les dispositions correctes des tours 3 et 4 vont par paires (deux positions sont dans la même paire si on passe de l'une à l'autre en échangeant les dossards 3 et 4).
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Oui vous avez raison, il y a deux cas possibles, et pas un. Désolé, je suis fatigué et peu rigoureux sur ce problème qui épuise mon énergie depuis un bout de temps (il fait partie d'un problème plus large).
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Excusez moi excusez moi :)
  • GaBuZoMeu
    GaBuZoMeu
    Quel problème plus large ?
    La façon dont tu t'y es pris n'est vraiment pas optimale. Si tu veux aller plus loin avec ces méthodes, ça risque fort de capoter.
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Mon problème plus large est le suivant.

    Sur un damier 8x8 on dispose de 4 tours blanches et 4 tours noires.
    Combien y a-t-il de combinaisons possibles sachant que les noires et les rouges ne peuvent pas être alignées entre elles, mais une noire et une rouge peut l'être.

    EDIT : correction le problème parle d'un damier 8x8 et non 16 x16
  • GaBuZoMeu
    GaBuZoMeu
    sachant que les noires et les rouges ne peuvent pas être alignées.
    Qu'est-ce que ça veut dire ?
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    - une noire ne peut pas être sur la même ligne ou colonne qu'une noire
    - une rouge ne peut pas être sur la même ligne ou colonne qu'une rouge
  • GaBuZoMeu
    GaBuZoMeu
    Bon, là c'est clair. Il vaut toujours mieux écrire les choses clairement.
    Ce problème se traite relativement facilement avec la méthode d'inclusion-exclusion que j'ai esquissée pour le cas de l'échiquier $4\times 4$.
    Pour commencer, combien de façons de disposer $n$ tours sur un échiquier $p\times p$ de telle sorte qu'il n'y ait jamais deux tours sur la même ligne ni sur la même colonne ?

    PS. La réponse à ton problème, pour un échiquier $17\times 17$, $4$ tours noires et $4$ tours blanches est $17475904352995200$. Avec des tours noires et des tours rouges, même résultat.
  • soland
    soland
    Pour le cas général, la formule $\quad\#$ de dérangements = Round$(n!/e)\quad$ vaut quand même de l'or.
  • GaBuZoMeu
    GaBuZoMeu
    Belle formule, mais qui ne dit rien sur le "problème plus large" de Turbolanding.
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Sur un autre forum on a je pense résolu le problème, mais sans passer par la formule d'inclusion exclusion.

    On a trouvé comme résultat final 10678197600.

    Je suis désolé, j'ai déjà grillé mon crédit de temps à passer sur ce problème.
    Mais si vous voulez discuter, exposer votre solution ici pas de soucis.
    Pour lancer la résolution mais je ne pourrais pas poursuivre, pour ma petite contribution je répondrais à la question précédente par $C_n^p n!$.
  • GaBuZoMeu
    GaBuZoMeu
    Décidément, ça ne va pas fort.
    La solution que tu indiques est celle pour un échiquier $8\times 8$, alors que tu parlais d'un échiquier $16\times 16$. Faudrait savoir !

    Ma solution en Sage : 
    def solution(n,p) :
    ie = sum((-1)^k*factorial(n)*binomial(p-k,n-k)^2/factorial(k) for k in range (n+1))
    return binomial(p,n)^2*factorial(n)*ie
    (n est le nombre de tours de chaque couleur, p la taille de l'échiquier.
    La question 
    solution(4,8)
    amène la réponse 
    10678197600
    De quel "autre forum" parles-tu ?

    PS. Ta réponse est incorrecte.
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Désolé fatigué, c'est bien damier 8 x 8 le problème

    Si tu veux voir pourquoi on a obtenu ce résultat tu peux regarder ici :

    http://forums.futura-sciences.com/mathematiques-college-lycee/795353-probabilites-echecs-5.html#post5944894
  • GaBuZoMeu
    GaBuZoMeu
    Ouais, ça a l'air assez pénible. Heureusement qu'il y a moyen de faire plus conceptuel et plus sûr avec le comptage par inclusion exclusion.
    Je dis brièvement le principe : on suppose les quatre tours blanches déjà correctement placées sur l'échiquier, aux cases $C_1,C_2,C_3, C_4$.
    On appelle $B$ l'ensemble des dispositions de tours noires qui respectent la contrainte pas deux sur la même ligne, pas deux sur la même colonne et $A_i$ le sous-ensemble de telles dispositions qui occupent la case $C_i$, pour $i=1,\ldots,4$.
    Il est facile de compter le cardinal de $B$ et les cardinaux des $A_i$, de leurs intersections 2 à 2, 3 à 3 et de l'intersection des quatre.
    À partir de là la formule d'inclusion-exclusion donne le cardinal de $B\setminus\bigcup_{i=1}^4 A_i$, qui est l'ensemble des bonnes dispositions des tours noires qui n'occupent aucune des cases des tours blanches.
    On a gagné et on obtient une formule qui marche en fait pour n'importe quelles taille d'échiquier et n'importe quel nombre de tours.
    .
  • messy
    messy
    BONJOUR
    quelqu'un peut me dire a quel niveau d'étude on apprend ces mathodes de derangement et dinclusion exclusion
    MErCI
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 7

AlainLyonFoys +5 Invités