Un défi par semaine

Janvier 2017, 2e défi

Le 13 janvier 2017  - Ecrit par  Ana Rechtman Voir les commentaires (8)

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

Semaine 2 :

On souhaite décomposer l’ensemble $\{2,3,\dots, 32\}$ en sous-ensembles vérifiant qu’aucun de ses éléments ne divise les autres. Compter le nombre minimal de sous-ensembles nécessaire afin que cela soit possible.

Solution du 1er défi de Janvier :

Enoncé

La réponse est non.

Comme $2017$ est impair et que la somme de deux nombres impairs est paire, le nombre d’entiers impairs consécutifs est nécessairement impair. Notons $c$ le nombre central de la somme donnant $2017$ : ses nombres voisins, $c-2$ et $c+2$, sont de somme $2c$. De même, leurs voisins sont aussi de somme $2c$ : en effet $(c-4) + (c+4) = 2c$.
En regroupant alors les termes de la somme deux à deux, on obtient que $2017$ s’écrit comme un multiple de $c$ et donc que $c$ divise $2017$.
Cependant, $2017$ est premier donc $c=1$ ou $c=2017$.

  • Si $c=1$ alors $c-2<0$, ce qui est interdit.
  • Si $c=2017$, la somme ne contient que ce nombre, ce qui est interdit.

Finalement $2017$ ne peut s’écrire comme la somme de nombres impairs consécutifs.

Post-scriptum :

Calendrier mathématique 2017 - Sous la direction d’Ana Rechtman, Maxime Bourrigan - Textes : Antoine Rousseau et Marcela Szopos.
2016, Presses universitaires de Strasbourg. Tous droits réservés.

Partager cet article

Pour citer cet article :

Ana Rechtman — «Janvier 2017, 2e défi» — Images des Mathématiques, CNRS, 2017

Crédits image :

Image à la une - Sinclair stammers / SPL-Science photo library / Biosphoto

Commentaire sur l'article

  • Janvier 2017, 2e défi

    le 13 janvier à 06:42, par Elrigo

    2 ; 4 ; 8 ; 16 ; 32 sont cinq puissances de deux qui ne peuvent se trouver deux à deux dans le même ensemble. Donc il y a au minimum cinq ensembles.

    Par exemple :
    2 ; 3 ; 5 ; 7 ; 11 ; 13 ; 17 ; 19 ; 23 ; 29 ; 31
    4 ; 6 ; 9 ; 10 ; 14 ; 15 ; 21 ; 22 ; 25 ; 26
    8 ; 12 ; 18 ; 20 ; 27 ; 28 ; 30
    16 ; 24
    32

    Répondre à ce message
  • Janvier 2017, 2e défi

    le 13 janvier à 08:50, par Idéophage

    Voir le théorème de Mirsky : https://en.wikipedia.org/wiki/Mirsky’s_theorem (c’est d’ailleurs l’exemple pris sur Wikipédia)

    Répondre à ce message
  • Janvier 2017, 2e défi

    le 13 janvier à 09:10, par Al_louarn

    On peut généraliser à tout ensemble $\{2,3,...,n\}$. Soit $m$ l’exposant de la plus grande puissance de $2$ inférieure ou égale à $n$ : $2^m \leq n < 2^{m+1}$.

    Il faut au moins $m$ sous-ensembles pour accueillir les $m$ puissances de $2$ inférieures ou égales à $n$ (et supérieures à $1$).

    Ensuite, pout tout $k \leq m$, on regroupe avec $2^k$ tous les nombres ayant exactement $k$ facteurs premiers (pas forcément distincts). En effet prenons deux nombres $a$ et $b$ tels que $a < b$. Si $b$ est multiple de $a$, alors $b$ a strictement plus de facteurs premiers que $a$. Donc à l’inverse si $a$ et $b$ ont le même nombre de facteurs premiers, $b$ ne peut pas être multiple de $a$.
    Pourrons-nous ranger tout nombre $r \in \{2,3,...,n\}$ dans un des $m$ sous-ensembles obtenus ? Oui car si $r$ a au moins $m+1$ facteurs premiers, alors $r \geq 2^{m+1}$ et donc $n < r$. Donc à l’inverse si $r \leq n$, il a au plus $m$ facteurs premiers.

    Donc $m$ est le nombre minimal de sous-ensembles nécessaires.

    Répondre à ce message
    • Janvier 2017, 2e défi

      le 16 janvier à 07:22, par ROUX

      Très belle construction-démonstration : je viens de m’amuser avec ;) !

      Répondre à ce message
  • Janvier 2017, 2e défi

    le 28 janvier à 21:13, par jb54

    On peut décomposer cet ensemble en :
    . S1 comprenant les nombres premiers
    . S2 comprenant les nombres facteurs de 2 nombres premiers
    . S3 comprenant les nombres facteurs de 3 nombres premiers
    . S4 comprenant les nombres facteurs de 4 nombres premiers
    . S5 comprenant les nombres facteurs de 5 nombres premiers

    Ce qui donne :
    S1 = 2,3,5,7,11,13,17,19,23,29,31
    S2 = 4,6,9,10,14,15,21,22,25,26
    S3 = 8,12,18,20,27,28,30
    S4 = 16,24
    S5 = 32

    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