Décembre 2020, 4e défi

Le 25 décembre 2020 - Ecrit par Ana Rechtman Voir les commentaires (3)
Lire l'article en

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

Le calendrier 2021 est en vente ! Il s’intitule : « Le ciel dans tous ses états ».
De janvier à décembre, à travers 12 textes superbement illustrés, découvrez l’histoire des équations cachées dans les trajectoires des planètes et des étoiles ainsi que le développement des grandes théories qui ont accompagné cette aventure.

Semaine 52
Combien peut-on choisir de nombres entre $1$ et $20$ de sorte que deux quelconques d’entre eux n’aient pas d’autre diviseur commun que $1$ ?

Solution du 3e défi de décembre :

Enoncé

La réponse est : $p=13$.

Comme $p-10$ est premier, $p$ vaut au moins $12$. Alors $p$ étant premier, il n’est pas un multiple de $3$.

Si le reste de $p$ quand on le divise par $3$ est $1$, alors le reste
de $p-10$ quand on le divise par $3$ est $0$.

Pour que $p-10$ soit premier, il faut donc $p-10=3$ et $p=13$. Dans ce cas, $p+10=23$ qui est aussi premier.

Si le reste de $p$ quand on le divise par $3$ est $2$, alors le reste
de $p+10$ est $0$, et donc $p+10\geq 22$ est multiple de $3$ et ne peut donc pas être premier.

Il n’y a donc qu’une solution, à savoir $p=13$.

Post-scriptum :

Calendrier mathématique 2020 - Sous la direction d’Ana Rechtman, avec la contribution de Nicolas Hussenot - Textes : Serge Abiteboul, Charlotte Truchet. 2019, Presses universitaires de Grenoble. Tous droits réservés.

Disponible en librairie et sur www.pug.fr

Commentaire sur l'article

Décembre 2020, 4e défi

le 25 décembre 2020 à 11:58, par Al_louarn

Regroupons les nombres en fonction de leur plus petit diviseur premier. Nous obtenons autant de classes qu’il y a de nombres premiers inférieurs à $20$, plus une classe à part pour $1$ qui n’a aucun diviseur premier, soit $9$ classes en tout :
$1$
$2,4,6,8,10,12,14,16,18,20$
$3,9,15$
$5$
$7$
$11$
$13$
$17$
$19$

Nous ne pouvons pas choisir deux nombres de la même classe car par définition ils ont un diviseur premier en commun, donc autre que $1$. Donc, avec au mieux un nombre par classe, on ne peut pas trouver un ensemble satisfaisant de plus de $9$ nombres. On atteint ce maximum en choisissant le plus petit nombre de chaque classe puisqu’il est premier ou $1$. La réponse est donc $9$.

En fait dans chaque classe on peut même choisir n’importe quelle puissance du plus petit nombre de cette classe. Par contre on ne doit pas choisir un nombre avec deux facteurs premiers $p \lt q$ car ainsi on s’interdirait tous les nombres de la classe de $q$. Nous obtenons ainsi $8$ solutions de taille $9$ :
$1,2,3,5,7,11,13,17,19$
$1,4,3,5,7,11,13,17,19$
$1,8,3,5,7,11,13,17,19$
$1,16,3,5,7,11,13,17,19$
$1,2,9,5,7,11,13,17,19$
$1,4,9,5,7,11,13,17,19$
$1,8,9,5,7,11,13,17,19$
$1,16,9,5,7,11,13,17,19$

Et joyeux Noël à tous !

Question subsidiaire : si on remplace $20$ par $n$, quel est le nombre de solutions (de taille maximale) en fonction de $n$ ?
Répondre à ce message

Décembre 2020, 4e défi

le 26 décembre 2020 à 07:43, par Niak

Le nombre de solutions (question subsidiaire) peut s’exprimer $\displaystyle\prod_{p\text{ premier }\leq n}\left\lfloor\log_pn\right\rfloor$ (et il apparaît d’ailleurs sur l’OEIS).
Répondre à ce message

Décembre 2020, 4e défi

le 27 décembre 2020 à 12:28, par Al_louarn

Oui, et notez qu’en pratique on peut s’arrêter aux nombres premiers $p \leq \sqrt{n}$ puisqu’au delà, et jusqu’à $n$, la partie entière des logarithmes est $1$.
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é ?