Un défi par semaine

Juin 2016, 3e défi

17 juin 2016  - Ecrit par  Ana Rechtman Voir les commentaires (8)

Nous vous proposons un défi du calendrier mathématique 2016 chaque vendredi et sa solution la semaine suivante.

Semaine 25 :

De combien de façons différentes peut-on ranger les nombres $\{1,2,3,4,5,6\}$ si l’on veut que le produit de deux nombres voisins soit toujours pair ?

Solution du 2e défi de Juin :

Enoncé

La réponse est $n=10$.

Nous commençons par $(a_0,b_0,c_0)=(1,2,3)$, ensuite $(a_1,b_1,c_1)=(3,5,4)$ et $(a_2,b_2,c_2)=(8,9,7)$, etc. Soit $x_0=a_0+b_0+c_0=6$ ; nous avons :

$x_1=a_1+b_1+c_1 = (a_0+b_0)+(b_0+c_0)+(c_0+a_0)$

$ = 2(a_0+b_0+c_0)=2x_0=12.$

Donc $x_2=a_2+b_2+c_2=2x_1=4x_0=24$ et ainsi successivement :
$x_1=2x_0$, $x_2=2x_1=2^2 x_0$, $x_3=2x_2=2^3 x_0$ et $x_n= 2^n x_0$. Nous cherchons donc $n$ tel que : $1000 < \frac{2^n\,x_0}{x_0}= 2^n < 2000$, d’où nous concluons que $n=10$, puisque $1000 < 1024 < 2000$.

Post-scriptum :

Calendrier mathématique 2016 - Sous la direction d’Ana Rechtman, Maxime Bourrigan - Textes : Aubin Arroyo, Fabiola Manjarrez et Ana Rechtman.
2015, Presses universitaires de Strasbourg. Tous droits réservés.

Partager cet article

Pour citer cet article :

Ana Rechtman — «Juin 2016, 3e défi» — Images des Mathématiques, CNRS, 2016

Commentaire sur l'article

  • Juin 2016, 3e défi

    le 17 juin à 07:54, par Al_louarn

    Rangeons les $6$ nombres dans un tableau de $6$ cases numérotées de $1$ à $6$.
    Il y a au total $6!$ façons de le faire (permutations).
    Si $i$ est le nombre de permutations où au moins un couple de nombres impairs apparaît dans $2$ cases consécutives, alors la réponse au problème est $6! - i$.

    Pour calculer $i$ on commence par choisir $(a,b)$, premier de ces couples de nombres impairs dans le tableau :

    • il y a $3$ choix possibles pour $a$ : $1$, $3$ ou $5$
    • il reste alors $2$ choix possibles pour $b$
      Ensuite on choisit la case $k$ de $a$ : $1 \leq k \leq 5$.
      Si $k=1$ alors $b$ est dans la case $2$, et il n’y a plus qu’à ranger les $4$ autres nombres dans un ordre quelconque dans les $4$ cases suivantes : $4! = 24$ choix possibles
      Si $2 \leq k \leq 5$ alors ça donne $4$ cas où :
    • on met un nombre pair dans la case $k-1$ : $3$ choix possibles
    • on met $b$ dans la case $k+1$
    • on range les $3$ autres nombres dans un ordre quelconque dans les $3$ cases restantes : $3! = 6$ choix possibles
      Donc $i=3 \times 2 \times (24 + 4 \times 3 \times 6)$.

    La solution est donc $6! - i = 144$.

    Répondre à ce message
    • Juin 2016, 3e défi

      le 17 juin à 12:40, par Ncastel

      J’aurais dit qu’il faut alterner pair-impair-pair-impair ...
      Il y a donc 3 emplacements pour 3 nombres pairs, donc 3 !=6 possibilités
      et pareil 6 pour les nombres impairs.
      Pair et impair sont indépendants donc 6*6=36 possibilités, si on commence par
      un nombre pair.
      Si on commence par un nombre impair, c’est pareil, 36
      Donc 72 au total.

      Répondre à ce message
      • Juin 2016, 3e défi

        le 17 juin à 16:21, par Al_louarn

        Il vous manque de nombreux cas, par exemple : impair,pair, pair, impair, pair, impair

        Répondre à ce message
  • Juin 2016, 3e défi

    le 17 juin à 12:32, par mesmaker

    Je trouve, évidemment, le même résultat mais avec une technique un peu différente.

    Ce qui importe c’est qu’il n’y ait pas de nombres impairs consécutifs. Donc voyons où peuvent être ces trois nombres impairs 1, 3 et 5.
    S’il y a deux nombres impairs sur les bords du type 1, 2, 3, 4, 6, 5.
    Alors il y a trois possibilités pour le nombres impairs sur le côté droit, il en reste deux pour le côté gauche et le dernier n’a que deux cases de possible la 3eme et la 4eme. Le reste sera rempli par les nombres pairs. Cela donne 3*2*2 * 3*2*1 = 72 combinaisons possibles.

    Ensuite je traite le cas où il n’y a qu’un seul nombre impair sur un côté, le gauche par exemple, du type 1, 2, 3, 4, 5, 6. Dans ce cas, on peut choisir trois nombres impairs à gauche, puis les deux autres nombres impairs doivent être sur les cases 3, 4 ou 5. Comme il ne peuvent se toucher ils doivent être sur les cases 3 et 5. Et comme il en reste deux, il y a deux possibilités. Le reste des cases est rempli par les chiffres pairs. Cela donne 3*2 * 3*2*1 possibilités. Il en est de même si le nombre impairs est sur le côté droit et non le côté gauche, donc on multiplie par 2 : 2 * 3*2 * 3*2*1 = 72 cas.

    Enfin s’il n’y a aucun nombre impairs sur les côtés alors ils doivent être sur les cases 2, 3, 4 et 5. Or trois impairs pour quatre cases consécutives cela donne obligatoirement deux impairs qui se touche. Donc pas de cas ici.

    En résumé, les cas avec deux impairs sur les côtés, 72, plus les cas avec un impair sur un côté, 72, donne bien les 144 cas.

    Répondre à ce message
  • Juin 2016, 3e défi

    le 17 juin à 14:20, par Daniate

    Autre vision, pour le problème de n pairs avec n impairs.

    Pour n=1 : 2 solutions ip et pi donc une seule s’achevant par un pair.

    Hypothèse de récurrence : avec n pairs et n impairs on a n+1 possibilités dont une seule s’achève par un pair.

    Pour passer au rang n+1 il faut prolonger soit par ip soit par pi . Or les finales impaires ne se prolongent que par pi et la finale paire par l’une ou l’autre. On a alors n+2 solutions dont une seule s’achève par paire.

    Pour finir on a 6 façons d’organiser les pairs (impairs) soit 36(n+1) possibilités pour n pairs et n impairs, avec ici n=3 donc 4*36=144 possibilités

    Répondre à ce message
    • Juin 2016, 3e défi

      le 17 juin à 17:35, par Daniate

      Errata : Je suis resté avec n=3, dans le cas général il y a n ! d’organiser les pairs (ou les impairs).La formule générale est donc (n+1)(n !)²

      Répondre à ce message
    • Juin 2016, 3e défi

      le 18 juin à 00:26, par Al_louarn

      Une autre approche du cas général, sans récurrence :

      Notons d’abord que tous les impairs sont nécessairement précédés par un pair, sauf le premier pour lequel c’est facultatif.

      On commence donc par construire une suite de $n$ impairs et $n-1$ pairs de la forme $I,P,I,...,P,I$ :
      On ordonne les $n$ impairs : $n!$ permutations
      On choisit le pair à exclure : $n$ choix
      On ordonne les $n-1$ pairs : $(n-1)!$ permutations

      Il reste à insérer le pair exclu :

      • soit avant le premier impair : $1$ choix
      • soit juste après un impair : $n$ choix
        Donc $n+1$ positions possibles pour l’exclu.

      On retrouve finalement $n! \times n \times (n-1)! \times (n+1) = (n!)^2(n+1)$.

      Répondre à ce message
      • Juin 2016, 3e défi

        le 18 juin à 11:05, par Daniate

        Bonjour,

        Merci pour votre élégante démonstration sans récurrence et à charge d’amicale revanche, puisqu’il n’y a pas si longtemps vous utilisiez la récurrence alors que d’autres utilisaient une méthode directe.

        Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM