Un défi par semaine

Août 2018, 3e défi

Le 17 août 2018  - Ecrit par  Ana Rechtman Voir les commentaires (22)

Nous vous proposons un défi du calendrier mathématique chaque vendredi et sa solution la semaine suivante. Il n’y aura pas d’édition papier du calendrier 2018, il faudra attendre l’édition 2019 !

Semaine 33

Est-il possible de diviser l’ensemble
$\{1, 2, 3, \dots, 32, 33\}$ en $11$ sous-ensembles disjoints, qui contiennent
trois éléments chacun dont l’un est égal à la somme des deux autres ?

Solution du 2e défi d’août :

Enoncé

La réponse est : $e>d>a>b>c.$

Par hypothèse
\[ \begin{eqnarray} a & > & b\label{ab} \\ e-a & = & d-b\label{eadb} \\ c-d & < & b-a \label{cdba}\\ a+b & = & c+d.\label{abcd} \end{eqnarray} \]

En additionnant $(\ref{cdba})$ et $(\ref{abcd})$ on obtient que

\[ \begin{array}{cccr} c-d+c+d & < & b-a +a+b & \\ 2c & < & 2b & \\ c & < & b. & \\ \end{array} \]

Avec les mêmes expressions $(\ref{cdba})$ et $(\ref{abcd})$ on obtient que
\[ \begin{array}{cccc} c-d+a+b & < & b-a +c+d & \\ -d+a & < & -a+d & \\ 2a & < & 2d & \\ a & < & d. & \\ \end{array} \]

Comme $a>b$ et $e-a=d-b$, on a que $a+(e-a)>b+(d-b)$, c’est-à-dire, $e>d$.
Par conséquent, $e>d>a>b>c.$

Partager cet article

Pour citer cet article :

Ana Rechtman — «Août 2018, 3e défi» — Images des Mathématiques, CNRS, 2018

Commentaire sur l'article

  • Août 2018, 3e défi

    le 17 août à 08:01, par mesmaker

    Cela est impossible.
    Raisonnons par l’absurde. Si cela était possible alors les 33 nombres seraient dans 11 sous-ensembles disjoints composés chacun de trois nombres différents. La somme 1+2+...+33 = 561 serait alors égale à la somme des nombres des 11 sous-ensembles. Or, dans chaque sous-ensemble composé de trois nombres, un nombre est la somme des deux autres. Alors la somme des trois nombres est paire (2 fois le plus grand nombre). Ainsi la somme des nombres des 11 sous-ensembles est une somme de nombres pairs donc paire. Donc 561 devrait être pair mais est impair : absurde.

    Répondre à ce message
    • Août 2018, 3e défi

      le 17 août à 10:02, par Niak

      Oui. Une petite variante consiste à observer qu’il n’y a que deux types de groupes : ceux constitués de $3$ pairs et ceux constitués de $2$ impairs et $1$ pair. Le nombre total d’impairs, qui vaut $17$, est donc aussi égal à $2$ fois le nombre de groupes du second type, et est donc pair...

      Répondre à ce message
    • Août 2018, 3e défi

      le 18 août à 13:05, par Pierre Cami

      la solution n’est possible qu’avec 1, 2, 3, 4, 5, ..., 26, 27, 29, 33, 39, 43, 49, 53 ensemble aux plus petits nombres possibles pour atteindre la solution et autres ensembles à somme supérieure, en effet :
      1+2=3, 4+5=9, 6+7=13, 8+10=18, 11+12=23, 14+15=29, 16+17=33, 19+20=39, 21+22=43, 24+25=49, 26+27=53

      Répondre à ce message
      • Août 2018, 3e défi

        le 19 août à 10:29, par Blaxapate

        C’est possible pour $\{1,\cdots,12\}$.

        Répondre à ce message
        • Août 2018, 3e défi

          le 19 août à 18:04, par Niak

          Mais si l’on s’autorise à réduire la taille de l’ensemble, alors à ce compte là c’est aussi possible pour $\{1,2,3\}$...

          Répondre à ce message
      • Août 2018, 3e défi

        le 19 août à 17:57, par Niak

        Cela me semble faux (mais vous ne dites pas ce que vous entendez par les « plus petits nombres possibles »), cf. les exemples que je donne plus bas.

        Répondre à ce message
  • Août 2018, 3e défi

    le 17 août à 18:07, par ROUX

    La somme de ces 33 entiers est égale à 561.
    Or la somme S de 22 de ces entiers devrait être égale à la somme S des 11 autres.
    On aurait alors 2×S=561 ce qui n’est pas possible.
    Donc non.

    Mais ce critère permet a priori de le faire pour les entiers de 2 à 34 dont la somme est 594.

    Mais est-ce un critère nécessaire ou suffisant ?

    Répondre à ce message
    • Août 2018, 3e défi

      le 18 août à 14:26, par Pierre Cami

      La somme minimum semble être 597 = 26*27/2+29+33+39+43+49+53

      Répondre à ce message
      • Août 2018, 3e défi

        le 19 août à 10:50, par Pierre Cami

        Désolé, je me suis trompé, le minimum est 27*28/2+29+33+39+43+49+53=624 !

        Répondre à ce message
      • Août 2018, 3e défi

        le 19 août à 17:38, par Niak

        Et pourquoi pas $562$ pour l’ensemble $\{1,2,\ldots,32,34\}$ ?

        Avec par exemple : $1+2=3$, $4+19=23$, $5+13=18$, $6+25=31$, $7+22=29$, $8+24=32$, $9+21=30$, $10+16=26$, $11+17=28$, $12+15=27$, $14+20=34$.

        Répondre à ce message
    • Août 2018, 3e défi

      le 19 août à 17:47, par Niak

      Je ne sais pas si le critère est suffisant en toute généralité (sous entendu pour des ensembles de nombres consécutifs ici), mais pour l’ensemble $\{2,3,\ldots,34\}$ il y a bien de nombreuses solutions.
      Par exemple : $2+31=33$, $3+11=14$, $4+22=26$, $5+16=21$, $6+24=30$, $7+25=32$, $8+20=28$, $9+18=27$, $10+13=23$, $12+17=29$, $15+19=34$.

      Répondre à ce message
      • Août 2018, 3e défi

        le 20 août à 10:42, par ROUX

        J’avais démontré que la moyenne des entiers seuls devait être exactement égale à 27 (27×11 qui est égale à la moitié de la somme de tous les entiers de 2 à 34).
        Comment avez-vous déterminé ces triplets : ordinateur ou protocole parce que moi au crayon et à la gomme je n’y arrivais pas 😢

        Répondre à ce message
        • Août 2018, 3e défi

          le 20 août à 14:31, par Niak

          J’ai en effet demandé gentiment à mon ordinateur.

          Répondre à ce message
          • Août 2018, 3e défi

            le 20 août à 15:46, par ROUX

            😉😊
            Et au crayon et à la gomme, une idée de protocole ? Comment distribuer les onze entiers seuls par exemple ?

            Répondre à ce message
            • Août 2018, 3e défi

              le 20 août à 17:20, par Niak

              Je ne sais pas. C’est un cas particulier d’Exact Cover, pour des sous-ensembles de taille $3$ définis par une contrainte arithmétique, mais je ne suis pas certain que cela simplifie grandement le problème d’origine pour lequel aucune méthode « efficace » (en un certain sens théorique) n’est connue...

              Répondre à ce message
    • Août 2018, 3e défi

      le 19 août à 19:58, par Niak

      En toute généralité, ce n’est pas une CNS, par exemple l’ensemble $\{1,3,4,6,7,9\}$ de taille $6$ de somme $30$ vérifie $6+9 = 1+3+4+7 = 15$ mais n’admet pas de solution car $9 = 3+6$ est un triplet indispensable mais $1+4\neq7$.

      Répondre à ce message
  • Août 2018, 3e défi

    le 21 août à 20:27, par drai.david

    Pour l’ensemble $\left\{1,...,12\right\}$, il existe $8$ partitions :

    1) 1-5-6 , 2-8-10 , 3-9-12 , 4-7-11
    2) 1-5-6 , 2-9-11 , 3-7-10 , 4-8-12
    3) 1-6-7 , 2-10-12 , 3-8-11 , 4-5-9
    4) 1-8-9 , 2-10-12 , 3-4-7 , 5-6-11
    5) 1-9-10 , 2-4-6 , 3-8-11 , 5-7-12
    6) 1-10-11 , 2-5-7 , 3-6-9 , 4-8-12
    7) 1-11-12 , 2-6-8 , 3-7-10 , 4-5-9
    8) 1-11-12 , 2-7-9 , 3-5-8 , 4-6-10

    Pour l’ensemble $\left\{1,...,15\right\}$, il en existe $21$.
    Pour l’ensemble $\left\{1,...,24\right\}$, il en existe $3\;040$.
    Pour l’ensemble $\left\{1,...,27\right\}$, il en existe $20\;505$.
    Pour l’ensemble $\left\{1,...,36\right\}$, il en existe $10\;567\;748$.
    Pour l’ensemble $\left\{1,...,39\right\}$, il en existe $103\;372\;655$.

    Des partitions existent si, et seulement si l’ensemble est de la forme $\left\{1,...,3n\right\}$ avec $n\equiv 0 \;\mathrm{ou}\;1\; [4]$.

    Répondre à ce message
    • Août 2018, 3e défi

      le 22 août à 22:54, par Niak

      En effet, ces valeurs sont d’ailleurs sur l’OEIS (qui renvoie à Dancing Links, un algorithme pour Exact Cover, comme méthode de calcul, ce qui semble conforter ce que je suggérais plus haut du coup).
      Combien de temps avez-vous mis pour calculer la dernière ?

      Répondre à ce message
      • Août 2018, 3e défi

        le 23 août à 12:46, par drai.david

        Soyons honnête : je débute en programmation et je viens de découvrir l’existence de l’algorithme des liens dansants il y a à peine 3 jours (page 194 du livre « Programmation efficace » de Christoph Dürr et Jill-Jênn Vie, Ellipses 2016) et je ne le maîtrise pas encore. J’ai donc programmé bêtement en itératif jusqu’à n=24, puis j’ai retrouvé ma suite sur l’OEIS.
        Donc les 3 dernières valeurs ne sont pas de moi...
        Conclusion : il faut toujours citer ses sources pour ne pas être pris la main dans le panier ! ;-)

        Répondre à ce message
        • Août 2018, 3e défi

          le 23 août à 14:45, par Niak

          Ah ok, parce que du coup par curiosité j’avais vraiment laissé tourner mon implémentation de Dancing Links (en C++, pas en Python comme celle de tryalgo dont vous parlez) dessus et il a tout de même fallu 1h45 pour obtenir la dernière valeur (calcul sur 1 cœur de CPU à 3.3GHz, code compilé avec g++ -O3) !...

          $ time ./a.out
          103372655
          ./a.out 6285,15s user 1,15s system 99% cpu 1:44:50,64 total

          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