Défis du calendrier mathématique Retour à la rubrique

Un défi par semaine

Janvier 2017, 2e défi

Le 13 janvier 2017 - Ecrit par Ana Rechtman Voir les commentaires (8)
Lire l'article en

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.

Article édité par Ana Rechtman

Commentaire sur l'article

Janvier 2017, 2e défi

le 13 janvier 2017 à 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 2017 à 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 14 janvier 2017 à 14:38, par Idéophage

Lien corrigé : Mirsky’s theorem.
Répondre à ce message
Janvier 2017, 2e défi

le 16 janvier 2017 à 00:05, par Niak

Et l’on pourrait aussi prolonger le défi avec le problème Project Euler 386 qui porte sur une question duale.
Répondre à ce message

Janvier 2017, 2e défi

le 16 janvier 2017 à 01:34, par Idéophage

Il y avait aussi ça à Prologin : https://prologin.org/train/2013/semifinal/grolopin.
Répondre à ce message

Janvier 2017, 2e défi

le 13 janvier 2017 à 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 2017 à 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 2017 à 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.

Connexion | s’inscrire | mot de passe oublié ?

L'auteur

Ana Rechtman

Un défi par semaine

Janvier 2017, 2e défi

Solution du 1er défi de Janvier :

Commentaire sur l'article